Лучший в худшем случае

[thesz]

Вот результаты моего развлечения над одним запросом из TPC-DS, конкретно, запрос 96. Это всё предварительное, я обнаружил проблемы в наборе данных.



Вот запрос:
select top 100 count(*)
from store_sales
,household_demographics
,time_dim, store
where ss_sold_time_sk = time_dim.t_time_sk
and ss_hdemo_sk = household_demographics.hd_demo_sk
and ss_store_sk = s_store_sk
and time_dim.t_hour = 8
and time_dim.t_minute >= 30
and household_demographics.hd_dep_count = 5
and store.s_store_name = 'ese'
order by count(*)
;Ничего особенного.

Что я делаю?

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

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

И вот, что у меня получилось:
scanning "store"
scanning "time_dim"
scanning "household_demographics"
scanning "store_sales"
field FieldInfo {fiTable = "household_demographics", ftName = "hd_demo_sk", fiIndex = 0, fiType = TyInt}: 720
field FieldInfo {fiTable = "store", ftName = "s_store_sk", fiIndex = 0, fiType = TyInt}: 1
field FieldInfo {fiTable = "store_sales", ftName = "ss_hdemo_sk", fiIndex = 5, fiType = TyInt}: 7201
field FieldInfo {fiTable = "store_sales", ftName = "ss_sold_time_sk", fiIndex = 1, fiType = TyInt}: 45648
field FieldInfo {fiTable = "store_sales", ftName = "ss_store_sk", fiIndex = 7, fiType = TyInt}: 7
field FieldInfo {fiTable = "time_dim", ftName = "t_time_sk", fiIndex = 0, fiType = TyInt}: 1800
table rows' counts:
table "store": 12 rows read, 1 rows pass filters.
table "time_dim": 86400 rows read, 1800 rows pass filters.
table "household_demographics": 7200 rows read, 720 rows pass filters.
table "store_sales": 2880404 rows read, 2880404 rows pass filters.
after combination:
field FieldInfo {fiTable = "household_demographics", ftName = "hd_demo_sk", fiIndex = 0, fiType = TyInt}: 720
field FieldInfo {fiTable = "store", ftName = "s_store_sk", fiIndex = 0, fiType = TyInt}: 1
field FieldInfo {fiTable = "store_sales", ftName = "ss_hdemo_sk", fiIndex = 5, fiType = TyInt}: 720
field FieldInfo {fiTable = "store_sales", ftName = "ss_sold_time_sk", fiIndex = 1, fiType = TyInt}: 1661
field FieldInfo {fiTable = "store_sales", ftName = "ss_store_sk", fiIndex = 7, fiType = TyInt}: 1
field FieldInfo {fiTable = "time_dim", ftName = "t_time_sk", fiIndex = 0, fiType = TyInt}: 1661
scanning "store"
scanning "time_dim"
scanning "household_demographics"
scanning "store_sales"
table rows' counts with sets filtering:
table "store": 12 rows read, 1 rows pass filters.
table "time_dim": 86400 rows read, 1661 rows pass filters.
table "household_demographics": 7200 rows read, 720 rows pass filters.
table "store_sales": 2880404 rows read, 949 rows pass filters.Пояснение: после сканирования я печатаю поля, что участвовали в связях и размеры множеств, что получились после фильтрации. Ещё показаны количества строк, что мы прочли, и что прошли все проверки. Потом я снова печатаю размеры множеств уже после вычисления пересечений, как и счётчики строк.

Итого, фильтрация оставила 1,6% данных (46 тысяч строк пройдёт), а пересечение оставило 3,6% от отфильтрованных данных (1661 строка пройдёт через дополнительную фильтрацию по пересечению). Нагрузка на вычисление объединений (join) будет совсем малой.

Я поправил ошибку в построении будущего представления запроса и добавил повторное сканирование с учётом накопленных данных. В результате, у самой большой таблицы через все проверки прошло всего 949 строк из почти трёх миллионов. Это 0,033%! Тридцать три тысячных процента!

Получается, даже фильтр Блюма с одним ключом (внутри фильтра Блюма, практически, битовая маска) может быть полезен.