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