[anarazel]

> 1. Add an option to EXPLAIN that will cause PostgreSQL's optimizer to spit out multiple plans it considered, with costs, and with a description of the plan that PostgreSQL can easily parse and fit to a query.

The biggest problem with that approach is that the way query planning works isn't that a 100 different plans are fully built, cost evaluated, and then compared. Instead it's more like a dynamic programming approach where you iteratively build pieces of a query plan from ground up, and then combine those pieces to build the layer one up. Given the space of possible query plans, especially with several relations and indexes on each relation involved, such an approach is required to actually ever finish planning.

> Add a PLAN command that can be applied to a prepared statement and will set its plan. It is an error to submit a plan that does not match the query.

It's not easily, if at all in the generic case!, possible to prove that a specific plan matches a query. You could obviously try to build every possible plan and match against each of those, but that's computationally infeasible (we're talking factorial number of plans, depending on relations here).

So I think such an approach has no chance of working.

What's more realistic is a running queries in a "training" mode. That training mode would, matching on the specific parsetree, store the resulting plans in a table. Before exiting training mode you'd mark all these plans approved (after looking for bad cases obviously). After that preparing a new query still does the original query planning, but by default the query stored in the "approved plans" table would be used. The cost differential and the new plan would then be associated with the currently approved plan. Regularly the DBA (or whoever fulfills that role), checks the potential plans and approves new ones.

Based on a configuration option queries without approved plans would error out, raise a log message, or just work.

Now even that has significant problems because e.g. DDL will have the tendency to "invalidate" all the approved plans. But that's manageable in comparison to being woken up Friday night.

[btilly]

I don't see how my objections are impossible.

On EXPLAIN, if you've passed my example PLANS=3 it would first do the plan in its usual way, and then try optimizing several more times, with some chance of randomly making suboptimal decisions at various decision points. It would keep doing this until it either had enough plans or else was making essentially random decisions and still couldn't find more.

I can see this requiring a significant refactor of existing code, but stochastically exploring "pretty good" plans doesn't require facing the whole tree of possible plans.

The DBA hopefully can recognize the desired plan if it turns up.

As for the PLAN command, I do not see the problem. I can look at the query and the EXPLAIN output, and I can figure out exactly how and where that query's conditions are being incorporated. You might need extra output from EXPLAIN to make it always possible to do in an automated way, but it should be possible.

Put another way, you propose that the database has a way to look at the query and a plan stored in the table and figure out how to execute that plan for that query. What would that table contain that couldn't be represented as a chunk of text supplied with a PLAN command?

[anarazel]

> On EXPLAIN, if you've passed my example PLANS=3 it would first do the plan in its usual way, and then try optimizing several more times, with some chance of randomly making suboptimal decisions at various decision points. It would keep doing this until it either had enough plans or else was making essentially random decisions and still couldn't find more.

You'd not get anything useful by doing that. If you really consider this as a dynamic programming problem, at which place in the 'pyramid' of steps would you choose the worse plan? To quote the source:

        /*
	 * We employ a simple "dynamic programming" algorithm: we first find all
	 * ways to build joins of two jointree items, then all ways to build joins
	 * of three items (from two-item joins and single items), then four-item
	 * joins, and so on until we have considered all ways to join all the
	 * items into one rel.
	 *

If you'd just make some random 'bad' decisions, you'll not have a significant likelihood of finding actually useful good plans.

> As for the PLAN command, I do not see the problem. I can look at the query and the EXPLAIN output, and I can figure out exactly how and where that query's conditions are being incorporated. You might need extra output from EXPLAIN to make it always possible to do in an automated way, but it should be possible.

Good luck. Besides generating all possible plans postgres knows to generate, you very quickly essentially run into something equivalent to the halting problem.

> Put another way, you propose that the database has a way to look at the query and a plan stored in the table and figure out how to execute that plan for that query.

What I'm proposing is matching on the parse tree of the user supplied query. For each query there's exactly one parsetree the postgres parser will generate. We have a way (for the awesome pg_stat_statements module) of building a 'hash' of that parse tree, and thus can build a fairly efficient mapping of parsetrees to additional data. In contrast to that, for plans you can have a humongous number of plans for each user supplied query.

> What would that table contain that couldn't be represented as a chunk of text supplied with a PLAN command?

It would contain a, less ambiguous, version of the user supplied query. Now you could argue that you could add that to the PLAN command for matching purposes - but then we'd need guarantee that you could supply arbitrarily corrupt plan trees to postgres, without being able to cause harm. Something that'd cause significant slowdown during execution.

EDIT: Formatting

[btilly]

You just use the approach used in simulated annealing. You set a threshold for making random decisions, and adjust that probability up and down as you try to optimize. For example you might say that in each step there is a 10% chance of adjusting the COST factor randomly by a factor between 0.2 to 5. If you've got 3 tables, most of the time you will come to the current optimal decision. Most of the rest of the time you will make one suboptimal choice. Run that a few times and you'll should several plans that are suboptimal but not actually horrible. Keep running and playing with the randomness factors until you either have enough plans, or are basically making entirely random choices and can't get enough.

As to the algorithm described in the comment, it is actually able to search through all plans. The dynamic programming bit just means that you don't have to unnecessarily traverse all possible logic paths that a naive recursive algorithm might. But if there is a good plan, it can be discovered.

It is unclear from the comment whether the algorithm can only find plans which involve adding one table at a time. This would not be unreasonable - for example I know that Oracle circa a decade ago did that to avoid having to consider too many query plans on large joins. I have no idea whether that ever got changed.

As to the parse tree, that seems like overkill to me. You have a query. It has a list of tables, and a list of join conditions. A query plan includes tables, indexes, filters, and so on. It could easily be augmented by stating which query condition was applied where.

To validate it you have to see that the lists of tables match, the list of applied conditions match, and each plan step could actually have the effect of doing that condition. If it all ties out, it is a valid plan. The fact that the plan might be crap is something that is explicitly left in the hands of the user - that's the whole point of the feature. But at that point it is clearly valid.

[garyclarke27]

I've always thought that there should be an option to allow the optimiser to try out different alternative plans during slack periods, in the background. It should then compare the performance of these alternatives to the original, then "change it's mind", if it finds a faster plan. It should use statistics to choose which plans to test, i.e. prioritise queries which are often called and which are slow.