[PATCH] Push limit to sort through a subquery

The function pass_down_bound() is a recursive function. For
SubqueryScanState we have to do something similar to ResultState i.e.
call pass_down_bound() recursively on subqueryScanState->subplan.

Please add this to the next commitfest.

On Wed, Apr 19, 2017 at 6:09 AM, Douglas Doole <dougdoole@gmail.com> wrote:

We've hit a case where pass_down_bound() isn't pushing the row count limit
from limit into sort. The issue is that we're getting a subquery scan node
between the limit and the sort. The subquery is only doing column projection
and has no quals or SRFs so it should be safe to push the limit into the
sort.

The query that hit the problem can be simplified to:

SELECT * FROM (SELECT A,B FROM T ORDER BY C) LIMIT 5

(Yeah, the query's a little screwy in that the ORDER BY should really be
outside the subselect, but it came from a query generator, so that's a
different conversation.)

Proposed patch is attached.

- Doug
Salesforce

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

--
Best Wishes,
Ashutosh Bapat
EnterpriseDB Corporation
The Postgres Database Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Thanks for the feedback Ashutosh.

I disagree that we need to call pass_down_bound() recursively. The whole
point of the recursive call would be to tunnel through a plan node. Since
SubqueryScanState only has one child (unlike MergeAppendState) this can be
more efficiently done inline rather than via a recursive call.

In the case of ResultState, this is classic tail-end recursion and the C
compiler should optimize it out. As we add more recursive calls though, it
becomes harder for the compiler to do the right thing. (I'll admit that I'm
not up on what state-of-the-art in recursion removal though, so maybe my
concern is moot. That said, I prefer not to depend on compiler
optimizations if there's a clean alternative way to express the code.)

I do agree that it would make the code cleaner to handle ResultState and
SubqueryScanState in a similar fashion. My preference, however, would be to
remove the recursive call from ResultState handling. That would give us
code like:

if child == SubqueryScanState
child = SubqueryScanState->child
else if child == ResultState
child = ResultState->child

if child == SortState
limit pushdown
else if child == MergeAppendState
recursive call on all children

If it is possible to get more than one SubqueryScanState and/or ResultState
between the limit and sort, then the first block of code could be placed in
a while loop.

If you'd prefer that I rework the patch as I discussed, just let me know
and I'll resubmit it.

- Doug
Salesforce

On Wed, Apr 19, 2017 at 1:57 AM Ashutosh Bapat <
ashutosh.bapat@enterprisedb.com> wrote:

On Wed, Apr 19, 2017 at 10:51 PM, Douglas Doole <dougdoole@gmail.com> wrote:

Thanks for the feedback Ashutosh.

I disagree that we need to call pass_down_bound() recursively. The whole
point of the recursive call would be to tunnel through a plan node. Since
SubqueryScanState only has one child (unlike MergeAppendState) this can be
more efficiently done inline rather than via a recursive call.

In the case of ResultState, this is classic tail-end recursion and the C
compiler should optimize it out. As we add more recursive calls though, it
becomes harder for the compiler to do the right thing. (I'll admit that I'm
not up on what state-of-the-art in recursion removal though, so maybe my
concern is moot. That said, I prefer not to depend on compiler optimizations
if there's a clean alternative way to express the code.)

I do agree that it would make the code cleaner to handle ResultState and
SubqueryScanState in a similar fashion. My preference, however, would be to
remove the recursive call from ResultState handling. That would give us code
like:

if child == SubqueryScanState
child = SubqueryScanState->child
else if child == ResultState
child = ResultState->child

if child == SortState
limit pushdown
else if child == MergeAppendState
recursive call on all children

If it is possible to get more than one SubqueryScanState and/or ResultState
between the limit and sort, then the first block of code could be placed in
a while loop.

If you'd prefer that I rework the patch as I discussed, just let me know and
I'll resubmit it.

Thinking more about it, pass_down_bound() optimization ultimately
targets sort nodes. It doesn't for example target ForeignScan nodes
which can benefit from such optimization. But I think any generic
LIMIT optimization will need to be handled in the planner as against
the executor.

Said that, I don't think community at large would accept serializing
pass_down_bound() as you are proposing. You may to wait for others'
opinions before working on it. If you add this to the commitfest app,
more people might look at it when the next commitfest opens. Also, it
might help if you can provide a query/ies with numbers where this
optimization shows improvement.

--
Best Wishes,
Ashutosh Bapat
EnterpriseDB Corporation
The Postgres Database Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

If you add this to the commitfest app, more people might look at it when
the next commitfest opens.

I have added it. https://commitfest.postgresql.org/14/1119/

Also, it might help if you can provide a query/ies with numbers where this

optimization shows improvement.

I can't provide the real queries where we encountered the problem because
they are internal. However I showed a simplified version of the queries in
my first post.

On our queries, the change made quite a difference - execution time dropped
from 31.4 seconds to 7.2 seconds. Explain analyze also shows that memory
use dropped significantly and we didn't have to spill the sort to disk

From:

-> Sort (cost=989.95..1013.27 rows=9326 width=30)
(node_startup_time/loop=31328.891, node_total_time/loop: 31329.756
rows=2001 loops=1) Buffers: temp read=772 written=11201 lsm_bufmgr
hits=3392 Sort Key: *** Sort Method: external merge Sort Space Used: 89592
Sort Space Type: Disk

To:

-> Sort (cost=989.95..1013.27 rows=9326 width=30)
(node_startup_time/loop=7123.275, node_total_time/loop: 7123.504 rows=2001
loops=1) Buffers: lsm_bufmgr hits=3387 Sort Key: *** Sort Method: top-N
heapsort Sort Space Used: 3256 Sort Space Type: Memory

On 29.04.2017 00:13, Douglas Doole wrote:

If you add this to the commitfest app, more people might look at
it when the next commitfest opens.

I have added it. https://commitfest.postgresql.org/14/1119/

Also, it might help if you can provide a query/ies with numbers
where this optimization shows improvement.

I can't provide the real queries where we encountered the problem
because they are internal. However I showed a simplified version of
the queries in my first post.

On our queries, the change made quite a difference - execution time
dropped from 31.4 seconds to 7.2 seconds. Explain analyze also shows
that memory use dropped significantly and we didn't have to spill the
sort to disk

From:

-> Sort (cost=989.95..1013.27 rows=9326 width=30)
(node_startup_time/loop=31328.891, node_total_time/loop: 31329.756
rows=2001 loops=1) Buffers: temp read=772 written=11201 lsm_bufmgr
hits=3392 Sort Key: *** Sort Method: external merge Sort Space Used:
89592 Sort Space Type: Disk

To:

-> Sort (cost=989.95..1013.27 rows=9326 width=30)
(node_startup_time/loop=7123.275, node_total_time/loop: 7123.504
rows=2001 loops=1) Buffers: lsm_bufmgr hits=3387 Sort Key: *** Sort
Method: top-N heapsort Sort Space Used: 3256 Sort Space Type: Memory

Attached please find yet another small patch which pushes down LIMIT to
ForeignScan.
I should notice that currently Postgres optimizer is using "Merge
Append" and fetches from remote nodes only required number of tuples.
So even without LIMIT push down, postgres_fdw will not pull the whole
table from remote host.
postgres_fdw is using cursor for fetching data from remote. Default
fetch size is 100, so even without limit remote query will fetch no
more than 100 rows at remote site.

Assume the following example:

postgres=# create extension postgres_fdw;
postgres=# create server shard1 FOREIGN DATA WRAPPER postgres_fdw
options(dbname 'postgres', host 'localhost', port '5432');
postgres=# create server shard2 FOREIGN DATA WRAPPER postgres_fdw
options(dbname 'postgres', host 'localhost', port '5432');
postgres=# CREATE USER MAPPING for $user SERVER shard1 options (user
'$user');
postgres=# CREATE USER MAPPING for $user SERVER shard1 options (user
'$user');
postgres=# CREATE TABLE t(u integer primary key, v integer);
postgres=# CREATE TABLE t1(u integer primary key, v integer);
postgres=# CREATE TABLE t2(u integer primary key, v integer);
postgres=# insert into t1 values (generate_series(1,100000),
random()*100000);
postgres=# insert into t2 values (generate_series(1,100000),
random()*100000);
postgres=# CREATE FOREIGN TABLE t_fdw1() inherits (t) server shard1
options(table_name 't1');
postgres=# CREATE FOREIGN TABLE t_fdw2() inherits (t) server shard2
options(table_name 't2');

postgres=# explain analyze select * from t order by u limit 1;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
Limit (cost=200.15..200.20 rows=1 width=8) (actual time=2.010..2.010
rows=1 loops=1)
-> Merge Append (cost=200.15..449.39 rows=5121 width=8) (actual
time=2.009..2.009 rows=1 loops=1)
Sort Key: t.u
-> Index Scan using t_pkey on t (cost=0.12..8.14 rows=1
width=8) (actual time=0.005..0.005 rows=0 loops=1)
-> Foreign Scan on t_fdw2 (cost=100.00..193.92 rows=2560
width=8) (actual time=1.074..1.074rows=1 loops=1)
-> Foreign Scan on t_fdw1 (cost=100.00..193.92 rows=2560
width=8) (actual time=0.928..0.928rows=1 loops=1)
Planning time: 0.769 ms
Execution time: 6.837 ms
(8 rows)

As you can see foreign scan fetches only one row from each remote node.

But still pushing down limit can have positive effect on performance,
especially if SORT can be replaced with TOP-N.
I got the following results (time in seconds):

Query
original
limit push down
select * from t order by u limit 1
2.276
1.777
select * from t order by v limit 1
100 42

There is index for "u", so fetching records with smallest "u" values can
be done without sorting, so times are similar.
But in case of sorting by "v", pushing down limit allows to use TOP-1
instead of global sort and it reduces query execution time more than 2
times.

--

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

I completely agree. The further a limit can be pushed down, the better.

The patch looks good to me.

On Thu, Aug 17, 2017 at 8:27 AM Konstantin Knizhnik <
k.knizhnik@postgrespro.ru> wrote:

On Thu, Aug 17, 2017 at 11:36 AM, Douglas Doole <dougdoole@gmail.com> wrote:

I completely agree. The further a limit can be pushed down, the better.

The patch looks good to me.

It seems like a somewhat ad-hoc approach; it supposes that we can take any
query produced by deparseSelectStmtForRel() and stick a LIMIT clause onto
the very end and all will be well. Maybe that's not a problematic
assumption, not sure. The grammar happens to allow both FOR UPDATE LIMIT n
and LIMIT n FOR UPDATE even though only the latter syntax is documented.

Regarding the other patch on this thread, you mentioned upthread that "If
it is possible to get more than one SubqueryScanState and/or ResultState
between the limit and sort, then the first block of code could be placed in
a while loop." I think that's not possible for a ResultState, but I think
it *is* possible for a SubqueryScanState.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Thanks for the feedback on my original patch Robert. Here's an updated
patch that will tunnel through multiple SubqueryScanStates.

- Doug
Salesforce

On Thu, Aug 17, 2017 at 6:33 PM Robert Haas <robertmhaas@gmail.com> wrote:

On Fri, Aug 18, 2017 at 11:42 AM, Douglas Doole <dougdoole@gmail.com> wrote:

Thanks for the feedback on my original patch Robert. Here's an updated patch
that will tunnel through multiple SubqueryScanStates.

Seems reasonable. I have some assorted nitpicks.

1. The header comment for pass_down_bound() could mention "one or more
levels of subqueries" rather than "a subquery".

2. The first of the comments in the function body appears to have a
whitespace issue that needs to be fixed manually or, better yet,
addressed by pgindent.

3. The formatting of the comment in the regression tests appears to be
unlike any other comment in that same file.

4. I am pretty doubtful that "Memory: 25kB" is going to be stable
enough for us to want that output memorialized in the regression
tests. It seems like it might vary on different platforms - e.g.
32-bit vs. 64-bit - and it also seems like minor changes to how we do
sorting could perturb it and, perhaps, make it unstable even if today
it isn't. So I think it would be good to give this a bit more thought
and see if you can come up with a way to test this without running
afoul of that problem. Maybe adapt from this:

do $$declare x text; begin execute 'explain select 1' into x; if x !~
'^Result' then raise notice '%', x; else raise notice 'looks ok'; end
if; end;$$;

BTW, regarding the other patch on this thread, it struck me that maybe
it would be better to just reduce/limit the fetch count for the cursor
instead of trying to inject LIMIT n into the query itself. That's not
as good for query optimization purposes but it's a lot more
future-proof.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

1. The header comment for pass_down_bound() could mention "one or more
levels of subqueries" rather than "a subquery".

Fixed

2. The first of the comments in the function body appears to have a

whitespace issue that needs to be fixed manually or, better yet,
addressed by pgindent.

Fixed

3. The formatting of the comment in the regression tests appears to be
unlike any other comment in that same file.

A side effect of inheriting it from our branches ;-) Reworked.

4. I am pretty doubtful that "Memory: 25kB" is going to be stable
enough for us to want that output memorialized in the regression ...

Fair enough. I wanted to be a bit more sophisticated in my check than
looking for a single value so I worked out something that distills the
explain down to the key elements.

On Fri, Aug 18, 2017 at 4:08 PM, Douglas Doole <dougdoole@gmail.com> wrote:

4. I am pretty doubtful that "Memory: 25kB" is going to be stable
enough for us to want that output memorialized in the regression ...

Fair enough. I wanted to be a bit more sophisticated in my check than
looking for a single value so I worked out something that distills the
explain down to the key elements.

Works for me. While I'm sure this won't eclipse previous achievements
in this area, it still seems worthwhile. So committed with one minor
change to shorten a long-ish line.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Aug 22, 2017 at 3:43 AM, Robert Haas <robertmhaas@gmail.com> wrote:

Works for me. While I'm sure this won't eclipse previous achievements
in this area, it still seems worthwhile.

This one is intentional per what happens in the US today? ;)
--
Michael

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 18.08.2017 04:33, Robert Haas wrote:

It seems like a somewhat ad-hoc approach; it supposes that we can take
any query produced by deparseSelectStmtForRel() and stick a LIMIT
clause onto the very end and all will be well. Maybe that's not a
problematic assumption, not sure. The grammar happens to allow both
FOR UPDATE LIMIT n and LIMIT n FOR UPDATE even though only the latter
syntax is documented.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

I am not absolutely sure that it is possible to append any query which
can be constructed by postgres_fdw for foreign scan with "LIMIT n" clause.
But I also do not know example when it is not possible. As you have
mentioned, "FOR UPDATE LIMIT n" is currently recognized by Postgres.

Can you suggest how to implement limit push down to FDW in better way?
Move deparseSelectStmtForRel() from postgresGetForeignPlan to
postgresIterateForeignScan ?
It seems to be problematic because many information required by
deparseSelectStmtForRel is not available in postgresIterateForeignScan.
In principle, it is possible to somehow propagate it here. But from my
point of view it is not right approach...

IMHO there is some contradiction in Postgres optimizer that static
information about limit is not taken in account at the planning stage
and is actually used only during query execution,
when pass_down_bound() function is called to propagate knowledge about
limit down through plan nodes. Certainly I understand that it gives more
flexibility: we can use information from
previous steps of query execution which was not available at planning stage.

But pushing down limit at planning stage requires too much changes. And
the proposed patch is very small and non-invasive. And in principle, it
can be used not only postgres_fdw, but also in other FDW implementations
to push down information about LIMIT.

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

On 22.08.2017 17:27, Konstantin Knizhnik wrote:

On 18.08.2017 04:33, Robert Haas wrote:

It seems like a somewhat ad-hoc approach; it supposes that we can
take any query produced by deparseSelectStmtForRel() and stick a
LIMIT clause onto the very end and all will be well. Maybe that's
not a problematic assumption, not sure. The grammar happens to allow
both FOR UPDATE LIMIT n and LIMIT n FOR UPDATE even though only the
latter syntax is documented.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

I am not absolutely sure that it is possible to append any query which
can be constructed by postgres_fdw for foreign scan with "LIMIT n" clause.
But I also do not know example when it is not possible. As you have
mentioned, "FOR UPDATE LIMIT n" is currently recognized by Postgres.

I have inspected deparseSelectStmtForRel function and now I am sure that
appending LIMIT to the SQL statement generated by this function will not
cause any problems.
It can produce only the following subset of SELECT:

select <target-list> FROM <table-list> [GROUP BY ... [ HAVING ... ]] [
OREDER BY ... ] [ FOR UPDATE ... ];

The only suspicious clause is FOR UPDATE, but I have checked that "FOR
UPDATE ... LIMIT n" is really accepted by Postgres parser.

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

On Wed, Aug 23, 2017 at 12:56 PM, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> wrote:

On 22.08.2017 17:27, Konstantin Knizhnik wrote:

On 18.08.2017 04:33, Robert Haas wrote:

It seems like a somewhat ad-hoc approach; it supposes that we can take any
query produced by deparseSelectStmtForRel() and stick a LIMIT clause onto
the very end and all will be well. Maybe that's not a problematic
assumption, not sure. The grammar happens to allow both FOR UPDATE LIMIT n
and LIMIT n FOR UPDATE even though only the latter syntax is documented.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

I am not absolutely sure that it is possible to append any query which can
be constructed by postgres_fdw for foreign scan with "LIMIT n" clause.
But I also do not know example when it is not possible. As you have
mentioned, "FOR UPDATE LIMIT n" is currently recognized by Postgres.

I have inspected deparseSelectStmtForRel function and now I am sure that
appending LIMIT to the SQL statement generated by this function will not
cause any problems.
It can produce only the following subset of SELECT:

select <target-list> FROM <table-list> [GROUP BY ... [ HAVING ... ]] [
OREDER BY ... ] [ FOR UPDATE ... ];

The only suspicious clause is FOR UPDATE, but I have checked that "FOR
UPDATE ... LIMIT n" is really accepted by Postgres parser.

There are two ways we can do this.
1. Implement limit handling in postgresGetForeignUpperPaths() when it
gets UPPERREL_FINAL (or we might want to break this rel into final and
limit rel). We then add paths for limit processing to the final rel
and add corresponding handling in deparseSelectStmtForRel(). If
foreign path happens to be cheaper, LIMIT gets pushed down to the
foreign server. But this approach does not take care of LIMITs passed
down by pass_down_bound(). But it will take care of deparsing the
query correctly and handle OFFSET clause as well.

2. Konstantin's approach takes care of LIMITs passed down by
pass_down_bound(), but "always" pushes down the LIMIT and assumes that
a LIMIT clause can be appended to the query already generated. Both of
these seem sane choices. But then it doesn't push down OFFSET clause
even when it's possible to push it down.

If we could defer deparsing the query to execution time we might be
able to achieve both the targets. It has one more advantage: we could
pass parameters embedded in the query, rather than binding them.

--
Best Wishes,
Ashutosh Bapat
EnterpriseDB Corporation
The Postgres Database Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Mon, Aug 21, 2017 at 2:43 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Works for me. While I'm sure this won't eclipse previous achievements
in this area, it still seems worthwhile. So committed with one minor
change to shorten a long-ish line.

Buildfarm members with force_parallel_mode=regress are failing now. I
haven't had a chance to investigate exactly what's going on here, but
I think there are probably several issues:

1. It's definitely the case that the details about a sort operation
aren't propagated from a worker back to the leader. This has elicited
complaint previously.

2. pass_down_bound() probably gets the Gather node at the top of the
tree and stops, since it doesn't know how to pass down a bound through
a Gather. We could probably teach it to pass down the bound through
Gather or Gather Merge on the same theory as Append/MergeAppend.

3. However, even if it did that, it would only affect the leader, not
the workers, because each worker will of course have a separate copy
of each executor state node. We could fix that by having the Gather
or Gather Merge node also store the bound and propagate that to each
worker via DSM, and then have each worker call pass_down_bound itself.
(This would require a bit of refactoring of the API for
pass_down_bound, but it looks doable.)

In the short run, I'm not sure we have a better alternative than
removing this test - unless somebody has a better idea? - but it would
be good to work on all of the above problems.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Buildfarm members with force_parallel_mode=regress are failing now. I
haven't had a chance to investigate exactly what's going on here, but
I think there are probably several issues:

Not an auspicious beginning for my first patch :-(

3. However, even if it did that, it would only affect the leader, not
the workers, because each worker will of course have a separate copy
of each executor state node. We could fix that by having the Gather
or Gather Merge node also store the bound and propagate that to each
worker via DSM, and then have each worker call pass_down_bound itself.
(This would require a bit of refactoring of the API for
pass_down_bound, but it looks doable.)

From previous experience, pushing the limit to the workers has the
potential to be a big win .

In the short run, I'm not sure we have a better alternative than

removing this test - unless somebody has a better idea? - but it would
be good to work on all of the above problems.

I haven't played with parallel mode at all yet. Is it possible to disable
force_parallel_mode for the new test? If not, then I'd agree that removing
the test is probably the only reasonable short term fix.

- Doug
Salesforce

On Wed, Aug 23, 2017 at 6:55 PM, Douglas Doole <dougdoole@gmail.com> wrote:

From previous experience, pushing the limit to the workers has the potential
to be a big win .

Here's a not-really-tested draft patch for that.

I haven't played with parallel mode at all yet. Is it possible to disable
force_parallel_mode for the new test?

Yeah, I suppose that's another alternative.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Here's a not-really-tested draft patch for that.

I don't know the parallel code so I'm not going to comment on the overall
patch, but a thought on ExecSetTupleBound().

That function is getting a number of cases where we're doing recursion for
a single child (result, gather, gather-merge). Recursion for a single child
isn't particularly efficient. I know that if there's a single case of
recursion like this, compilers will frequently turn it into a loop, but I
don't know if compilers can optimize a branched case like this.

Would we be better off moving those cases into the while loop I added to
avoid the recursion? So we'd end up with something like:

while ()
{
if subquery
else if result
else if gather
else if gather merge
}

if sort
else if merge append

And a nit from my original fix now that I've looked at the pg10 code more.
The two casts I added (to SubqueryScanState and Node) should probably be
changed to castNode() calls.

- Doug
Salesforce