Блог

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

Ниже показана одна такая гистограмма для отношения R для дискретного атрибута a с доменом [1..10] :

 Bucket 1: range = [1..2] Cumulative tuple count = 6 

Bucket 2: range = [3..8] Cumulative tuple count = 30

Bucket 3: range = [9..10] Cumulative tuple count = 10
  

Каков предполагаемый размер операции самосоединения R x R

 A) 46
B) 218
C) 248
D) 1,036
E) 5,672
  

Ответ, приведенный в решениях: B

Как вычисляется ответ?

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

Здесь частота указана в сегментах, например, первый сегмент имеет 2 значения r с частотой = 6, поэтому мы можем предположить, что частота каждого значения в первом сегменте равна частоте = 3, аналогично для второго сегмента частота каждого = 30/6 = 5, а для третьего сегмента частота каждого значения = 10/2= 5.

Следовательно, размер

 Size =  [(3^2)*2]   [(5^2)*6]   [(5^2)*2]
     =  218
  

Я пытался разобраться в этом сам (это из экзамена GRE по подготовке к предметному тестированию по информатике). До сих пор я не нашел ответа на вопрос, почему ответ равен 218, но я нашел связь между заданными числами и правильным ответом.

Оказывается, что сумма квадратов суммарного количества кортежей, деленная на количество дискретных значений в каждом сегменте, вы получаете 218. Менее абстрактно : 6²/2 30²/5 10²/2 = 218 .

Это не ответ, но, по крайней мере, есть связь =)