2011-gre-cs-practice-book.pdf/Q66 — различия между версиями

Версия 10:01, 12 января 2025

Вопрос: Q66-08c765

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

Пример одной из таких гистограмм для отношения R по дискретному атрибуту a с доменом :

• Бакет 1: Диапазон = , кумулятивное количество кортежей = 6
• Бакет 2: Диапазон = , кумулятивное количество кортежей = 30
• Бакет 3: Диапазон = , кумулятивное количество кортежей = 10

Какова оценка размера операции self-join ?

Ответы

• 46
• Правильный ответ: 218
• 248
• 1036
• 5672

Объяснение

Исходники — вопрос 66 на 46 странице книги «2011-gre-cs-practice-book.pdf»

У нас есть три бакета с равномерными частотами:

• Бакет 1: 2 значения, каждое с
• Бакет 2: 6 значений, каждое с
• Бакет 3: 2 значения, каждое с

Для self-join по атрибуту a оценка размера равна , где — это количество кортежей, имеющих значение по атрибуту .

Следовательно:

import sympy
 
f1, f2, f3 = sympy.symbols('f1 f2 f3', positive=True)
c1, c2, c3 = sympy.symbols('c1 c2 c3', positive=True)
 
expr = c1*f1**2 + c2*f2**2 + c3*f3**2
 
values = {f1: 3, f2: 5, f3: 5, c1: 2, c2: 6, c3: 2}
 
res = expr.subs(values)
print("Оценка размера self-join:", res)  # 218