∑ LpBound: Pessimistic Cardinality Estimation using lp-Norms of Degree Sequences
#CBE #cardinality #linear #algebra

🥼 Article https://arxiv.org/abs/2502.05912
📹 20 min video https://www.youtube.com/watch?v=ys-iQeERav8

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

🪨 Context
В базах данных перед выполнением запроса всегда есть Query Optimizer, который знает что-то про данные и придумывает правильный путь обхода, как правильно обрабоать их.
Optimizer опирается на несколько вариантов выполнения и ищет самый дешевый Cost-Based Optimizer и Cardinality Estimator, который в свою очередь старается определить количество возвращаемых строк на каждом из этапов. В зависимости от cardinality можно выбрать разные алгоритмы.

🧂The idea
В статье используются L^p space для оценки верхней границы cardinality.
Если оценивать среднюю cardinality, то можно в среднем хорошо попадать, но могут быть ситации промахов, когда из-за неправильного алгоритма выполнение запроса не влезло в память и упало с OutOfMemory. И нужно писать логику с перезапуском запроса, что сложно.

В работе авторы как раз стараются более точно оценивать верхнюю границу и у них это получается, причем используя меньший memory footprint.

🤔 My opinion
Для меня это выглядит как черная магия, перестановкой операторов в Execution Plan можно добиться значительного ускорения запроса.
Эти алгебраические трюки намного важнее всех Memory Management, io_uring и форматов хранения, и других оптимизаций.
Чистая математика и красота.

Линал не понял, но очень интересно. (с)

Углублюсь в него и вернусь в такие работы чуть позже.