From 1f6d515a67ec98194c23a5db25660856c9aab944 Mon Sep 17 00:00:00 2001 From: Robert Haas Date: Mon, 21 Aug 2017 14:43:01 -0400 Subject: [PATCH] Push limit through subqueries to underlying sort, where possible. Douglas Doole, reviewed by Ashutosh Bapat and by me. Minor formatting change by me. Discussion: http://postgr.es/m/CADE5jYLuugnEEUsyW6Q_4mZFYTxHxaVCQmGAsF0yiY8ZDggi-w@mail.gmail.com --- src/backend/executor/nodeLimit.c | 26 +++++++++++++ src/test/regress/expected/subselect.out | 52 +++++++++++++++++++++++++ src/test/regress/sql/subselect.sql | 46 ++++++++++++++++++++++ 3 files changed, 124 insertions(+) diff --git a/src/backend/executor/nodeLimit.c b/src/backend/executor/nodeLimit.c index ac5a2ff0e6..09af1a5d8b 100644 --- a/src/backend/executor/nodeLimit.c +++ b/src/backend/executor/nodeLimit.c @@ -308,6 +308,9 @@ recompute_limits(LimitState *node) * since the MergeAppend surely need read no more than that many tuples from * any one input. We also have to be prepared to look through a Result, * since the planner might stick one atop MergeAppend for projection purposes. + * We can also accept one or more levels of subqueries that have no quals or + * SRFs (that is, each subquery is just projecting columns) between the LIMIT + * and any of the above. * * This is a bit of a kluge, but we don't have any more-abstract way of * communicating between the two nodes; and it doesn't seem worth trying @@ -320,6 +323,29 @@ recompute_limits(LimitState *node) static void pass_down_bound(LimitState *node, PlanState *child_node) { + /* + * If the child is a subquery that does no filtering (no predicates) + * and does not have any SRFs in the target list then we can potentially + * push the limit through the subquery. It is possible that we could have + * multiple subqueries, so tunnel through them all. + */ + while (IsA(child_node, SubqueryScanState)) + { + SubqueryScanState *subqueryScanState; + + subqueryScanState = (SubqueryScanState *) child_node; + + /* + * Non-empty predicates or an SRF means we cannot push down the limit. + */ + if (subqueryScanState->ss.ps.qual != NULL || + expression_returns_set((Node *) child_node->plan->targetlist)) + return; + + /* Use the child in the following checks */ + child_node = subqueryScanState->subplan; + } + if (IsA(child_node, SortState)) { SortState *sortState = (SortState *) child_node; diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out index ed7d6d8034..8419dea08e 100644 --- a/src/test/regress/expected/subselect.out +++ b/src/test/regress/expected/subselect.out @@ -1041,3 +1041,55 @@ NOTICE: x = 9, y = 13 (3 rows) drop function tattle(x int, y int); +-- +-- Test that LIMIT can be pushed to SORT through a subquery that just +-- projects columns +-- +create table sq_limit (pk int primary key, c1 int, c2 int); +insert into sq_limit values + (1, 1, 1), + (2, 2, 2), + (3, 3, 3), + (4, 4, 4), + (5, 1, 1), + (6, 2, 2), + (7, 3, 3), + (8, 4, 4); +-- The explain contains data that may not be invariant, so +-- filter for just the interesting bits. The goal here is that +-- we should see three notices, in order: +-- NOTICE: Limit +-- NOTICE: Subquery +-- NOTICE: Top-N Sort +-- A missing step, or steps out of order means we have a problem. +do $$ + declare x text; + begin + for x in + explain (analyze, summary off, timing off, costs off) + select * from (select pk,c2 from sq_limit order by c1,pk) as x limit 3 + loop + if (left(ltrim(x), 5) = 'Limit') then + raise notice 'Limit'; + end if; + if (left(ltrim(x), 12) = '-> Subquery') then + raise notice 'Subquery'; + end if; + if (left(ltrim(x), 18) = 'Sort Method: top-N') then + raise notice 'Top-N Sort'; + end if; + end loop; + end; +$$; +NOTICE: Limit +NOTICE: Subquery +NOTICE: Top-N Sort +select * from (select pk,c2 from sq_limit order by c1,pk) as x limit 3; + pk | c2 +----+---- + 1 | 1 + 5 | 1 + 2 | 2 +(3 rows) + +drop table sq_limit; diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql index 2fc0e26ca0..7087ee27cd 100644 --- a/src/test/regress/sql/subselect.sql +++ b/src/test/regress/sql/subselect.sql @@ -540,3 +540,49 @@ select * from where tattle(x, u); drop function tattle(x int, y int); + +-- +-- Test that LIMIT can be pushed to SORT through a subquery that just +-- projects columns +-- +create table sq_limit (pk int primary key, c1 int, c2 int); +insert into sq_limit values + (1, 1, 1), + (2, 2, 2), + (3, 3, 3), + (4, 4, 4), + (5, 1, 1), + (6, 2, 2), + (7, 3, 3), + (8, 4, 4); + +-- The explain contains data that may not be invariant, so +-- filter for just the interesting bits. The goal here is that +-- we should see three notices, in order: +-- NOTICE: Limit +-- NOTICE: Subquery +-- NOTICE: Top-N Sort +-- A missing step, or steps out of order means we have a problem. +do $$ + declare x text; + begin + for x in + explain (analyze, summary off, timing off, costs off) + select * from (select pk,c2 from sq_limit order by c1,pk) as x limit 3 + loop + if (left(ltrim(x), 5) = 'Limit') then + raise notice 'Limit'; + end if; + if (left(ltrim(x), 12) = '-> Subquery') then + raise notice 'Subquery'; + end if; + if (left(ltrim(x), 18) = 'Sort Method: top-N') then + raise notice 'Top-N Sort'; + end if; + end loop; + end; +$$; + +select * from (select pk,c2 from sq_limit order by c1,pk) as x limit 3; + +drop table sq_limit; -- 2.40.0