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