search

egraphs-good / egg

egg is a flexible, high-performance e-graph library
https://egraphs-good.github.io
MIT License
1.35k stars 136 forks source link

Cascades like SQL query optimizer using egg? #227

Closed fabianmurariu closed 1 year ago

fabianmurariu commented 1 year ago

Hi,

I've been looking at writing a general purpose SQL query optimizer on top of egg. Are you aware of anyone else trying to do so? I'd prefer not starting from scratch. Egg looks very close to what Cascades/Columbia optimizers do but in a more generic way.

Cheers

mwillsey commented 1 year ago

It is something we've discussed, but I don't know of anyone who has yet done it. I think it's a great idea though! One big challenge left to connect the two frameworks is cost-driven optimization. Cascades relies on branch-and-bound, top-down search to prune the search space. We don't yet know how to emulate this with the bottom-up approach that egg/equality saturation does. But I suspect it can be made to work!