To reproduce the problem see 'problem.sql' in attachment: Out of explain analyze see in 'problem_explain.txt'
As you can see, executor scan each of 1e5 outer tuples despite the fact that inner can't return any tuples.
Teodor Sigaev and I developed a patch to solve this problem. Result of explain analyze procedure can be found in the 'optimized_execution.txt'.
-- Andrey Lepikhov Postgres Professional https://postgrespro.com The Russian Postgres Company
problem.sql
Description: application/sql
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.29..1515.83 rows=1 width=80) (actual time=25.194..25.194 rows=0
loops=1)
-> Nested Loop (cost=0.29..504674.12 rows=333 width=80) (actual
time=25.193..25.193 rows=0 loops=1)
Join Filter: (big.id = small.id)
-> Index Scan Backward using big_pkey on big (cost=0.29..5152.29
rows=100000 width=44) (actual time=0.005..12.933 rows=100000 loops=1)
-> Materialize (cost=0.00..22.66 rows=333 width=36) (actual
time=0.000..0.000 rows=0 loops=100000)
-> Seq Scan on small (cost=0.00..21.00 rows=333 width=36)
(actual time=0.145..0.145 rows=0 loops=1)
Filter: ((id)::numeric > '1000'::numeric)
Rows Removed by Filter: 1000
Planning Time: 0.215 ms
Execution Time: 25.214 ms
(10 rows)
>From 40ffbd2d9ee5954e5ae09f1e5a929ae2f2b17b8c Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <a.lepik...@postgrespro.ru>
Date: Mon, 9 Dec 2019 18:25:04 +0500
Subject: [PATCH] Skip scan of outer subtree if inner of the NestedLoop node is
guaranteed empty.
---
src/backend/executor/nodeMaterial.c | 11 +++++++++++
src/backend/executor/nodeNestloop.c | 5 +++++
src/include/nodes/execnodes.h | 4 ++++
src/test/regress/expected/partition_prune.out | 8 ++++----
4 files changed, 24 insertions(+), 4 deletions(-)
diff --git a/src/backend/executor/nodeMaterial.c b/src/backend/executor/nodeMaterial.c
index cc93bbe45b..98771647f6 100644
--- a/src/backend/executor/nodeMaterial.c
+++ b/src/backend/executor/nodeMaterial.c
@@ -135,6 +135,8 @@ ExecMaterial(PlanState *pstate)
if (TupIsNull(outerslot))
{
node->eof_underlying = true;
+ if (tuplestorestate && tuplestore_tuple_count(tuplestorestate) == 0)
+ node->ss.ps.guaranteed_empty = true;
return NULL;
}
@@ -348,6 +350,9 @@ ExecReScanMaterial(MaterialState *node)
node->tuplestorestate = NULL;
if (outerPlan->chgParam == NULL)
ExecReScan(outerPlan);
+ else
+ /* At first look no cases can lead to this code. But still. */
+ node->ss.ps.guaranteed_empty = false;
node->eof_underlying = false;
}
else
@@ -363,6 +368,12 @@ ExecReScanMaterial(MaterialState *node)
*/
if (outerPlan->chgParam == NULL)
ExecReScan(outerPlan);
+
+ /*
+ * The node suppress tuplestore and guaranteed_empty trick isn't work.
+ */
+ Assert(node->ss.ps.guaranteed_empty == false);
+
node->eof_underlying = false;
}
}
diff --git a/src/backend/executor/nodeNestloop.c b/src/backend/executor/nodeNestloop.c
index fc6667ef82..ea26a7d9d1 100644
--- a/src/backend/executor/nodeNestloop.c
+++ b/src/backend/executor/nodeNestloop.c
@@ -164,6 +164,11 @@ ExecNestLoop(PlanState *pstate)
{
ENL1_printf("no inner tuple, need new outer tuple");
+ if (innerPlan->guaranteed_empty &&
+ (node->js.jointype == JOIN_INNER ||
+ node->js.jointype == JOIN_SEMI))
+ return NULL;
+
node->nl_NeedNewOuter = true;
if (!node->nl_MatchedOuter &&
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 692438d6df..c7f1a14526 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1007,6 +1007,9 @@ typedef struct PlanState
* ExecConditionalAssignProjectionInfo()). If no projection is necessary
* ExecConditionalAssignProjectionInfo() defaults those fields to the scan
* operations.
+ *
+ * If guaranteed_empty field is true, this means that no tuple will be
+ * returned by the node.
*/
const TupleTableSlotOps *scanops;
const TupleTableSlotOps *outerops;
@@ -1020,6 +1023,7 @@ typedef struct PlanState
bool outeropsset;
bool inneropsset;
bool resultopsset;
+ bool guaranteed_empty;
} PlanState;
/* ----------------
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index f9eeda60e6..04cfe0944e 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -2455,9 +2455,9 @@ update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;
Heap Blocks: exact=1
-> Bitmap Index Scan on ab_a1_b2_a_idx (actual rows=1 loops=1)
Index Cond: (a = 1)
- -> Bitmap Heap Scan on ab_a1_b3 ab_2 (actual rows=0 loops=1)
+ -> Bitmap Heap Scan on ab_a1_b3 ab_2 (never executed)
Recheck Cond: (a = 1)
- -> Bitmap Index Scan on ab_a1_b3_a_idx (actual rows=0 loops=1)
+ -> Bitmap Index Scan on ab_a1_b3_a_idx (never executed)
Index Cond: (a = 1)
-> Materialize (actual rows=0 loops=1)
-> Bitmap Heap Scan on ab_a1_b1 ab_a1_1 (actual rows=0 loops=1)
@@ -2496,9 +2496,9 @@ update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;
Heap Blocks: exact=1
-> Bitmap Index Scan on ab_a1_b2_a_idx (actual rows=1 loops=1)
Index Cond: (a = 1)
- -> Bitmap Heap Scan on ab_a1_b3 ab_2 (actual rows=0 loops=1)
+ -> Bitmap Heap Scan on ab_a1_b3 ab_2 (never executed)
Recheck Cond: (a = 1)
- -> Bitmap Index Scan on ab_a1_b3_a_idx (actual rows=1 loops=1)
+ -> Bitmap Index Scan on ab_a1_b3_a_idx (never executed)
Index Cond: (a = 1)
-> Materialize (actual rows=0 loops=1)
-> Bitmap Heap Scan on ab_a1_b3 ab_a1_3 (actual rows=0 loops=1)
--
2.17.1
Limit (cost=0.29..1515.83 rows=1 width=80) (actual time=0.151..0.151 rows=0
loops=1)
-> Nested Loop (cost=0.29..504674.12 rows=333 width=80) (actual
time=0.150..0.150 rows=0 loops=1)
Join Filter: (big.id = small.id)
-> Index Scan Backward using big_pkey on big (cost=0.29..5152.29
rows=100000 width=44) (actual time=0.004..0.004 rows=1 loops=1)
-> Materialize (cost=0.00..22.66 rows=333 width=36) (actual
time=0.145..0.145 rows=0 loops=1)
-> Seq Scan on small (cost=0.00..21.00 rows=333 width=36)
(actual time=0.144..0.144 rows=0 loops=1)
Filter: ((id)::numeric > '1000'::numeric)
Rows Removed by Filter: 1000
Planning Time: 0.182 ms
Execution Time: 0.166 ms
(10 rows)
