Предполагаемый размер операции самосоединения для отношения R с учетом гистограммы для R

Question

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

Ниже показана одна такая гистограмма для отношения 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

Как рассчитать ответ?

Answer 1

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

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

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

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

Answer 2

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

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

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