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



Answers

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

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

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

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

Question

Я занимаюсь некоторыми исследованиями в базах данных, и я рассматриваю некоторые ограничения реляционных БД.

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

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

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




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

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

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

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

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

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

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

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

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




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

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

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

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




Related