I tend to dislike cost-based optimizers because they add a layer of uncertainty when you're attempting to optimize database queries. I know what I want the optimizer to do. The problem is that when I run test queries against a local database or even a staging database, the statistics used to calculate costs differ. This means production can do something totally undesirable.
People generally interested in this topic might also find the CMU Intro to DB Systems youtube of interest.<p>Note that it's an introduction to <i>building</i> database systems (not just using them).<p><a href="https://www.youtube.com/playlist?list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7" rel="nofollow">https://www.youtube.com/playlist?list=PLSE8ODhjZXja3hgmuwhf8...</a>
Great article, and it sounds like it took a pretty big leap of faith to go from heuristics to cost-based optimization. If this was addressed in the article I apologize: do you only ever select transformations that yield equivalent results, with immediately lower cost, or do you also explore transformations that incur in immediate cost increase, but then later pay off? i.e. are you doing simple hill climbing, or something more interesting?
Maybe of interest - postgres planner documentation<p><a href="https://www.postgresql.org/docs/current/planner-optimizer.html" rel="nofollow">https://www.postgresql.org/docs/current/planner-optimizer.ht...</a><p>Genetic query optimiser: <a href="https://www.postgresql.org/docs/current/geqo.html" rel="nofollow">https://www.postgresql.org/docs/current/geqo.html</a><p>postgres has a number of hooks, which can be used to override the default behaviour. In particular, there are a bunch of hooks that can be used to install a custom query planner. <a href="https://github.com/AmatanHead/psql-hooks/blob/master/Readme.md#planner-hooks" rel="nofollow">https://github.com/AmatanHead/psql-hooks/blob/master/Readme....</a><p>more generally, ignoring database query optimisation specifically, if you are interested in learning about discrete optimisation techniques, I recommend this course: <a href="https://www.coursera.org/learn/discrete-optimization" rel="nofollow">https://www.coursera.org/learn/discrete-optimization</a>
> outside expert on database optimizers run a months-long bootcamp, with the goal of teaching our developers how state-of-the-art optimizers work, complete with homework assignments to read seminal papers on the subject<p>Any chance you could share more about this? This general area of how to build a production grade SQL optimizer seems to be a thing that's more scattered in tiny pieces across a wide number of papers, or held in peoples' heads, than aggregated in a teaching manner. It seemed that the realistic general advice on how to build a SQL optimizer was to poach someone from the SQL Server team. ;)<p>I've generally just gone referring back to the unfinished Building Query Compilers[1] when pondering this subject. Not that the hundreds of references don't provide sufficient material to read though as well, but it'd be interesting to hear what a bootcamp like this presented as state of the art.<p>[1]: <a href="http://pi3.informatik.uni-mannheim.de/~moer/querycompiler.pdf" rel="nofollow">http://pi3.informatik.uni-mannheim.de/~moer/querycompiler.pd...</a>
This is like studying chess, the approach to studying the complexities that arise from the number of routes a query can be executed is like how one will study an opening, also the tree data structure mentioned is reminiscent to chess, statistics also hence studying GM games. I feel like someone with a good understanding of chess will enjoy such a project. Anyways great post and breakdown.
Ah, my past life and knowledge developing Oracle systems comes flooding back.<p>I don't know if Oracle still uses CBO now, or even SQL or PL/SQL but I am sure that a large chunk of their revenue still comes from supporting these legacy systems.
I've been looking for books that cover database implementation techniques such as this — the "memo" algorithm was new to me, but I'm also generally interested in query planning and optimization. Anyone got any recommendations? I started a thread: <a href="https://news.ycombinator.com/item?id=18410692" rel="nofollow">https://news.ycombinator.com/item?id=18410692</a>.
Shouldn't "unless both inputs are sorted on the same key" be "unless both inputs are sorted on the join key"? And similarly later.
Excellent write-up. Thanks.<p>Has any thought been given to whether this query planner could be adapted (much further down the road, I'd guess) to support dynamic replanning? (That is, altering the plan mid-query, if it should be found that the row-count estimates were way off.)