Adaptive query optimization

Hi,

Inefficiency of Postgres on some complex queries in most cases is caused
by errors in selectivity estimations.
Postgres doesn't take in account correlation between columns unless you
explicitly create mutlicolumn statistics
(but multicolumn statistic is used only for restriction clauses, not for
join selectivity, where estimation errors are most critical).

Certainly it is possible to collect more statistics and improve
estimation formulas but c'est la vie is that estimation of relation size
after several joins //more looks like an exercise in guesswork. This is
why alternative approach based on adaptive query optimization
seems to be more promising. When we analyze query execution with EXPLAIN
ANALYZE, we can see actual number of rows for each plan node.
We can use this information to adjust clause selectivity and reduce
estimation error.

At PGconf 2017 my former colleague Oleg Ivanov made presentation about
using machine learning for AQO:
https://www.pgcon.org/2017/schedule/events/1086.en.html
Right now this project is available from PostgresPro repository:
https://github.com/postgrespro/aqo

There are several problems with this approach:
1. It requires "learning phase"
2. It saves collected data in Postgres tables, which makes read-only
transaction executing only queries to become read-write transaction,
obtaining XID...
3. It doesn't take in account concrete values of literals used in
clauses, so it is not able to address data skews.
4. Machine learning  can be quite  expensive and seems to be overkill if
we want just to adjust selectivities according to actual number of
affected rows.

I tried to create much simpler version of AQO based on auto_explain
extension.
This extension provide all necessary infrastructure to analyze
statements with long execution time.
I have added two new modes to auto_explain:
1. Auto generation of multicolumn statistics for variables using in
clauses with large estimation error.
2. Direct adjustment of estimated number of rows based on information
collected by EXPLAIN ANALYZE.

As well as in Oleg's implementation, it requires few changes  in
Postgres core: introducing some new hooks for relation size estimation.
But most of functionality is implemented in auto_explain extension.
Attached please find patch to vanilla.
Please read Readme.ms file for more details.

I have tested it on join order benchmark JOB
https://github.com/gregrahn/join-order-benchmark
aqo.svg contains results of applying my and Oleg's versions of AQO to
JOB queries. First result corresponds to the vanilla Postgres, second -
my AQO keeping literal values, third my AQO ignoring literal values
and last one result of Oleg's machine learning (after 10 iterations).

The principle problem with AQO approach is that using provided explain
feedback we are able to adjust selectivities only for one particular plan.
But there may be many other alternative plans, and once we adjust one
plan, optimizer most likely choose some other plan which actually can be
ever worser than
original plan. Certainly if we continue learning, then sooner or later
we will know real selectivities for all possible clauses. But number of
possible plans can be very
large for queries with many joins (factorial), so many iterations may be
required. What is worser some intermediate bad plans can take huge
amount of time.
Particularly sixth iteration of Oleg's AQO on JOB queries set takes
about two hours (instead of original 10 minutes!).
Such thing doesn't happen with my AQO, but it seems to be just matter of
luck.

Any comments and feed back are welcome.

--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company