Уж сколько за последние годы написано об оптимизации sql-запросов, а вопросы на sql.ru те же самые -- все же работало, и как-то вдруг перестало?! Heelp!

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

Начнем с простого запроса к одной таблице. Для примера возьмем таблицу заказов из некоторой гипотетической системы учета продаж бананов. Сценарий создания таблицы приведен ниже:

create table dbo.order  (

                        order_id           int                    identity (1, 1)

            ,           customer_id     int

            ,           order_date       datetime

            ,           shipping_date   datetime

            ,           order_no          nvarchar(32)

            ,           order_amt        int

            ,           order_total       money

)

Итак, таблица создана, клиентское приложение написано, пользователи вносят данные и периодически им требуется строить различные отчеты. Например, очень важный отчет – список заказов, которые необходимо доставить определенному клиенту в некоторый день:

Совсем несложно написать запрос,который вернет такой список:

select               customer_id

            ,           shipping_date

            ,           order_no

            ,           order_amt

            ,           order_total

from dbo.order o

where              customer_id    = 1

            and      order_date       ='20080809'

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

Что же случилось? Почему правильный запрос, совсем недавно выполнявшийся за несколько мгновений, теперь выполняется часами и ставит под угрозу нашу карьеру? Может быть давно пора перейти на Oracle, DB2 или вообще на MySQL (поговаривают, MySQL действительно быстр)?

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

Назад к динозаврам

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

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

Круглые сутки она заполняет вот такие бланки и складывает их в папки:

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

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

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

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

Другой вариант – увеличить производительность труда самой Маши. Для этого можно воспользоваться несколькими методиками.

Руководство по алгоритмам поиска для Маши Ведро

В нашем случае можно отсортировать все бланки заказов по дате доставки, а Машу отправить на принудительное лечение, чтобы она их больше не путала:

В терминах баз данных мытолько что создали индекс. Теперь Маша может воспользоваться различными алгоритмами для быстрого поиска необходимых заказов.

Один из таких алгоритмов – двоичный (бинарный) поиск. Работает он следующим образом – допустим, намтребуется найти заказ за 20080403, тогда, множество записей, отсортированное по некоторому ключу (shipping_date в нашем случае), разбивается на две половины. Средний элемент в нашейтаблице – 200080605 (если количество элементов четное, можно выбрать правый илилевый элемент – это не имеет существенного значения). Дата 20080403 предшестует среднему элементу (200080605) и так как множество записей отсортировано по shipping_date, это значит, что искомый элемент (если он существует), находится в первой половине. Снова повторяем этот процесс – разбиваемся первую половину на две и сравниваемискомое значение со средним элементом. В нашем случае – это 20080605. Повторяем процесс – у нас остался один элемент – 20080403, процесс окончен, заказ найден.

Давайте посчитаем,сколько времени мы сэкономили, используя этот алгоритм поиска. Допустим, что напросмотр одного бланка заказа у Маши уходит 1 минута, тогда на полный просмотр всех заказов у нее ушло бы 5 минут. В нашем случае ей понадобилось просмотреть только три заказа – 3 минуты. Теперь допустим, что заказов не 5, а 10000. Сколько бланков придется просмотреть в худшем случае? Делим 10000 пополам – 5000, 5000 пополам – 2500 и так далее, в результате получается 9 бланков или 9 минут, вместо 10000 минут – преимущество по сравнению с полным просмотром очевидно. Сколько же бланков придется просмотреть в общем случае? Для n бланков в худшем случае потребуется выполнить log n операций – столько раз можно разделить n на два, прежде чем получится 1.

Двоичный поиск – один их первых алгоритмов, разработанных для оптимизации поиска по большим массивам данных. Однако этот алгоритм имеет один недостаток – количество операций (азначит и время доступа) для разных записей может отличаться. Например, длянахождения заказа от 20080605 понадобится выполнить всего одну операцию просмотра, а для заказа от 20080403 – три. Это может не лучшим образом сказаться на производительности система. В MS SQL для организации индексов и поиска по ним использует другой алгоритм, чтобы гарантировать одинаковое время доступа ко всем элементам индекса – B+деревья.