Re: Adaptive query optimization

I don't think "learning phase" is an issue, in fact I think that's
something we need to do - it ensures we have enough data to make good
decisions.

What is wrong with learning phase is that it requires some DBA assistance: somebody should determine when to start learning,
provide relevant workload and determine when learning is finished.
One of the most recent trends in DBMSes is autonomous databases with zero administration effort.
It is especially important for clouds. And of one the main advantages of AQO is that it allows to optimize queries without human interaction.

But unfortunately I really do not know how to avoid learning phase, especially if we what to run queries at replica.

2. It saves collected data in Postgres tables, which makes read-only transaction executing only queries to become read-write transaction, obtaining XID...

Yeah, that's an issue because it makes it useless on standbys etc. I
think it'd be enough to do something similar to pg_stat_statements, i.e.
store it in memory and flush it to disk once in a while.

Thus is why my AQO implementation is storing data in file.

3. It doesn't take in account concrete values of literals used in clauses, so it is not able to address data skews.

Yep. I don't think it's necessarily an issue with all approaches to
adaptive optimization, though. But I agree we should detect both
systemic estimation issues, and misestimates for particular parameter
values. I think that's doable.

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 think that depends - some machine learning approaches are not that
bad. But I think there's a more serious issue - explainability. We need
a solution where we can explain/justify why it makes some decisions. I
really don't want a black box that produces numbers that you just need
to take at face value.

The good thing is that the simpler the method, the less expensive and
more explainable it is.

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.

Interesting! I probably wouldn't consider this part of adaptive query
optimization, but it probably makes sense to make it part of this. I
wonder if we might improve this to also suggest "missing" indexes?

I think that it should be nest step of adaptive query optimization:
- autogeneration of indexes
- auto adjustment of optimizer cost parameters (cpu cost, random/sequential page access cost,...)

There is already extension hypothetical index https://github.com/HypoPG/hypopg
which can be used to estimate effect of introducing new indexes.

Right. But I think I might have an idea how to address (some of) this.

As I already mentioned, I was experimenting with something similar,
maybe two or three years ago (I remember chatting about it with Teodor
at pgcon last week). I was facing the same issues, and my approach was
based on hooks too.

But my idea was to not to track stats for a plan as a whole, but instead
decompose it into individual nodes, categoried into three basic groups -
scans, joins and aggregations. And then use this extracted information
to other plans, with "matching" nodes.

For example, let's consider a simple "single-scan" query

   SELECT * FROM t1 WHERE a = ? AND b = ? AND c < ?;

Now, if you execute this enought times (say, 100x or 1000x), tracking
the estimates and actual row counts, you may then compute the average
misestimate (maybe a geometric mean would be more appropriate here?):

   AVG(actual/estimate)

Certainly stats should be collected for each plan node, not for the whole plan.
And it is done now in Oleg's and my implementation.
Oleg is using gradient descent method. I first tried to calculate average, but then find out that building something like "histogram",
where bin is determined as log10 of estimated number of rows.

and if this is significantly different from 1.0, then we can say there's
a systemic misestimate, and we can use this as a correction coefficient
when computing the scan estimate. (And we need to be careful about
collection new data, because the estimates will include this correction.
But that can be done by tracking "epoch" of the plan.)

Now, if someone uses this same scan in a join, like for example

   SELECT * FROM t1 JOIN t2 ON (t1.id = t2.id)
    WHERE (t1.a = ? AND t1.b = ? AND t1.c < ?)
      AND (t2.x = ? AND t2.y = ?)

then we can still apply the same correction to the t1 scan (I think).
But then we can also collect data for the t1-t2 join, and compute a
correction coefficient in a similar way. It requires a bit of care
because we need to compensate for misestimates of inputs, but I think
that's doable.

Of course, all this is rather speculative, and I never got to anything
beyond a very simple PoC. So I hope it makes at least some sense.

As far as I know Oleg's AQO is now used by Amason.
So it is something more than just PoC. But certainly there are still many problems
and my experiments with JOB benchmark shown that there are still a lot of things to improve.