Когда и почему объединение баз данных обходится дорого?

StackOverflow https://stackoverflow.com/questions/173726

Вопрос

Я провожу некоторые исследования в области баз данных и рассматриваю некоторые ограничения реляционных баз данных.

Я понимаю, что объединение больших таблиц обходится очень дорого, но я не совсем уверен, почему.Что нужно сделать СУБД для выполнения операции объединения, где находится узкое место?
Как денормализация может помочь преодолеть эти расходы?Как помогают другие методы оптимизации (например, индексация)?

Личный опыт приветствуется!Если вы собираетесь размещать ссылки на ресурсы, пожалуйста, избегайте Википедии.Я уже знаю, где это найти.

В связи с этим меня интересуют денормализованные подходы, используемые базами данных облачных сервисов, такими как BigTable и SimpleDB.Видишь этот вопрос.

Это было полезно?

Решение

Денормализация для повышения производительности?Это звучит убедительно, но не выдерживает критики.

Крис Дейт, который в компании с доктором Тедом Коддом был первоначальным сторонником реляционной модели данных, потерял терпение к дезинформированным аргументам против нормализации и систематически опровергал их, используя научный метод:у него были большие базы данных и проверенный эти утверждения.

Я думаю, он написал это в Записи реляционных баз данных 1988-1991 но позже эта книга была включена в шестое издание Введение в системы баз данных, который является тот самый окончательный текст по теории и проектированию баз данных выходит в восьмом издании на момент написания статьи и, вероятно, останется в печати на десятилетия вперед.Крис Дейт был экспертом в этой области, когда большинство из нас еще бегали босиком.

Он обнаружил , что:

  • Некоторые из них предназначены для особых случаев
  • Все они не окупаются для общего пользования
  • Все они значительно хуже для других особых случаев

Все сводится к уменьшению размера рабочего набора.Соединения, включающие правильно выбранные ключи с правильно настроенными индексами, дешевы, а не дороги, поскольку позволяют значительно сократить результат до того, как ряды материализуются.

Материализация результата требует массового чтения с диска, что на порядок дороже всего.Выполнение соединения, напротив, логически требует извлечения только ключи.На практике извлекаются даже значения ключей:ключевые хэш-значения используются для сравнения соединений, снижая стоимость многоколоночных соединений и радикально снижая стоимость соединений, включающих сравнение строк.Это не только значительно больше поместит в кэш, но и значительно сократит время чтения с диска.

Более того, хороший оптимизатор выберет наиболее ограничительное условие и применит его перед выполнением объединения, очень эффективно используя высокую селективность объединений по индексам с высокой мощностью.

По общему признанию, этот тип оптимизации также может быть применен к денормализованным базам данных, но люди, которые хотеть чтобы денормализовать схему, обычно не думают о мощности, когда (если) они настраивают индексы.

Важно понимать, что сканирование таблиц (проверка каждой строки в таблице в процессе создания соединения) на практике встречается редко.Оптимизатор запросов выберет сканирование таблицы только при выполнении одного или нескольких из следующих действий.

  • В отношении меньше 200 строк (в этом случае сканирование обойдется дешевле).
  • В столбцах объединения нет подходящих индексов (если объединение в этих столбцах имеет смысл, то почему они не индексируются?исправь это)
  • Перед сравнением столбцов требуется приведение к типу (WTF?!исправь это или иди домой) СМОТРИТЕ ПРИМЕЧАНИЯ К ВЫПУСКУ ADO.NET
  • Одним из аргументов сравнения является выражение (без индекса).

Выполнение операции обходится дороже, чем ее отсутствие.Однако, выполняя неправильно операция принудительного ввода-вывода на бессмысленный диск и последующего удаления мусора перед выполнением соединения, которое вам действительно нужно, заключается в многое более дорогой.Даже если "неправильная" операция предварительно вычислена и индексы были применены разумно, остается значительный штраф.Денормализация для предварительного вычисления соединения - несмотря на связанные с этим аномалии обновления - это приверженность конкретному соединению.Если вам нужен другой присоединяйтесь, это обязательство дорого вам обойдется большой.

Если кто-нибудь захочет напомнить мне, что мир меняется, я думаю, вы обнаружите, что большие наборы данных на более грубом оборудовании просто преувеличивают распространение результатов Date.

Для всех вас, кто работает над биллинговыми системами или генераторами нежелательной почты (позор вам) и возмущенно кладет руку на клавиатуру, чтобы сказать мне, что вы точно знаете, что денормализация происходит быстрее, извините, но вы живете в одном из особых случаев - в частности, в случае, когда вы обрабатываете ВСЕ из данных, расположенных по порядку.Это не общий случай, и вы являются оправдано в вашей стратегии.

Ты такой нет оправдано ложное обобщение этого.Смотрите в конце раздела примечания для получения дополнительной информации о надлежащем использовании денормализации в сценариях хранения данных.

Я также хотел бы ответить на

Соединения - это просто декартовы произведения с небольшим количеством блеска для губ

Что за чушь собачья.Ограничения вводятся как можно раньше, сначала самые строгие.Вы прочитали теорию, но вы ее не поняли.Соединения - это обработанный как "декартовы произведения, к которым применимы предикаты". Только оптимизатором запросов.Это символическое представление (фактически нормализация) для облегчения символьной декомпозиции, чтобы оптимизатор мог произвести все эквивалентные преобразования и ранжировать их по стоимости и избирательности, чтобы он мог выбрать наилучший план запроса.

Единственный способ заставить оптимизатор выдать декартово произведение - это не указать предикат: SELECT * FROM A,B

Примечания

Дэвид Олдридж предоставляет некоторую важную дополнительную информацию.

Действительно, существует множество других стратегий, помимо индексации и сканирования таблиц, и современный оптимизатор обойдется без них всех, прежде чем составить план выполнения.

Практический совет:если он может быть использован в качестве внешнего ключа, то проиндексируйте его, чтобы стратегия индексации была Доступно для оптимизатора.

Раньше я был умнее оптимизатора MSSQL.Это изменилось две версии назад.Сейчас это вообще учит я.Это, в самом прямом смысле, экспертная система, кодифицирующая всю мудрость многих очень умных людей в достаточно закрытой области, чтобы система, основанная на правилах, была эффективной.

"Чушь собачья", возможно, было бестактно.Меня просят быть менее надменным и напоминают, что математика не лжет.Это верно, но не все следствия из математических моделей обязательно следует понимать буквально.Квадратные корни из отрицательных чисел очень удобны, если вы тщательно избегаете рассмотрения их абсурдности (каламбур) и чертовски уверены, что вычеркнули их все, прежде чем пытаться интерпретировать свое уравнение.

Причина, по которой я отреагировал так яростно, заключалась в том, что в формулировке заявления говорится, что

Присоединяется являются декартовы произведения...

Возможно, это не то, что имелось в виду, но это является то, что было написано, и это категорически не соответствует действительности.Декартово произведение - это отношение.Соединение - это функция.Более конкретно, соединение - это функция, выражаемая отношением.С пустым предикатом это приведет к декартову произведению, и проверка того, что это так, является одной из проверок корректности для механизма запросов к базе данных, но на практике никто не пишет неограниченные соединения, потому что они не имеют практической ценности за пределами классной комнаты.

Я упомянул об этом, потому что не хочу, чтобы читатели попадали в старую ловушку путаницы модели с моделируемым объектом.Модель - это приближение, намеренно упрощенное для удобства манипулирования.

Ограничение для выбора стратегии объединения при сканировании таблиц может варьироваться в зависимости от ядра базы данных.На это влияет ряд решений по реализации, таких как коэффициент заполнения узла дерева, размер ключа-значения и тонкости алгоритма, но, вообще говоря, высокопроизводительное индексирование требует времени выполнения k журнал регистрации n + c.Термин C - это фиксированные накладные расходы, в основном связанные со временем настройки, а форма кривой означает, что вы не получите отдачи (по сравнению с линейным поиском) до тех пор, пока n исчисляется сотнями.

Иногда денормализация - хорошая идея

Денормализация - это приверженность определенной стратегии объединения.Как упоминалось ранее, это мешает Другое присоединяйтесь к стратегиям.Но если у вас много дискового пространства, предсказуемые схемы доступа и склонность обрабатывать большую его часть или все целиком, то предварительное вычисление соединения может оказаться очень полезным.

Вы также можете определить пути доступа, которые обычно использует ваша операция, и предварительно вычислить все соединения для этих путей доступа.Это предпосылка, лежащая в основе хранилищ данных, или, по крайней мере, так бывает, когда они создаются людьми, которые знают, почему они делают то, что делают, а не просто ради соответствия модным словам.

Правильно спроектированное хранилище данных периодически создается путем массового преобразования из нормализованной системы обработки транзакций.Такое разделение баз данных операций и отчетов имеет очень желаемый эффект устранения противоречия между OLTP и OLAP (онлайн-обработка транзакций, т.е. ввод данных, и онлайн-аналитическая обработка, т.е. отчетность).

Важным моментом здесь является то, что помимо периодических обновлений, хранилище данных только для чтения.Это делает спорным вопрос об аномалиях обновления.

Не совершайте ошибку денормализации вашей базы данных OLTP (базы данных, в которой происходит ввод данных).Это может быть быстрее при выставлении счетов, но если вы это сделаете, то получите аномалии обновления.Вы когда-нибудь пытались заставить "Ридерз Дайджест" перестать присылать вам материалы?

В наши дни дисковое пространство стоит дешево, так что напрягите себя.Но денормализация - это только часть истории с хранилищами данных.Гораздо больший прирост производительности достигается за счет предварительно вычисленных сводных значений:ежемесячные итоги, что-то в этом роде.Это всегда о сокращении рабочего набора.

ADO.NET проблема с несоответствием типов

Предположим, у вас есть таблица SQL Server, содержащая индексированный столбец типа varchar, и вы используете AddWithValue для передачи параметра, ограничивающего запрос к этому столбцу.Строки C # являются юникодными, поэтому предполагаемым типом параметра будет NVARCHAR, который не соответствует VARCHAR .

Преобразование VARCHAR в NVARCHAR - это расширяющееся преобразование, поэтому оно происходит неявно - но попрощайтесь с индексацией и удачи в выяснении причины.

"Подсчитай количество попаданий на диск" (Рик Джеймс)

Если все кэшировано в оперативной памяти, JOINs стоят довольно дешево.То есть нормализация не имеет большого значения снижение производительности.

Если "нормализованная" схема вызывает JOINs чтобы сильно ударять по диску, но эквивалентная "денормализованная" схема не должна была бы ударять по диску, тогда денормализация выигрывает соревнование по производительности.

Комментарий от оригинального автора:Современные движки баз данных очень хороши в организации последовательности доступа, чтобы минимизировать промахи в кэше во время операций объединения.Сказанное выше, хотя и верно, может быть неверно истолковано как подразумевающее, что объединения обязательно проблематичны для больших данных.Это привело бы к неправильному принятию решений неопытными разработчиками.

Другие советы

Чего большинство комментаторов не замечают, так это широкого спектра методологий объединения, доступных в сложной СУБД, и денормализаторы неизменно замалчивают более высокую стоимость обслуживания денормализованных данных.Не каждое объединение основано на индексах, и базы данных имеют множество оптимизированных алгоритмов и методологий объединения, которые предназначены для снижения затрат на объединение.

В любом случае, стоимость присоединения зависит от его типа и нескольких других факторов.Это совсем не обязательно должно быть дорого - вот несколько примеров.

  • Хэш-соединение, при котором объемные данные равносоединяются, действительно очень дешево, и затраты становятся значительными только в том случае, если хэш-таблицу нельзя кэшировать в памяти.Индекс не требуется.Равномерное разделение между объединенными наборами данных может оказать большую помощь.
  • Стоимость соединения сортировка-слияние определяется стоимостью сортировки, а не самим слиянием - метод доступа на основе индекса может практически исключить стоимость сортировки.
  • Стоимость соединения вложенного цикла с индексом зависит от высоты индекса b-дерева и доступа к самому табличному блоку.Это быстро, но не подходит для массовых соединений.
  • Объединение с вложенным циклом, основанное на кластере, намного дешевле, с меньшим количеством логических операций ввода-вывода, необходимых для каждой строки объединения - если обе объединенные таблицы находятся в одном кластере, то объединение становится очень дешевым за счет совместного размещения соединенных строк.

Базы данных предназначены для объединения, и они очень гибки в том, как они это делают, и, как правило, очень производительны, если только они не используют неправильный механизм объединения.

Я думаю, что весь вопрос основан на ложной предпосылке. Соединения на больших таблицах не обязательно дорогие. Фактически, эффективное объединение является одной из основных причин, по которой реляционные базы данных существуют . Объединения с большими наборами часто дороги, но очень редко вы хотите объединить все содержимое большой таблицы A со всем содержимым большой таблицы B. Вместо этого вы пишете запрос так, что используются только важные строки каждой таблицы, а фактический набор, сохраняемый соединением, остается меньшим.

Кроме того, у вас есть эффективность, упомянутая Питером Воне, так что только важные части каждой записи должны храниться в памяти, пока не будет получен окончательный набор результатов. Кроме того, в больших запросах с большим количеством объединений обычно требуется начинать с небольших наборов таблиц и переходить к большим, чтобы набор, сохраняемый в памяти, оставался как можно меньшим как можно дольше.

При правильном выполнении объединений, как правило, лучший способ сравнивать, объединять или фильтровать большие объемы данных.

Узким местом является в значительной степени всегда дисковый ввод-вывод, а еще более конкретно - случайный дисковый ввод-вывод (для сравнения, последовательные чтения выполняются довольно быстро и могут быть кэшированы с помощью стратегий опережающего чтения).

Присоединяется может увеличьте количество случайных запросов - если вы перескакиваете с места на место, читая небольшие фрагменты большой таблицы.Но оптимизаторы запросов ищут это и преобразуют в последовательное сканирование таблицы (отбрасывая ненужные строки), если сочтут, что так будет лучше.

Одна денормализованная таблица имеет аналогичную проблему - строки большие и поэтому меньше умещаются на одной странице данных.Если вам нужны строки, расположенные далеко друг от друга (а большой размер строки делает их еще дальше друг от друга), то у вас будет больше случайного ввода-вывода.Опять же, сканирование таблицы может быть принудительным, чтобы избежать этого.Но на этот раз при сканировании таблицы необходимо считывать больше данных из-за большого размера строки.Добавьте к этому тот факт, что вы копирование данных из одного места в несколько мест, и СУБД имеет гораздо больше возможностей для чтения (и кэширования).

Имея 2 таблицы, вы также получаете 2 кластеризованных индекса - и, как правило, можете индексировать больше (из-за меньших накладных расходов на вставку / обновление), что может значительно повысить производительность (в основном, опять же, потому, что индексы (относительно) малы, быстро считываются с диска (или дешево кэшируются) и уменьшают количество строк таблицы, которые вам нужно прочитать с диска).

Пожалуй, единственные накладные расходы при объединении связаны с вычислением совпадающих строк.Sql Server использует 3 различных типа соединений, в основном основанных на размерах набора данных, для поиска совпадающих строк.Если оптимизатор выберет неправильный тип соединения (из-за неточной статистики, неадекватных индексов или просто ошибки оптимизатора), это может существенно повлиять на время выполнения запроса.

  • Объединение в цикл обходится значительно дешевле для (по крайней мере, 1) небольшого набора данных.
  • Для объединения слиянием сначала требуется сортировка обоих наборов данных.Однако, если вы объединяетесь по индексированному столбцу, то индекс уже отсортирован и никакой дальнейшей работы выполнять не нужно.В противном случае при сортировке возникают некоторые накладные расходы на процессор и память.
  • Для хэш-соединения требуются как память (для хранения хэш-таблицы), так и процессор (для построения хэша).Опять же, это довольно быстро по отношению к дисковому вводу-выводу. Однако, если оперативной памяти недостаточно для хранения хэш-таблицы, Sql Server будет использовать базу данных tempdb для хранения частей хэш-таблицы и найденных строк, а затем обрабатывать одновременно только части хэш-таблицы.Как и во всем, что связано с диском, это происходит довольно медленно.

В оптимальном случае они не вызывают дискового ввода-вывода - и поэтому незначительны с точки зрения производительности.

В общем, в худшем случае - на самом деле должно быть быстрее прочитать такое же количество логичный данные из x объединенных таблиц, как из одной денормализованной таблицы из-за меньшего объема операций чтения с диска.Чтобы прочитать такое же количество физический данных, могут возникнуть некоторые незначительные накладные расходы.

Поскольку во времени запроса обычно доминируют затраты на ввод-вывод, а размер ваших данных не изменяется (за вычетом некоторых очень незначительных накладных расходов на строки) при денормализации, простое объединение таблиц не принесет огромной пользы.Тип денормализации, который имеет тенденцию повышать производительность, IME, заключается в кэшировании вычисленных значений вместо чтения 10 000 строк, необходимых для их вычисления.

Порядок, в котором вы присоединяетесь к столам, чрезвычайно важен. Если у вас есть два набора данных, попробуйте построить запрос таким образом, чтобы сначала использовался наименьший размер, чтобы уменьшить объем данных, с которыми должен работать запрос.

Для некоторых баз данных это не имеет значения, например, MS SQL большую часть времени знает правильный порядок соединения. Для некоторых (например, IBM Informix) порядок имеет все значение.

Принятие решения о денормализации или нормализации является довольно простым процессом, если принять во внимание класс сложности объединения. Например, я склонен проектировать свои базы данных с нормализацией, когда запросы O (k log n), где k относительно желаемой выходной величины.

Простой способ денормализации и оптимизации производительности - подумать о том, как изменения в вашей нормализованной структуре влияют на вашу денормализованную структуру. Однако это может быть проблематично, поскольку для работы с денормализованной структурой может потребоваться транзакционная логика.

Спор о нормализации и денормализации не закончится, поскольку проблемы огромны. Есть много проблем, где естественное решение требует обоих подходов.

Как правило, я всегда сохранял нормализованную структуру и денормализованные кэши, которые можно восстановить. В конце концов, эти кеши спасают мою задницу, чтобы решить будущие проблемы нормализации.

Разработка того, что сказали другие,

Соединения - это просто декартовы произведения с некоторым блеском для губ. {1,2,3,4} X {1,2,3} даст нам 12 комбинаций (nXn = n ^ 2). Этот вычисленный набор действует как ссылка, к которой применяются условия. СУБД применяет условия (например, где левые и правые равны 2 или 3), чтобы дать нам соответствующие условия. На самом деле он более оптимизирован, но проблема та же. Изменения в размере наборов будут увеличивать размер результата в геометрической прогрессии. Количество потребляемой памяти и количество циклов ЦП определяются экспоненциально.

Когда мы денормализуем, мы вообще избегаем этого вычисления, думая о том, чтобы иметь цветную наклейку, прикрепленную к каждой странице вашей книги. Вы можете вывести информацию без использования ссылки. Наказание, которое мы платим, заключается в том, что мы компрометируем сущность СУБД (оптимальная организация данных)

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top