Введение
Наверное, не будет большим преувеличением сказать, что процессор запросов (query processor) является стержневым элементом архитектуры серверов баз данных. Его эффективность в значительной мере определяет популярность продукта на рынке СУБД. Проектирование процессора запросов Microsoft SQL Server 7.0 ставило своей основной задачей обеспечение функциональности, быстродействия и надежности при работе с базами данных масштаба крупной корпорации. Несмотря на то, что предыдущим версиям Microsoft SQL Server уже принадлежали многочисленные рекорды по удельной (из расчета на один узел) OLTP-производительности и по критерию "цена / производительность", процессор запросов в версии 7.0 был подвергнут существенной переработке исходя из особенностей корпоративных систем, таких как наличие унаследованных источников данных, большое число пользователей, значительные объемы информации и преобладание сложных запросов по ее обработке. Эта специфика получила свое отражение в архитектуре и логике работы процессора запросов и подсистемы управления блокировками.
Таинство превращения множественно-ориентированного стиля языка SQL в процедурный план выполнения начинается с разбора (parsing) запроса, за которым следуют нормализация (normalization), предобработка (preprocessing), компиляция (compilation) и, собственно, выполнение. Важнейшей задачей компиляции является не просто генерация программного псевдокода (p-code), а построение оптимального (наискорейшего) способа выполнения запроса. Для этого к процессу обработки подключается оптимизатор, который выполняет анализ запроса на основе имеющихся индексов, распределения данных в проиндексированных колонках, количества данных в таблицах, операторов и величин в условиях where, join, union, group by, order by и т.д. В заключение оптимизатор принимает решение о режиме обновления (deferred или direct) и уровне блокировки. Изменения в процессоре запросов Microsoft SQL Server 7.0 коснулись практически каждого из перечисленных этапов оптимизации. Не претендуя на исчерпывающий рассказ о каждом из них, в рамках настоящей статьи мы коснемся лишь некоторых новых черт, посвященных этапу построения связей, а также стратегиям внутризапросного параллелизма и универсального доступа к данным.
Автор выражает искреннюю признательность Гётцу Графэ (Goetz Graefe), Microsoft, чьи идеи, консультации и советы оказали неоценимую помощь в ходе работы над данной статьей.
1. Стратегии построения связей
1.1 Nested Loop
Из теории, а точнее, практики реляционных баз данных мы знаем, что существуют различные способы реализации связей (joins): nested loop, index lookup, hash lookup, merge и т.д. Давайте посмотрим, как строятся связи между таблицами в SQL Server. Вложенный цикл (nested loop, в выдачах плана SQL Server 6.х - nested iteration) является самым простым из перечисленных алгоритмов:
set showplan_text on
go
select * from authors a inner join titleauthor ta on a.au_id=ta.au_id
where a.au_lname like "R%"
go
set showplan_text off
go
План выглядит следующим образом:
StmtText
------------------------
/-Nested Loops(Inner Join)
/-Bookmark Lookup(Bmk1000 IN pubs..authors AS a)
/--Filter(like(a.au_lname, "R%"))
/---Index Seek(pubs..authors. aunmind AS a,
SEEK: (a.au_lname >= "QЯ" AND a.au_lname < "s") ORDERED)
/--Clustered Index Seek(pubs. .titleauthor.UPKCL_taind AS ta,
SEEK:(ta.au_id=a.au_id) ORDERED)
Лист.1.1.1
Вложенный цикл был практически единственной стратегией реализации связей в предыдущих версиях продукта ([9]). Как следует из названия стратегии, построение связи осуществляется по следующему алгоритму: для каждой записи таблицы authors пробежать таблицу titleauthor, выбрав из нее все записи, которые можно сопоставить текущей записи таблицы authors. В этой терминологии таблица, соответствующая внутреннему циклу (titleauthor), называется внутренней, соответствующая внешнему циклу (authors)- внешней. Алгоритм можно охарактеризовать как метод грубой силы, поскольку при отсутствии подходящих индексов внутренняя таблица должна просматриваться столько раз, сколько записей во внешней. Если, как в нашем примере, подходящие индексы существуют, nested loop объединяется с поиском по индексу (index lookup). Cтоимость связи вычисляется как количество страниц во внешней таблице + количество записей, удовлетворяющих возможному условию фильтрации во внешней таблице * количество страниц, которые необходимо прочитать за один поиск во внутренней таблице. Желающие узнать, как считается количество страниц при поиске записи, удовлетворяющей определенному условию, если это условие является SARGом (индексный поиск), могут обратиться к [8]. Если же индекса для выражения условия подобрать не удается, это будет просто общее количество страниц во внутренней таблице. SQL Server 6.х полагал, что независимо от действительного местоположения на начало выполнения запроса внутренняя таблица во время первой итерации должна считываться с диска, а при последующих - из кэша данных (буферного кэша), если его свободный размер позволяет ее туда засунуть.
Легко видеть, что здесь стоимость связи зависит от порядка связывания. Рассмотрим два возможных порядка связывания: titleauthor -> author и authors -> titleauthor. Пусть имеем индексы по authors.au_lname и titleauthor.au_id. Индекс по authors.au_id предположим отсутствующим. Отработка связывания по первому порядку будет происходить следующим образом: 1) взять запись из titleauthor; 2) сканированием таблицы authors найти в ней все подходящие записи (у которых author.au_id=titleauthor.au_id для текущей записи в titleauthor) и взять только те из них, у кого au_lname like "R%". Второй порядок будет выполняться так: 1) взять запись из author; 2) если она не удовлетворяет условию фильтрации authors.au_lname like "R%", перейти к следующей; 3) найти с использованием индекса по titleauthor.au_id все подходящие записи с таким же au_id в titleauthor. Очевидно, что второй порядок будет стоить существенно дешевле. Таким образом, интуитивно понятно, что на роль оптимальных претендуют порядки, где внешняя таблица имеет условие фильтрации, внутренняя таблица меньше по размеру (чтобы с большей вероятностью поместиться в кэше) и имеет индекс по внешнему ключу. Последнее условие, на самом деле, носит нестрогий характер, потому что если такого индекса нет, SQL Server 6.х мог применять так называемую стратегию реформатирования (reformatting strategy). Эта небольшая прелюдия к основному алгоритму заключается в копировании содержимого внутренней таблицы в tempdb и построении на временную таблицу кластерного индекса по полям, участвующим в join, после чего она связывается с внешней. Наличие кластерного индекса существенно снижает время поиска подходящей записи во внутренней таблице. Если выигрыш, который за счет этого достигается, окупает копирование таблицы и создание индекса, выбиралась стратегия реформатирования. SQL Server 6.5 можно заставить использовать ее вообще всегда независимо от выигрыша или проигрыша, если поднять флаг трассировки 318. В запросе может происходить связывание большого числа таблиц. Как в этом случае определить оптимальный порядок? Простой перебор дает n! возможных комбинаций. Если предположить, что одна комбинация оценивается за 10-6 с, то определение оптимального порядка среди 16 таблиц заняло бы, как легко видеть, порядка 230 дней. В связи с этим используется приближенная оценка. Процессор запросов SQL Server 6.х производил упорядоченные выборки из n связываемых таблиц по 4 и определят среди них оптимальную. Внешняя таблица этой выборки считается самой внешней в окончательном порядке и из дальнейшего перебора исключается. Данная процедура повторяется для оставшихся n-1 таблиц, затем n-2 и т.д. Всего число комбинаций, которое при таком подходе необходимо перебрать оптимизатору, составляет An4 + An-14 + ... + A44, где Ank=n!/(n-k)! - число размещений из n по k. При k<<n эта сумма будет существенно меньше, чем n!. В частности, для n=32, k=4 на 28 порядков. Включение флага трассировки 345 дает оптимизатору SQL Server 6.5 указание рассматривать по 6 таблиц одновременно, что приводит к увеличению времени компиляции, но повышает точность выбора оптимального порядка. Обычно это использовалось для выполнения TPC-D запросов.
Рассмотрим следующий запрос:
select a.au_fname, a.au_lname, t.title, p.pub_name, s.qty, st.stor_name
from authors a inner join titleauthor ta on a.au_id=ta.au_id
inner join titleauthor t on ta.title_id=t.title_id
inner join publishers p on t. pub_id=p.pub_id
inner join sales s on s.title_id=t.title_id
inner join stores st on s.stor_id=st.stor_id
StmtText
------------------------
/-Nested Loops(Inner Join)
/--Nested Loops(Inner Join)
/---Bookmark Lookup(BOOKMARK: ([Bmk1004]),
OBJECT:([pubs].[dbo]. [sales] AS [s]) WITH PREFETCH)
-----Nested Loops(Inner Join)
------Nested Loops(Inner Join)
-------Nested Loops(Inner Join)
--------Index ScaBJECT:([pubs]. [dbo].[authors].[aunmind] AS [a]))
--------Index Seek(OBJECT:([pubs]. [dbo].[titleauthor].[auidind] AS [ta]),
SEEK:([ta].[au_id]=[a]. [au_id]) ORDERED)
-------Clustered Index Seek(OBJECT: ([pubs].[dbo].[titles].[UPKCL_titleidind] AS [t]),
SEEK:([t]. [title_id]=[ta].[title_id]) ORDERED)
------Index Seek(OBJECT:([pubs]. [dbo].[sales].[titleidind] AS [s]),
SEEK:([s].[title_id]=[t]. [title_id]) ORDERED)
----Clustered Index Seek(OBJECT: ([pubs].[dbo].[publishers]. [UPKCL_pubind] AS [p]),
SEEK:([p]. [pub_id]=[t].[pub_id]) ORDERED)
---Clustered Index Seek(OBJECT: ([pubs].[dbo].[stores].
[UPK_storieid] AS [st]), SEEK: ([st]. [stor_id]=[s].[stor_id]) ORDERED)
Лист.1.1.2
Мы видим, что порядок построения связей, выбранный оптимизатором, имеет вид: authors-> titleauthor-> titles-> sales-> publishers-> stores, т.е. таблицы publishers и sales поменялись местами. Применение команды SET FORCEPLAN ON обяжет оптимизатор строить связи между таблицами ровно в том порядке, в каком они были перечислены в операторе SELECT. Кстати, заодно стоит обратить внимание, что аргумент на шаге Bookmark Lookup после присоединения таблицы sales помечен как with prefetch, что означает, что поиск закладок идет с использованием опережающего чтения (read ahead).
1.2 Merge Join
В SQL Server 6.5 существовала еще одна разновидность связывания, которую можно условно охарактеризовать как псевдо-merge join. Рассмотрим случай, когда нам необходимо связать таблицы T1, T2 и Т3, причем для только для связи между Т1 join Т2 существует подходящий индекс. Тогда по этому индексу таблицы Т1 и Т2 связываются во временную рабочую таблицу W, проиндексированную для быстрой связи с Т3. Флаг 343 включал принудительное применение этой стратегии, флаг 342, наоборот, предотвращал ее применение когда бы то ни было. Физически реализация связи все равно осуществлялась через indexed nested loop, поэтому по отношению к 6.5 мы употребили термин "псевдо-merge".
В процессоре запросов SQL Server 7.0 реализована полноценная стратегия merge join. Рассмотрим пример:
select m.lastname, m.firstname, ch.charge_dt, ch.charge_amt
from member m, charge ch where m.member_no=ch.member_no
order by ch.member_no
Таблица member состоит из 10000 записей, charge - из 100000. План выполнения запроса:
StmtText
----------------------------------
/-Merge Join(Inner Join, MANY-TO-MANY MERGE: ch.member_no)=(m.member_no)
RESIDUAL:(ch.member_no=m. member_no))
/-Sort(ORDER BY: (ch.member_no asc))
/ /-Clustered Index Scan(Credit..charge.IX_charge AS ch)
/-Clustered Index Scan(Credit..member.IX_member AS m, ORDERED)
Лист.1.2.1
Обратите внимание на то, что таблицы member и charge имеют кластерные индексы. В этом состоит особенность merge join. Ее очень выгодно использовать, когда все входы (связываемые таблицы в запросе) физически отсортированы по атрибутам связи. Пусть нам нужно завязать отношением "многие-ко-многим" таблицы Т1 по атрибуту fld1 и Т2 по атрибуту fld2. Псевдокод алгоритма merge join при построении отношения выглядит примерно так.
while not T1.eof and not T2.eof do begin
attr=T1.CurrentRecord.fld1;
while T2.CurrentRecord.fld2 < attr do T2.MoveToNextRecord();
t1=T1.CurrentRecord.RowID();
while T2.CurrentRecord.fld2=attr
while T1.CurrentRecord.fld1=attr do begin
< пара T1.CurrentRecord * T2.CurrentRecord удовлетворяет
условию связи;
добавить ее в результат >;
T1.MoveToNextRecord();
end while
T1.MoveTo(t1);
T2.MoveToNextRecord();
end while
end while
Как следует из этого псевдокода, преимущество условия предварительной сортировки таблиц состоит в том, что при построении связи нам приходится просматривать один раз таблицу Т2 и почти один раз Т1 (почти - за счет возвратов при разрешении связи "многие-ко-многим", количество возвратов зависит от селективности Т1.fld1). Если Т1 связана с Т2 отношением "один-ко-многим", то просмотр Т1 и Т2 выполняется строго по одному разу. Таким образом, необходимое число итераций в этом случае будет не n1*n2, как в случае nested loop без индексов (n1, n2 - количество записей в таблицах), а n1+n2, что, очевидно, приятней. Т.е. записи в таблицах как бы складываются друг с другом, из-за чего эта стратегия и называется merge (слияние). Из сказанного следует, что оптимизатор будет выбирать ее в ситуациях, когда входы (inputs) отсортированы по атрибутам связи, например, по полям fld1 и fld2 существуют кластерные индексы, и этот порядок должен быть сохранен на выходе ([6]).
1.3 Hash Join
Продолжим работу с нашей базой. Сделаем индексы по таблицам member и charge некластерными и отправим запрос:
select m.lastname, m.firstname, ch.charge_dt, ch.charge_amt,
ca.category_desc
from member m, charge ch, category ca
where m.member_no=ch.member_no and ch.category_no=ca.category_no
SQL Server выполняет его по следующему плану:
StmtText
----------------------------------
/-Hash Match(Inner Join, HASH:(ca.category_no)=
(ch.category_no))
/-Table Scan(Credit..
category AS ca)
/-Hash Match(Inner Join, HASH:(m.member_no)=(ch.member_no))
/-Table
Scan(Credit..member AS m)
/-Table
Scan(Credit..charge AS ch)
Лист.1.3.1
Ход рассуждений процессора запросов выглядит примерно так. Так, входы здоровые, это плохо, nested loop влетит в копеечку, надо что-нибудь похитрее. Входы неотсортированы, значит, merge join тоже не подходит, а жаль. Ага, пользователя, по-видимому, устраивает, если записи на выходе будут возвращены в их физическом порядке, во всяком случае ничего обратного он мне не сказал. В результате, как мы видим, процессор запросов избирает стратегию под названием hash join. Коротко поясним ее принципы на примере связывания двух таблиц. Если одна из них, скажем, Т1, не превышает размер памяти, отводимой под данную операцию, то для нее в памяти строится хэш-таблица. Отсюда, Т1 будет называться build input. При этом над атрибутом связи А (полями, участвующими в join) каждого кортежа (записи) ti1 отношения (таблицы) Т1 выполняется некоторая хэш-функция h (ti1.А) и результат от нее вместе с указателем на данную запись кладется в хэш-таблицу H. Атрибут А в этом случае называется хэш-ключом (hash key), а результат применения хэш-функции h (ti1.А) - хэш-значением (hash value). Хэш-значение должно занимать меньше места, чем хэш-ключ. Основные требования к хэш-преобразованию - быстрота, равномерность распределения результатов, малое число коллизий. Пусть число слотов в хэш-таблице равно N. Примеры хэш-функций: 1) h(x) = x mod N (лучше, если N - простое число); 2) h(x) = q средних битов от x2, где N = 2q; 3) h(x) = p1(x) xor ... xor pm(x), где N=2q, а pi(x) - i-я группа по q битов из х, выстроенная в обратном порядке. В качестве бытовых примеров хэширования обычно приводится записная книжка. Достаточно открыть записную книжку на нужной букве и пробежать цепочку коллизий (фамилий, начинающихся с одной и той же буквы), пока не наткнемся на искомое.
Коллизия (hash collision, или hash clash) происходит, когда хэш-функция дает одно и то же значение для нескольких разных записей, т.е. когда мы обнаруживаем, что слот, соответствующий h(tj1.A), куда мы хотели положить указатель на tj1, уже занят под одну из предыдущих записей ti1, потому что h(ti1.A)= h(tj1.A), где А - атрибут связи. Один из выходов - растить из этого слота цепочку, в которую увязывать указатели на все такие записи. Такая схема разрешения коллизий носит название chaining (варианты: separate chaining, coalesced chaining). Другой выход - поискать свободный слот (linear probing, double hashing) и т.д. Схема разрешения коллизий способна оказать даже большее влияние на производительность, чем вид хэш-функции. Для ускорения поиска мы можем сгруппировать по тому или иному принципу слоты хэш-таблицы. Такие группы слотов называются hash buckets (переводится как "хэш-корзины", также в последнее время часто встречается неформальное "букеты"). В качестве принципа группировки можно выбрать другое хэш-преобразование g, например, взятие остатка от деления результата первой хэш-функции h на количество букетов, которое в этом случае стоит положить равным простому числу для улучшения свойств g. Именно по такому принципу ([11]) осуществлялся доступ к страницам памяти в кэше данных SQL Server 6.х (настройка hash buckets в серверной конфигурации). Итак, в общем случае структура хэш-таблицы представляет собой связный список букетов, состоящих из слотов с хэш-ключами. Если в качестве алгоритма разрешения коллизий выбран separate chaining, то из каждого слота еще могут тянуться цепочки коллизий. Иногда группировка слотов не производится, в этом случае букетом считается каждый слот с относящимися к нему коллизиями.
После того, как хэш-таблица Н построена, то же самое преобразование h применяется ко второй таблице Т2 (probe input). Для каждой записи ti2 вычисляется h(ti2.B), где В - атрибут связи в Т2. Для h(ti2.B) определяется соответствующий букет в Н, содержимое которого сканируется и сопоставляется с ti2. Все подходящие пары ti1 * ti2добавляются в результат. Аналогично выполняются запросы с предикатами DISTINCT и GROUP BY. В первом случае хэш-функция применяется ко всем полям в SELECT, во втором - только к тем, которые относятся к условию группировки. Стоит заметить, что в предыдущих версиях SQL Server выполнял GROUP BY сортировкой, поэтому результат приходил заведомо упорядоченный по полям, входящим в GROUP BY. В 7.0 результат возвращается в порядке, определенном хэш-функцией, поэтому если есть необходимость его отсортировать, то наряду с GROUP BY следует явно поставить ORDER BY. Сходным образом происходит вычисление агрегатов. Алгоритм для hash aggregation выглядит так: 1) взять запись из таблицы на входе; 2) вычислить хэш-величину и определить подходящий букет; 3) если эта хэш-величина содержится в букете, добавить значение агрегатного поля данной записи к текущему значению агрегата; 4) в противном случае добавить в букет новую запись с вычисленной хэш-величиной.
Рассмотренная ситуация описывает простейшую разновидность hash join, известную как in-memory hash. Если ни одна из таблиц, участвующих в операции связывания, целиком не помещается в памяти, SQL Server 7.0 применяет алгоритм grace join (названный так по имени исследовательского проекта GRACE [4]). Он заключается в разбиении (partioning) таблиц Т1 и Т2 на фрагменты меньшего размера (fan-outs) на основе все того же хэш-преобразования. Для каждого из входов (Т1, Т2) фрагменту назначается так называемый файл переполнения (overflow file). В отличие от коллизии, переполнение в хэш-алгоритмах обозначает ситуацию, когда место в букете исчерпано. Коллизии могут приводить к возникновению переполнения. Если probing-разрешение коллизий, как мы упоминали, пытается переназначить слоты хэш-таблицы, то, например, при сhaining-разрешении первая же коллизия вызовет переполнение. Файлы переполнения хранятся на диске. В случае chaining-разрешения каждый файл удобно рассматривать как объединение цепочек коллизий для всех букетов фрагмента по данному входу. Букет может принадлежать только одному фрагменту. Считается, что размер одного фрагмента достаточно мал, чтобы уместиться в памяти, отведенной под запрос, за вычетом входных / выходных буферов (I/O buffers) и служебных объектов управления. В противном случае к фрагменту применяется повторное разбиение (recursive partitioning). Затем фрагменты попарно связываются друг с другом, как самостоятельные таблицы. Окончательный результат Т1 join T2 строится как T11 join T21 union ... union T1n join T2n. Очевидно, что T1i join T2i не пересекается с T1j join T2j (i<>j), так как если кортеж t1 * t2 удовлетворяет условию связи, то h(t1)=h(t2) и они попадают в одну пару. Возникает резонный вопрос: что происходит, если по прошествии нескольких уровней вглубь рекурсии разбиения нам все равно не удалось добиться размера фрагмента, приемлемого для in-memory hash или хотя бы hybrid hash (cм.ниже). Например, некий зловредный фрагмент обладает нулевой селективностью по атрибуту (т.е. содержит одинаковые ключи). Понятно, что его можно хэшировать до посинения, меньше он от этого все равно не станет. В этом случае оптимизатор выбирает альтернативные стратегии (bail out), в частности, уже рассмотренные нами sort- или loop-based join, которые применяются только по отношению к данному фрагменту, а не ко входам целиком. Возникает другой резонный вопрос: вместо того, чтобы тратить время на бесполезные в данном случае разбиения, нельзя ли как-то предсказать эту неприятную ситуацию заранее? Очевидно, что можно. Для этого на каждом шаге рекурсии следует собирать статистику распределения хэш-значений для последующего уровня погружения, что позволит нам вовремя остановиться. Эта методика называется histogram-guided partitioning ([6]). Кстати, набранная статистика может потом пригодиться, например, для обращения ролей (см.ниже).
Если build input ненамного превышает размер доступной памяти, SQL Server 7.0 использует hybrid hash join. Представим себе, что, обрабатывая build input, по алгоритму grace join, мы тем не менее добросовестно запихиваем в хэш-таблицу все, что относится к первому букету. Все остальные букеты скидываются на диск (spilled buckets). Вот наконец в буфере входа показалась страница от probe input. Хэшируем каждую принадлежащую ей запись и, если она относится к первому букету, быстро ищем для нее сопоставления на основе хэш-значений build input и посылаем их в output buffer. Если запись попадает в другой букет, ссылка на нее записывается в probe-файл переполнения, соответствующий фрагменту, которому принадлежит этот букет. Таким образом, часть хэш-таблицы обрабатывается подобно in-memory hash, а остальное - как в случае grace, чем и объясняется название hybrid join. Чтобы сэкономить на операциях ввода / вывода, можно попытаться исключить не участвующие в связи кортежи на возможно более ранних стадиях ее сборки. Для этого в SQL Server 7.0 применяется алгоритм фильтрации на основе битового вектора (bit vector filtering). При выполнении операций hash join SQL Server строит хэш-таблицу в виде довольно большого массива (порядка тысяч или десятков тысяч слотов в зависимости от объема доступной памяти). К каждому слоту привязан букет. Элементы букета содержат хэш-значение и указатель на запись. Они объединяются в структуры по 64 байта, которые составляют связный список, корнем которого является слот массива. Если во время построения hybrid join букет был положен на диск, то вместо указателя на букет слот хранит специальный битовый массив (вектор), образующийся по следующему принципу. К домену атрибута связи DA применяется некоторое преобразование I, которое отображает его на совокупность целых чисел. Создадим битовый массив с диапазоном [0, MI], включающим I(DA). Все элементы с индексами из I(DA) поднимем в 1, остальные будут нулевыми. Каждый букет, таким образом, будет содержать битовую карту входящих в него элементов, на основании которой, не залезая на диск, легко сказать, найдутся ли для текущей записи из probe input соответствия в данном spilled bucket. Если нет, то эта запись тут же выбрасывается или идет в output (например, для outer join), в любом случае она не пишется в probe-файл переполнения. Может статься, что хорошо отфильтрованный probe-файл переполнения T2i окажется меньше своего build'a T1i. В этом случае, как мы понимаем, выгодно поменять их местами, превратив probe input в build input и наоборот. Собственно, SQL Server 7.0 это тоже понимает и выполняет то, что называется dynamic role reversal (динамическое обращение ролей).
1.4 Hash Teams
Существенным нововведением в процессоре запросов SQL Server 7.0 является технология хэш-групп (hash teams). Рассмотрим ее более подробно. Обобщенный алгоритм обработки хэш-таблиц ([5]) удобно представить в виде вложенного цикла глубины 3. Самый внешний - по фрагментам, промежуточный - по входам и внутренний - по записям. Как правило, процедуры промежуточного цикла ориентированы на число входных параметров, не превышающее 2. Если мы привлекаем hash join для операций группировки или устранения дубликатов, получается один вход. Если с помощью hash join строится связь из n таблиц, то сначала выбираются две, которые связываются в промежуточный результат, тот, в свою очередь, связывается с третьей таблицей и т.д., образуя всякий раз по два входных параметра. Складывается впечатление, что для большинства распространенных задач достаточно иметь унарный или бинарный hash join. Тем не менее, например, в практике оптимизации запросов с операциями сортировки широко используется методика существенных порядков (interesting orders). Cмысл этого подхода очень простой: предположим, мы имеем запрос, выполняющий merge join 3-х таблиц по одному и тому же ключу. Если применять бинарный оператор, то потребуется выполнить 4 сортировки (3 исходных таблицы + 1 промежуточная). Но промежуточный результат подается на вход в уже отсортированном (после первого шага) виде, причем порядок сортировки нас устраивает, так как было оговорено, что ключ одинаков. Стало быть, можно сэкономить, отказавшись от сортировки промежуточных результатов, т.е. по сути дела, применить n-арный оператор связи. Идея хэш-групп ([5]) есть продолжение методики существенных порядков на область hash joins. Из запроса выделяются таблицы, связываемые по одному и тому же хэш-ключу. В каком бы порядке они ни обрабатывались, для них не требуется выполнять хэширование и разбиение промежуточных результатов, поскольку это делается в процессе обработки исходных таблиц, а атрибуты связи, по определению хэш-группы, одинаковы. Для реализации этой идеи модули, управляющие разбиением и сбросом букетов на диск, были выделены из индивидуальной операции хэширования и приписаны менеджеру группы (team manager). Проиллюстрируем сказанное примером. Таблицы member, charge и payment связываются по общему атрибуту member_no.
select m.lastname, m.firstname, ch.charge_dt, ch.charge_amt, p.payment_dt,
p.payment_amt
from member m, charge ch, payme p
where m.member_no=ch.member_no and ch.member_no=p.member_no
План выполнения запроса:
StmtText
----------------------------------
/-Hash Match Root(Inner Join, HASH:(p.member_no)=(ch.member_no))
/-Hash Match Team(Inner Join, HASH:(m.member_no)=(p.member_no))
/ /-Clustered Index Scan(credit..member.PK_member AS m)
/ /-Clustered Index Scan(credit..payment.PK_payment AS p)
/-Table Scan(credit..charge AS ch)
Лист.1.4.1
Здесь Hash Match Root соответствует менеджеру группы. Кроме того, из этого примера мы видим, что оптимизатор "понимает" транзитивные предикаты, т.е. что из m.member_no= ch.member_no и ch.member_no = p.member_no следует m.member_no = p.member_no. Поскольку при выполнении запроса ему оказалось выгоднее сначала связать таблицы member и payment, то он воспользовался свойством транзитивности.
Итак, в процессоре запросов SQL Server 7.0 интегрированы практически все современные технологии построения связей. Решение о том, какая из них будет выбрана в каждом конкретном случае, принимается оптимизатором, ибо не существует, как мы могли убедиться, универсальной стратегии, выигрышной всюду. В зависимости от обстоятельств любой из перечисленных алгоритмов может оказаться оптимальнее своих альтернатив. Например, для таблиц небольшого размера будет, скорее всего, использоваться вложенный цикл, так как оказывается дешевле просканировать каждый из входов, чем отводить память под хэш-таблицу. Кроме того, вложенный цикл - единственный приемлемый алгоритм для разрешения связи типа "больше-меньше", так как и merge, и hash join могут использоваться, когда предикат связи включает хотя бы один подходящий оператор равенства. В принципе, это не такое уж серьезное ограничение, поскольку одно из основных назначений join - реализация связей типа "первичный ключ - внешний ключ", где равенство всегда присутствует. Если входы достаточно велики и отсортированы по атрибуту связи (либо есть возможность быстро выполнить эту сортировку, либо результаты сортировки потом для чего-нибудь пригодятся и т.д.), наиболее оптимальным выбором представляется sort merge, в противном случае - вероятно, hash match. Широкий спектр доступных стратегий позволяет оптимизатору иметь наиболее эффективные инструменты построения связи для самых различных ситуаций. Еще одним преимуществом выступает возможность динамической адаптации (dynamic destaging). Очевидно, что оценка параметров итератора (например, количество записей на выходе) дается с той или иной степенью погрешности ([13]). В сложных планах с большим числом промежуточных этапов ошибка может накапливаться. Например, исходя из условий оценки оптимизатор считал возможным применить in-memory hash, но реальный размер build input не позволяет это сделать. При этом будут последовательно испробованы hybrid join, grace join или recursive hash join. Таким образом, в результате динамической адаптации плана ошибка оценки способна вызвать в худшем случае плавное снижение производительности (graceful degradation) в зависимости от величины расхождения.
1.5 Подсказки для Join
Внедрение перечисленных стратегий привело к пополнению подсказок оптимизатора ([2]). Инструкции с ключевыми словами LOOP, MERGE, HASH позволяют принудительно указать методику построения связи. Например, если мы слегка модифицируем запрос на Лист.1:
select * from authors a inner hash join titleauthor ta on a.au_id=ta.au_id where a.au_lname like "R%"
то в плане увидим, что вместо nested loop связь будет построена с помощью hash match. Если вместо hash поставить merge, то оптимизатор предложит выбрать из authors все записи, удовлетворяющие условию фильтрации, отсортировать их по au_id (по au_id существует индекс, но он некластерный) и связать с titleauthor, которая имеет кластерный индекс по (au_id, title_id). Среди запросных хинтов к теме данной главы относятся HASH / ORDER GROUP - оговаривает условия выполнения группирования: хэшированием или по-старому через stream-based сортировку; MERGE / HASH / CONCAT UNION - способ построения объединения; FORCE ORDER - действия, аналогичные упоминавшейся выше команде SET FORCEORDER, но только для данного запроса. Пример: по умолчанию оптимизатор намерен выполнять select au_lname from authors group by au_lname сканированием таблицы authors, сортировкой выходного потока и последующим агрегированием. Применение опции hash group:
select au_lname from authors group by au_lname option (hash group)
StmtText
----------------------------------
/-Hash Match(Aggregate, HASH:(authors.au_lname)RESIDUAL: (authors.au_lname=authors. au_lname))
/-Index Scan(pubs..authors.aunmind)
Лист.1.5.1
заставляет оптимизатор сформировать хэш-таблицу и сгруппировать записи по совпадающим хэш-значениям. Поэтому в первом случае мы получим результат, упорядоченный по au_lname, а во втором - в порядке следования хэш-значений. Еще одно изменение в синтаксисе Transact-SQL касается количества таблиц в запросе, которое может теперь достигать 256 (по сравнению с 16 в предыдущей версии). Читателям, желающим убедиться в этом на собственной практике, предлагается следующий модельный скрипт:
Dim adoCnn As ADODB.Connection
Set adoCnn = CreateObject("ADODB.Connection")
adoCnn.Provider = "SQLOLEDB"
adoCnn.Properties("Data Source") = "alexeysh_lapt"
adoCnn.Properties("User ID").Value = "sa
"adoCnn.Properties("Password"). Value = ""
adoCnn.Properties("Initial Catalog") = "pubs"
adoCnn.Open
Dim i As Integer, n As Integer
n = 256
For i = 1 To n
adoCnn.Execute ("select * into authors" & CStr(i) & " from authors")
Next
If adoCnn.State <> adStateOpen Then Exit Sub
Dim cStmt(2) As String
cStmt(0) = "select a1.au_lname"
cStmt(1) = "from authors1 a1"
cStmt(2) = "where "
For i = 2 To n
cStmt(0) = cStmt(0) & ", a" & CStr(i) & ".au_lname"
cStmt(1) = cStmt(1) & ", authors" & CStr(i) & " a" & CStr(i)
cStmt(2) = cStmt(2) & "a1.au_id=a" & CStr(i) & ".au_id and "
Next
cStmt(2) = Left(cStmt(2), Len(cStmt(2)) - 5)
Debug.Print Len(cStmt(0) & " " & cStmt(1) & " " & cStmt(2))
Dim adoRS As ADODB.Recordset
Debug.Print cStmt(0) & " " & cStmt(1) & " " & cStmt(2)
adoCnn.CommandTimeout = 3600
Dim t As Date
t = Now()
Set adoRS = adoCnn.Execute(cStmt(0) & " " & cStmt(1) & " " & cStmt(2))
Debug.Print Format(Now() - t, "hh:mm:ss")
Debug.Print adoRS.GetString(adClipString, -1, , , "")
For i = 1 To n
adoCnn.Execute ("drop table authors" & CStr(i))
Next
adoCnn.Close
В настольной (точнее, "наколенной") конфигурации с Pentium MMX 133 MHz и 80 Mb RAM запрос был отработан за 17 мин. Помимо SQL Server 7.0, были запущены SQL Profiler, Performance Monitor и MS Word.
1.6 Оптимизация OLAP-запросов
Возможность использования большего количества таблиц в запросе наряду с уже упоминавшимися характеристиками позволяет процессору запросов эффективно выполнять OLAP-запросы. Работа со звездными схемами или "снежинками" не требует какой-либо дополнительной адаптации кода по сравнению с OLTP-запросами. Обычно считается, что для операций над множествами мы должны иметь bitmap-индексы. Нам представляется, однако, что как и для других типов неуникальных некластерных индексов, это лишь вопрос формы представления множества RIDов, ассоциированных с ключом поиска. Вitmap-индексы представляют его (множество) в виде битовой карты, тогда как B-Tree индексы явно нумеруют всех членов каждого множества. Оба представления имеют свои слабые и сильные стороны, соответственно, существуют ситуации, в которых каждое может проявить себя наилучшим образом. Так, при работе с MOLAP-хранилищами в Microsoft OLAP Services for SQL Server широко применяются bitmap-индексы. Однако, говоря о ROLAP и SQL Server, еще раз подчеркнем, что все операции над битовыми индексами, также выполнимы для обычных индексов. Рассмотрим следующие два запроса вместе с их планами выполнения:
select * from sales_fact_1997 where product_id between 300 and 302
and customer_id between 1000 and 1002
----------------------------------
/-Bookmark Lookup(BOOKMARK:([Bmk1000]), OBJECT:([FoodMart].[dbo]. [sales_fact_1997]))
/-Hash Match(Inner Join, HASH:([Bmk1000])=([Bmk1000]), RESIDUAL: ([Bmk1000]=[Bmk1000]))
/-Index Seek(OBJECT:
([FoodMart].[dbo].[sales_fact_1997]. [IX_sales_fact_1997_2]), SEEK:([sales_fact_1997].
[customer_id] BETWEEN 1000 AND 1002) ORDERED)
/-Index Seek(OBJECT:
([FoodMart].[dbo].[sales_fact_1997]. [IX_sales_fact_1997]),
SEEK:([sales_fact_1997].[product_id] BETWEEN 300 AND 302) ORDERED)
и
select * from sales_fact_1997 where product_id between 300
and 302 or customer_id between 1000 and 1002
----------------------------------
/-Bookmark Lookup(BOOKMARK:([Bmk1000]),
OBJECT:([FoodMart].[dbo]. [sales_fact_1997]) WITH PREFETCH)
/-Hash Match(Union)
/-Index Seek(OBJECT:
([FoodMart].[dbo].[sales_fact_1997]. [IX_sales_fact_1997]),
SEEK:([sales_fact_1997].[product_id] BETWEEN 300 AND 302) ORDERED)
/-Index Seek(OBJECT:
([FoodMart].[dbo].[sales_fact_1997].[IX_sales_fact_1997_2]),
SEEK:([sales_fact_1997].[customer_id] BETWEEN 1000 AND 1002) ORDERED)
Лист.1.6.1
К сожалению, рассказ о работе с индексами в SQL Server 7.0 выведет нас далеко за рамки отведенного объема статьи, поэтому мы ограничимся вышеприведенными примерами для того, чтобы проиллюстрировать, как процессор запросов привлекает стратегию hash match для выполнения теоретико-множественных операций (в данном случае, соответственно, пересечение и объединение) над традиционными индексами B-Tree структуры. Заметим только, что в запросах вида select fld1, fld2 from tbl where fld1=... and fld2=... это избавляет нас от необходимости иметь самостоятельный покрывающий индекс по (fld1, fld2), так как при наличии отдельных индексов по fld1 и по fld2 SQL Server 7.0 построит его динамически.
Вернемся тем не менее к аналитическим запросам. Рассмотрим пример:
select f.unit_sales, s.store_name from sales_fact_1997 f, store s, store s1
where f.store_id = s.store_id and f.store_id = s1.store_id and
s.store_city = "Seattle" and s1.store_type = "Supermarket".
Как правило, таблица фактов много больше, чем каждая из таблиц таблиц измерений. В данном случае Sales_Fact _1997 имеет 86837 записей, а Store всего 24. Не имеет смысла два раза связывать измерение с массивной таблицей фактов. Гораздо дешевле будет построить два промежуточных множества, одно из которых отфильтровано по ограничению на store_city, другое по store_type, сделать из них декартово произведение (все равно оно получится небольшим по сравнению с таблицей фактов) и уже его связывать с Sales_Fact_1997. Именно так поступает SQL Server:
----------------------------------
/-Hash Match(Inner Join, HASH:(s1.store_id)=(f.store_id) RESIDUAL:(f.store_id=s1.store_id))
/-Nested Loops(Inner Join)
/ /-Clustered Index Scan(FoodMart..store.PK_store AS s,
WHERE:(s.store_city="Seattle")ORDERED)
/ /-Clustered Index Seek(FoodMart..store.PK_store AS s1, SEEK:(s1.store_id=s.store_id),
WHERE:(s1.store_type="Supermarket") ORDERED)
/-Table Scan(FoodMart..sales_fact_1997 As f)
Рассмотрим другой запрос:
select f.unit_sales, s.store_name from sales_fact_1997 f, store s, time_by_day t
where f.store_id = s.store_id and f.time_id = t.time_id and
s.store_city = "Seattle" and t.the_month = "May"
Лист.1.6.2
Временное измерение здесь выступает в роли ограничивающего фактора, данные из него возвращать не требуется, так что нецелесообразно строить связь между Time_By_Day и Sales_Fact_1997. Декартово произведение измерений в случае semi-join также не имеет смысла. Поэтому процессор запросов выполняет hash match между измерением Store и таблицей фактов, а промежуточные результаты пересекает с Time_By_Day:
----------------------------------
/-Hash Match(Inner Join, HASH:(t.time_id)=(f.time_id) RESIDUAL:(f.time_id=t.time_id))
/-Clustered Index Scan
(FoodMart..time_by_day. PK_time_by_day AS t, WHERE:(t.the_month="May"))
/-Hash Match(Inner Join, HASH:(s.store_id)=(f.store_id) RESIDUAL:(f.store_id=s.store_id))
/-Clustered Index Scan
(FoodMart..store.PK_store AS s, WHERE:(s.store_city="Seattle"))
/-Table Scan(FoodMart..sales_fact_1997 AS f)
Лист.1.6.3
Приведем еще один пример оптимизации при работе с хранилищами. Пусть наше хранилище содержит несколько таблиц фактов, каждая из которых хранит данные за определенный период времени, допустим, за год. Мы строим виртуальный куб в виде представления (view) как объединение разбиений по годам: create view All_Years_View as select * from Year1991 union all ... union all select * from Year1998. Тогда запрос select ... from All_Years_View where year=1997 приведет к обработке не всего представления в целом, а только отдельной таблицы, содержащей данные за выбранный год (Year1997). Для этого годовые ограничения должны быть явно заданы на таблицах в виде check: check(year=1991) и т.д.
Продолжение часть 2 >>