🪖 Saving Private Hash Join
#hashjoin #sortjoin #duckdb #bufferpool

📝 Article https://www.vldb.org/pvldb/vol18/p2748-kuiper.pdf

🪨 Context
Когда база данных делает join, она создает временные структуры, которые надо где-то хранить на время запроса.
Есть несколько вариантов где хранить: оперативная память или диск.
Есть два класса алгоритмов, которые предназначены для этого и они разные, в памяти выгодней hashjoin а на диске sort-merge join и переключаться между ними в процессе работы сложно.

Поэтому все базы данных делают обычно такой выбор из таких варинтов:
1. Делаем все в памяти на Hash Join, все что не влезает в оперативку, падаем и не поддерживаем. Сорян, докиньте больше оперативки или уменьшите объем данных в запросе.
2. Делаем все всегда на Sort-Merge Join, медленее, но зато всегда точно все посчитаем, не важно каких объемов.
3. Гибридные варианты: стараемся с помощью cost-based-optimiser понять влизаем ли в память, если да, то HashJoin, если нет, то Sort-Merge Join. Есть еще вариант всегда сначала HJ и фоллбек на SMJ.

Но всегда приходится платить:
1. Либо мы в первом варианте не можем посчитать большой join.
2. Либо мы можем, но всегда медленно.
3. В части случаев можем быстро, но как только HashJoin пересает влезать в память скорость запроса резко падает на порядок, мы встречаем -- Performance Cliff, про который видно часто в работах DuckDB.

В статье как раз рассказано как с этим Performance Cliff боролись.

🧂The idea
Обычно базы данных когда реализуют BufferPool, они разделяют его управление на две части:
* Persistent Block, страницы которые должны быть всегда загружены в память
* Transient Block, страницы, которые могут быть вытеснены когда есть memory pressure

В этой работе можно сказать что BufferPool общий, и внутри него страницы отмечаются можно их вытеснять или нет.
У каждой страницы при этом, в отличии от обычной Linux Memory Page есть дополнительная информация о том участвует ли она в текущем запросе, какая это партиция джойна и прочее.
В результате можно сказать что это более эффективная реализация Linux Page Cache с учетом знаний о том что и как правильно вытеснять.

Страницы достаточно большие чтобы их было выгодно писать на NVM'e без большого overhead, eviction асинхронный относительно остальных процессов.
На графиках ребята как раз и показывают, что такой механизмов позволяет им запускать более ресурсоемкие запросы, чем те которые могут прожевать остальные -- postgresql, umbra и прочие. Они либо отстреливаются по таймауту, потому что упираются в сырую производительность дисков, либо по OOM.

🤔 My opinion
Сложности на уровне взаимодействия DB, mmap, PageCache и дисковой активности постоянные.
Если базе данных дать больше управления над системой и использовать внутренюю статистику, то она всегда может быть круче generic решения.
У автора из статьи был тезис что задача у них есть задача "duckdb это OLAP база данных, которая может запускаться на чем угодно".
С учетом таких ограничений всегда может быть memory pressure и то что они борятся с этим performance cliff это круто.

На сколько успешно? Надо пробовать.
Они про это заявляли в 2022, но тогда было много segfaults от прошлой реализации и люди не поверили в рабочее решение.
Сейчас его упростили и сделали лучше:)