6 ms·
How We Built a Cost-Based SQL Optimizer
- ryanworl 8y agoHow do you manage statistics in the system catalog in CockroachDB?
- radub 8y ago[Cockroach Labs engineer here, I worked on statistics] All table statistics are stored in a system table (system.table_statistics). CREATE STATISTICS scans the table, calculating statistics on a column, and adds a new row to system.table_statistics. We still have a ways to go in making statistics automatic (right now it requires a manual call to CREATE STATISTICS) and more useful to the optimizer (which currently only uses basic stats). We're working on that right now for the 2.2 release.
- Lemaxoxo 8y agoAre you planning to support multivariate statistics?
- radub 8y agoWe plan to support cardinality estimations for multiple columns. Other than that there are no plans for multivariate stats in the near future.
- SaifAlHarthi 8y agoWhat if the tables were partitioned, do you calculate local statistics or you aggregate the stats and expose it to the optimizer?
- edmundhuber 8y agoGreat 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?
- setr 8y ago>it sounds like it took a pretty big leap of faith to go from heuristics to cost-based optimization Im pretty sure cost-based optimization is common enough and practically proven effective enough that its not really fair to call it a “leap of faith”; eg im pretty sure mysql and postgres both do it (and you can it see it in their EXPLAINs), and I imagine most commercial dbs do as well Its more of just a natural progression as the db gets improved Its a good article/work nonetheless, but nothing out of the ordinary in db implementation afaik
- Tostino 8y agoYes, Postgres, MySQL, MSSQL, Oracle, and i'm sure DB2 all use a cost based optimizer. +1 on the sentiment, good to see them continuing to improve, they have lots of competition to look at for examples of what to do / not to do. Progress is good none the less.
- andydb 8y agoPostgres and MySQL both do calculate costs. One difference is that they are not based around the Memo data structure (someone correct me if I'm wrong about that!), which gives an extra measure of flexibility, power, and elegance to solving the problem of SQL optimization. The Memo structure was introduced by Goetz Graefe in his seminal papers on top-down, rule-based query optimization (Exodus, Volcano, Cascades), which are the chief inspiration for CockroachDB's new optimizer. In the late 90's, Goetz joined Microsoft, and assisted the SQL Server team in rewriting their optimizer from scratch based on the techniques he had pioneered. I believe this foundation is a big reason why the SQL Server optimizer has become one of the best (if not the best) in the world. We are indeed building on the shoulders of giants.
- setr 8y ago>I believe this foundation is a big reason why the SQL Server optimizer has become one of the best (if not the best) in the world Im not at all versed in the subject, but it seems like the memo datastructure isn’t significant to the correctness of the outcome: it makes the search space smaller/faster, but doesn’t seem to lead to better cost assignment, and the logical equivalence rules should be enforced regardless of the memo dt (the alternative being external to the memoization structure) Is it just that faster search => more paths searched before timing out/giving up? And perhaps easier to reason about/encode?
- jzelinskie 8y agoI 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.
- andydb 8y agoYes, that's a real problem that DBAs routinely grapple with. To address the problem, RDBMS vendors typically support hints and "plan management" features that allow DBAs to "pin" a particular plan once they've determined it's best. However, this usually requires a knowledgeable DBA; many developers would prefer that the database automatically chooses the plan, even if it changes from time to time. CockroachDB will definitely want to support both kinds of users.
- mamcx 8y agoI think is best if it was a per-session hint, like: SET PLANNER TO COST or similar, and default to a more "static" one.
- jzelinskie 8y agoYeah, the problem is that basically none of this is portable, though. So if you're attempting to support both MySQL variants and Postgres variants, it gets nasty fast.
- joncrocks 8y agoNot portable and you have to deploy separate from your application. A company I worked for solved this by using/setting hints for queries that were known to be mis-optimised in the common case. If you're looking to be cross platform then hopefully you've already got a layer to translate intent to an appropriate SQL dialect, so you can drop it in there.
- tkyjonathan 8y ago
- dzidol 8y agoShouldn't "unless both inputs are sorted on the same key" be "unless both inputs are sorted on the join key"? And similarly later.
- andydb 8y agoYes, that would be clearer language. I'll look into updating the text.
- shoo 8y agoMaybe of interest - postgres planner documentation https://www.postgresql.org/docs/current/planner-optimizer.html https://www.postgresql.org/docs/current/planner-optimizer.ht... Genetic query optimiser: https://www.postgresql.org/docs/current/geqo.html https://www.postgresql.org/docs/current/geqo.html 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. https://github.com/AmatanHead/psql-hooks/blob/master/Readme.md#planner-hooks https://github.com/AmatanHead/psql-hooks/blob/master/Readme.... more generally, ignoring database query optimisation specifically, if you are interested in learning about discrete optimisation techniques, I recommend this course: https://www.coursera.org/learn/discrete-optimization https://www.coursera.org/learn/discrete-optimization
- timClicks 8y agoAlso of interest perhaps is a podcast episode from Software Engineering Radio with Bruce Momjian, who maintains the PostgreSQL query planner: http://www.se-radio.net/2018/06/se-radio-episode-328-bruce-momjian-on-the-postgres-query-planner/ http://www.se-radio.net/2018/06/se-radio-episode-328-bruce-m...
- anarazel 8y agoHe does not maintain the postgresql planner. He's a PostgreSQL developer, but he has not focused on the planner for at least a decade. Edit: Grammar.
- Tostino 8y agoJust listened to the podcast, really good listen which explains the basics really well. Highly recommend. Thanks for the link. Wasn't aware of this podcast before.
- atombender 8y agoI'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: https://news.ycombinator.com/item?id=18410692 https://news.ycombinator.com/item?id=18410692.
- manigandham 8y agoPosted in that thread: https://news.ycombinator.com/item?id=18411110 https://news.ycombinator.com/item?id=18411110 TLDR: check out CMU DB group at https://db.cs.cmu.edu/ https://db.cs.cmu.edu/
- andydb 8y agoThis is not a book, but we did write up some documentation for developers that gives a nice overview of how the optimizer works: https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt/doc.go https://github.com/cockroachdb/cockroach/blob/master/pkg/sql... Might be worth a read if you're interested in implementation techniques.
- kunthar 8y agois still no avail to use sqlalchemy within your cockroach? ok go ahead with plans.
- manigandham 8y agoCockroachDB uses the PostgreSQL protocol so you can reuse any Postgres drivers and tooling to connect. They have an entire section in their documentation for Python and SQLAlchemy: https://www.cockroachlabs.com/docs/stable/build-a-python-app-with-cockroachdb-sqlalchemy.html https://www.cockroachlabs.com/docs/stable/build-a-python-app...
- poooogles 8y agosqlalchemy has a cockroach dialect.
- DreamSpinner 8y agoPeople generally interested in this topic might also find the CMU Intro to DB Systems youtube of interest. Note that it's an introduction to building database systems (not just using them). https://www.youtube.com/playlist?list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7 https://www.youtube.com/playlist?list=PLSE8ODhjZXja3hgmuwhf8...
- altitudinous 8y agoAh, my past life and knowledge developing Oracle systems comes flooding back. 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.
- radiowave 8y agoExcellent write-up. Thanks. 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.)
- andydb 8y agoWe've talked about ideas along those lines. However, rather than altering the plan mid-query, we'd be more likely to have some kind of feedback mechanism that corrects estimates for the benefit of future plans. Another commenter posted an interesting paper that's related to your question: https://www.microsoft.com/en-us/research/uploads/prod/2018/07/p1123-ding.pdf https://www.microsoft.com/en-us/research/uploads/prod/2018/0...
- radiowave 8y agoThanks, I'll check that out.
- deleted 8y ago[deleted]
- georgewfraser 8y agoIs the cost based planner relevant to OLTP-style queries, where everything is an indexed lookup, or only to OLAP-style queries that involve scans?
- manigandham 8y agoSure, there are plenty of OLTP queries involving joins and complex queries that can have severe performance impacts from bad query plans.
- georgewfraser 8y agoI’m struggling to think of an example of an OLTP query where simple heuristics don’t work but I’m not an expert, can you give an example?
- andydb 8y agoSELECT * FROM a, b WHERE a.x = b.x AND a.y='foo' AND b.z='bar' The best plan for this simple query depends on the selectivity of the predicates. For example, if 20k rows have a.y='foo', but only 10 rows have b.z='bar', then it's best to scan a b.z index, then lookup matching rows in a. But if the #rows is reversed, then it's better to scan an a.y index and lookup in b. This is a simplified example, but we do see queries along these lines in real OLTP workloads. You're correct that for many OLTP workload queries, simple heuristics are sufficient. However, even if that's true for 90% of queries, it's the last 10% that gets you. We've seen customers with 10 queries in their workload, where 9 work well but the last 1 gets a bad plan that is 10x slower than it could/should be. Maybe they can rewrite it, or maybe they don't have sufficient knowledge to do so. Or perhaps they're using an ORM and don't have control over the queries it's sending to the DB. In addition, many mostly-OLTP workloads contain a few OLAP reporting queries in the mix. Developers don't expect their OLTP database to perform like a dedicated OLAP data warehouse DB, but they also expect it not to fall over when it gets a more complex query.
- georgewfraser 8y ago
- cy6erlion 8y agoThis 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.
- andydb 8y agoI think you're right; I'm a chess player, and working on the optimizer does hit some of the same neural pathways.
- millrawr 8y ago> 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 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. ;) 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. [1]: http://pi3.informatik.uni-mannheim.de/~moer/querycompiler.pdf http://pi3.informatik.uni-mannheim.de/~moer/querycompiler.pd...