Процесор запитів Microsoft SQL Server. Частина 1, Інші СУБД, Бази даних, статті

Введення


Напевно, не буде великим перебільшенням сказати, що процесор запитів (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). Вартість зв'язку обчислюється як кількість сторінок у зовнішній таблиці + кількість записів, що задовольняють можливого умові фільтрації у зовнішній таблиці * кількість сторінок, які необхідно прочитати за один пошук у внутрішній таблиці. Бажаючі дізнатися, як вважається кількість сторінок при пошуку запису, що задовольняє певній умові, якщо ця умова є 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! / (nk)! – Число розміщень з 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 виявиться менше свого builda 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>>


Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*