Індексні об’єднання в SQL Server, Інші СУБД, Бази даних, статті

За матеріалами статті Craig Freedman: Index Union
Переклад Ірини Наумової

Раніше я планував продовжити писати про паралелізм (і зроблю це наступного разу в іншій статті), але отримав цікаве питання і вирішив написати про індексних об’єднаннях в SQL Server.


Почнемо:







create table T (a int, b int, c int, x char(200))
create unique clustered index Ta on T(a)
create index Tb on T(b)
create index Tc on T(c)

insert T values (1, 1, 1, 1)
insert T values (2, 2, 2, 2)
insert T values (3, 3, 3, 3)

select a from T where b = 1 or b = 3


/ – Index Seek (OBJECT: ([Т]. [Тb]), SEEK: ([Т]. [B] = (1) OR [Т]. [B] = (3)) ORDERED FORWARD)

У нас є індекс на поле “b”, і, як і очікувалося, оптимізатор вибирає пошук за індексом. Оскільки ми маємо два предиката для поля “b”, ми отримаємо пошук з двома предикатами. Спочатку виконається предикат “B = 1”, а зетем “b = 3”. Зверніть увагу, що оскільки ми виводимо стовпець “a”, а він є кластеризованих (і таким чином покриває всі некластеризованих індекси), не виникає необхідності в операції BOOKMARK LOOKUP (пошук закладок). Поки немає ніяких несподіванок.
Зверніть увагу, що ми могли записати цей запит в іншому вигляді:







select a from T where b = 1
union all
select a from T where b = 3


  /–Concatenation
/ – Index Seek (OBJECT: ([Т]. [Тb]), SEEK: ([Т]. [B] = (1)) ORDERED FORWARD)
/ – Index Seek (OBJECT: ([Т]. [Тb]), SEEK: ([Т]. [B] = (3)) ORDERED FORWARD)

Оптимізатор не об’єднує ці операції в одну операцію INDEX SEEK (пошуку за індексом), але запити та плани логічно ідентичні.
Розглянемо наступний запит:







select a from T where b = 1 or c < 3


/ – Clustered Index Scan (OBJECT: ([Т]. [Тa]), WHERE: ([Т]. [B] = (1) OR [Т]. [C] <(3)))

У нас є індекси на шпальтах “b” і “c”, але оптимізатор їх не використав. Чому? Нам потрібні всі рядки, що задовольняють будь-якого з предикатів. Ми могли б використовувати індекс на стовпці “b”, щоб отримати рядки, що задовольняють предикату “b = 1”, але при цьому ми можемо пропустити рядки, які задовольняють предикату “з <3", і для яких "b! = 1". Наприклад, ми пропустили б рядок зі значенням (2,2,2,2). Та ж сама проблема виникає при використанні індексу на стовпці "с", щоб задовольнити предикату "c <3". (В моєму прикладі дані не включають рядків зі значенням "b = 1", для яких виконується предикат "З> 3″, але такий рядок могла б існувати, тому ми повинні передбачити і такий варіант).


Індексні об’єднання

І так, давайте розберемося, чи буде SQL Server так виконувати декомпозицію запиту, щоб використовувати два індекси? Так! Спочатку для того щоб оптимізатор вибрав інший план, в якому не буде сканування кластерного індексу, ми повинні додати досить велику кількість даних в таблицю, щоб зробити операцію сканування кластерного індексу більш дорогої.
Зверніть увагу, що до використовуваної раніше таблиці я додав стовпець типу char (200), щоб рядки стали більше. Додавання цього стовпця призведе до того, що таблиця буде займати більше сторінок, що також зробить операцію перегляду більш дорогої.







truncate table T

set nocount on
declare @i int
set @i = 0
while @i < 1000
  begin
    insert T values(@i, @i, @i, @i)
    set @i = @i + 1
  end

select a from T where b = 1 or c < 3


/ – Sort (DISTINCT ORDER BY: ([T]. [А] ASC))
     /–Concatenation
        /–Index Seek(OBJECT:([T].[Tb]), SEEK:([T]. [ b ]=(1)) ORDERED FORWARD)
        /–Index Seek(OBJECT:([T].[Tc]), SEEK:([T]. [ c ] < (3)) ORDERED FORWARD)

Цей план дуже схожий на наведений вище план з оператором UNION ALL. Оптимізатор виконав декомпозицію таким чином, що запит став виглядати так:







select a from T where b = 1
union
select a from T where c < 3


Однак, варто звернути увагу на те, що два об’єднуються запиту можуть повернути дублікати рядків, тому потрібно використовувати оператор UNION (який усуває дублікати), а не UNION ALL (який цього не робить). Оператор CONCATENATION реалізує конструкцію UNION ALL, а SORT DISTINCT усуває дублікати, перетворюючи UNION ALL в UNION. Такий тип плану виконання запиту можна вважати індексним об’єднанням.


Merge Join


Давайте трохи змінимо запит:







select a from T where b = 1 or c = 3


/ – Stream Aggregate (GROUP BY: ([Т]. [A]))
     /–Merge Join(Concatenation)
/ – Index Seek (OBJECT: ([Т]. [Тb]), SEEK: ([Т]. [B] = (1)) ORDERED FORWARD)
/ – Index Seek (OBJECT: ([Т]. [Тс]), SEEK: ([Т]. [C] = (3)) ORDERED FORWARD)

Тепер, замість операторів CONCATENATION і SORT DISTINCT ми маємо MERGE JOIN (Concatenation) і STREAM AGGREGATE. Що ж сталося? MERGE JOIN (Concatenation) або “MERGE UNION” насправді нічого не з’єднують. Це здійснюється також, як за допомогою ітератора MERGE UNION, але насправді виконується операція UNION ALL із збереженням порядку вхідних рядків. Після цього використовується STREAM AGGREGATE, який усуває дублікати (для отримання більш детальної інформації, вивчіть статтю “Агрегат потоку (Stream Aggregate)”, в якій написано про використання STREAM AGGREGATE для усунення дублікатів). Такий план виконання запиту буде працювати краще, тому що не буде використовувати SORT DISTINCT, який використовує пам’ять і може стати причиною скидання сторінки даних на диск, якщо дія виконується за межами пам’яті. В цьому плані виконання запиту використовується STREAM AGGREGATE, який пам’ять не використовує.

Тоді чому ж ми не використовували цей план з самого початку? Точно так само як MERGE JOIN, MERGE UNION вимагає, щоб вхідні дані були розсортовані по ключу злиття (у нашому випадку це стовпець “a”). Некластеризованих індекс “Tb” покриває ключ індексу “b” і ключ кластеризованого індексу “a”. Таким чином, цей індекс повертає рядки в порядку (b, a). Однак, це еквівалентно предикату “b = 1”, стовпець “b” – константа, цим ми фактично упорядковуємо рядки по стовпцю “a”. Те ж саме трапляється з індексом Tc і предикатом “c = 3”. Таким чином, у нас є два вхідних потоку, які обидва впорядковані за стовпцем “а”, і ми можемо використовувати MERGE UNION.
У попередньому прикладі, одним з предикатів був “c 3”. Оскільки цей предикат – нерівність, INDEX SEEK повертає рядки в порядку (c, a). І так як рядки не розсортовані за стовпцем “a”, ми не зможемо використовувати MERGE UNION.


Об’єднання трьох індексів


Оператор CONCATENATION може підтримувати більше двох вхідних потоків:







select a from T where a = 1 or b = 2 or c < 3


/ – Sort (DISTINCT ORDER BY: ([Т]. [А] ASC))
     /–Concatenation
/ – Clustered Index Seek (OBJECT: ([Т]. [Тa]), SEEK: ([Т]. [A] = (1)) ORDERED FORWARD)
/ – Index Seek (OBJECT: ([Т]. [Тb]), SEEK: ([Т]. [B] = (2)) ORDERED FORWARD)
/ – Index Seek (OBJECT: ([Т]. [Тс]), SEEK: ([Т]. [С] <(3)) ORDERED FORWARD)

MERGE UNION підтримує тільки два вхідних потоку, але вхідні потоки можна об’єднувати каскадом, щоб дозволяє в підсумку об’єднати більше двох вхідних потоків:







select a from T where a = 1 or b = 2 or c = 3


/ – Stream Aggregate (GROUP BY: ([Т]. [A]))
     /–Merge Join(Concatenation)
        /–Merge Join(Concatenation)
/ / – Clustered Index Seek (OBJECT: ([Т]. [Тa]), SEEK: ([Т]. [A] = (1)) ORDERED FORWARD)
/ / – Index Seek (OBJECT: ([Т]. [Тb]), SEEK: ([Т]. [B] = (2)) ORDERED FORWARD)
/ – Index Seek (OBJECT: ([Т]. [Тс]), SEEK: ([Т]. [C] = (3)) ORDERED FORWARD)

Які стовпці повертає об’єднання?

Об’єднання повертає тільки ті стовпці, які є загальними для всіх його вхідних потоків. У всіх наведених вище прикладах індексних об’єднань, єдиним стовпцем, який у індексів був загальним, був ключ кластеризованого індексу – колонка “a” (це як якби індекс Tb складався з стовпців “b, a”, а індекс Tc складався з “c, a”). Таким чином, наше об’єднання може повернути тільки стовпець “A”. Якщо будуть запитані і інші стовпці, використовуватиметься BOOKMARK LOOKUP. Так буде навіть в тому випадку, якщо один з індексів в об’єднанні буде покривають ще для будь-яких стовпців. Наприклад, якщо ми запитаємо всі три колонки “a”, “b” і “c”, в плані виконання буде BOOKMARK LOOKUP, незважаючи на те, що стовпець “b” буде покриватися індексом Тb, а стовпчик “c” буде покриватися індексом тс:







select a, b, c from T where b = 1 or c = 3


/ – Nested Loops (Inner Join, OUTER REFERENCES: ([Т]. [A]))
/ – Stream Aggregate (GROUP BY: ([Т]. [A]))
        /   /–Merge Join(Concatenation)
/ / – Index Seek (OBJECT: ([Т]. [Тb]), SEEK: ([T]. [B] = (1)) ORDERED FORWARD)
/ / – Index Seek (OBJECT: ([Т]. [Тс]), SEEK: ([Т]. [C] = (3)) ORDERED FORWARD)
/ – Clustered Index Seek (OBJECT: ([Т]. [Тa]), SEEK: ([Т]. [A] = [Т]. [A]) LOOKUP ORDERED FORWARD)

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


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

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

Ваш отзыв

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

*

*