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

41–50 of 59 posts

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

#41

Post by flooo »

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.

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

#42

Post by Someone »

aeyes wrote: post #35
devmunchies wrote: post #27

Earlier quoted context omitted.

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

> You don’t just design a good table schema independently and start querying it This is only true for trivial problems, in the real world you are going to have tradeoffs. You can't design a schema for transactional and analytical workload at the same time, yet every type of business needs some sort of analytics on their data. The great thing about SQL is that you don't exactly need to know what your future queries ar…

Yes, you don’t exactly need to know what queries will look like, but I don’t think the GP claimed that.

You need to have a fairly detailed knowledge, though. How are you going to make educated trade-offs if you don’t know what kind of queries will be made, how often, and how important it is they run fast?

That’s why, in evolving programs, the database evolves, too, even if the table content stays 100% the same. Moving some tables to faster storage, splitting them horizontally or vertically, adding or removing indices, compressing or no longer compressing fields, updating statistics more frequently, etc.

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

#43

Post by ghusbands »

petergeoghegan wrote: post #30
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…

> 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 queries, as with SQL.

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

#44

Post by tornato7 »

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…

One big reason I appreciate Couchbase is it's USE INDEX functionality

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

#45

Post by random_savv »

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…

I think the parent's point might have been: SQL tried with mixed success. What makes the GraphQL compiler different?

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

#46

Post by Someone »

obi1kenobi wrote: post #3
devmunchies wrote: post #2

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

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 different tables to different disks, etc. for performance.

“The GraphQL compiler turns read-only queries written in GraphQL syntax to different query languages” is useful for GraphQL ‘fans’, but I don’t see how that is going to solve that.

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

For SQL, there’s half a century of research on that. This paper is part of it, and indicates that, at this moment in time, effort is better spent on methods for keeping statistics on data up to date than on making cost models more fine grained.

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

#47

Post by tsimionescu »

devmunchies wrote: post #33
jacobsenscott wrote: post #31

Earlier quoted context omitted.

And's and or's are trivial in any good ORM. There are valid reasons to not want to use an ORM, but they are more around the the object/relational impedance mismatch, coupling table design to the domain model, etc. But the alternative to an ORM is not opaque blobs if SQL hard coded into the app all over. How do you handle SQL injection attacks for example? What if you add/rename/drop a column? Do you just grep you cod…

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…

In the end, if you're writing in a non-relational language, using a relational database, and processing/using the DB responses in any way other than just returning them to the user, then you will have an ORM layer/library somewhere. Whether you should be using an off-the-shelf one or not is a different question, but you can't really escape the need to Map between your Object and Relational models (substitute Object for Datatype or Struct if you prefer).

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

#48

Post by sradman »

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

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

#49

Post by obi1kenobi »

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…

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

Microsoft SQL Server-flavored compiled SQL output: 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.

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

#50

Post by darksaints »

obi1kenobi wrote: post #49
ghusbands wrote: post #43

Earlier quoted context omitted.

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…

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?
Post reply on HN