Денормализация для улучшения производительности? Звучит убедительно, но не выдерживает критики.
Крис Дэйт, который в компании с доктором Тедом Коддом был первоначальным сторонником реляционной модели данных, потерял терпение с помощью дезинформированных аргументов против нормализации и систематически уничтожал их, используя научный метод: он получил большие базы данных и протестировал эти утверждения.
Я думаю, что он написал это в Записи реляционных баз данных 1988-1991 , но эта книга была позже свернута в шестое издание Введение в системы баз данных , которое окончательный текст по теории и дизайну баз данных, в его восьмом издании, которое я пишу, и, вероятно, останется в печати в течение десятилетий. Крис Дэйт был экспертом в этой области, когда большинство из нас все еще бегали босиком.
Он обнаружил, что:
- Некоторые из них действительны для особых случаев
- Все они не в состоянии расплатиться за общее использование
- Все они значительно хуже для других особых случаев
Все это сводится к уменьшению размера рабочего набора. Объединения, включающие правильно выбранные ключи с правильно настроенными индексами, дешевы, не дороги, потому что они позволяют значительно сократить результат до строк.
Материализация результата включает в себя массовые чтения с диска, которые на порядок являются самым дорогим аспектом упражнения. Выполнение объединения, напротив, логически требует извлечения только клавиш . На практике даже ключевые значения не извлекаются: ключевые хэш-значения используются для сравнений соединений, что снижает стоимость объединений с несколькими столбцами и радикально снижает стоимость объединений, связанных со сравнениями строк. Мало того, что он будет гораздо больше вписываться в кеш, там гораздо меньше чтения с диска.
Кроме того, хороший оптимизатор выберет наиболее ограничивающее условие и применит его перед выполнением объединения, очень эффективно используя высокую селективность объединений для индексов с высокой мощностью.
По общему признанию, этот тип оптимизации может также применяться к денормализованным базам данных, но люди, которые хотят , чтобы денормализовать схему, обычно не думают о количестве элементов, когда (если) они устанавливают индексы.
Важно понимать, что сканирование таблицы (проверка каждой строки таблицы в процессе создания объединения) на практике встречается редко. Оптимизатор запросов будет выбирать сканирование таблицы, только когда выполняется одно или несколько из следующих значений.
- В отношении менее 200 строк (в этом случае сканирование будет дешевле)
- Нет подходящих индексов для столбцов соединения (если целесообразно объединить эти столбцы, то почему они не проиндексированы? Исправить это)
- Приведение типов требуется перед сравнением столбцов (WTF ?! исправить это или вернуться домой) СМ. КОНЕЦ ЗАМЕЧАНИЯ ПО ВЫПУСКУ ADO.NET
- Одним из аргументов сравнения является выражение (без индекса)
Выполнение операции обходится дороже, чем ее не выполнение. Однако выполнение операции неправильно , принудительное выполнение бессмысленного дискового ввода-вывода и последующее удаление дросса перед выполнением действительно необходимого объединения, на намного дороже. Даже когда «неправильная» операция предварительно вычислена и индексы были разумно применены, остается значительный штраф. Денормализация предварительного вычисления объединения - несмотря на связанные с этим аномалии обновления - является обязательством для конкретного объединения. Если вам нужно другое соединение, это обязательство будет стоить вам большое .
Если кто-то захочет напомнить мне, что это изменяющийся мир, я думаю, вы обнаружите, что большие наборы данных на более жестком оборудовании только преувеличивают распространение результатов Дейта.
Для всех вас, кто работает над биллинговыми системами или генераторами нежелательной почты (как вам не стыдно) и возмущенно протягивает руку к клавиатуре, чтобы сказать мне, что вы точно знаете, что денормализация происходит быстрее, извините, но вы живете в одной из особых случаев - в частности, случай, когда вы обрабатываете все данных, в порядке. Это не общий случай, и вы оправданы в своей стратегии.
Вы не оправданы в ложном обобщении. См. Конец раздела примечаний для получения дополнительной информации о надлежащем использовании денормализации в сценариях хранилищ данных.
Я также хотел бы ответить на
Соединения - это просто декартовы произведения с некоторым блеском для губ
Что за бред Ограничения применяются как можно раньше, в первую очередь наиболее ограничительные. Вы читали теорию, но не поняли ее. Объединения обрабатываются как "декартовы произведения, к которым применяются предикаты" only оптимизатором запросов. Это символическое представление (фактически нормализация) для облегчения символьной декомпозиции, чтобы оптимизатор мог производить все эквивалентные преобразования и ранжировать их по стоимости и селективности, чтобы он мог выбрать лучший план запроса.
Единственный способ получить оптимизатор для создания декартового произведения - не указывать предикат: 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 часто попадает на диск, но эквивалентная «денормализованная» схема не должна попадать на диск, то денормализация побеждает в конкуренции за производительность.
Комментарий от оригинального автора: современные движки баз данных очень хороши в организации последовательности доступа, чтобы минимизировать пропуски кэша во время операций соединения. Вышеприведенное, хотя и верно, может быть неверно истолковано, поскольку подразумевает, что объединение обязательно проблематично дорого для больших данных. Это может привести к плохому принятию решений со стороны неопытных разработчиков.