Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

vldb.org

Post reply on HN
Print view View original

51–59 of 59 posts

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

#51

Post by obi1kenobi »

darksaints wrote: post #50
obi1kenobi wrote: post #49

Earlier quoted context omitted.

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 q…

If you know all of the quirks of the various databases, why aren't you hacking on their optimizers? Why write a compiler that knows what's slow and what's not when you can just fix what's slow?

It's an "and" rather than an "either-or" :)

When the database is open-source, and I spot something that's broken that I know how to fix, I try to fix it. Here's a fix for a severe database query planner correctness bug I contributed to an open-source database called OrientDB: https://github.com/orientechnologies/orientdb/pull/7015

Unfortunately, Microsoft SQL Server, Oracle, and many other databases are not open-source, and I can't hack on their query planners. And even if they were, SQL is an absolutely massive language (the complete spec is 100,000+ pages). The GraphQL compiler query language is tiny in comparison, the spec is maybe 10 pages: https://graphql-compiler.readthedocs.io/en/latest/language_s...

It's a lot easier to intelligently map a small language to a big one than it is to optimize the big language outright.

In a sense, SQL is just not designed to be easy to optimize — it's too broad, and there are too many equivalent-ish ways of doing the same thing. This is why even after incredibly smart people cumulatively spent engineer-millennia on the query execution and optimization systems in SQL databases, we still keep having issues and there are still plenty of areas for improvement.

More info and more concrete examples of "why not just write SQL" in my upcoming blog post!

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

#52

Post by obi1kenobi »

Someone wrote: post #46
obi1kenobi wrote: post #3

Earlier quoted context omitted.

I wrote a thread on this on Twitter: 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 proje…

It’s a leaky abstraction, yes. In the ideal world, SQL query planners always would find the optimal plan in zero seconds and DDL would allow you to express non-functional requirements for various kinds of queries (“retrieving this record by ID should take at most 1ms”, “looking up related records in that table by order number should…”), but the world isn’t ideal. We have to manually create indices, split tables, move…

> Designing a user friendly query language for relational data isn’t the hard part. Executing such queries efficiently is.

I couldn't agree more with this part :)

To be clear, GraphQL compiler isn't trying to "solve" SQL itself, just merely the fact that by the time all the table splitting, sharding across disks and machines, and similar required maintenance operations are done, your SQL query has grown impractically complex and entirely unreasonable to write. At sufficient scale, and with sufficient additional non-SQL databases in play, writing adequate queries becomes wildly impractical.

In the GraphQL compiler world, all your databases (SQL and non-SQL) are represented in one unified schema against which you write database-agnostic queries, and GraphQL compiler handles the nitty-gritty details of "which query runs where." GraphQL compiler is not a toy project I build for fun — it's a core piece of data infrastructure that Kensho (company where I work) has been happily using in production for over 3 years now.

I'm writing a blog post about exactly this, and I hope to publish it very soon! Follow me on Twitter if you'd like to see it when it comes out.

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

#53

Post by coolgeek »

ghusbands wrote: post #43
petergeoghegan wrote: post #30

Earlier quoted context omitted.

> 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?

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 user you're replying to presumably understands a bit about the cited inconveniences, as well as SQL, in general

> user: petergeoghegan > about: PostgreSQL major contributor, committer.

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

#54

Post by petergeoghegan »

obi1kenobi wrote: post #51
darksaints wrote: post #50

Earlier quoted context omitted.

If you know all of the quirks of the various databases, why aren't you hacking on their optimizers? Why write a compiler that knows what's slow and what's not when you can just fix what's slow?

It's an "and" rather than an "either-or" :) When the database is open-source, and I spot something that's broken that I know how to fix, I try to fix it. Here's a fix for a severe database query planner correctness bug I contributed to an open-source database called OrientDB: https://github.com/orientechnologies/orientdb/pull/7015 Unfortunately, Microsoft SQL Server, Oracle, and many other databases are not open-sour…

> In a sense, SQL is just not designed to be easy to optimize — it's too broad, and there are too many equivalent-ish ways of doing the same thing. This is why even after incredibly smart people cumulatively spent engineer-millennia on the query execution and optimization systems in SQL databases, we still keep having issues and there are still plenty of areas for improvement.

The main reason is the inherent difficulty of cardinality estimation, as the paper says.

Not every optimization is worth having. There is typically a distributed cost, paid in extra planner cycles for queries that don't benefit from the optimization. This is one of the main reasons why it's hard to contribute new optimizations to the Postgres planner. Naturally, it's possible that a marginal optimization will be incredibly important to one particular query or user. It's a value judgement in each case.

Frankly, I find the suggestion that SQL is not designed to be easy to optimize baffling.

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

#55

Post by devmunchies »

grey-area wrote: post #36
devmunchies wrote: post #33

Earlier quoted context omitted.

Why would we have table references all over the app? We still use centralized models, just not ORMs. Have a class representing a table and methods where you hit the database and map the response to an instance of the class. It’s nice in a typed language when I map what the query will return and the compiler enforces it. But not all my queries map to a class, but it’s not a big mess since we only use statically typed…

Ah ok, so you wrote your own mapping of object relations.

yes. mapping is the trivial part. The query optimization is the more important part IMO so I like doing it manually.

I guess my problem isn't with ORM's, its with ORM SQL generation.

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

#56

Post by obi1kenobi »

petergeoghegan wrote: post #54
obi1kenobi wrote: post #51

Earlier quoted context omitted.

It's an "and" rather than an "either-or" :) When the database is open-source, and I spot something that's broken that I know how to fix, I try to fix it. Here's a fix for a severe database query planner correctness bug I contributed to an open-source database called OrientDB: https://github.com/orientechnologies/orientdb/pull/7015 Unfortunately, Microsoft SQL Server, Oracle, and many other databases are not open-sour…

> In a sense, SQL is just not designed to be easy to optimize — it's too broad, and there are too many equivalent-ish ways of doing the same thing. This is why even after incredibly smart people cumulatively spent engineer-millennia on the query execution and optimization systems in SQL databases, we still keep having issues and there are still plenty of areas for improvement. The main reason is the inherent difficul…

I think we agree more than may seem apparent at first glance. In a sense, you are also making the same point I was trying and probably failed to make. Please bear with me as I give it another shot.

The difficulty of cardinality estimation is a function of the expressiveness of the language. Imagine a new query language, SQL2, that only has the SELECT and FROM keywords -- no WHERE, no JOIN, nothing else. Cardinality estimation in SQL2 is trivial: just store the counts for each table, and you can estimate everything trivially. Optimal query plans are trivial by extension as well.

Now let's add the WHERE keyword and a few operators to this SQL2. Cardinality estimation and good query planning got much harder now! For example, if the WHERE predicate touches two columns, we need to know about correlations between the two columns, or we might make incorrect estimates and therefore get worse plans. And since the plan space got bigger, we spend more cycles on planning. If we continue to add more features to SQL2 to bring it to parity with SQL proper, all these problems get harder as we go.

The language semantics behind GraphQL compiler aim to get sufficient expressiveness for many (hopefully, most) use cases, while limiting the scope so that the problems of cardinality estimation and good planning don't become too hard to solve effectively. In comparison, SQL is significantly more expressive, and as a result also much more difficult to execute and optimize.

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

#57

Post by grey-area »

devmunchies wrote: post #55
grey-area wrote: post #36

Earlier quoted context omitted.

Ah ok, so you wrote your own mapping of object relations.

yes. mapping is the trivial part. The query optimization is the more important part IMO so I like doing it manually. I guess my problem isn't with ORM's, its with ORM SQL generation.

ORMs are just a tool, and they really don't preclude query optimisation.

All the ones I've used or written allow bypassing selects, joins or an entire query and manually translating results, so they don't have to get in the way when optimisation really matters, but the vast majority of the time IME in most apps that just isn't necessary so I'll take the reduced friction of a query builder that automates the basics as long as it allows bypassing it when required.

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

#58

Post by SigmundA »

ninkendo wrote: post #12
SigmundA wrote: post #9

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 tha…

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.

The query is slower otherwise I would not even notice, I don't care which index it uses if its fast.

It's not just about index usage, its also which type of join (loop, hash or merge) and join order.

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

#59

Post by abernard1 »

petergeoghegan wrote: post #32
abernard1 wrote: post #4

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?

Most of that stuff depends on explicit CREATE STATISTICS commands being run in order to work around column correlations and stuff like that. The general assumption of independence among columns/attributes is pretty universal (as the paper actually says). One of the most useful areas for future improvement is making plans more robust against misestimations during execution, for example by using techniques like role-re…

> The general assumption of independence among columns/attributes is pretty universal (as the paper actually says).

So, the paper definitely talks about how independent column statistics are a problem with big tables in the default stats configuration.

...But the option of creating correlated, non-independent column statistics did not exist in PG until after this paper. Which was my point.

In my experience, flat out increasing statistics sample rates fixes 80%+ of the problems in this paper, with basically no downsides. (You can push that computation to downtime when no-one cares.)

Post reply on HN