8.2.4. Оценка размера результата оператора выбора

При выполнении оператора выбора (selection) σ количество кортежей, как правило, уменьшается, но размер отдельного кортежа сохраняется. В простейшем варианте выбора, когда атрибут сравнивается с константой, оценить размер итогового отношения несложно, если имеется возможность выяснить или приближенно оценить количество различных значений сопоставляемого атрибута. Рассмотрим оператор S = σ_a=c(R), где а — атрибут отношения R, а с — некоторая константа. В качестве оценки реко­мендуется использовать следующее соотношение:

T(S) = T(R) / V(R, a).

Оценка становится точной, если все значения атрибута а распределены с равной ве­роятностью. Впрочем, представленная формула все еще остается наилучшей оценкой в среднем — даже в том случае, если распределение значений а не является однородным, но все значения а одинаково часто упоминаются в запросах, в которых адресуется атрибут а. Еще более близкие к точным оценки удается получить, если СУБД поддерживает усо­вершенствованные функции сбора статистических характеристик и ведения гисто­грамм (histograms) данных.

Получение оценок размеров итоговых отношений становится более проблематич­ным, если критерий выбора основан на неравенстве — скажем, S= σ_а<l0(R). Навскид­ку можно было бы предположить, что в среднем одна половина значений удовлетво­ряет подобному условию, а другая — нет, и потому использовать в качестве оценки размера S значение T(R) /2. Однако интуиция подсказывает, что при обработке запро­сов, в которых в качестве условий выбора привлекаются неравенства, вообще говоря, достаточно обращаться к небольшой части всех кортежей. Поэтому мы предлагаем правило, которое согласуется с подобными эмпирическими соображениями и подра­зумевает, что типичный запрос с условием выбора, заданным в виде неравенства, воз­вращает около трети, а не половину всех кортежей исходного отношения. Таким об­разом, если S= σ_a<с(R), прогнозируемое значение T(S) выглядит как

T(S) = T(R)/3.

Случай использования условия выбора "не равно" относительно редок. Впрочем, если оператор вида S=σ_a≠c(R) все-таки встретится, в качестве оценки T(S) мы реко­мендуем использовать соотношение T(S) = T(R), т.е. считать, будто практически все кортежи исходного отношения удовлетворяют критерию а ≠ с выбора. С другой сторо­ны, можно было бы применить и такую оценку, как T(S) = T(R)(V(R, а)- l) / V(R, а), ко­торая незначительно ниже величины T(R) и согласуется с эвристикой, подразумеваю­щей, что примерно (1 / V(R, а))-я часть всех кортежей R не удовлетворяет условию, по­скольку значения их компонентов а равны заданной константе с.

Если условие С выбора представляет собой конъюнкцию (and) нескольких ра­венств и/или неравенств, оператор σ_С(R) следует трактовать как цепочку "вложенных" операторов σ, каждым из которых проверяется один конъюнкт. Заметим, что порядок перечисления частных операторов выбора несуществен. Прогнозируемый размер итогового отношения в этом случае можно представить как количество кортежей в исходном отношении, умноженное на коэффициенты "избирательности" всех част­ных операторов — 1/3 для неравенств вида > и <, 1 для ≠ и 1/ V(R, а) для условий срав­нения значений атрибута а с константой.

Пример. Рассмотрим отношение R(a,b,c) и оператор S=σ_{a=10 and b<20}(R), Допус­тим, что T(R)= 10000 и V(R, a) = 50. Тогда в качестве оценки T(S) можно принять вели­чину T(R) / (50 * 3) = 67, полагая, что примерно (1/50)-я часть кортежей R удовлетворяет условию a= 10, а (1/3) -я — условию b<20.

Частный случай, опровергающий доводы в пользу применяемого нами способа прогнозирования, связан с ситуацией, когда условие внутренне противоречи­во. Рассмотрим для примера оператор S=σ_{a=10 and а<20}(R). В соответствии с указанным правилом T(S) = T(R) / (3V(R, a)), т.е. отношение S должно было бы содержать примерно 67 кортежей. Однако совершенно очевидно, что кортежей, удовлетворяющих условиям а =10 и а>20 одновременно, не существует, так что в действительности T(S) = 0. Вы­полняя перезапись логического плана, оптимизатор запросов руководствуется, поми­мо всего прочего, множеством правил, отвечающих различным частным случаям. При обработке рассматриваемого здесь условия выбора добротный оптимизатор способен применить правило сведения условия к значению false и принять в качестве резуль­тата операции пустое множество.

Если критерий выбора образован на основе дизъюнкции (or) отдельных условий (скажем, S = σ_{C1 or C2}(R)), тогда ожидаемый размер итогового отношения не столь оче­виден. Одно из подходящих на первый взгляд соображений состоит в том, что ни один кортеж, якобы, не удовлетворяет одновременно обоим условиям, так что размер итогового отношения можно представить как сумму количеств кортежей, отвечающих каждому из условий. Подобная оценка, как правило, оказывается завышенной и под­час способна привести к совершенно абсурдному заключению о том, будто в итоговом отношении S больше кортежей, нежели в исходном R. Другой столь же простой и не­сколько более корректный подход предполагает использование в качестве оценки размера результата S минимального из двух значений — размера отношения-операнда R и суммы количеств кортежей, удовлетворяющих отдельным условиям С₁ и С₂.

Менее тривиальную и, вероятно, более точную оценку величины S= (R) можно получить в том случае, если трактовать условия С₁ и С₂ как независимые. Если R содержит п кортежей, m₁ из которых удовлетворяют условию С₁, а т₂ — усло­вию С₂, количество кортежей в S можно представить как

Внесем ясность: 1-т₁/ п — это доля кортежей, не удовлетворяющих условию С_1ь а (1 -т₂/ п) — часть кортежей, которые не отвечают условию С₂; произведение этих величин представляет часть кортежей R, которые не включаются в S, а разность еди­ницы и произведения — ту долю кортежей R, которые, напротив, в S "попадают".

Пример. Рассмотрим отношение R(a, b) с T{R) = 10000 кортежей и оператор

S=σ_{a=10 or b<20}(R).

Пусть V(R, а) = 50. Тогда количество кортежей, удовлетворяющих условию а = 10, мож­но представить как T(R) / V(R, a) = 200, а число кортежей, соответствующих условию b<20, — как T(R)/3 3333. Простейшая оценка размера S выглядит как сумма двух значений, т.е. 3533. Применение более серьезного подхода, основанного на допуще­нии, что условия а = 10 и b< 20 являются независимыми, дает

10000(l - (1 - 200/10000)(1 - 3333/10000)) = 3466.

Впрочем, в этом случае оценки различаются весьма незначительно, и маловероятно, что решение о предпочтении той или иной из них способно радикальным образом повлиять на выбор наилучшего физического плана.

Наконец, вкратце обсудим способ прогнозирования размера итогового отношения, если в условии оператора выбора присутствует логический оператор not. Ожидаемое количество кортежей отношения R, удовлетворяющих условию not С, равно T(R) за вычетом приближенного числа кортежей, отвечающих условию С.