Hacker News Reader

Comment by allan_s | Hacker News Reader

Maybe a very newbie question but I've always been wondering:

As query optimizer can't explore the whole possibility tree because of time constraint. Would it be possible theoretically (and if so, has any RDBMS implemented it) to do like for prepare statement "tell the optimizer to take its time to give the best optimized code it can" and even, let's be crazy crafting some JIT-ish code heavily optimized just for that one request.

I'm certainly missing a lot of things, but it would certainly make sense for webservices where you have very limited set of "critical" queries that you may want to tell your RDBMS to optimize the best it can regarding current set of data at service startup.

View on HN

To do this, you would have to prepare a plan once and then use it for many queries. The problem with that is that you can't make use of query-specific information when making the plan, and that can be crucial to picking the right plan.

For example, if you have a query like 'select * from products where category = ?', then you basically just have to choose between a table scan and an index lookup. Which is best will depend on how selective the predicate is: if the category in question only covers one in a million products, an index lookup is probably be faster, but if it covers a quarter of them, then a table scan will probably be faster.

If you know from statistics that no category covers more than a small fraction of products, then sure, prepare an index lookup plan for all queries, and vice versa if you know that all categories cover a substantial fraction of all products. But if you have a spread, with some categories being big and some small, then you are best off leaving the selection of the plan to runtime.

It's much the same situation as with ahead-of-time vs just-in-time compilation, but with a bigger penalty for picking the wrong plan, and a smaller ratio of time spent planning to time spent executing, both of which push towards deferring the decision.

That said, perhaps a good strategy would be to do what JIT compilers can do with dynamic deoptimisation: pick a plan that looks good, but guard it with assertions about the things which vary at runtime. So, with the example above, if your categories are mostly small, prepare a plan which uses an index, but guard it with a check that the category is in fact small. If a query comes along for a big category, ignore the prepared plan and make a new one from scratch. Then track statistics about the hit rates on the guard conditions, and if it looks like different assumptions would lead to a more useful plan, switch to those. You could even have multiple plans for different conditions.

As for crazily crafting some JIT-ish code heavily optimized just for that one request, people are already working on that (the slides are in Russian, but the abstract is still interesting!):

https://pgconf.ru/en/2016/89652

There's been discussion of such a feature but AFAIK it's not implemented.

If you consider a data warehousing situation where queries may run for multiple minutes (or longer!) adding a second of additional processing to come up with a better plan can be well worth it. The reverse situation is an OLTP plan where the query itself will execute in 1ms; additional planning time is pointless.

A more complicated (though if you ask me wayyy cooler) approach is to spend X time units finding a decent plan, start executing the query, and then keep planning in the background. If you come across a much better plan and you're not done yet, switch to that plan instead. The MVCC semantics of Postgres would allow for this as the new plan would see the same data "as of" when the query started. Again this isn't implemented yet but has been tossed around.

Postgres doesn't alott (as far as I know) the planner a maximum amount of time. Rather, it picks the algorithm to use based on the number of joins.

The computational complexity of the default algorithm used by the query optimizer depends on the number of joins, and will explode if the number of joins gets high. Thus, if the number of joins exceeds a certain value (the default is 12), it will switch to use the genetic query optimizer (GEQO) [1], which uses genetic algorithms to randomly search towards an optimal plan. GEQO isn't constrained by time, either, but programmed with a maximum number of generations.

[1] http://www.postgresql.org/docs/9.0/static/geqo.html

Oracle takes this to its logical extreme by allowing pre-queries that sample some of the data, so it can change the query plan on the fly if it's taking too long. It's a very powerful feature, but for many workloads it's not worth it. It's worth noting that better statistics and data sampling are usually more important to producing a great plan than exhaustively exploring, e.g., join order (especially for things like many-to-many joins).

Postgres offers a variety of session-based tunings for their genetic query optimizer. See items such as geqo_effort. Note that postgres caches query plans, so the query planning cost for a well-constructed query will only be paid once(ish).

http://www.postgresql.org/docs/9.2/static/runtime-config-que...

Reply on news.ycombinator.com