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

354

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

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

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

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

Rik
источник
3
Вы также ищете преимущества? ;)
Дэвид Олдридж
Я смотрю на объективное (если есть такое) сравнение. За, против, что-у-ты.
Рик
Пред-рендеринг подходов облачных вычислений основан на том, что они могут делать ставки любым способом, избегая проблемы «неправильного соединения». У Google есть некоторые технические документы на их собственных системах. Довольно интересно - способы расширить применимость особых случаев.
Питер Воне
@PeterWone - хотите дать ссылку на некоторые из этих работ? ps, чтобы ответить на вопрос в вашем профиле, Android является открытым исходным кодом - ну, по крайней мере, частично, поэтому выродки запрыгнули на эту популярность. С точки зрения технически продвинутых великих немытых, они последовали за леммингами в плотные и потные объятия Google! Кто-нибудь Betamax? Ближе к моему сердцу (и поколению), как MySQL (без FOREGIN KEYFFS) стал (и остается) самой популярной в мире "R" СУБД, когда у нее была конкуренция со стороны PostgreSQL (без родной версии Windows) и Firebird (фиаско Opensourcing) или даже SQLite?
Верас
Излишне говорить, что я считаю PostgreSQL и Firebird значительно превосходящими MySQL для многопользовательских систем, а SQLite - звездные в однопользовательской сфере. SQLite обрабатывает сайт sqlite.org (400,00 посещений в день!).
Верас

Ответы:

470

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

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

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

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

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

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

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

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

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

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

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

Выполнение операции обходится дороже, чем ее отсутствие. Однако выполнение неправильной операции, принудительное выполнение бессмысленного дискового ввода-вывода, а затем отбрасывание шлака перед выполнением действительно необходимого объединения, намного дороже. Даже когда «неправильная» операция предварительно вычислена и индексы были разумно применены, остается значительный штраф. Денормализация предварительного вычисления объединения - несмотря на связанные с этим аномалии обновления - является обязательством для конкретного объединения. Если вам нужен РАЗЛИЧНЫХ присоединиться, что обязательство будет стоить вам большой .

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

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

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

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

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

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

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


Ноты


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

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

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

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


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

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

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

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

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


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


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

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

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

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

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

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

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


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

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

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


«Подсчитайте попадания диска» (Рик Джеймс)

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

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

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

Peter Wone
источник
7
Сонмы этих утверждений специфичны для конкретной СУБД, не так ли? например. «В отношении менее 200 строк»
Дэвид Олдридж,
2
Значительно ли влияет на все это использование суррогатных ключей?
Дэвид Племптон
3
Великий Э. Ф. Кодд несет исключительную ответственность за реляционную модель. СиДжей Дэйт, а в последнее время Х. Дарвен оба идиоты, которые не понимают РМ и предоставляют массу информации о том, «как улучшить» РМ, и все это можно отклонить, потому что нельзя исправить то, чего не понимаешь , Они служат только для того, чтобы нанести ущерб актуальности РМ, предполагая, что что-то «упущено».
ПроизводительностьDBA
7
Кроме того, не забывайте, что многие базы данных NoSQL - это те же базы данных, которые мы отбросили 40 лет назад. Молодые люди всегда думают, что открыли что-то новое. Фабиан Паскаль: dbdebunk.com/2014/02/thinking-logically-sql-nosql-and.html
Запад
3
Агрессивный. Это был хороший счет, но агрессия и микроагрессия не добавляют к содержанию или ценности содержания.
MrMesees
46

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

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

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

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

Дэвид Олдридж
источник
Я думаю, что все сводится к "если сомневаешься, спроси своего администратора". Современные базы данных представляют собой сложные звери и требуют изучения, чтобы понять. Я использую Oracle только с 1996 года, и это постоянная работа, чтобы идти в ногу с новыми функциями. SQLserver также проделал огромный путь с 2005 года. Это не черный ящик!
Парень
2
Хм, ну, по моему скромному опыту, там слишком много администраторов баз данных, которые никогда не слышали о хэш-соединении или думают, что они универсально плохи.
Дэвид Олдридж
28

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

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

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

Джоэл Коухорн
источник
1
@joel. Обратное также верно. Соединения больших наборов данных могут быть дорогими и иногда требуются, но вы не хотите делать это слишком часто, если а) вы не можете обрабатывать необходимые операции ввода-вывода и оперативной памяти и б) вы делаете это не слишком часто. Рассмотрим материализованные представления, системы отчетности, отчеты в реальном времени и отчеты CoB.
Парень
11

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

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

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

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

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

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

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

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

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

Марк Брэкетт
источник
Сокращение числа случайных поисков: хороший момент, хотя хороший RAID-контроллер с большим кешем будет выполнять чтение / запись лифта.
Питер Воне
3

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

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

Илья Кочетов
источник
1
В общем, на порядочный оптимизатор запросов не повлияет порядок перечисления объединений или таблиц, и он самостоятельно определит наиболее эффективный способ выполнения объединения.
Дэвид Олдридж
5
MySQL, Oracle, SQL Server, Sybase, postgreSQL и т. Д. не заботьтесь о порядке соединений. Я работал с DB2, и мне также все равно, в каком порядке вы их разместите. Это не очень полезный совет в общем случае
Мэтт Рогиш,
Кластеризация MySQL с использованием механизма NDB (по общему признанию, крайний случай, и только продвинутые разработчики собираются приблизиться к NDB) не угадывает порядок соединения правильно, поэтому вы должны добавить операторы «USE INDEX» в большинство присоединяемых запросов, или они быть ужасно неэффективным. MySQL документы покрывают это.
Джоэлхарди
@iiya, Понимание того, что выберет оптимизатор, важнее обобщенных утверждений или «мифов» о порядке упорядочения таблиц. Не полагайтесь на конкретную причуду в вашем SQL, так как поведение часто изменяется при обновлении СУБД. Начиная с версии 7 Oracle несколько раз меняла свое поведение.
Парень
1
@Matt Я видел, как Oracle 9i выполняет очень разные оптимизации и планы запросов, просто меняя порядок соединения. Может быть, это изменилось с версии 10i?
Камило Диас Репка
0

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

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

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

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

MathGladiator
источник
-8

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

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

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

questzen
источник
3
-1: Этот пост является отличным примером того, почему вы позволяете СУБД выполнять соединения - потому что разработчики СУБД постоянно думают об этих проблемах и находят более эффективные способы сделать это, чем метод compsci 101.
Дэвид Олдридж
2
@ Дэвид: Согласен. Программисты оптимизатора СУБД - это умные куки
Мэтт Рогиш,
Этот ответ неверен. Если ваш запрос выполняется к нормализованной, проиндексированной базе данных и имеет какой-либо тип фильтра или условия соединения, оптимизатор найдет способ избежать декартова произведения и минимизировать использование памяти и циклы ЦП. Если вы действительно намерены выбрать декартово произведение, вы будете использовать ту же память в нормализованной или ненормализованной БД.
rileymcdowell