Subject: Query planner gaining the ability to replanning after start of query execution.

From: Oliver Mattos <[email-masked]>
Date: Mon, 13 Nov 2017 16:44:49 +0000

I am interested in giving the query planner the ability to replan (or
re-rank plans) after query execution has begun, based on the
progression of the query so far.

Example use case:

*  A LIMIT 1 query is planned using an expensive scan which the
planner expects to return a large number of results, and to terminate
early.   The reality is the query actually produces no results, and
the scan must run to completion, potentially taking thousands of times
longer than expected.

*  If this plans costs were adjusted mid-execution to reflect the fact
that the scan is producing far fewer rows than expected, then another
query plan might come out ahead, which would complete far faster.

Has this been done before?   Are there any pitfalls to beware of?

-- 
Sent via pgsql-performance mailing list ([email-masked])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance

---

From: Arne Roland <[email-masked]>
Date: Mon, 13 Nov 2017 20:06:20 +0000

Hello,

I'd love to have some sort of dynamic query feedback, yet it's very complicated to do it right. I am not convinced that changing the plan during a single execution is the right way to do it, not only because it sounds intrusive to do crazy things in the executor, but also because don't understand why the new plan should be any better than the old one. Can you be more elaborate how you'd want to go about it?

In your example (which presumably just has a single relation), we have no notion of whether the scan returns no rows because we were unlucky, because just the first few pages were empty of matching rows (which in my experience happens more often), or because the cardinality estimation is wrong. Even if the cardinality estimation is wrong, we have no notion of which predicate or predicate combination actually caused the misestimation. If the first few pages where empty, the same might happen with every order (so also with every available indexscan). Imagine a very simple seqscan plan of 
select * from mytab where a = 3 and b = 40 limit 1
Even if we know the cardinality is overestimated, we have no idea whether the cardinality of a = 3 or b = 40 is wrong or they just correlate, so there is no notion of which is actually the cheapest plan. Usual workaround for most of these queries is to add an order by (which has the nice addition of having a deterministic result) with an appropriate complex index, usually resulting in indexscans.

While we actually know more after the first execution of a nodes like materialize, sort or hash nodes, I rarely encounter materialize nodes in the wild. Consequently that is the place where the work is usually already done, which is especially true with the hash node. Even though it still might be more optimal to switch from a mergejoin to a hashjoin in some cases, I doubt that's worth any work (and even less the maintenance).

Best regards
Arne Roland

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Oliver Mattos
Sent: Monday, November 13, 2017 5:45 PM
To: [email-masked]
Subject: [PERFORM] Query planner gaining the ability to replanning after start of query execution.

I am interested in giving the query planner the ability to replan (or re-rank plans) after query execution has begun, based on the progression of the query so far.

Example use case:

*  A LIMIT 1 query is planned using an expensive scan which the planner expects to return a large number of results, and to terminate
early.   The reality is the query actually produces no results, and
the scan must run to completion, potentially taking thousands of times longer than expected.

*  If this plans costs were adjusted mid-execution to reflect the fact that the scan is producing far fewer rows than expected, then another query plan might come out ahead, which would complete far faster.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Oliver Mattos
Sent: Monday, November 13, 2017 5:45 PM
To: [email-masked]
Subject: [PERFORM] Query planner gaining the ability to replanning after start of query execution.

I am interested in giving the query planner the ability to replan (or re-rank plans) after query execution has begun, based on the progression of the query so far.

Example use case:

*  A LIMIT 1 query is planned using an expensive scan which the planner expects to return a large number of results, and to terminate
early.   The reality is the query actually produces no results, and
the scan must run to completion, potentially taking thousands of times longer than expected.

*  If this plans costs were adjusted mid-execution to reflect the fact that the scan is producing far fewer rows than expected, then another query plan might come out ahead, which would complete far faster.

---

From: Oliver Mattos <[email-masked]>
Date: Mon, 13 Nov 2017 21:51:32 +0000

> Can you be more elaborate how you'd want to go about it?

My initial approach would be to try to identify places in the plan
where selectivity is seriously over or underestimated.   I would reuse
the instrumentation infrastructure's counts of filtered and returned
tuples for each execnode, and periodically call back into the planner
(for example at every power of 2 tuples processed).

The planner would have a wrapper to clauselist_selectivity which
somehow combines the existing estimate with the filtered and returned
tuples so far.   Exactly how to merge them isn't clear, but I could
imagine using a poisson distribution to calculate the probability that
the selectivity estimate is representative of the filtered and
returned numbers, and then blending the two linearly based on that
estimate.

When the planner has re-estimated the cost of the current plan, a
discount would be applied for the percentage of each execnode
completed (rows processed / estimated rows), and all candidate plans
compared.

If another candidate plan is now lower cost, the current plan would be
terminated[1] by setting a flag instructing each execnode to return as
if it had reached the end of the input, although still caching the
node selectivity values, and the new plan started from scratch.

The old plan is kept within the query planner candidate list, together
with it's cached selectivity values.  If at some point it again is
cheaper, it is started from scratch too.

> Even if we know the cardinality is overestimated, we have no idea whether the cardinality of a = 3 or b = 40 is wrong or they just correlate

The goal would be not to know which is wrong, but to try each,
discarding it if it turns out worse than we estimated.  Processing a
few hundred rows of each of 5 plans is tiny compared to a scan of 1M
rows...

[1]:   An improvement here (with much more code complexity) is to keep
multiple partially executed plans around, so that whichever one is
most promising can be worked on, but can be halted and resumed later
as selectivity (and hence cost) estimates change.

---

From: Arne Roland <[email-masked]>
Date: Mon, 13 Nov 2017 22:48:49 +0000

Hello,

that method is bound to introduce errors if the physical location of a row correlates strongly with a column, imagine "and my_timestamp> now() - INTERVAL '1 year'" as part of a where clause of a query without limit on an insert only table which is one and a half years old with a seqscan. There might be similar effects if an index on the timestamp is used to go about a query, if other rows of the filter correlate.

This method furthermore only judges filter predicates.
So it's not that easy to just go about the expected rowcount of a single node, since the underling node might return a totally inaccurate number of rows. While that isn't that common with underlying seqscans, it is very frequent if an indexscan is used without being able to rely on the MCV. While it's still possible to notice a misestimation there is no sense of how wrong it is, until the rows are already processed.

Furthermore: Did you think about parallel plans and most importantly cursors?

Best regards
Arne Roland

-----Original Message-----
From: Oliver Mattos [mailto:[email-masked]] 
Sent: Monday, November 13, 2017 10:52 PM
To: Arne Roland <[email-masked]>
Cc: [email-masked]
Subject: Re: [PERFORM] Query planner gaining the ability to replanning after start of query execution.

My initial approach would be to try to identify places in the plan
where selectivity is seriously over or underestimated.   I would reuse
the instrumentation infrastructure's counts of filtered and returned tuples for each execnode, and periodically call back into the planner (for example at every power of 2 tuples processed).

The planner would have a wrapper to clauselist_selectivity which somehow combines the existing estimate with the filtered and returned
tuples so far.   Exactly how to merge them isn't clear, but I could
imagine using a poisson distribution to calculate the probability that the selectivity estimate is representative of the filtered and returned numbers, and then blending the two linearly based on that estimate.

When the planner has re-estimated the cost of the current plan, a discount would be applied for the percentage of each execnode completed (rows processed / estimated rows), and all candidate plans compared.

If another candidate plan is now lower cost, the current plan would be terminated[1] by setting a flag instructing each execnode to return as if it had reached the end of the input, although still caching the node selectivity values, and the new plan started from scratch.

The old plan is kept within the query planner candidate list, together with it's cached selectivity values.  If at some point it again is cheaper, it is started from scratch too.

> Even if we know the cardinality is overestimated, we have no idea 
> whether the cardinality of a = 3 or b = 40 is wrong or they just 
> correlate

The goal would be not to know which is wrong, but to try each, discarding it if it turns out worse than we estimated.  Processing a few hundred rows of each of 5 plans is tiny compared to a scan of 1M rows...

[1]:   An improvement here (with much more code complexity) is to keep
multiple partially executed plans around, so that whichever one is most promising can be worked on, but can be halted and resumed later as selectivity (and hence cost) estimates change.

On Mon, Nov 13, 2017 at 8:06 PM, Arne Roland <[email-masked]> wrote:
> In your example (which presumably just has a single relation), we have 
> no notion of whether the scan returns no rows because we were unlucky, 
> because just the first few pages were empty of matching rows (which in my experience happens more often), or because the cardinality estimation is wrong. Even if the cardinality estimation is wrong, we have no notion of which predicate or predicate combination actually caused the misestimation. If the first few pages where empty, the same might happen with every order (so also with every available indexscan). Imagine a very simple seqscan plan of select * from mytab where a = 3 and b = 40 limit 1 Even if we know the cardinality is overestimated, we have no idea whether the cardinality of a = 3 or b = 40 is wrong or they just correlate, so there is no notion of which is actually the cheapest plan. Usual workaround for most of these queries is to add an order by (which has the nice addition of having a deterministic result) with an appropriate complex index, usually resulting in indexscans.
>
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Oliver 
> Mattos
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Oliver 
> Mattos

---

From: Tom Lane <[email-masked]>
Date: Mon, 13 Nov 2017 17:49:33 -0500

> ... If another candidate plan is now lower cost, the current plan would be

Quite aside from the implementation difficulties you'll have, that
approach is a show-stopper right there.  You can't just restart from
scratch, because we may already have shipped rows to the client, or
for DML cases already inserted/updated/deleted rows (and even if you
could roll those back, we've possibly fired triggers with unpredictable
side effects).  Queries containing volatile functions are another no-fly
zone for this approach.

I can't see any way around that without unacceptable performance costs
(i.e. buffering all the rows until we're done) or wire-protocol breakage.

I think that a more practical way to address the class of problems
you're talking about is to teach the planner to have some notion of
worst-case as well as expected-case costs, and then incorporate some
perhaps-configurable amount of risk aversion in its choices.

			regards, tom lane

PS: please do not top-post, and do not quote the entire darn thread
in each message.

---

From: Oliver Mattos <[email-masked]>
Date: Mon, 13 Nov 2017 23:20:44 +0000

>  You can't just restart from scratch, because we may already have shipped rows to the client

For v1, replanning wouldn't be an option if rows have already been
shipped, or for DML statements.

> parallel plans and most importantly cursors?
Parallel plans look do-able with the same approach, but cursor use I'd
probably stop replanning as soon as the first row is delivered to the
client, as above.   One could imagine more complex approaches like a
limited size buffer of 'delivered' rows, allowing a new plan to be
selected and the delivered rows excluded from the new plans resultset
via a special extra prepending+dupe filtering execnode.   The memory
and computation costs of that execnode would be factored into the
replanning decision like any other node.

>errors if the physical location of a row correlates strongly with a column
This is my largest concern.  These cases already lead to large errors
currently (SELECT * FROM foo WHERE created_date = today LIMIT 1) might
scan all data, only to find all of today's records in the last
physical block.

It's hard to say if replacing one bad estimate with another will lead
to overall better/worse results...   My hope is that in most cases a
bunch of plans will be tried, all end up with cost estimates revised
up a lot, and then one settled on as rows start getting passed to
upper layers.

>underling node might return a totally inaccurate number of rows for index scans
One might imagine using the last returned row as an extra histogram
point when estimating how many rows are left in an index scan.   That
should at least make the estimate more accurate than it is without
feedback.

---

From: legrand legrand <[email-masked]>
Date: Tue, 14 Nov 2017 14:26:16 -0700 (MST)

As a first step, before relaunching the query with a new plan I would be
happy to be able to get information about sql queries having wrong
estimates.

Maybe thoses SQL queries could be collected using something similar to
"auto_explain" module (tracing finished or cancelled queries).

If the "corrected plan" taking into account real cardinalities was proposed
(with some advices on how to get it) it would be a great tuning adviser ;o)

--
Sent from: http://www.postgresql-archive.org/PostgreSQL-performance-f2050081.html

---

From: Gunter <[email-masked]>
Date: Wed, 15 Nov 2017 12:57:44 -0700 (MST)

May I suggest the recent discussion over the dreaded NL issue ... I had some
similar ideas.

http://www.postgresql-archive.org/OLAP-reporting-queries-fall-into-nested-loops-over-seq-scans-or-other-horrible-planner-choices-td5990160.html

This could be massively useful and a huge leap in the industry.