8 ms·

How good are query optimizers, really? [pdf] (2015)

70 points by guodong 6y ago

devmunchies 6y ago
One of the most important things I learned with databases was to run each of my queries using EXPLAIN (EXPLAIN QUERY PLAN in sqlite) and seeing which indexes are being used, if any. One of the reasons I don't like ORMs is that I'm not able to see the underlining query and truly optimize a service. That may be fine for a new service where performance isn't crucial, but once it needs to scale, you need to put on your engineering hat, get your hands dirty, and optimize queries. You'll find you need to re-write queries so that there isn't complex nesting in the WHERE statement and flatten your logic so that the SQL optimizer can use your indexes. You may need to put SELECT statements within SELECT statements, where the innermost SELECT uses indexes and the outer queries are using the result of the inner query, which is smaller than the whole table.
- obi1kenobi 6y ago
  I wrote a thread on this on Twitter: https://twitter.com/PredragGruevski/status/1263916599062540288?s=20 https://twitter.com/PredragGruevski/status/12639165990625402... I feel that SQL aimed to be Python and became x86 assembly instead. It's no longer a simple "just works" query language the moment you have to worry about predicate flattening, join decomposition, CTEs that introduce optimization barriers, and "IN()" being faster than equivalent "JOINs". As a result, I started a project that allows you to write read-only database-agnostic queries called GraphQL compiler: https://graphql-compiler.readthedocs.io/ https://graphql-compiler.readthedocs.io/ https://github.com/kensho-technologies/graphql-compiler https://github.com/kensho-technologies/graphql-compiler The core idea of the project is to get us the convenience of specifying the "what question I want answered," but without the inconvenience of "how is the answer computed / with which specific set of queries / where did the data come from?" -- unless you want to peek under the hood, of course. All the visibility into the nitty-gritty details available on demand, but without the tedium of having to hand-optimize queries and know all the "magic" ways in which queries get faster or slower for each individual kind of database.
  - petergeoghegan 6y ago
    > The core idea of the project is to get us the convenience of specifying the "what question I want answered," but without the inconvenience of "how is the answer computed / with which specific set of queries / where did the data come from?" So...exactly like SQL, then?
    - ghusbands 6y ago
      The post you're replying to directly addresses that. When you write SQL: > It's no longer a simple "just works" query language the moment you have to worry about predicate flattening, join decomposition, CTEs that introduce optimization barriers, and "IN()" being faster than equivalent "JOINs". Though it doesn't seem to address how to optimize things using the GraphQL compiler, when there's a need, without massaging the queries, as with SQL.
      - random_savv 6y ago
        I think the parent's point might have been: SQL tried with mixed success. What makes the GraphQL compiler different?
      - obi1kenobi 6y ago
        Just like how GCC and Clang/LLVM know all the quirks of various CPUs and can optimize accordingly, GraphQL compiler aims to know the quirks of various databases (down to individual database versions: e.g., in Postgres 12 certain kinds of CTEs are no longer an optimization barrier) and optimize accordingly. This is clearly a massive challenge, but one made easier by the fact that GraphQL compiler queries (unlike SQL queries) operate at a much higher level of abstraction. In SQL, you write "here's a CTE, now recursively JOIN X.foo to Y.bar" where X and Y could be just about anything, even something where a recursive JOIN is nonsensical. If you want to put a WHERE clause, you have to decide whether it goes in the recursive CTE itself, in a separate CTE that is ordered before the recursive CTE, or if you want to wrap the recursive CTE into another SELECT and put the WHERE there. The correct answer varies from database to database, and as a function of the size, layout, and index coverage of your data. In GraphQL compiler, your queries are much more declarative in comparison: your query would say "find all subgraphs where vertex A's field 'foo' has value 123, and where A has a recursively-expanded edge (i.e. 0+ hops along that edge) to a vertex with field 'bar' with value 456". It's then the compiler's job to figure out which of the many equivalent SQL statements (or other db language queries, if you aren't using SQL) is going to be the best way to compute the result you asked for. Here's an example from our test suite: input query: https://github.com/kensho-technologies/graphql-compiler/blob/main/graphql_compiler/tests/test_input_data.py#L941 https://github.com/kensho-technologies/graphql-compiler/blob... Microsoft SQL Server-flavored compiled SQL output: https://github.com/kensho-technologies/graphql-compiler/blob/main/graphql_compiler/tests/test_compiler.py#L2449 https://github.com/kensho-technologies/graphql-compiler/blob... I'm writing a blog post about this with more detail, follow me on Twitter if you'd like to see it when it comes out.
- vsareto 6y ago
  >One of the reasons I don't like ORMs is that I'm not able to see the underlining query and truly optimize a service. I thought most of them had some feature where you could dump the query before it gets sent to the DB. Stuff like this: https://stackoverflow.com/questions/1412863/how-do-i-view-the-sql-generated-by-the-entity-framework https://stackoverflow.com/questions/1412863/how-do-i-view-th...
  - devmunchies 6y ago
    yeah but if the generated SQL doesn't look how you want it, now you gotta optimize it using the ORM's language and not SQL. Tweak the ORM, see the generated SQL, tweak again... etc. If you're looking at the generated SQL I would rather just use the SQL directly in my code. There's probably features in ORMs where you can write raw SQL and tell it how to map the result to an object but I haven't used an ORM in a while.
    - jacobsenscott 6y ago
      Generally it is the table design, and not the ORM that is the constraint on how you can write your queries. A good ORM lets you customize any part of the query, or even just write plain sql. Most performance problems that pop up as a product matures aren't because the ORM generates "slow" queries, it is because the table design didn't scale. That can't be fixed by writing plain sql.
      - devmunchies 6y ago
        This doesn’t really make sense to me. You don’t just design a good table schema independently and start querying it. The design isn’t a step that comes before the queries. The queries and the design are created in tandem. You design the schemas with the indices and queries in mind, write queries that use your indices. A good design doesn’t magically scale. It’s based on how you set up your indices and write SQL. A good table design is only good BECAUSE it enables efficient predicate use on the SQL queries. You can’t just query any column willy nilly, you have to plan it. That’s why I like thinking in SQL with the table definition on-hand. Example, if I write “SELECT * WHERE x OR y” and “y” isn’t indexed, then this will do a full table scan. Not ok. I need to plan my queries so it does something like “WHERE x OR (y AND z)” where “z” is indexed so it filters by “z” and then “y”. I don’t want to have to try and figure out how to get the ORM to produce that.
- ris 6y ago
  > One of the reasons I don't like ORMs is that I'm not able to see the underlining query and truly optimize a service. The vast majority of your queries will not fall into the category of "bottlenecks that need to be optimized" though, and you (and your probably more inexperienced team) will benefit massively from the less error-prone & more extensible nature of ORMs (I never again want to have to deal with an attempt at SQL code reuse that has grown into a string-formatted, quadruple-manifestation, triple-escaped nightmare) A good ORM will also ease the transition into more manual SQL too, so that you can still retain the benefits of e.g. uniform abstract objects app-side.
- lmm 6y ago
  This kind of thing is the reasons why I do like ORMs. Even if you can see the SQL, that doesn't mean you can tell what it's doing: you don't know what indices will be used or not used, you don't know why the query planner will do things one way or another, you're not actually "close to the metal" at all. So might as well have the convenience of an ORM; sure, you'll have to do some fiddly profiling as and when you have performance problems, but even if you were using hand-written SQL you'd still have to do that.
  - devmunchies 6y ago
    > Even if you can see the SQL, that doesn't mean you can tell what it's doing You can. I mentioned EXPLAIN in my comment. And the query planner isn’t a black box. Once you read the documentation on how the order of operations is determined by the engine, you can start to be thinking on the same plane as the query engine. You can infer how a query will use indices and the way the WHERE clause will be used. Admittedly it’s not as easy as using an ORM, but if you’re a SQL expert then you can make queries much more optimized. You’ll never internalize how a SQL interpreter reads your queries unless you do it. I’m talking about huge tables that are hit many times a second, where you need to start thinking like a Formula One team, being creative with queries to shave off hundreds of milliseconds.
    - lmm 6y ago
      > And the query planner isn’t a black box. Once you read the documentation on how the order of operations is determined by the engine, you can start to be thinking on the same plane as the query engine. You can infer how a query will use indices and the way the WHERE clause will be used. If you're willing to put that kind of time and effort in, you should have no trouble understanding how your ORM generates queries - IME they tend to be far clearer, better documented, and more introspectable than database query planners.
      - devmunchies 6y ago
        It’s not that I’m willing to put in the effort, it’s that the scale I operate at requires it. I would rather become highly proficient at SQL and use it universally with any server language than become an expert at a specific ORM. But I don’t see how one could become an expert at writing ORM queries without knowing the underlining SQL, which means you’re putting in the time to master two languages. I may be just be an outlier, and that’s fine. I like geeking out over SQL optimization.
- rst 6y ago
  That depends on the ORM -- ActiveRecord has a ".explain" method on the proxy objects for its query builder which displays the SQL, and the query plan (displayed in db-specific format).
  - why-el 6y ago
    Note that AR's `explain` actually runs the query (effectively an explain analyze). This might or might not matter depends on what you are trying to achieve.
abernard1 6y ago
This paper is from 2015 it appears. Can anyone comment on how relevant this is with the enhanced statistics types in Postgres 10, 11, 12?
- jzelinskie 6y ago
  I can't comment on your question, but thank you for finding the year this paper was written. Having read many older papers, it's sometimes like solving a murder mystery figuring out what year a paper was written. The year a paper is written is vital for understanding social context of the research being presented in addition to any context cited in the paper.
  - nighthawk454 6y ago
    Agreed, especially in fast-changing fields or after recent breakthroughs. One trick I use is look at the References and find the approx. max year cited. Generally the same or pretty close to the year of the paper.
  - Ar-Curunir 6y ago
    Isn’t it usually a matter of just googling the title?
  - jasonwatkinspdx 6y ago
    This has long been a pet peeve of mine.
  - ergl 6y ago
    With CS conference papers, it's quite easy to see the date on the bottom-left of the first page. You see the copyright year, conference name, etc
- __s 6y ago
  Here's a neat extension that tries to use genetic algorithms to learn better planning for one's queries, includes slides which cite this & have TPC numbers https://www.pgcon.org/2017/schedule/events/1086.en.html https://www.pgcon.org/2017/schedule/events/1086.en.html
SigmundA 6y ago
I have really tried to let the optimizer do its thing and generally it does and everything's ok. Until its not and then I want hints to save my ass, and they are not hints, I want want to TELL the f'ing computer what to do because I know better than the optimizer period. So surprised to find out PG doesn't support hints don't think I will ever be able to move anything serious until it does, just not going to take that kind of risk. I have played the whole rewrite query to try and convince the optimizer what to do with barrier tricks, no thanks, give me some hints and I will tell it exactly what to do when thanks.
- ninkendo 6y ago
  Is the query actually slower, or is it just not using an index you want it to use? Often times PG won’t bother with an index for a variety of reasons (sequential scans can be legitimately faster in some scenarios), especially when the number of rows is small.
  - stubish 6y ago
    The cool thing about hints is you can quickly drop in a hint to confirm your suspicions and narrow down the problem, rather than trying to do this sort of diagnosis in a vacuum. But because some people use hints for evil, nobody is allowed to use them.
    - why-el 6y ago
      You can also disable seq_scan and force pg to consider indexes, usually that's enough.
      - iracic 6y ago
        Access method is just part of the story. Same index may be accessed in different ways, you might also want to combine them. Sometimes you may change table join order to see how it estimates (or executes). Usually there are two parts 1) cost and reasoning for some estimation 2) how it executes (timings, resource usage, locks/contention)
deleted 6y ago
[deleted]
jzoch 6y ago
The simplified cost model they use was really surprising. 34% better than the complex pg one not only sounds great (incoming "simple is better" replies below) but is really nice to hear. Hopefully postgres has or will consider changing the default cost model to a simpler, more modern function that takes the current landscape into account.
- petergeoghegan 6y ago
  That may be true, but that doesn't seem like the important takeaway to me. The important takeaway is "In contrast to cardinality estimation, the contribution of the cost model to the overall query performance is limited". Actually, the paper itself says "This improvement [the 34% one you mention] is not insignificant, but on the other hand, it is dwarfed by improvement in query runtime observed when we replace estimated cardinalities with the real ones". Optimizers are weird.
  - jzoch 6y ago
    Oh definitely agree. Mainly I find the cost model interesting because it’s so simple and contained. Cardinality estimation is a hard problem and requires real expertise. But the easy wins you get by just throwing out something based on old assumptions like the cost model is fun!
flooo 6y ago
I'm surprised there is no mention of Postgres' Genetic Query Optimizer (GEQO) here. It kicks in when there is a large number of joins and reduces query planning time at the cost of query execution time. Another post in this thread mentions adaptive query planning and mistakenly imply that the GEQO is a module for this. My hands have been itching to look into experimenting on some improvements on the GEQO, specifically by improving the genetic algorithms used. When there are many similar queries, so in the adaptive query planning setting, one could also use reinforcement learning to improve query planning over time.
sradman 6y ago
I like the methodology of the Join Order Benchmark (JOB). The key takeaway is PostgreSQL specific: > ...the most important statistic for join estimation in PostgreSQL is the number of distinct values. These statistics are estimated from a fixed-sized sample, and we have observed severe underestimates for large tables. Live statistics, incrementally updated on DML execution, is a key feature for a good query optimizer. As a zero-administration RDBMS, SQL Anywhere had gained a reputation as a best-of-breed query optimizer [1] a decade ago; I'm curious if this still holds true. In the last decade, the importance of OLAP queries in row stores has diminished due to the superiority of column stores. I'd be interested in a comparison of the Citus query optimizer vs. say Presto. [1] https://www.student.cs.uwaterloo.ca/~cs448/W11/cs448_Paulley_March_2011.pdf https://www.student.cs.uwaterloo.ca/~cs448/W11/cs448_Paulley...

70 points by guodong 6y ago

One of the most important things I learned with databases was to run each of my queries using EXPLAIN (EXPLAIN QUERY PLAN in sqlite) and seeing which indexes are being used, if any. One of the reasons I don't like ORMs is that I'm not able to see the underlining query and truly optimize a service. That may be fine for a new service where performance isn't crucial, but once it needs to scale, you need to put on your engineering hat, get your hands dirty, and optimize queries. You'll find you need to re-write queries so that there isn't complex nesting in the WHERE statement and flatten your logic so that the SQL optimizer can use your indexes. You may need to put SELECT statements within SELECT statements, where the innermost SELECT uses indexes and the outer queries are using the result of the inner query, which is smaller than the whole table.

obi1kenobi 6y ago
I wrote a thread on this on Twitter: https://twitter.com/PredragGruevski/status/1263916599062540288?s=20 https://twitter.com/PredragGruevski/status/12639165990625402... I feel that SQL aimed to be Python and became x86 assembly instead. It's no longer a simple "just works" query language the moment you have to worry about predicate flattening, join decomposition, CTEs that introduce optimization barriers, and "IN()" being faster than equivalent "JOINs". As a result, I started a project that allows you to write read-only database-agnostic queries called GraphQL compiler: https://graphql-compiler.readthedocs.io/ https://graphql-compiler.readthedocs.io/ https://github.com/kensho-technologies/graphql-compiler https://github.com/kensho-technologies/graphql-compiler The core idea of the project is to get us the convenience of specifying the "what question I want answered," but without the inconvenience of "how is the answer computed / with which specific set of queries / where did the data come from?" -- unless you want to peek under the hood, of course. All the visibility into the nitty-gritty details available on demand, but without the tedium of having to hand-optimize queries and know all the "magic" ways in which queries get faster or slower for each individual kind of database.
- petergeoghegan 6y ago
  > The core idea of the project is to get us the convenience of specifying the "what question I want answered," but without the inconvenience of "how is the answer computed / with which specific set of queries / where did the data come from?" So...exactly like SQL, then?
  - ghusbands 6y ago
    The post you're replying to directly addresses that. When you write SQL: > It's no longer a simple "just works" query language the moment you have to worry about predicate flattening, join decomposition, CTEs that introduce optimization barriers, and "IN()" being faster than equivalent "JOINs". Though it doesn't seem to address how to optimize things using the GraphQL compiler, when there's a need, without massaging the queries, as with SQL.
    - random_savv 6y ago
      I think the parent's point might have been: SQL tried with mixed success. What makes the GraphQL compiler different?
    - obi1kenobi 6y ago
      Just like how GCC and Clang/LLVM know all the quirks of various CPUs and can optimize accordingly, GraphQL compiler aims to know the quirks of various databases (down to individual database versions: e.g., in Postgres 12 certain kinds of CTEs are no longer an optimization barrier) and optimize accordingly. This is clearly a massive challenge, but one made easier by the fact that GraphQL compiler queries (unlike SQL queries) operate at a much higher level of abstraction. In SQL, you write "here's a CTE, now recursively JOIN X.foo to Y.bar" where X and Y could be just about anything, even something where a recursive JOIN is nonsensical. If you want to put a WHERE clause, you have to decide whether it goes in the recursive CTE itself, in a separate CTE that is ordered before the recursive CTE, or if you want to wrap the recursive CTE into another SELECT and put the WHERE there. The correct answer varies from database to database, and as a function of the size, layout, and index coverage of your data. In GraphQL compiler, your queries are much more declarative in comparison: your query would say "find all subgraphs where vertex A's field 'foo' has value 123, and where A has a recursively-expanded edge (i.e. 0+ hops along that edge) to a vertex with field 'bar' with value 456". It's then the compiler's job to figure out which of the many equivalent SQL statements (or other db language queries, if you aren't using SQL) is going to be the best way to compute the result you asked for. Here's an example from our test suite: input query: https://github.com/kensho-technologies/graphql-compiler/blob/main/graphql_compiler/tests/test_input_data.py#L941 https://github.com/kensho-technologies/graphql-compiler/blob... Microsoft SQL Server-flavored compiled SQL output: https://github.com/kensho-technologies/graphql-compiler/blob/main/graphql_compiler/tests/test_compiler.py#L2449 https://github.com/kensho-technologies/graphql-compiler/blob... I'm writing a blog post about this with more detail, follow me on Twitter if you'd like to see it when it comes out.
vsareto 6y ago
>One of the reasons I don't like ORMs is that I'm not able to see the underlining query and truly optimize a service. I thought most of them had some feature where you could dump the query before it gets sent to the DB. Stuff like this: https://stackoverflow.com/questions/1412863/how-do-i-view-the-sql-generated-by-the-entity-framework https://stackoverflow.com/questions/1412863/how-do-i-view-th...
- devmunchies 6y ago
  yeah but if the generated SQL doesn't look how you want it, now you gotta optimize it using the ORM's language and not SQL. Tweak the ORM, see the generated SQL, tweak again... etc. If you're looking at the generated SQL I would rather just use the SQL directly in my code. There's probably features in ORMs where you can write raw SQL and tell it how to map the result to an object but I haven't used an ORM in a while.
  - jacobsenscott 6y ago
    Generally it is the table design, and not the ORM that is the constraint on how you can write your queries. A good ORM lets you customize any part of the query, or even just write plain sql. Most performance problems that pop up as a product matures aren't because the ORM generates "slow" queries, it is because the table design didn't scale. That can't be fixed by writing plain sql.
    - devmunchies 6y ago
      This doesn’t really make sense to me. You don’t just design a good table schema independently and start querying it. The design isn’t a step that comes before the queries. The queries and the design are created in tandem. You design the schemas with the indices and queries in mind, write queries that use your indices. A good design doesn’t magically scale. It’s based on how you set up your indices and write SQL. A good table design is only good BECAUSE it enables efficient predicate use on the SQL queries. You can’t just query any column willy nilly, you have to plan it. That’s why I like thinking in SQL with the table definition on-hand. Example, if I write “SELECT * WHERE x OR y” and “y” isn’t indexed, then this will do a full table scan. Not ok. I need to plan my queries so it does something like “WHERE x OR (y AND z)” where “z” is indexed so it filters by “z” and then “y”. I don’t want to have to try and figure out how to get the ORM to produce that.
ris 6y ago
> One of the reasons I don't like ORMs is that I'm not able to see the underlining query and truly optimize a service. The vast majority of your queries will not fall into the category of "bottlenecks that need to be optimized" though, and you (and your probably more inexperienced team) will benefit massively from the less error-prone & more extensible nature of ORMs (I never again want to have to deal with an attempt at SQL code reuse that has grown into a string-formatted, quadruple-manifestation, triple-escaped nightmare) A good ORM will also ease the transition into more manual SQL too, so that you can still retain the benefits of e.g. uniform abstract objects app-side.
lmm 6y ago
This kind of thing is the reasons why I do like ORMs. Even if you can see the SQL, that doesn't mean you can tell what it's doing: you don't know what indices will be used or not used, you don't know why the query planner will do things one way or another, you're not actually "close to the metal" at all. So might as well have the convenience of an ORM; sure, you'll have to do some fiddly profiling as and when you have performance problems, but even if you were using hand-written SQL you'd still have to do that.
- devmunchies 6y ago
  > Even if you can see the SQL, that doesn't mean you can tell what it's doing You can. I mentioned EXPLAIN in my comment. And the query planner isn’t a black box. Once you read the documentation on how the order of operations is determined by the engine, you can start to be thinking on the same plane as the query engine. You can infer how a query will use indices and the way the WHERE clause will be used. Admittedly it’s not as easy as using an ORM, but if you’re a SQL expert then you can make queries much more optimized. You’ll never internalize how a SQL interpreter reads your queries unless you do it. I’m talking about huge tables that are hit many times a second, where you need to start thinking like a Formula One team, being creative with queries to shave off hundreds of milliseconds.
  - lmm 6y ago
    > And the query planner isn’t a black box. Once you read the documentation on how the order of operations is determined by the engine, you can start to be thinking on the same plane as the query engine. You can infer how a query will use indices and the way the WHERE clause will be used. If you're willing to put that kind of time and effort in, you should have no trouble understanding how your ORM generates queries - IME they tend to be far clearer, better documented, and more introspectable than database query planners.
    - devmunchies 6y ago
      It’s not that I’m willing to put in the effort, it’s that the scale I operate at requires it. I would rather become highly proficient at SQL and use it universally with any server language than become an expert at a specific ORM. But I don’t see how one could become an expert at writing ORM queries without knowing the underlining SQL, which means you’re putting in the time to master two languages. I may be just be an outlier, and that’s fine. I like geeking out over SQL optimization.
rst 6y ago
That depends on the ORM -- ActiveRecord has a ".explain" method on the proxy objects for its query builder which displays the SQL, and the query plan (displayed in db-specific format).
- why-el 6y ago
  Note that AR's `explain` actually runs the query (effectively an explain analyze). This might or might not matter depends on what you are trying to achieve.

abernard1 6y ago

This paper is from 2015 it appears. Can anyone comment on how relevant this is with the enhanced statistics types in Postgres 10, 11, 12?

jzelinskie 6y ago
I can't comment on your question, but thank you for finding the year this paper was written. Having read many older papers, it's sometimes like solving a murder mystery figuring out what year a paper was written. The year a paper is written is vital for understanding social context of the research being presented in addition to any context cited in the paper.
- nighthawk454 6y ago
  Agreed, especially in fast-changing fields or after recent breakthroughs. One trick I use is look at the References and find the approx. max year cited. Generally the same or pretty close to the year of the paper.
- Ar-Curunir 6y ago
  Isn’t it usually a matter of just googling the title?
- jasonwatkinspdx 6y ago
  This has long been a pet peeve of mine.
- ergl 6y ago
  With CS conference papers, it's quite easy to see the date on the bottom-left of the first page. You see the copyright year, conference name, etc
__s 6y ago
Here's a neat extension that tries to use genetic algorithms to learn better planning for one's queries, includes slides which cite this & have TPC numbers https://www.pgcon.org/2017/schedule/events/1086.en.html https://www.pgcon.org/2017/schedule/events/1086.en.html

SigmundA 6y ago

I have really tried to let the optimizer do its thing and generally it does and everything's ok. Until its not and then I want hints to save my ass, and they are not hints, I want want to TELL the f'ing computer what to do because I know better than the optimizer period. So surprised to find out PG doesn't support hints don't think I will ever be able to move anything serious until it does, just not going to take that kind of risk. I have played the whole rewrite query to try and convince the optimizer what to do with barrier tricks, no thanks, give me some hints and I will tell it exactly what to do when thanks.

ninkendo 6y ago
Is the query actually slower, or is it just not using an index you want it to use? Often times PG won’t bother with an index for a variety of reasons (sequential scans can be legitimately faster in some scenarios), especially when the number of rows is small.
- stubish 6y ago
  The cool thing about hints is you can quickly drop in a hint to confirm your suspicions and narrow down the problem, rather than trying to do this sort of diagnosis in a vacuum. But because some people use hints for evil, nobody is allowed to use them.
  - why-el 6y ago
    You can also disable seq_scan and force pg to consider indexes, usually that's enough.
    - iracic 6y ago
      Access method is just part of the story. Same index may be accessed in different ways, you might also want to combine them. Sometimes you may change table join order to see how it estimates (or executes). Usually there are two parts 1) cost and reasoning for some estimation 2) how it executes (timings, resource usage, locks/contention)

deleted 6y ago

[deleted]

jzoch 6y ago

The simplified cost model they use was really surprising. 34% better than the complex pg one not only sounds great (incoming "simple is better" replies below) but is really nice to hear. Hopefully postgres has or will consider changing the default cost model to a simpler, more modern function that takes the current landscape into account.

petergeoghegan 6y ago
That may be true, but that doesn't seem like the important takeaway to me. The important takeaway is "In contrast to cardinality estimation, the contribution of the cost model to the overall query performance is limited". Actually, the paper itself says "This improvement [the 34% one you mention] is not insignificant, but on the other hand, it is dwarfed by improvement in query runtime observed when we replace estimated cardinalities with the real ones". Optimizers are weird.
- jzoch 6y ago
  Oh definitely agree. Mainly I find the cost model interesting because it’s so simple and contained. Cardinality estimation is a hard problem and requires real expertise. But the easy wins you get by just throwing out something based on old assumptions like the cost model is fun!

flooo 6y ago

I'm surprised there is no mention of Postgres' Genetic Query Optimizer (GEQO) here. It kicks in when there is a large number of joins and reduces query planning time at the cost of query execution time. Another post in this thread mentions adaptive query planning and mistakenly imply that the GEQO is a module for this. My hands have been itching to look into experimenting on some improvements on the GEQO, specifically by improving the genetic algorithms used. When there are many similar queries, so in the adaptive query planning setting, one could also use reinforcement learning to improve query planning over time.

sradman 6y ago

I like the methodology of the Join Order Benchmark (JOB). The key takeaway is PostgreSQL specific: > ...the most important statistic for join estimation in PostgreSQL is the number of distinct values. These statistics are estimated from a fixed-sized sample, and we have observed severe underestimates for large tables. Live statistics, incrementally updated on DML execution, is a key feature for a good query optimizer. As a zero-administration RDBMS, SQL Anywhere had gained a reputation as a best-of-breed query optimizer [1] a decade ago; I'm curious if this still holds true. In the last decade, the importance of OLAP queries in row stores has diminished due to the superiority of column stores. I'd be interested in a comparison of the Citus query optimizer vs. say Presto. [1] https://www.student.cs.uwaterloo.ca/~cs448/W11/cs448_Paulley_March_2011.pdf https://www.student.cs.uwaterloo.ca/~cs448/W11/cs448_Paulley...