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

Данный физический план реализуется следующим образом;

1. для реализации подзапроса к R 1 читается вся таблица, записи фильтруются по f 1 и получаемая таблица является правым аргументов в операции соединения;
2. из таблицы R 2 выделяется подусловие y для индексируемого атрибута, а потом выполняется чтение записей, удовлетворяющих этому условию. Полученные записи фильтруются по f 2 и получаемая таблица является левым аргументом в операции соединения.

Как мы уже знаем, оптимизатор для каждого физического плана рассчитывает стоимость. Рассмотрим этот расчёт для данного примера: Cost Σ= Cost (TableScan (R 1), Filter (f 1,Π A 1))+ Cost (IndexScan (R 2, y), Filter (f 2,Π A 2))+ Cost (⋈)

Каждая из Cost () учитывает и процессорную составляющую, и временную составляющую ввода-вывода.

 

Лекция №11 - Оценки

 

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

Физический план

Методы выбора записей из исходной таблицы

Оценка числа кортежей в промежуточной таблице

В таблице Q. Вычисляется по формуле:

Q =Π A (σf (R))

T (Q)= T (R)⋅ p

здесь:

Q - промежуточная таблица;

T (Q) - число кортежей в промежуточной таблице;

T (R) - число записей в исходной таблице R;

p - вероятность того, запись из таблицы R удовлетворяет условию F.

Расчёт p:

1. если f = F 1⋂ F 2, то p = p 1⋅ p 2;
2. если f = F 1⋃ F 2, то p = p 1+ p 2− p 1⋅ p 2;
3. если f = F 1¯¯¯¯, то p =1− p 1.

Для i -ой вероятности:

pi = kI (R, a)

здесь:

k - мощность атрибута a в запросе;

I (R, a) - мощность атрибута a в таблице R.

Пример

Допустим, T (R)=1000, I (R, a)=5, I (R, b)=10, I (R, c)=2, где a, b, c - положительные натуральные числа.

И f =(a <3 OR b ≥5) AND c =2

Найти T (Q).

Обозначим:

• a <3 как F 1;
• b ≥5 как F 2;
• f =(a <3 ORb ≥5) как F 3;
• c =2 как F 4.

1)

F 1⋃ F 2= F 3

p 3= p 1+ p 2− p 1⋅ p 2=25+610−25⋅610=0.76

2)

f = F 3⋂ F 4

p = p 3⋅ p 4=0.76⋅12=0.38 - это вероятность того, что запись из R удовлетворяет условию f.

3)

T (Q)=1000⋅0.38=380

Оценка количества блоков

Q =Π A (σf (R))

B (Q)=[ T (Q) LB ] - скобки обзначают, что огругление с избытком.

здесь:

T (Q) - прогнозируемое число записей в подзапросе;

LB - длина блока (число записей в блоке) с учётом Π A.

Порядок соединения промежуточных таблиц

Деревья соединения

Используются деревья соединения, которые бывают трёх видов:

• левостороннее;
• кустовое, ветвящееся;
• правостороннее.

Левостороннее

Предположим, соединяются таблицы R, S, T, U:

В каждом соединении правым аргументом является одна из таблиц.

Преимущества:

• число перебора вариантов меньше, чем для произвольного варианта соединения (если количество соединений n, то вариантов перебора будет n!);
• достаточно просто организивать каналы обработки - возможность передачи результата выполнения одной операции на вход другой через оперативную память (без сохранения на диск);

В канале левый аргумент называется опорным и он должен храниться в оперативной памяти. Правый аргумент называется тестируемым и он может храниться и на диске. При хранении в оперативной памяти не надо читать с диска, потому всё можно выполнить за один проход.

Недостатки:

• путём перебора порядков соединения можно выбрать квазиоптимальный план (потому что на самом деле вариантов перебора больше, чем n!, потому что правый аргумент - всегда таблица).

Кустовое

Тут таблицы могут соединяться в любом порядке.

Так что перебираются все возможные варианты соединения.

Преимущества:

• всегда выбирается оптимальный план.

Недостатки:

• если количество соединяемых таблиц велико, то перебор всех деревьев может занять много времени;
• могут возникнуть сложности в организации канала обработки, так как возрастают требования к объёму оперативной памяти. Чтобы реализовать соединение за один проход, в памяти должно храниться слишком много таблиц.

Правостороннее

При таком порядке левым аргументом каждого соединения является исходная таблица.

Такой способ практически не используется, потому что для него требуется, чтобы каждая из исходных таблиц и промежуточные результаты могли уместиться в оперативной памяти.