Когда и почему объединение баз данных дорого?
Я делаю некоторые исследования в базах данных, и я смотрю на некоторые ограничения реляционных БД.
Я думаю, что соединения больших таблиц очень дорого, но я не совсем уверен, почему. Что нужно сделать СУБД для выполнения операции соединения, где узкое место?
Как денормализация может помочь преодолеть эти расходы? Как помогают другие методы оптимизации (например, индексация)?
личный опыт приветствуется! Если вы собираетесь размещайте ссылки на ресурсы, пожалуйста, избегайте Википедии. Я уже знаю, где это найти.
в связи с этим мне интересно узнать о денормализованных подходах, используемых базами данных облачных сервисов, таких как BigTable и SimpleDB. Смотрите этот вопрос.
7 ответов:
денормализация для повышения производительности? Звучит убедительно, но это не выдерживает критики.
Крис Дейт, который в компании с доктором Тедом Коддом был первоначальным сторонником реляционной модели данных, вышел из терпения с дезинформированными аргументами против нормализации и систематически уничтожал их с помощью научного метода: он получил большие базы данных и проверен эти утверждения.
Я думаю, что он написал это в Записи Реляционных Баз Данных 1988-1991 но эта книга была позже свернута в шестое издание введение в системы баз данных, которая составляет the окончательный текст по теории и дизайну баз данных, в его восьмом издании, как я пишу, и, вероятно, останется в печати на десятилетия вперед. Крис Дейт был экспертом в этой области, когда большинство из нас все еще бегали босиком.
он обнаружил, что:
- некоторые из них держат для особых случаев
- все они не рассчитаться за общее пользование
- все они значительно хуже для других особых случаев
все сводится к смягчению размера рабочего набора. Соединения, включающие правильно выбранные ключи с правильно настроенными индексами, дешевы, не дороги, потому что они позволяют значительно сократить результат до строки.
материализация результата включает в себя массовые чтения диска, которые являются самыми дорогими аспект упражнения на порядок больше. Выполнение соединения, напротив, логически требует извлечения только ключи. На практике даже Ключевые значения не извлекаются: ключевые хэш-значения используются для сравнения соединений, что снижает стоимость многоколоночных соединений и радикально снижает стоимость соединений, связанных со сравнением строк. Мало того, что значительно больше поместится в кэше, там намного меньше чтения диска, чтобы сделать.
кроме того, хороший оптимизатор выберет наиболее ограничительное условие и применять его перед выполнением соединения, очень эффективно используя высокую селективность соединений по индексам с высокой мощностью.
По общему признанию, этот тип оптимизации также может быть применен к денормализованным базам данных, но такие люди, которые хочу для денормализации схемы обычно не думают о мощности, когда (если) они устанавливают индексы.
важно понимать, что таблица сканирует (проверка каждой строки в таблица в процессе создания соединения) редки на практике. Оптимизатор запросов выбирает сканирование таблицы только в том случае, если выполняется одно или несколько из следующих действий.
- меньше, чем 200 строк в отношении (в этом случае сканирование будет дешевле)
- в Столбцах соединения нет подходящих индексов (если имеет смысл присоединяться к этим столбцам, то почему они не индексируются? исправить это)
- перед сравнением столбцов требуется приведение типа (WTF?! исправь это или иди домой)СМ. КОНЕЧНЫЕ ПРИМЕЧАНИЯ ДЛЯ ADO.NET ВЫПУСК
- одним из аргументов сравнения является выражение (без индекса)
выполнение операции обходится дороже, чем ее невыполнение. Однако, выполняя неправильно операция, будучи вынужденным в бессмысленный диск ввода-вывода, а затем отбрасывая шлак до выполнения соединения вам действительно нужно, это много дороже. Даже при "неправильной" операции предварительно вычислены и индексы были разумно применены, остается значительный штраф. Денормализация для предварительного вычисления соединения, несмотря на аномалии обновления, является обязательством для конкретного соединения. Если вам нужен разные присоединяйтесь, это обязательство будет стоить вам большой.
Если кто-то хочет напомнить мне, что это меняющийся мир, я думаю, вы обнаружите, что большие наборы данных на более грубом оборудовании просто преувеличивают распространение даты полученные данные.
для всех вас, кто работает на биллинговых системах или генераторах нежелательной почты (позор вам) и с негодованием настраивает руку на клавиатуру, чтобы сказать мне, что вы знаете, что денормализация быстрее, извините, но вы живете в одном из особых случаев - в частности, в случае, когда вы обрабатываете все данных, по порядку. Это не общий случай, а вы are оправдана в вашей стратегии.
вы не оправдан в ложно обобщая его. Дополнительную информацию о надлежащем использовании денормализации в сценариях хранения данных см. В конце раздела Примечания.
Я также хотел бы ответить на
соединения-это просто декартовы произведения с некоторым блеском для губ
что за фигня. Ограничения применяются как можно раньше, в первую очередь наиболее ограничительные. Вы читали теорию, но не поняли ее. Присоединяетсялечение как "декартовы произведения, к которым применяются предикаты"только С помощью оптимизатора запросов. Это символическое представление (фактически нормализация) для облегчения символьной декомпозиции, чтобы оптимизатор мог производить все эквивалентные преобразования и ранжировать их по стоимости и селективности, чтобы он мог выбрать лучший план запроса.
единственный способ, которым вы когда-либо получите оптимизатор для создания декартового произведения, - это не предоставить предикат:
SELECT * FROM A,B
Примечания
Дэвид Олдридж предоставляет некоторую важную дополнительную информацию.
существует множество других стратегий, помимо индексов и сканирования таблиц, и современный оптимизатор будет стоить их всех, прежде чем создавать план выполнения.
практический совет: если его можно использовать в качестве внешнего ключа, то проиндексируйте его, чтобы стратегия индекса была скачать для оптимизатора.
I раньше был умнее, чем оптимизатор MSSQL. Это изменилось две версии назад. Теперь он вообще учит меня. Это, в очень реальном смысле, экспертная система, кодифицирующая всю мудрость многих очень умных людей в области, достаточно закрытой, чтобы система, основанная на правилах, была эффективной.
"яйца", возможно, были бестактны. Меня просят быть менее надменным и напоминают, что математика не лжет. Это верно, но не все выводы математических моделей должны обязательно нужно понимать буквально. Квадратные корни отрицательных чисел очень удобны, если вы тщательно избегаете изучения их абсурдности (каламбур там) и убедитесь, что вы отменяете их все, прежде чем пытаться интерпретировать свое уравнение.
причина, по которой я ответил так свирепо, заключалась в том, что в заявлении, как сформулировано, говорится, что
соединения are декартовым...
это может быть не то, что подразумевалось, но это и что было написано, и это категорически не соответствует действительности. Декартово произведение-это отношение. Соединение-это функция. Более конкретно, соединение-это функция с отношениями. С пустым предикатом он будет производить декартово произведение, и проверка того, что он делает это, является одной проверкой правильности для механизма запросов к базе данных, но никто не пишет неограниченные соединения на практике, потому что они не имеют практической ценности вне класса.
Я вызвал это, потому что я не хочу, чтобы читатели попадали в древние ловушка путать модель с моделируемой вещью. Модель-это аппроксимация, намеренно упрощенная для удобства манипулирования.
отсечка для выбора стратегии соединения сканирования таблиц может варьироваться в зависимости от ядра СУБД. На него влияет ряд решений по реализации, таких как коэффициент заполнения узла дерева, размер ключевого значения и тонкости алгоритма, но в целом высокопроизводительное индексирование имеет время выполнения 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чтобы попасть на диск много, но эквивалентная" денормализованная " схема не должна была бы попасть на диск, тогда денормализация выигрывает соревнование по исполнению.комментарий от оригинального автора: современные движки баз данных очень хороши в организации последовательности доступа, чтобы минимизировать промахи кэша во время операций соединения. Вышеизложенное, хотя и верно, может быть неверно истолковано как подразумевающее, что соединения обязательно проблематично дороги на больших данных. Это привело бы к плохому принятию решений со стороны неопытных разработчиков.
то, что большинство комментаторов не замечают, - это широкий спектр методологий объединения, доступных в сложной СУБД, и денормализаторы неизменно замалчивают более высокую стоимость поддержания денормализованных данных. Не каждое соединение основано на индексах, и базы данных имеют много оптимизированных алготитмов и методологий для объединения, которые предназначены для снижения затрат на объединение.
в любом случае, стоимость соединения зависит от его типа и ряда других факторов. Это не должно быть дорого вообще-некоторые образцы.
- хэш-соединение, в котором массовые данные равнозначны, действительно очень дешево, и стоимость становится значительной только в том случае, если хэш-таблица не может быть кэширована в памяти. Индекс не требуется. Равное разделение между объединенными наборами данных может быть большим подспорьем.
- стоимость соединения типа sort-merge определяется стоимостью сортировки, а не слиянием-метод доступа на основе индекса может практически исключить стоимость сортировки.
- стоимость вложенного цикла объединение по индексу определяется высотой индекса b-дерева и доступом к самому блоку таблицы. Это быстро, но не подходит для массовых соединений.
- соединение вложенного цикла на основе кластера намного дешевле, с меньшим количеством логических операций ввода-вывода, требуемых для каждой строки соединения-если Соединенные таблицы находятся в одном кластере, то соединение становится очень дешевым за счет размещения Соединенных строк.
базы данных предназначены для объединения, и они очень гибки в том, как они это делают и как правило, очень эффективны, если они не получают механизм соединения неправильно.
Я думаю, что весь вопрос основан на ложной предпосылке. Соединения на больших таблицах являются не обязательно дорогие. На самом деле,эффективное выполнение соединений является одной из основных причин существования реляционных баз данных на всех. Присоединяется по большому наборы часто стоят дорого, но очень редко вы хотите объединить все содержимое большой таблицы A со всем содержимым большой таблицы B. вместо этого вы пишете запрос таким образом, что только важные строки каждой таблицы используются, и фактический набор, сохраненный соединением, остается меньше.
кроме того, у вас есть эффективность, упомянутая Питером Воном, так что только важные части каждой записи должны быть в памяти до тех пор, пока не будет материализован конечный результирующий набор. Кроме того, в больших запросах со многими соединениями вы обычно хотите начать с меньших наборов таблиц и работать до больших, чтобы набор, хранящийся в памяти, оставался как можно меньше до тех пор, пока вероятный.
когда все сделано правильно, соединения, как правило,лучший способ для сравнения, объединения или фильтрации больших объемов данных.
узкое место в значительной степени всегда дисковый ввод-вывод, и даже более конкретно - случайный дисковый ввод-вывод (Для сравнения, последовательные чтения довольно быстры и могут быть кэшированы с помощью стратегий чтения вперед).
соединения can увеличение случайных поисков - если вы прыгаете вокруг чтения небольших частей большой таблицы. Но оптимизаторы запросов ищут это и превратят его в последовательное сканирование таблицы (отбрасывая ненужные строки), если он думает, что это будет лучше.
одна денормализованная таблица имеет аналогичную проблему-строки большие, и поэтому меньше подходят на одной странице данных. Если вам нужны строки, которые расположены далеко от других (и большой размер строки делает их еще дальше друг от друга), то у вас снова будет более случайный ввод-вывод, сканирование таблицы может быть вынуждено избежать этого. Но на этот раз сканирование таблицы должно считывать больше данных из-за большого размера строки. Добавьте к этому тот факт, что ты копирование данных из одного места в несколько местоположений, и у СУБД есть гораздо больше для чтения (и кэширования).
с 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), чтобы дать нам соответствующие условия. На самом деле он более оптимизирован, но проблема та же. Изменения размера наборы приведет к увеличению размера результат в геометрической прогрессии. Количество потребляемых циклов памяти и процессора осуществляется в экспоненциальном выражении.
когда мы denormalise, мы избегаем этот расчет вообще, думаю, с цветной липкий, прикрепленный к каждой странице книги. Вы можете вывести информацию без использования ссылки. Штраф, который мы платим, заключается в том, что мы компрометируем сущность СУБД (оптимальная организация данных)