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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Выполнение операции более дорогое, чем не выполнение. Тем не менее, выполнение неправильной операции, принуждение к бессмысленным дисковым ввода-выводам, а затем отбрасывание шлака перед выполнением соединения, которое вам действительно нужно, намного дороже. Даже когда «неправильная» операция предварительно вычисляется, и показатели были разумно применены, остается значительное наказание. Денормализация для предкоммутации соединения – невзирая на аномалии обновления, – это приверженность конкретному соединению. Если вам нужно другое соединение, это обязательство будет стоить вам дорого.

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

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

    Вы не оправдались в ложном обобщении. Более подробную информацию о надлежащем использовании денормализации в сценариях хранения данных см. В конце раздела примечаний.

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

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

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

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


    Заметки


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

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

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

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


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

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

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

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

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


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


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

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

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

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

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

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

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


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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Разрабатывая то, что говорили другие,

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

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

    Давайте будем гением компьютера.