Thread: 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 

Hello,
this seems very interesting and make me think about 2 other projets:
- https://github.com/trustly/pg_badplan
- https://github.com/ossc-db/pg_plan_advsr

As I understand all this, there are actually 3 steps:
- compare actual / estimated rows
- suggests some statistics gathering modification
- store optimised plans (or optimized stats) for reuse

I really like the "advisor Idea", permitting to identify where statistics
are wrong 
and how to fix them with ANALYZE command.
Is there a chance that some futur Optimizer  / statistics improvements
make thoses "statistics advices" enough to get good plans (without having to
store live stats 
or optimized plan) ?

Thanks in advance
Regards
PAscal



--
Sent from: http://www.postgresql-archive.org/PostgreSQL-hackers-f1928748.html

Hi Alexander,

Thanks for starting this thread. I've had similar ideas in the past and
even hacked together something (very dirty), so it's great someone else
is interested in this topic too.

On Mon, Jun 10, 2019 at 11:53:02AM +0300, Konstantin Knizhnik wrote:
>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).
>

Yes, that's the current status. I'd say we want to allow using
multicolumn stats to join estimation too, but that's a hard problem.

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

I'd go even further - it's a simple fact we can't have perfect stats
that would give us "sufficiently good" estimates for all common data
distributions and clauses.

Firstly, stats are a merely a simplified representation of the overall
data distribution - which makes them small, but eliminates some details
(which may be quite important for highly non-uniform distributions).

Secondly, we only have a number of generic stats types (MCV, histogram,
...) but that may not be sufficient to "capture" the imporant aspects of
the data distribution.

And finally, we only know how to use those stats for specific types of
clauses (equality, inequality, ...) with very simple expressions. But
that's often not what the users do.

I think adaptive query optimization - in the sense of collecting data
from query executions and and leverating that when planning future
queries - can (hopefully) help with all those challenges. At least in
some cases.

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

Yep, that's roughly the idea. I don't think we need EXPLAIN ANALYZE, it
should be enough to instrument queries to collect row counts on the fly.
But I guess that's mostly what the explain_analyze changes do.

>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"

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.

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

>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? 

>2. Direct adjustment of estimated number of rows based on information 
>collected by EXPLAIN ANALYZE.
>

Yep!

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

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)

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.



regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services 

>>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? 

Shouldn't this be extended to adjust the default_statistics_target
configuration 
variable,  or on a column-by-column basis by setting the per-column
statistics
target with ALTER TABLE ... ALTER COLUMN ... SET STATISTICS ?

Regards
PAscal



--
Sent from: http://www.postgresql-archive.org/PostgreSQL-hackers-f1928748.html

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.

Hello,

On Wed, Jun 12, 2019 at 5:06 PM Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> wrote:
> On 12.06.2019 0:43, Tomas Vondra wrote:
> 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
withouthuman interaction.
 
>
> But unfortunately I really do not know how to avoid learning phase, especially if we what to run queries at replica.
>
Avoiding learning phase in AQO a implementation sounds like an oxymoron. :-)
Perhaps, you meant how we can minimize the effort in learning phase. A
learning phase has its own complications - like
a. deciding the the number of iterations needed to achieve certain
kind of confidence
b. which parameters to tune (are the existing parameters enough?)
c. deciding the cost model
Coming up answers for these things is pretty hard.

>
> 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.
+1

>
> 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 like this part of the implementation. I also agree that this can be
used to come up with good hypothetical index suggestions. But, it
needs some additional algorithms. For example, after analysing a set
of queries, we can come up with a minimal set of indexes that needs to
be created to minimize the total cost. I've not checked the internal
implementation of hypogo. Probably, I should do that.

>
> 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,...)
AFAIK, the need for adjustment of cost parameters are highly dominated
by solving the selectivity estimation errors. But of course, you can
argue with that.

>
> 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.
>
I think maintaining a "histogram" sounds good. I've read a paper
called "Self-tuning Histograms: Building Histograms Without
Looking at Data" which tries to do something similar[1].

>
> 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.
>
That'll be an interesting work. For the above query, we can definitely
calculate the correction coefficient of t1-t2 join given (t1.a = ? AND
t1.b = ? AND t1.c < ?) and
(t2.x = ? AND t2.y = ?) are true. But, I'm not sure how we can
extrapolate that value for t1-t2 join.
>
> 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.
>
Nice.

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.21.921&rep=rep1&type=pdf
-- 
Thanks & Regards,
Kuntal Ghosh
EnterpriseDB: http://www.enterprisedb.com

re: is used at Amazon

Not yet (for RDS, anyway), but I've played with AQO on the Join Order
Benchmark and I was very impressed.  The version I was using required a very
'hands on' user (me, in this case) to participate in the training phase. 
Usability issues aside, AQO worked remarkably well.  I think it has a lot of
potential.



-----
Jim Finnerty, AWS, Amazon Aurora PostgreSQL
--
Sent from: http://www.postgresql-archive.org/PostgreSQL-hackers-f1928748.html

On Wed, Jun 12, 2019 at 06:14:41PM +0530, Kuntal Ghosh wrote:
>Hello,
>
>On Wed, Jun 12, 2019 at 5:06 PM Konstantin Knizhnik
><k.knizhnik@postgrespro.ru> wrote:
>> On 12.06.2019 0:43, Tomas Vondra wrote:
>> 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
withouthuman interaction.
 
>>
>> But unfortunately I really do not know how to avoid learning phase, especially if we what to run queries at
replica.
>>
>Avoiding learning phase in AQO a implementation sounds like an oxymoron. :-)
>Perhaps, you meant how we can minimize the effort in learning phase. A
>learning phase has its own complications - like
>a. deciding the the number of iterations needed to achieve certain
>kind of confidence
>b. which parameters to tune (are the existing parameters enough?)
>c. deciding the cost model
>Coming up answers for these things is pretty hard.
>

I kinda agree with both of you - the learning phase may be a significant
burden. But I don't think we can get rid of it entirely - we simply need
to collect the data to learn from somehow. But we should make it as
unobtrusive and easy to perform as possible.

My plan was to allow continuous learning during regular operation, i.e.
from workload generated by the application. So instead of requiring a
separate learning phase, we'd require a certain number of samples for a
given node, because we start using it to correct estimates.

For example, we might require 1000 samples for a given node (say, scan
with some quals), before we start using it to tweak the estimates. Once
we get the number of estimates, we can continue collecting more data,
and once in a while update the correction. This would require some care,
of course, because we need to know what coefficient was used to compute
the estimate, but that's solvable by having some sort of epoch.

Of course, the question is what number should we use, but overall this
would be a much lower-overhead way to do the learning.

Unfortunately, the learning as implemented in the patch does not allow
this. It pretty much requires dedicated learning phase with generated
workload, in a single process.

But I think that's solvable, assuming we:

1) Store the data in shared memory, instead of a file. Collect data from
all backends, instead of just a single one, etc.

2) Make the decision for individual entries, depending on how many
samples we have for it.

>>
>> 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.
>+1
>
>>
>> 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 like this part of the implementation. I also agree that this can be
>used to come up with good hypothetical index suggestions. But, it
>needs some additional algorithms. For example, after analysing a set
>of queries, we can come up with a minimal set of indexes that needs to
>be created to minimize the total cost. I've not checked the internal
>implementation of hypogo. Probably, I should do that.
>

I suggest we try to solve one issue at a time. I agree advising which
indexes to create is a very interesting (and valuable) thing, but I see
it as an extension of the AQO feature. That is, basic AQO (tweaking row
estimates) can work without it.

>>
>> 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,...)
>AFAIK, the need for adjustment of cost parameters are highly dominated
>by solving the selectivity estimation errors. But of course, you can
>argue with that.

That's probably true. But more to the point, it makes little sense to
tune cost parameters until the row estimates are fairly accurate. So I
think we should focus on getting that part working first, and then maybe
look into tuning cost parameters when this part works well enough.

Furthermore, I wonder how would we even tune cost parameters? I mean, it
seems much harder than correcting row estimates, because the feedback
seems much less reliable. For row estimates we know the actual row
count, but for cost parameters we only have the total query runtime.
Which is somehow correlated, but it seems to rather noisy (e.g., due to
sharing resources with other stuff on the same system), and it's unclear
how to map the duration to individual nodes (which may be using very
different costing formulas).

>
>>
>> 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.
>>
>I think maintaining a "histogram" sounds good. I've read a paper
>called "Self-tuning Histograms: Building Histograms Without
>Looking at Data" which tries to do something similar[1].
>

Yeah. As long as we know how to compute the correction coefficient, it
does not matter how exactly we store the data (array of values,
histogram, something else).

But I think we should keep this simple, so the self-tuning histograms
may be an overkill here.

>>
>> 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.
>>
>That'll be an interesting work. For the above query, we can definitely
>calculate the correction coefficient of t1-t2 join given (t1.a = ? AND
>t1.b = ? AND t1.c < ?) and
>(t2.x = ? AND t2.y = ?) are true. But, I'm not sure how we can
>extrapolate that value for t1-t2 join.

I'm not sure I see the problem? Essentially, we need to know the sizes
of the join inputs, i.e.

    t1 WHERE (t1.a = ? AND t1.b = ? AND t1.c < ?)

    t2 WHERE (t2.x = ? AND t2.y = ?)

(which we know, and we know how to correct the estimate), and then the
selectivity of the join condition. Which we also know.

Obviously, there's a chance those parts (clauses at the scan / join
level) are correlated, which could make this less accurate. But again,
this is about systemic estimation errors - if all queries are affected
by this, then the correction will reflect that.


regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services 

On Thu, Jun 13, 2019 at 5:49 AM Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
>
> For example, we might require 1000 samples for a given node (say, scan
> with some quals), before we start using it to tweak the estimates. Once
> we get the number of estimates, we can continue collecting more data,
> and once in a while update the correction. This would require some care,
> of course, because we need to know what coefficient was used to compute
> the estimate, but that's solvable by having some sort of epoch.
>
> Of course, the question is what number should we use, but overall this
> would be a much lower-overhead way to do the learning.
>
> Unfortunately, the learning as implemented in the patch does not allow
> this. It pretty much requires dedicated learning phase with generated
> workload, in a single process.
>
> But I think that's solvable, assuming we:
>
> 1) Store the data in shared memory, instead of a file. Collect data from
> all backends, instead of just a single one, etc.
>
> 2) Make the decision for individual entries, depending on how many
> samples we have for it.
>
Sounds good. I was trying to think whether we can maintain a running
coefficient. In that way, we don't have to store the samples. But,
calculating a running coefficient for more than two variables (with
some single pass algorithm) seems to be a hard problem. Moreover, it
can introduce significant misestimation. Your suggested approach works
better.

> I suggest we try to solve one issue at a time. I agree advising which
> indexes to create is a very interesting (and valuable) thing, but I see
> it as an extension of the AQO feature. That is, basic AQO (tweaking row
> estimates) can work without it.
>
+1

> >> 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.
> >>
> >That'll be an interesting work. For the above query, we can definitely
> >calculate the correction coefficient of t1-t2 join given (t1.a = ? AND
> >t1.b = ? AND t1.c < ?) and
> >(t2.x = ? AND t2.y = ?) are true. But, I'm not sure how we can
> >extrapolate that value for t1-t2 join.
>
> I'm not sure I see the problem? Essentially, we need to know the sizes
> of the join inputs, i.e.
>
>     t1 WHERE (t1.a = ? AND t1.b = ? AND t1.c < ?)
>
>     t2 WHERE (t2.x = ? AND t2.y = ?)
>
> (which we know, and we know how to correct the estimate), and then the
> selectivity of the join condition. Which we also know.
>
> Obviously, there's a chance those parts (clauses at the scan / join
> level) are correlated, which could make this less accurate.
This is exactly what my concern is. The base predicate selectivities
of t1 and t2 should have an impact on the calculation of the
correction coefficient. If those selectivities are low, the
misestimation (which is actual/estimate) should not affect the t1-t2
join correction coefficient much.


-- 
Thanks & Regards,
Kuntal Ghosh
EnterpriseDB: http://www.enterprisedb.com

On Thu, 13 Jun 2019 at 06:07, Kuntal Ghosh <kuntalghosh.2007@gmail.com> wrote:
>
> On Thu, Jun 13, 2019 at 5:49 AM Tomas Vondra
> <tomas.vondra@2ndquadrant.com> wrote:
> >
> > For example, we might require 1000 samples for a given node (say, scan
> > with some quals), before we start using it to tweak the estimates. Once
> > we get the number of estimates, we can continue collecting more data,
> > and once in a while update the correction. This would require some care,
> > of course, because we need to know what coefficient was used to compute
> > the estimate, but that's solvable by having some sort of epoch.
> >
> > Of course, the question is what number should we use, but overall this
> > would be a much lower-overhead way to do the learning.
> >
> > Unfortunately, the learning as implemented in the patch does not allow
> > this. It pretty much requires dedicated learning phase with generated
> > workload, in a single process.
> >
> > But I think that's solvable, assuming we:
> >
> > 1) Store the data in shared memory, instead of a file. Collect data from
> > all backends, instead of just a single one, etc.
> >
> > 2) Make the decision for individual entries, depending on how many
> > samples we have for it.
> >
> Sounds good. I was trying to think whether we can maintain a running
> coefficient. In that way, we don't have to store the samples. But,
> calculating a running coefficient for more than two variables (with
> some single pass algorithm) seems to be a hard problem. Moreover, it
> can introduce significant misestimation. Your suggested approach works
> better.
>
> > I suggest we try to solve one issue at a time. I agree advising which
> > indexes to create is a very interesting (and valuable) thing, but I see
> > it as an extension of the AQO feature. That is, basic AQO (tweaking row
> > estimates) can work without it.
> >
> +1
>
> > >> 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.
> > >>
> > >That'll be an interesting work. For the above query, we can definitely
> > >calculate the correction coefficient of t1-t2 join given (t1.a = ? AND
> > >t1.b = ? AND t1.c < ?) and
> > >(t2.x = ? AND t2.y = ?) are true. But, I'm not sure how we can
> > >extrapolate that value for t1-t2 join.
> >
> > I'm not sure I see the problem? Essentially, we need to know the sizes
> > of the join inputs, i.e.
> >
> >     t1 WHERE (t1.a = ? AND t1.b = ? AND t1.c < ?)
> >
> >     t2 WHERE (t2.x = ? AND t2.y = ?)
> >
> > (which we know, and we know how to correct the estimate), and then the
> > selectivity of the join condition. Which we also know.
> >
> > Obviously, there's a chance those parts (clauses at the scan / join
> > level) are correlated, which could make this less accurate.
> This is exactly what my concern is. The base predicate selectivities
> of t1 and t2 should have an impact on the calculation of the
> correction coefficient. If those selectivities are low, the
> misestimation (which is actual/estimate) should not affect the t1-t2
> join correction coefficient much.
>
Interesting discussion. Talking of query optimization techniques and
challenges, isn't the biggest challenge there is of selectivity
estimation? Then instead of working on optimizing the process which
has been talked of since long, how about skipping the process
altogether. This reminds of the work I came across sometime back[1].
Basically, the idea is to not spend any energy on estimation the
selectivities rather get on with the execution. Precisely, a set of
plans is kept apriori for different selectivities and at the execution
time it starts with the plans one by one, starting from the lower
selectivity one till the query execution completes. It might sound
like too much work but it isn't, there are some theoretical guarantees
to bound the worst case execution time. The trick is in choosing the
plan-set and switching at the time of execution. Another good point
about this is that it works smoothly for join predicates as well.

Since, we are talking about this problem here, I though it might be a
good idea to shed some light on such an approach and see if there is
some interesting trick we might use.

[1] https://dsl.cds.iisc.ac.in/publications/conference/bouquet.pdf

-- 
Regards,
Rafia Sabih

On Thu, Jun 13, 2019 at 09:37:07AM +0530, Kuntal Ghosh wrote:
>On Thu, Jun 13, 2019 at 5:49 AM Tomas Vondra
><tomas.vondra@2ndquadrant.com> wrote:
>>
>> For example, we might require 1000 samples for a given node (say, scan
>> with some quals), before we start using it to tweak the estimates. Once
>> we get the number of estimates, we can continue collecting more data,
>> and once in a while update the correction. This would require some care,
>> of course, because we need to know what coefficient was used to compute
>> the estimate, but that's solvable by having some sort of epoch.
>>
>> Of course, the question is what number should we use, but overall this
>> would be a much lower-overhead way to do the learning.
>>
>> Unfortunately, the learning as implemented in the patch does not allow
>> this. It pretty much requires dedicated learning phase with generated
>> workload, in a single process.
>>
>> But I think that's solvable, assuming we:
>>
>> 1) Store the data in shared memory, instead of a file. Collect data from
>> all backends, instead of just a single one, etc.
>>
>> 2) Make the decision for individual entries, depending on how many
>> samples we have for it.
>>
>Sounds good. I was trying to think whether we can maintain a running
>coefficient. In that way, we don't have to store the samples. But,
>calculating a running coefficient for more than two variables (with
>some single pass algorithm) seems to be a hard problem. Moreover, it
>can introduce significant misestimation. Your suggested approach works
>better.
>

I don't know, TBH. I think it would be enough to store the coefficient and
the number of samples it's based on, so that you can consider that as a
weight when merging it with additional values. But I don't think it's a
solved issue, so we may need to experiment a bit.

>> I suggest we try to solve one issue at a time. I agree advising which
>> indexes to create is a very interesting (and valuable) thing, but I see
>> it as an extension of the AQO feature. That is, basic AQO (tweaking row
>> estimates) can work without it.
>>
>+1
>
>> >> 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.
>> >>
>> >That'll be an interesting work. For the above query, we can definitely
>> >calculate the correction coefficient of t1-t2 join given (t1.a = ? AND
>> >t1.b = ? AND t1.c < ?) and
>> >(t2.x = ? AND t2.y = ?) are true. But, I'm not sure how we can
>> >extrapolate that value for t1-t2 join.
>>
>> I'm not sure I see the problem? Essentially, we need to know the sizes
>> of the join inputs, i.e.
>>
>>     t1 WHERE (t1.a = ? AND t1.b = ? AND t1.c < ?)
>>
>>     t2 WHERE (t2.x = ? AND t2.y = ?)
>>
>> (which we know, and we know how to correct the estimate), and then the
>> selectivity of the join condition. Which we also know.
>>
>> Obviously, there's a chance those parts (clauses at the scan / join
>> level) are correlated, which could make this less accurate.
>This is exactly what my concern is. The base predicate selectivities
>of t1 and t2 should have an impact on the calculation of the
>correction coefficient. If those selectivities are low, the
>misestimation (which is actual/estimate) should not affect the t1-t2
>join correction coefficient much.
>

The question is whether it really matters. The question is whether this
correlation between restriction and join clauses is universal (applies to
most queries) or an exception.

If it's an exception (only for a small number of rarely queried values),
then we have little chance to fix it. If we ever get extended statistics
on joins, that might help, but I think AQO alone is unlikely to help.

OTOH if it's a systemic misestimate (affecting most queries), then we'll
catch it just fine.


regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On Thu, Jun 13, 2019 at 03:17:07PM +0200, Rafia Sabih wrote:
>On Thu, 13 Jun 2019 at 06:07, Kuntal Ghosh <kuntalghosh.2007@gmail.com> wrote:
>>
>> On Thu, Jun 13, 2019 at 5:49 AM Tomas Vondra
>> <tomas.vondra@2ndquadrant.com> wrote:
>> >
>> > >> ...
>> > >>
>> > >That'll be an interesting work. For the above query, we can definitely
>> > >calculate the correction coefficient of t1-t2 join given (t1.a = ? AND
>> > >t1.b = ? AND t1.c < ?) and
>> > >(t2.x = ? AND t2.y = ?) are true. But, I'm not sure how we can
>> > >extrapolate that value for t1-t2 join.
>> >
>> > I'm not sure I see the problem? Essentially, we need to know the sizes
>> > of the join inputs, i.e.
>> >
>> >     t1 WHERE (t1.a = ? AND t1.b = ? AND t1.c < ?)
>> >
>> >     t2 WHERE (t2.x = ? AND t2.y = ?)
>> >
>> > (which we know, and we know how to correct the estimate), and then the
>> > selectivity of the join condition. Which we also know.
>> >
>> > Obviously, there's a chance those parts (clauses at the scan / join
>> > level) are correlated, which could make this less accurate.
>> This is exactly what my concern is. The base predicate selectivities
>> of t1 and t2 should have an impact on the calculation of the
>> correction coefficient. If those selectivities are low, the
>> misestimation (which is actual/estimate) should not affect the t1-t2
>> join correction coefficient much.
>>
>Interesting discussion. Talking of query optimization techniques and
>challenges, isn't the biggest challenge there is of selectivity
>estimation?

Yes, selectivity estimation is the major challenge. It's not the only one,
but we rely on the estimates quite a bit - it's probably the main factor
affecting cost estimates.

> Then instead of working on optimizing the process which
>has been talked of since long, how about skipping the process
>altogether. This reminds of the work I came across sometime back[1].
>Basically, the idea is to not spend any energy on estimation the
>selectivities rather get on with the execution. Precisely, a set of
>plans is kept apriori for different selectivities and at the execution
>time it starts with the plans one by one, starting from the lower
>selectivity one till the query execution completes. It might sound
>like too much work but it isn't, there are some theoretical guarantees
>to bound the worst case execution time. The trick is in choosing the
>plan-set and switching at the time of execution. Another good point
>about this is that it works smoothly for join predicates as well.
>
>Since, we are talking about this problem here, I though it might be a
>good idea to shed some light on such an approach and see if there is
>some interesting trick we might use.
>
>[1] https://dsl.cds.iisc.ac.in/publications/conference/bouquet.pdf
>

AFAIK adaptive execution (switching from one plan to another
mid-execution) is actually quite difficult to implement in practice,
especially when some of the rows might have been already sent to the
user, etc. Which is why databases (outside of academia) use this only
in very limited/specific situations.

regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services