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

1. Чтение всех записей таблицы и их фильтрация.

Схематично эту операцию (TableScan + Filter) можно представить в следующем виде (Рис. 1 .7, нижние индексы в обозначениях таблиц и условий поиска будем пока опускать).

Рис. 1.7. Чтение всех записей.

Стоимость работы процессора и дискового ввода-вывода рассчитывается по формулам:

C_CPU = T(R) · C_filter , (5.4)

C_I/O = B(R) · C_B ,

где

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

B(R) – число физических блоков таблицы R;

С_filter – время фильтрации одной записи в ОП;

C_B – время чтения/записи одного блока на диск.

2. Чтение записей с помощью индекса и их фильтрация.

Схема операции (IndexScan + Filter) представлена на Рис. 1 .8.

Рис. 1.8. Чтение записей с помощью индекса.

Стоимость работы процессора и подсистемы ввода-вывода определяются следующими выражениями:

(5.5)

где

T(R) – число записей в таблице R;

B(R) – число блоков таблицы R;

I(R,a) – мощность атрибута "а" в таблице R (число различных значений);

B(Index(R,a)) – число блоков на листовом уровне индекса по атрибуту "а";

С_filter – время фильтрации одной записи в ОП;

C_B – время чтения/записи одного блока на диск;

k – мощность атрибута "а" в запросе (число различных значений, указанных в подзапросе φ).

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

Мощность атрибута в запросе (параметр k) можно оценить с помощью следующих выражений:

(5.6)

Величину в формулах (5.5) можно интерпретировать как вероятность, что запись таблицы R удовлетворяет условию φ по атрибуту "а".

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

Число кортежей оценивается с помощью следующей формулы:

T(Q) = T(R)·p , (5.7)

где

Q=_F(R) – промежуточной таблица, соответствующая подзапросу Q,

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

T(R) – общее число кортежей в исходной таблице R,

p – вероятность того, что кортеж из R удовлетворяет условию поиска F.

Для расчета вероятности p можно воспользоваться следующими рекурсивными выражениями:

1. Пусть F = f₁ AND f­₂ . Тогда

p = p₁p₂ ,

где p_i – вероятность того, что запись из R удовлетворяет подусловию f_i (i=1,2).

2. Пусть F = f₁ OR f­₂ . Тогда

p = p₁ + p₂ – p₁p₂ .

3. Пусть F = NOT f₁ . В этом случае

p = 1 – p₁ .

Если в приведенных выше случаях 1–3 f_i – подусловие по какому-либо атрибуту "а", то вероятность p_i рассчитывается по следующей формуле:

,

где k – мощность атрибута в подзапросе (см. формулу (5.6)),

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

Ниже приведён пример расчёта числа кортежей в промежуточной таблице.

Пусть таблица R включает атрибуты (a, b, c). Число кортежей T(R) = 1000. Мощности атрибутов: I(R,a) = 5, I(R,b) = 10, I(R,c) = 2. Для простоты полагаем, что a, b, c – натуральные положительные числа.

Пусть задано условие выбора записей таблицы R:

F = (a < 3 OR b  5) AND c = 2

f₁

f₂

f₄

f₃

Требуется оценить число записей, удовлетворяющих условию F.

Решение.

1. f₃ = f₁ OR f­₂

2. F = f₃ AND f­₄

– вероятность того, что запись из R удовлетворяет условию F.

3. T(Q) = T(R)·p = 1000·0,38 = 380 – оценка числа записей, удовлетворяющих условию F.