Внутренности оптимизации в запросов
От: Sinclair Россия https://github.com/evilguest/
Дата: 25.03.03 05:08
Оценка: 173 (16) +1
#Имя: FAQ.db.optimization
SVZ>Может кто-нибудь знает/слышал о том, какие методы оптимизации запросов используют современные СУБД.
SVZ>Меня интересуют алгоритмические методы, уловки с архитектурой БД и т.д. и т.п. Конечно, такие данные являются коммерческой тайной, но ведь есть разработки программистского сообщества. Если кто-то может кинуть ссылочку или лучше доку — буду премного благодарен. Если кто-то имеет интересы в данной области, можно законнектиться по e-почте.

Что-то пробегало с полгода назад мимо меня...
Что-то не вижу тех статей в фаворитах, ну да ладно.
Там были интервью с разработчиками DB2 и всяким таким народом.
В общем, имхо начинать надо с Кнута III. Как бы то ни было, вопросы поиска по одному ключу там рассмотрены достаточно подробно (вот только нет алгоритма слияния страниц для B-tree)
Также весьма полезно почитать SQL Books Online от MS SQL 2000, ибо там раскрыты многие подробности того, как устроен сторадж для шустрости действия. Ну и некоторые другие вещи, из которых можно сделать определенные выводы, хотя явно там написано только "наш оптимайзер крут, крут, и очень крут." Например, между 7 и 2000 они сменили статистику. Но об этом далее.
Конечно, хорошей ссылкой является поиск в Гугле, хотя по нему довольно долго искать.

Вкратце дело сводится к следующему:
Математически, каждый запрос можно представить несколькими способами. Так же, как в обычной алгебре, где a*(b+c) = a*b+a*c, можно выбирать различные способы вычисления. От выбора способа зависит стоимость (в примере мы выбираем между одним сложением и одним умножением и двумя умножениями и одним сложением).
В однотабличных запросах ключевым является выбор индекса, по которому делается первичный поиск. Т.е. предикат разбивается на две части — одна из них выражается в терминах ключа индекса, вторая, так называемый остаток (residual) применяется к результату сканирования индекса. Первая операция выполняется логарифмически, вторая — линейно. Цена имеет порядок O(log(N)+Ki), где Ki — количество записей, отобранных при сканировании индекса i, а N — полное количество записей. В данном случае оптимизация сводится к выбору правильного индекса среди имеющихся и правильному разворачиванию предиката с целью максимизации селективности, т.е. минимизации Ki. Задача эта уже нетривиальна хотя бы потому, что селективность запроса — вещь трудно предсказуемая. Скажем, если есть табличка народа, из которой надо выбрать женщин-программистов, то на первый взгляд из индексов по полу и профессии надо выбирать второй. Полов всего 2, и потому можно ожидать всего лишь 50% селективности, и половину записей придется прогнать через линейный поиск. Доля же программеров невелика, и среди этих нескольких процентов отобрать всех женщин гораздо проще. Примерно так действует MS SQL 7.0. Однако такой алгоритм встрянет, если в таблице случайно оказалась всего одна женщина. Выбор индекса по полу привел бы к единственной проверке на профессию. Поэтому MS SQL 2000 хранит, помимо количества различных ключей в индексе также и гистограмму по диапазонам. Если в 7ке план запроса не зависел от того, подставим ли мы в него 'М' или 'Ж', то в 2000 зависимость будет.

В случаях сложных предикатов типа (a>b) все сразу становится хуже. Потому, что альтернативой линейному поиску по такому предикату (очевидно, невыразимомому в терминах индексов по a либо b) становится только переход к псевдо-join, т.е. (t1.id=t2.id and t1.a>t2.b), который в некоторых случаях дешевле. Отсюда видно, как расширяется пространство планов, соответствующих исходному запросу.

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

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

Насколько я знаю, современные движки используют эвристические методы выбора оптимальной стратегии. Кроме того, стоимость самого выбора плана ограничивается, чтобы не ухудшить общее время работы. Эти алгоритмы (в отличие от форматов файлов, стратегий блокировки, и прочей технической информации), как правило являются закрытыми. Потому, что именно они определяют, кто окажется в Top10 www.tpc.org. В доке от MS вскользь упомянуто, что из оптимизатор "не гарантирует выбор оптимального плана, но гарантирует квазиоптимальность", то есть план не более чем на известную величину хуже, чем оптимальный.
... << RSDN@Home 1.0 beta 6 >>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.