How bloom filters made SQLite 10x faster

Re:How bloom filters made SQLite 10x faster by somat on Monday December 23, 2024 @12:22PM (#42495968)

The one I liked was the postgres genetic optimizer.

https://www.postgresql.org/docs/17/geqo-pg-intro.html

The theory being an exhaustive search of all possible query plans is np-hard and would take too long, so you do a limited, iterative, best fit search.

My understanding is it never worked super great and would only be used if your query exceeded some high level of complexity. I distinctly remember it being removed at some point, but I see it mentioned in current docs, so I am probably wrong about that.

Anyway I wonder if, with some of the new advances in machine learning, it would be worth revisiting this approach to optimization.

[ Parent | on HN ]

Re:How bloom filters made SQLite 10x faster by thesz on Tuesday December 24, 2024 @06:09AM (#42501168)

As you mentioned machine learning, a useful way to implement inference in language models is to use a beam search: https://en.wikipedia.org/wiki/Beam_search

Beam search approximates NP-hard solutions (make wider beam, have better approximation), is very old and it is used in SQLite query planner: https://www.sqlite.org/queryplanner-ng.html

[ Parent | on HN ]