Оптимизация 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 ())