Лекция №15 - Пример оценки

Оптимизация SQL-запросов

Методы соединения таблиц

Алгоритмы для поиска физического плана

Пример оценки физического плана

Исходные данные:

1) количество записей в таблице T (R 1) = 10000, количество записей в таблице T (R 2) = 100000;

2) количество записей в одном блоке таблицы L (R 1)= L (R 2) = 100, количество записей в соединении LJOIN = 1000;

3) количество записей в блоке индекса код_пользователя {{Формула|f=L} = 200, количество записей в блоке индекса номер_счёта {{Формула|f=L} = 200;

Примечание: записи исходных таблиц могут читаться в сортированном виде по своим индексированным атрибутам. Записи в таблице R1 сгруппированы по атрибуту код_пользователя (кластеризованный индекс), а в таблице R2 не сгруппированы.

4) мощность атрибутов:

• R 1, код_пользователя 5000;
• R 1, номер_счёта 10000;
• R 2, номер_счёта 100000
• R 2, остаток - неизвестно.

5) тут почему-то пусто

6) b = 10, CCOMP = CMOVE = Cfilter =0.01 мс, CB =10 мс.

Для построение оптимального физического плана используется алгоритм динамического программирования (из предыдущей лекции).

Алгоритм:

1) AccessPlan

а) R 1 - таблица пользователи;

j =1, чтение всей таблицы

C 1= CCPU 1+ CI / O 1= T (R 1)⋅ Cfilter + B (R 1)⋅ CB =10000⋅0.01+10000100⋅10=1100 мс

j =2 - индекс по атрибуту код_пользователя

C 2= CCPU 2+ CI / O 2= T (R 1)⋅ KI (R 1, a)⋅ Cfilter + B (Index (a))⋅ kI (R 1, a)⋅ Cb + B (R 2)⋅ kI (R 1, a)=

=10000⋅15000⋅0.01+(10000/200)⋅15000⋅10+10000/100⋅15000⋅10=0.02+0.3=0.32 мс

С= min (С1,С2)=0.32 мс

С I / O = CI / O 2=0.3 мс

T (Q 1)= T (R 2)⋅ P код_пользователя=3= T (R 2)⋅ kI (R 1, a)=10000⋅1/5000=2

B (Q 1)=⌈ T (Q 1) L (R 1)⋅10⌉=⌈2100⋅10⌉=1

str [1]={{ Q 1},∅,∅,0.32,0.3,{2,1,{2},2}}

б) R 2 - таблица счёт.

j =1

C 1=100000⋅0.01+100000100⋅10=11000 мс

j =2

C = C 1=11000 мс

CI / O = CI / O 1=10000 мс

T (Q 2)= T (R 2)⋅ PR 2.остаток>1500=100000⋅1/3=33000, вероятность принята равной 1/3, так как по условию эта мощность неизвестна

B (Q 2)=⌈ T (Q 2) L (R 2)⋅10⌉=⌈33000100⋅10⌉=33

str [2]={{ Q 2},∅,∅,11000,10000,{33000,33,{33000},1}}

2) JoinPlan

m 1=1, m 2=2 - номера экземпляров структур, таких, что str [ m 1]. W = Q 1 и str [ m 2]. W = Q 2

а)

i =1, NLJ

C 1= CCPU 1+ CI / O 1= T (Q 1)⋅ T (Q 2)⋅ CCOMP +⌊ B (Q 1) b ⌋⋅ CI / O (Q 2)=2⋅33000⋅0.01+⌊110⌋⋅10000=660 мс

i =2, SMJ

таблица Q 2 уже отсортирована по номер_счёта, так как имеется индекс по номеру счёта

С2=С CPU 2+ CI / O 2= CSORTCPU (Q 1)+С JOINCPU (Q 1, Q 2)+ CSORTI / O (Q 1)+ CJOINI / O (Q 1, Q 2)=

=2⋅log22⌊1/10⌋⋅(0.01+0.01)+(log101−1)⋅2⋅(10⋅0.01+0.01)+((3300033000+2⋅2+

+33000⋅(1−233000))⋅0.01+(2⋅1⋅log10⋅1)⋅10+(1+0)⋅10=340 мс

C = min (C 1, C 2)=340

C = str [1]. Z + str [2]. Z + C =0.32+11000+340=11340.32 мс

CI / O = str [1]. ZIO + str [2]. ZIO + CI / O 2=0.3+10000+10=10010.3 мс

T (Q 1⋈ Q 2)= T (Q 1)⋅ T (Q 2) max (I (Q 1, a), I (Q 2, a))=2⋅33000 max (2,33000)=2

B (Q 1⋈ Q 2)=⌈21000⌉=1

I (Q 1⋈ Q 2, a)= min (I (Q 1, a), I (Q 2, a))= min (2,33000)=2

str [3]={{ Q 1, Q 2},{ Q 1},{ Q 2},11340,10010,{2,1,{2},2}}

б)

структура остаётся такая же

3) OptPlanReturn - вывод оптимального плана и представление этого плана в графическом виде.

1) (Q 1, Q 2)= Q 1⋈ Q 2

2) Q 1=(IndexScan ()+ Filter ())

3) Q 2=(TableScan ()+ Filter ())