public inbox for [email protected]
help / color / mirror / Atom feed[PATCH v27 4/9] Add Incremental View Maintenance support to pg_dump
6+ messages / 4 participants
[nested] [flat]
* [PATCH v27 4/9] Add Incremental View Maintenance support to pg_dump
@ 2020-11-11 08:01 Yugo Nagata <[email protected]>
0 siblings, 0 replies; 6+ messages in thread
From: Yugo Nagata @ 2020-11-11 08:01 UTC (permalink / raw)
Support CREATE INCREMENTAL MATERIALIZED VIEW syntax.
---
src/bin/pg_dump/pg_dump.c | 18 +++++++++++++++---
src/bin/pg_dump/pg_dump.h | 1 +
src/bin/pg_dump/t/002_pg_dump.pl | 15 +++++++++++++++
3 files changed, 31 insertions(+), 3 deletions(-)
diff --git a/src/bin/pg_dump/pg_dump.c b/src/bin/pg_dump/pg_dump.c
index 969e2a7a46..3c764076d2 100644
--- a/src/bin/pg_dump/pg_dump.c
+++ b/src/bin/pg_dump/pg_dump.c
@@ -6089,6 +6089,7 @@ getTables(Archive *fout, int *numTables)
int i_relacl;
int i_acldefault;
int i_ispartition;
+ int i_isivm;
/*
* Find all the tables and table-like objects.
@@ -6191,10 +6192,17 @@ getTables(Archive *fout, int *numTables)
if (fout->remoteVersion >= 100000)
appendPQExpBufferStr(query,
- "c.relispartition AS ispartition ");
+ "c.relispartition AS ispartition, ");
else
appendPQExpBufferStr(query,
- "false AS ispartition ");
+ "false AS ispartition, ");
+
+ if (fout->remoteVersion >= 160000)
+ appendPQExpBufferStr(query,
+ "c.relisivm AS isivm ");
+ else
+ appendPQExpBufferStr(query,
+ "false AS isivm ");
/*
* Left join to pg_depend to pick up dependency info linking sequences to
@@ -6303,6 +6311,7 @@ getTables(Archive *fout, int *numTables)
i_relacl = PQfnumber(res, "relacl");
i_acldefault = PQfnumber(res, "acldefault");
i_ispartition = PQfnumber(res, "ispartition");
+ i_isivm = PQfnumber(res, "isivm");
if (dopt->lockWaitTimeout)
{
@@ -6380,6 +6389,7 @@ getTables(Archive *fout, int *numTables)
tblinfo[i].amname = pg_strdup(PQgetvalue(res, i, i_amname));
tblinfo[i].is_identity_sequence = (strcmp(PQgetvalue(res, i, i_is_identity_sequence), "t") == 0);
tblinfo[i].ispartition = (strcmp(PQgetvalue(res, i, i_ispartition), "t") == 0);
+ tblinfo[i].isivm = (strcmp(PQgetvalue(res, i, i_isivm), "t") == 0);
/* other fields were zeroed above */
@@ -15115,9 +15125,11 @@ dumpTableSchema(Archive *fout, const TableInfo *tbinfo)
binary_upgrade_set_pg_class_oids(fout, q,
tbinfo->dobj.catId.oid, false);
- appendPQExpBuffer(q, "CREATE %s%s %s",
+ appendPQExpBuffer(q, "CREATE %s%s%s %s",
tbinfo->relpersistence == RELPERSISTENCE_UNLOGGED ?
"UNLOGGED " : "",
+ tbinfo->relkind == RELKIND_MATVIEW && tbinfo->isivm ?
+ "INCREMENTAL " : "",
reltypename,
qualrelname);
diff --git a/src/bin/pg_dump/pg_dump.h b/src/bin/pg_dump/pg_dump.h
index 1d21c2906f..0b798ad5de 100644
--- a/src/bin/pg_dump/pg_dump.h
+++ b/src/bin/pg_dump/pg_dump.h
@@ -318,6 +318,7 @@ typedef struct _tableInfo
bool dummy_view; /* view's real definition must be postponed */
bool postponed_def; /* matview must be postponed into post-data */
bool ispartition; /* is table a partition? */
+ bool isivm; /* is incrementally maintainable materialized view? */
/*
* These fields are computed only if we decide the table is interesting
diff --git a/src/bin/pg_dump/t/002_pg_dump.pl b/src/bin/pg_dump/t/002_pg_dump.pl
index c65c92bfb0..3655727472 100644
--- a/src/bin/pg_dump/t/002_pg_dump.pl
+++ b/src/bin/pg_dump/t/002_pg_dump.pl
@@ -2295,6 +2295,21 @@ my %tests = (
{ exclude_dump_test_schema => 1, no_toast_compression => 1, },
},
+ 'CREATE MATERIALIZED VIEW matview_ivm' => {
+ create_order => 21,
+ create_sql => 'CREATE INCREMENTAL MATERIALIZED VIEW dump_test.matview_ivm (col1) AS
+ SELECT col1 FROM dump_test.test_table;',
+ regexp => qr/^
+ \QCREATE INCREMENTAL MATERIALIZED VIEW dump_test.matview_ivm AS\E
+ \n\s+\QSELECT test_table.col1\E
+ \n\s+\QFROM dump_test.test_table\E
+ \n\s+\QWITH NO DATA;\E
+ /xm,
+ like =>
+ { %full_runs, %dump_test_schema_runs, section_pre_data => 1, },
+ unlike => { exclude_dump_test_schema => 1, },
+ },
+
'CREATE POLICY p1 ON test_table' => {
create_order => 22,
create_sql => 'CREATE POLICY p1 ON dump_test.test_table
--
2.17.1
--Multipart=_Fri__22_Apr_2022_11_29_39_+0900_ZOAC7UMt5e8j1Nvx
Content-Type: text/x-diff;
name="v27-0005-Add-Incremental-View-Maintenance-support-to-psql.patch"
Content-Disposition: attachment;
filename="v27-0005-Add-Incremental-View-Maintenance-support-to-psql.patch"
Content-Transfer-Encoding: 7bit
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Support run-time partition pruning for hash join
@ 2023-11-07 07:55 Richard Guo <[email protected]>
2024-01-27 03:29 ` Re: Support run-time partition pruning for hash join vignesh C <[email protected]>
0 siblings, 1 reply; 6+ messages in thread
From: Richard Guo @ 2023-11-07 07:55 UTC (permalink / raw)
To: Alexander Lakhin <[email protected]>; +Cc: David Rowley <[email protected]>; Andy Fan <[email protected]>; pgsql-hackers
On Mon, Nov 6, 2023 at 11:00 PM Alexander Lakhin <[email protected]>
wrote:
> Please look at a warning and an assertion failure triggered by the
> following script:
> set parallel_setup_cost = 0;
> set parallel_tuple_cost = 0;
> set min_parallel_table_scan_size = '1kB';
>
> create table t1 (i int) partition by range (i);
> create table t1_1 partition of t1 for values from (1) to (2);
> create table t1_2 partition of t1 for values from (2) to (3);
> insert into t1 values (1), (2);
>
> create table t2(i int);
> insert into t2 values (1), (2);
> analyze t1, t2;
>
> select * from t1 right join t2 on t1.i = t2.i;
>
> 2023-11-06 14:11:37.398 UTC|law|regression|6548f419.392cf5|WARNING: Join
> partition pruning $0 has not been performed yet.
> TRAP: failed Assert("node->as_prune_state"), File: "nodeAppend.c", Line:
> 846, PID: 3747061
>
Thanks for the report! I failed to take care of the parallel-hashjoin
case, and I have to admit that it's not clear to me yet how we should do
join partition pruning in that case.
For now I think it's better to just avoid performing join partition
pruning for parallel hashjoin, so that the patch doesn't become too
complex for review. We can always extend it in the future.
I have done that in v5. Thanks for testing!
Thanks
Richard
Attachments:
[application/octet-stream] v5-0001-Support-run-time-partition-pruning-for-hash-join.patch (59.4K, ../../CAMbWs49ppLP7oToSj4MiMJ6tbt-nRz-Mwy+ZZMcauAAVJk4gPA@mail.gmail.com/3-v5-0001-Support-run-time-partition-pruning-for-hash-join.patch)
download | inline diff:
From 470ebcee95f4c0b162b6826ce840bf17d8df5266 Mon Sep 17 00:00:00 2001
From: Richard Guo <[email protected]>
Date: Mon, 14 Aug 2023 14:55:26 +0800
Subject: [PATCH v5] Support run-time partition pruning for hash join
If we have a hash join with an Append node on the outer side, something
like
Hash Join
Hash Cond: (pt.a = t.a)
-> Append
-> Seq Scan on pt_p1 pt_1
-> Seq Scan on pt_p2 pt_2
-> Seq Scan on pt_p3 pt_3
-> Hash
-> Seq Scan on t
We can actually prune those subnodes of the Append that cannot possibly
contain any matching tuples from the other side of the join. To do
that, when building the Hash table, for each row from the inner side we
can compute the minimum set of subnodes that can possibly match the join
condition. When we have built the Hash table and start to execute the
Append node, we should have known which subnodes are survived and thus
can skip other subnodes.
This patch implements this idea.
---
src/backend/commands/explain.c | 61 ++++
src/backend/executor/execPartition.c | 127 +++++++-
src/backend/executor/nodeAppend.c | 32 +-
src/backend/executor/nodeHash.c | 75 +++++
src/backend/executor/nodeHashjoin.c | 10 +
src/backend/executor/nodeMergeAppend.c | 22 +-
src/backend/optimizer/path/costsize.c | 106 +++++++
src/backend/optimizer/plan/createplan.c | 49 ++-
src/backend/optimizer/plan/setrefs.c | 61 ++++
src/backend/partitioning/partprune.c | 298 ++++++++++++++++--
src/include/executor/execPartition.h | 17 +-
src/include/nodes/execnodes.h | 3 +
src/include/nodes/pathnodes.h | 3 +
src/include/nodes/plannodes.h | 36 +++
src/include/optimizer/cost.h | 4 +
src/include/partitioning/partprune.h | 12 +-
src/test/regress/expected/partition_prune.out | 86 +++++
src/test/regress/sql/partition_prune.sql | 39 +++
18 files changed, 992 insertions(+), 49 deletions(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index f1d71bc54e..c51cf6beb6 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -18,6 +18,7 @@
#include "commands/createas.h"
#include "commands/defrem.h"
#include "commands/prepare.h"
+#include "executor/execPartition.h"
#include "executor/nodeHash.h"
#include "foreign/fdwapi.h"
#include "jit/jit.h"
@@ -118,6 +119,9 @@ static void show_instrumentation_count(const char *qlabel, int which,
PlanState *planstate, ExplainState *es);
static void show_foreignscan_info(ForeignScanState *fsstate, ExplainState *es);
static void show_eval_params(Bitmapset *bms_params, ExplainState *es);
+static void show_join_pruning_result_info(Bitmapset *join_prune_paramids,
+ ExplainState *es);
+static void show_joinpartprune_info(HashState *hashstate, ExplainState *es);
static const char *explain_get_index_name(Oid indexId);
static void show_buffer_usage(ExplainState *es, const BufferUsage *usage,
bool planning);
@@ -2057,9 +2061,17 @@ ExplainNode(PlanState *planstate, List *ancestors,
show_incremental_sort_info(castNode(IncrementalSortState, planstate),
es);
break;
+ case T_Append:
+ if (es->verbose)
+ show_join_pruning_result_info(((Append *) plan)->join_prune_paramids,
+ es);
+ break;
case T_MergeAppend:
show_merge_append_keys(castNode(MergeAppendState, planstate),
ancestors, es);
+ if (es->verbose)
+ show_join_pruning_result_info(((MergeAppend *) plan)->join_prune_paramids,
+ es);
break;
case T_Result:
show_upper_qual((List *) ((Result *) plan)->resconstantqual,
@@ -2075,6 +2087,8 @@ ExplainNode(PlanState *planstate, List *ancestors,
break;
case T_Hash:
show_hash_info(castNode(HashState, planstate), es);
+ if (es->verbose)
+ show_joinpartprune_info(castNode(HashState, planstate), es);
break;
case T_Memoize:
show_memoize_info(castNode(MemoizeState, planstate), ancestors,
@@ -3515,6 +3529,53 @@ show_eval_params(Bitmapset *bms_params, ExplainState *es)
ExplainPropertyList("Params Evaluated", params, es);
}
+/*
+ * Show join partition pruning results at Append/MergeAppend nodes.
+ */
+static void
+show_join_pruning_result_info(Bitmapset *join_prune_paramids, ExplainState *es)
+{
+ int paramid = -1;
+ List *params = NIL;
+
+ if (bms_is_empty(join_prune_paramids))
+ return;
+
+ while ((paramid = bms_next_member(join_prune_paramids, paramid)) >= 0)
+ {
+ char param[32];
+
+ snprintf(param, sizeof(param), "$%d", paramid);
+ params = lappend(params, pstrdup(param));
+ }
+
+ ExplainPropertyList("Join Partition Pruning", params, es);
+}
+
+/*
+ * Show join partition pruning infos at Hash nodes.
+ */
+static void
+show_joinpartprune_info(HashState *hashstate, ExplainState *es)
+{
+ List *params = NIL;
+ ListCell *lc;
+
+ if (!hashstate->joinpartprune_state_list)
+ return;
+
+ foreach(lc, hashstate->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+ char param[32];
+
+ snprintf(param, sizeof(param), "$%d", jpstate->paramid);
+ params = lappend(params, pstrdup(param));
+ }
+
+ ExplainPropertyList("Partition Prune", params, es);
+}
+
/*
* Fetch the name of an index in an EXPLAIN
*
diff --git a/src/backend/executor/execPartition.c b/src/backend/executor/execPartition.c
index f6c34328b8..35a9149a39 100644
--- a/src/backend/executor/execPartition.c
+++ b/src/backend/executor/execPartition.c
@@ -199,6 +199,8 @@ static void find_matching_subplans_recurse(PartitionPruningData *prunedata,
PartitionedRelPruningData *pprune,
bool initial_prune,
Bitmapset **validsubplans);
+static bool get_join_prune_matching_subplans(PlanState *planstate,
+ Bitmapset **partset);
/*
@@ -1806,7 +1808,7 @@ ExecInitPartitionPruning(PlanState *planstate,
* Perform an initial partition prune pass, if required.
*/
if (prunestate->do_initial_prune)
- *initially_valid_subplans = ExecFindMatchingSubPlans(prunestate, true);
+ *initially_valid_subplans = ExecFindMatchingSubPlans(prunestate, true, NULL);
else
{
/* No pruning, so we'll need to initialize all subplans */
@@ -1836,6 +1838,37 @@ ExecInitPartitionPruning(PlanState *planstate,
return prunestate;
}
+/*
+ * ExecInitJoinpartpruneList
+ * Initialize data structures needed for join partition pruning
+ */
+List *
+ExecInitJoinpartpruneList(PlanState *planstate,
+ List *joinpartprune_info_list)
+{
+ ListCell *lc;
+ List *result = NIL;
+
+ foreach(lc, joinpartprune_info_list)
+ {
+ JoinPartitionPruneInfo *jpinfo = (JoinPartitionPruneInfo *) lfirst(lc);
+ JoinPartitionPruneState *jpstate = palloc(sizeof(JoinPartitionPruneState));
+
+ jpstate->part_prune_state =
+ CreatePartitionPruneState(planstate, jpinfo->part_prune_info);
+ Assert(jpstate->part_prune_state->do_exec_prune);
+
+ jpstate->paramid = jpinfo->paramid;
+ jpstate->nplans = jpinfo->nplans;
+ jpstate->finished = false;
+ jpstate->part_prune_result = NULL;
+
+ result = lappend(result, jpstate);
+ }
+
+ return result;
+}
+
/*
* CreatePartitionPruneState
* Build the data structure required for calling ExecFindMatchingSubPlans
@@ -2273,7 +2306,9 @@ PartitionPruneFixSubPlanMap(PartitionPruneState *prunestate,
/*
* ExecFindMatchingSubPlans
* Determine which subplans match the pruning steps detailed in
- * 'prunestate' for the current comparison expression values.
+ * 'prunestate' if any for the current comparison expression values, and
+ * meanwhile match the join partition pruning results if any stored in
+ * Append/MergeAppend node's join_prune_paramids.
*
* Pass initial_prune if PARAM_EXEC Params cannot yet be evaluated. This
* differentiates the initial executor-time pruning step from later
@@ -2281,11 +2316,30 @@ PartitionPruneFixSubPlanMap(PartitionPruneState *prunestate,
*/
Bitmapset *
ExecFindMatchingSubPlans(PartitionPruneState *prunestate,
- bool initial_prune)
+ bool initial_prune,
+ PlanState *planstate)
{
Bitmapset *result = NULL;
MemoryContext oldcontext;
int i;
+ Bitmapset *join_prune_partset = NULL;
+ bool do_join_prune;
+
+ /* Retrieve the join partition pruning results if any */
+ do_join_prune =
+ get_join_prune_matching_subplans(planstate, &join_prune_partset);
+
+ /*
+ * Either we're here on partition prune done according to the pruning steps
+ * detailed in 'prunestate', or we have done join partition prune.
+ */
+ Assert(do_join_prune || prunestate != NULL);
+
+ /*
+ * If there is no 'prunestate', then rely entirely on join pruning.
+ */
+ if (prunestate == NULL)
+ return join_prune_partset;
/*
* Either we're here on the initial prune done during pruning
@@ -2326,6 +2380,10 @@ ExecFindMatchingSubPlans(PartitionPruneState *prunestate,
/* Add in any subplans that partition pruning didn't account for */
result = bms_add_members(result, prunestate->other_subplans);
+ /* Intersect join partition pruning results */
+ if (do_join_prune)
+ result = bms_intersect(result, join_prune_partset);
+
MemoryContextSwitchTo(oldcontext);
/* Copy result out of the temp context before we reset it */
@@ -2396,3 +2454,66 @@ find_matching_subplans_recurse(PartitionPruningData *prunedata,
}
}
}
+
+/*
+ * get_join_prune_matching_subplans
+ * Retrieve the join partition pruning results if any stored in
+ * Append/MergeAppend node's join_prune_paramids. Return true if we can
+ * do join partition pruning, otherwise return false.
+ *
+ * Adds valid (non-prunable) subplan IDs to *partset
+ */
+static bool
+get_join_prune_matching_subplans(PlanState *planstate, Bitmapset **partset)
+{
+ Bitmapset *join_prune_paramids;
+ int nplans;
+ int paramid;
+
+ if (planstate == NULL)
+ return false;
+
+ if (IsA(planstate, AppendState))
+ {
+ join_prune_paramids =
+ ((Append *) planstate->plan)->join_prune_paramids;
+ nplans = ((AppendState *) planstate)->as_nplans;
+ }
+ else if (IsA(planstate, MergeAppendState))
+ {
+ join_prune_paramids =
+ ((MergeAppend *) planstate->plan)->join_prune_paramids;
+ nplans = ((MergeAppendState *) planstate)->ms_nplans;
+ }
+ else
+ {
+ elog(ERROR, "unrecognized node type: %d", (int) nodeTag(planstate));
+ return false;
+ }
+
+ if (bms_is_empty(join_prune_paramids))
+ return false;
+
+ Assert(nplans > 0);
+ *partset = bms_add_range(NULL, 0, nplans - 1);
+
+ paramid = -1;
+ while ((paramid = bms_next_member(join_prune_paramids, paramid)) >= 0)
+ {
+ ParamExecData *param;
+ JoinPartitionPruneState *jpstate;
+
+ param = &(planstate->state->es_param_exec_vals[paramid]);
+ Assert(param->execPlan == NULL);
+ Assert(!param->isnull);
+ jpstate = (JoinPartitionPruneState *) DatumGetPointer(param->value);
+
+ if (jpstate != NULL)
+ *partset = bms_intersect(*partset, jpstate->part_prune_result);
+ else /* the Hash node for this pruning has not been executed */
+ elog(WARNING, "Join partition pruning $%d has not been performed yet.",
+ paramid);
+ }
+
+ return true;
+}
diff --git a/src/backend/executor/nodeAppend.c b/src/backend/executor/nodeAppend.c
index 609df6b9e6..c8dd8583d2 100644
--- a/src/backend/executor/nodeAppend.c
+++ b/src/backend/executor/nodeAppend.c
@@ -151,11 +151,13 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
nplans = bms_num_members(validsubplans);
/*
- * When no run-time pruning is required and there's at least one
- * subplan, we can fill as_valid_subplans immediately, preventing
- * later calls to ExecFindMatchingSubPlans.
+ * When no run-time pruning or join pruning is required and there's at
+ * least one subplan, we can fill as_valid_subplans immediately,
+ * preventing later calls to ExecFindMatchingSubPlans.
*/
- if (!prunestate->do_exec_prune && nplans > 0)
+ if (!prunestate->do_exec_prune &&
+ bms_is_empty(node->join_prune_paramids) &&
+ nplans > 0)
{
appendstate->as_valid_subplans = bms_add_range(NULL, 0, nplans - 1);
appendstate->as_valid_subplans_identified = true;
@@ -170,10 +172,18 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
* subplans as valid; they must also all be initialized.
*/
Assert(nplans > 0);
- appendstate->as_valid_subplans = validsubplans =
- bms_add_range(NULL, 0, nplans - 1);
- appendstate->as_valid_subplans_identified = true;
+ validsubplans = bms_add_range(NULL, 0, nplans - 1);
appendstate->as_prune_state = NULL;
+
+ /*
+ * When join pruning is not enabled we can fill as_valid_subplans
+ * immediately, preventing later calls to ExecFindMatchingSubPlans.
+ */
+ if (bms_is_empty(node->join_prune_paramids))
+ {
+ appendstate->as_valid_subplans = validsubplans;
+ appendstate->as_valid_subplans_identified = true;
+ }
}
/*
@@ -580,7 +590,7 @@ choose_next_subplan_locally(AppendState *node)
else if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
}
@@ -647,7 +657,7 @@ choose_next_subplan_for_leader(AppendState *node)
if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
/*
@@ -723,7 +733,7 @@ choose_next_subplan_for_worker(AppendState *node)
else if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
mark_invalid_subplans_as_finished(node);
@@ -876,7 +886,7 @@ ExecAppendAsyncBegin(AppendState *node)
if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
classify_matching_subplans(node);
diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index e72f0986c2..9ca8bf49d9 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -31,6 +31,7 @@
#include "catalog/pg_statistic.h"
#include "commands/tablespace.h"
#include "executor/execdebug.h"
+#include "executor/execPartition.h"
#include "executor/hashjoin.h"
#include "executor/nodeHash.h"
#include "executor/nodeHashjoin.h"
@@ -48,6 +49,8 @@ static void ExecHashIncreaseNumBatches(HashJoinTable hashtable);
static void ExecHashIncreaseNumBuckets(HashJoinTable hashtable);
static void ExecParallelHashIncreaseNumBatches(HashJoinTable hashtable);
static void ExecParallelHashIncreaseNumBuckets(HashJoinTable hashtable);
+static void ExecJoinPartitionPrune(HashState *node);
+static void ExecStoreJoinPartitionPruneResult(HashState *node);
static void ExecHashBuildSkewHash(HashJoinTable hashtable, Hash *node,
int mcvsToUse);
static void ExecHashSkewTableInsert(HashJoinTable hashtable,
@@ -189,8 +192,14 @@ MultiExecPrivateHash(HashState *node)
}
hashtable->totalTuples += 1;
}
+
+ /* Perform join partition pruning */
+ ExecJoinPartitionPrune(node);
}
+ /* Store the surviving partitions for Append/MergeAppend nodes */
+ ExecStoreJoinPartitionPruneResult(node);
+
/* resize the hash table if needed (NTUP_PER_BUCKET exceeded) */
if (hashtable->nbuckets != hashtable->nbuckets_optimal)
ExecHashIncreaseNumBuckets(hashtable);
@@ -401,6 +410,12 @@ ExecInitHash(Hash *node, EState *estate, int eflags)
hashstate->hashkeys =
ExecInitExprList(node->hashkeys, (PlanState *) hashstate);
+ /*
+ * initialize join partition pruning infos
+ */
+ hashstate->joinpartprune_state_list =
+ ExecInitJoinpartpruneList(&hashstate->ps, node->joinpartprune_info_list);
+
return hashstate;
}
@@ -1601,6 +1616,56 @@ ExecParallelHashIncreaseNumBuckets(HashJoinTable hashtable)
}
}
+/*
+ * ExecJoinPartitionPrune
+ * Perform join partition pruning at this join for each
+ * JoinPartitionPruneState.
+ */
+static void
+ExecJoinPartitionPrune(HashState *node)
+{
+ ListCell *lc;
+
+ foreach(lc, node->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+ Bitmapset *matching_subPlans;
+
+ if (jpstate->finished)
+ continue;
+
+ matching_subPlans =
+ ExecFindMatchingSubPlans(jpstate->part_prune_state, false, NULL);
+ jpstate->part_prune_result =
+ bms_add_members(jpstate->part_prune_result, matching_subPlans);
+
+ if (bms_num_members(jpstate->part_prune_result) == jpstate->nplans)
+ jpstate->finished = true;
+ }
+}
+
+/*
+ * ExecStoreJoinPartitionPruneResult
+ * For each JoinPartitionPruneState, store the set of surviving partitions
+ * to make it available for the Append/MergeAppend node.
+ */
+static void
+ExecStoreJoinPartitionPruneResult(HashState *node)
+{
+ ListCell *lc;
+
+ foreach(lc, node->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+ ParamExecData *param;
+
+ param = &(node->ps.state->es_param_exec_vals[jpstate->paramid]);
+ Assert(param->execPlan == NULL);
+ Assert(!param->isnull);
+ param->value = PointerGetDatum(jpstate);
+ }
+}
+
/*
* ExecHashTableInsert
* insert a tuple into the hash table depending on the hash value
@@ -2345,6 +2410,16 @@ void
ExecReScanHash(HashState *node)
{
PlanState *outerPlan = outerPlanState(node);
+ ListCell *lc;
+
+ /* reset the state in JoinPartitionPruneStates */
+ foreach(lc, node->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+
+ jpstate->finished = false;
+ jpstate->part_prune_result = NULL;
+ }
/*
* if chgParam of subnode is not null then plan will be re-scanned by
diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c
index 25a2d78f15..ddca824206 100644
--- a/src/backend/executor/nodeHashjoin.c
+++ b/src/backend/executor/nodeHashjoin.c
@@ -311,6 +311,16 @@ ExecHashJoinImpl(PlanState *pstate, bool parallel)
*/
node->hj_FirstOuterTupleSlot = NULL;
}
+ else if (hashNode->joinpartprune_state_list != NIL)
+ {
+ /*
+ * Give the hash node a chance to run join partition
+ * pruning if there is any JoinPartitionPruneState that can
+ * be evaluated at it. So do not apply the empty-outer
+ * optimization in this case.
+ */
+ node->hj_FirstOuterTupleSlot = NULL;
+ }
else if (HJ_FILL_OUTER(node) ||
(outerNode->plan->startup_cost < hashNode->ps.plan->total_cost &&
!node->hj_OuterNotEmpty))
diff --git a/src/backend/executor/nodeMergeAppend.c b/src/backend/executor/nodeMergeAppend.c
index 21b5726e6e..9eb276abc8 100644
--- a/src/backend/executor/nodeMergeAppend.c
+++ b/src/backend/executor/nodeMergeAppend.c
@@ -99,11 +99,13 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
nplans = bms_num_members(validsubplans);
/*
- * When no run-time pruning is required and there's at least one
- * subplan, we can fill ms_valid_subplans immediately, preventing
- * later calls to ExecFindMatchingSubPlans.
+ * When no run-time pruning or join pruning is required and there's at
+ * least one subplan, we can fill ms_valid_subplans immediately,
+ * preventing later calls to ExecFindMatchingSubPlans.
*/
- if (!prunestate->do_exec_prune && nplans > 0)
+ if (!prunestate->do_exec_prune &&
+ bms_is_empty(node->join_prune_paramids) &&
+ nplans > 0)
mergestate->ms_valid_subplans = bms_add_range(NULL, 0, nplans - 1);
}
else
@@ -115,9 +117,15 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
* subplans as valid; they must also all be initialized.
*/
Assert(nplans > 0);
- mergestate->ms_valid_subplans = validsubplans =
- bms_add_range(NULL, 0, nplans - 1);
+ validsubplans = bms_add_range(NULL, 0, nplans - 1);
mergestate->ms_prune_state = NULL;
+
+ /*
+ * When join pruning is not enabled we can fill ms_valid_subplans
+ * immediately, preventing later calls to ExecFindMatchingSubPlans.
+ */
+ if (bms_is_empty(node->join_prune_paramids))
+ mergestate->ms_valid_subplans = validsubplans;
}
mergeplanstates = (PlanState **) palloc(nplans * sizeof(PlanState *));
@@ -218,7 +226,7 @@ ExecMergeAppend(PlanState *pstate)
*/
if (node->ms_valid_subplans == NULL)
node->ms_valid_subplans =
- ExecFindMatchingSubPlans(node->ms_prune_state, false);
+ ExecFindMatchingSubPlans(node->ms_prune_state, false, &node->ps);
/*
* First time through: pull the first tuple from each valid subplan,
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index d6ceafd51c..9bdc88a9db 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -173,6 +173,10 @@ static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel,
static bool has_indexed_join_quals(NestPath *path);
static double approx_tuple_count(PlannerInfo *root, JoinPath *path,
List *quals);
+static double get_joinrel_matching_outer_size(PlannerInfo *root,
+ RelOptInfo *outer_rel,
+ Relids inner_relids,
+ List *restrictlist);
static double calc_joinrel_size_estimate(PlannerInfo *root,
RelOptInfo *joinrel,
RelOptInfo *outer_rel,
@@ -5380,6 +5384,61 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
return nrows;
}
+/*
+ * get_joinrel_matching_outer_size
+ * Make a size estimate for the outer side that matches the inner side.
+ */
+static double
+get_joinrel_matching_outer_size(PlannerInfo *root,
+ RelOptInfo *outer_rel,
+ Relids inner_relids,
+ List *restrictlist)
+{
+ double nrows;
+ Selectivity fkselec;
+ Selectivity jselec;
+ SpecialJoinInfo *sjinfo;
+ SpecialJoinInfo sjinfo_data;
+
+ sjinfo = &sjinfo_data;
+ sjinfo->type = T_SpecialJoinInfo;
+ sjinfo->min_lefthand = outer_rel->relids;
+ sjinfo->min_righthand = inner_relids;
+ sjinfo->syn_lefthand = outer_rel->relids;
+ sjinfo->syn_righthand = inner_relids;
+ sjinfo->jointype = JOIN_SEMI;
+ sjinfo->ojrelid = 0;
+ sjinfo->commute_above_l = NULL;
+ sjinfo->commute_above_r = NULL;
+ sjinfo->commute_below_l = NULL;
+ sjinfo->commute_below_r = NULL;
+ /* we don't bother trying to make the remaining fields valid */
+ sjinfo->lhs_strict = false;
+ sjinfo->semi_can_btree = false;
+ sjinfo->semi_can_hash = false;
+ sjinfo->semi_operators = NIL;
+ sjinfo->semi_rhs_exprs = NIL;
+
+ fkselec = get_foreign_key_join_selectivity(root,
+ outer_rel->relids,
+ inner_relids,
+ sjinfo,
+ &restrictlist);
+ jselec = clauselist_selectivity(root,
+ restrictlist,
+ 0,
+ sjinfo->jointype,
+ sjinfo);
+
+ nrows = outer_rel->rows * fkselec * jselec;
+ nrows = clamp_row_est(nrows);
+
+ /* For safety, make sure result is not more than the base estimate */
+ if (nrows > outer_rel->rows)
+ nrows = outer_rel->rows;
+ return nrows;
+}
+
/*
* calc_joinrel_size_estimate
* Workhorse for set_joinrel_size_estimates and
@@ -6495,3 +6554,50 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual,
return pages_fetched;
}
+
+/*
+ * compute_partprune_cost
+ * Compute the overhead of join partition pruning.
+ */
+double
+compute_partprune_cost(PlannerInfo *root, RelOptInfo *appendrel,
+ Cost append_total_cost, int append_nplans,
+ Relids inner_relids, double inner_rows,
+ List *prunequal)
+{
+ Cost prune_cost;
+ Cost saved_cost;
+ double matching_outer_rows;
+ double unmatched_nplans;
+
+ switch (appendrel->part_scheme->strategy)
+ {
+
+ case PARTITION_STRATEGY_LIST:
+ case PARTITION_STRATEGY_RANGE:
+ prune_cost = cpu_operator_cost * LOG2(append_nplans) * inner_rows;
+ break;
+ case PARTITION_STRATEGY_HASH:
+ prune_cost = cpu_operator_cost * append_nplans * inner_rows;
+ break;
+ default:
+ elog(ERROR, "unexpected partition strategy: %d",
+ (int) appendrel->part_scheme->strategy);
+ break;
+ }
+
+ matching_outer_rows =
+ get_joinrel_matching_outer_size(root,
+ appendrel,
+ inner_relids,
+ prunequal);
+
+ /*
+ * We assume that each outer joined row occupies one new partition. This
+ * is really the worst case.
+ */
+ unmatched_nplans = append_nplans - Min(matching_outer_rows, append_nplans);
+ saved_cost = (unmatched_nplans / append_nplans) * append_total_cost;
+
+ return prune_cost - saved_cost;
+}
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 34ca6d4ac2..308ff452d3 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -242,7 +242,8 @@ static Hash *make_hash(Plan *lefttree,
List *hashkeys,
Oid skewTable,
AttrNumber skewColumn,
- bool skewInherit);
+ bool skewInherit,
+ List *joinpartprune_info_list);
static MergeJoin *make_mergejoin(List *tlist,
List *joinclauses, List *otherclauses,
List *mergeclauses,
@@ -342,6 +343,7 @@ create_plan(PlannerInfo *root, Path *best_path)
/* Initialize this module's workspace in PlannerInfo */
root->curOuterRels = NULL;
root->curOuterParams = NIL;
+ root->join_partition_prune_candidates = NIL;
/* Recursively process the path tree, demanding the correct tlist result */
plan = create_plan_recurse(root, best_path, CP_EXACT_TLIST);
@@ -369,6 +371,8 @@ create_plan(PlannerInfo *root, Path *best_path)
if (root->curOuterParams != NIL)
elog(ERROR, "failed to assign all NestLoopParams to plan nodes");
+ Assert(root->join_partition_prune_candidates == NIL);
+
/*
* Reset plan_params to ensure param IDs used for nestloop params are not
* re-used later
@@ -1223,6 +1227,7 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
int nasyncplans = 0;
RelOptInfo *rel = best_path->path.parent;
PartitionPruneInfo *partpruneinfo = NULL;
+ Bitmapset *join_prune_paramids = NULL;
int nodenumsortkeys = 0;
AttrNumber *nodeSortColIdx = NULL;
Oid *nodeSortOperators = NULL;
@@ -1377,6 +1382,8 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
* If any quals exist, they may be useful to perform further partition
* pruning during execution. Gather information needed by the executor to
* do partition pruning.
+ *
+ * Also gather information needed by the executor to do join pruning.
*/
if (enable_partition_pruning)
{
@@ -1399,13 +1406,20 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
partpruneinfo =
make_partition_pruneinfo(root, rel,
best_path->subpaths,
- prunequal);
+ prunequal,
+ NULL);
+
+ join_prune_paramids =
+ make_join_partition_pruneinfos(root, rel,
+ (Path *) best_path,
+ best_path->subpaths);
}
plan->appendplans = subplans;
plan->nasyncplans = nasyncplans;
plan->first_partial_plan = best_path->first_partial_path;
plan->part_prune_info = partpruneinfo;
+ plan->join_prune_paramids = join_prune_paramids;
copy_generic_path_info(&plan->plan, (Path *) best_path);
@@ -1445,6 +1459,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
ListCell *subpaths;
RelOptInfo *rel = best_path->path.parent;
PartitionPruneInfo *partpruneinfo = NULL;
+ Bitmapset *join_prune_paramids = NULL;
/*
* We don't have the actual creation of the MergeAppend node split out
@@ -1541,6 +1556,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
* If any quals exist, they may be useful to perform further partition
* pruning during execution. Gather information needed by the executor to
* do partition pruning.
+ *
+ * Also gather information needed by the executor to do join pruning.
*/
if (enable_partition_pruning)
{
@@ -1554,11 +1571,18 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
if (prunequal != NIL)
partpruneinfo = make_partition_pruneinfo(root, rel,
best_path->subpaths,
- prunequal);
+ prunequal,
+ NULL);
+
+ join_prune_paramids =
+ make_join_partition_pruneinfos(root, rel,
+ (Path *) best_path,
+ best_path->subpaths);
}
node->mergeplans = subplans;
node->part_prune_info = partpruneinfo;
+ node->join_prune_paramids = join_prune_paramids;
/*
* If prepare_sort_from_pathkeys added sort columns, but we were told to
@@ -4734,6 +4758,13 @@ create_hashjoin_plan(PlannerInfo *root,
AttrNumber skewColumn = InvalidAttrNumber;
bool skewInherit = false;
ListCell *lc;
+ List *joinpartprune_info_list;
+
+ /*
+ * Collect information required to build JoinPartitionPruneInfos at this
+ * join.
+ */
+ prepare_join_partition_prune_candidate(root, &best_path->jpath);
/*
* HashJoin can project, so we don't have to demand exact tlists from the
@@ -4745,6 +4776,11 @@ create_hashjoin_plan(PlannerInfo *root,
outer_plan = create_plan_recurse(root, best_path->jpath.outerjoinpath,
(best_path->num_batches > 1) ? CP_SMALL_TLIST : 0);
+ /*
+ * Retrieve all the JoinPartitionPruneInfos for this join.
+ */
+ joinpartprune_info_list = get_join_partition_prune_candidate(root);
+
inner_plan = create_plan_recurse(root, best_path->jpath.innerjoinpath,
CP_SMALL_TLIST);
@@ -4850,7 +4886,8 @@ create_hashjoin_plan(PlannerInfo *root,
inner_hashkeys,
skewTable,
skewColumn,
- skewInherit);
+ skewInherit,
+ joinpartprune_info_list);
/*
* Set Hash node's startup & total costs equal to total cost of input
@@ -5977,7 +6014,8 @@ make_hash(Plan *lefttree,
List *hashkeys,
Oid skewTable,
AttrNumber skewColumn,
- bool skewInherit)
+ bool skewInherit,
+ List *joinpartprune_info_list)
{
Hash *node = makeNode(Hash);
Plan *plan = &node->plan;
@@ -5991,6 +6029,7 @@ make_hash(Plan *lefttree,
node->skewTable = skewTable;
node->skewColumn = skewColumn;
node->skewInherit = skewInherit;
+ node->joinpartprune_info_list = joinpartprune_info_list;
return node;
}
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index fc3709510d..c416e7ccda 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -156,6 +156,11 @@ static Plan *set_mergeappend_references(PlannerInfo *root,
MergeAppend *mplan,
int rtoffset);
static void set_hash_references(PlannerInfo *root, Plan *plan, int rtoffset);
+static void set_joinpartitionprune_references(PlannerInfo *root,
+ List *joinpartprune_info_list,
+ indexed_tlist *outer_itlist,
+ int rtoffset,
+ double num_exec);
static Relids offset_relid_set(Relids relids, int rtoffset);
static Node *fix_scan_expr(PlannerInfo *root, Node *node,
int rtoffset, double num_exec);
@@ -1897,6 +1902,62 @@ set_hash_references(PlannerInfo *root, Plan *plan, int rtoffset)
/* Hash nodes don't have their own quals */
Assert(plan->qual == NIL);
+
+ set_joinpartitionprune_references(root,
+ hplan->joinpartprune_info_list,
+ outer_itlist,
+ rtoffset,
+ NUM_EXEC_TLIST(plan));
+}
+
+/*
+ * set_joinpartitionprune_references
+ * Do set_plan_references processing on JoinPartitionPruneInfos
+ */
+static void
+set_joinpartitionprune_references(PlannerInfo *root,
+ List *joinpartprune_info_list,
+ indexed_tlist *outer_itlist,
+ int rtoffset,
+ double num_exec)
+{
+ ListCell *l;
+
+ foreach(l, joinpartprune_info_list)
+ {
+ JoinPartitionPruneInfo *jpinfo = (JoinPartitionPruneInfo *) lfirst(l);
+ ListCell *l1;
+
+ foreach(l1, jpinfo->part_prune_info->prune_infos)
+ {
+ List *prune_infos = lfirst(l1);
+ ListCell *l2;
+
+ foreach(l2, prune_infos)
+ {
+ PartitionedRelPruneInfo *pinfo = lfirst(l2);
+
+ pinfo->rtindex += rtoffset;
+
+ pinfo->initial_pruning_steps = (List *)
+ fix_upper_expr(root,
+ (Node *) pinfo->initial_pruning_steps,
+ outer_itlist,
+ OUTER_VAR,
+ rtoffset,
+ NRM_EQUAL,
+ num_exec);
+ pinfo->exec_pruning_steps = (List *)
+ fix_upper_expr(root,
+ (Node *) pinfo->exec_pruning_steps,
+ outer_itlist,
+ OUTER_VAR,
+ rtoffset,
+ NRM_EQUAL,
+ num_exec);
+ }
+ }
+ }
}
/*
diff --git a/src/backend/partitioning/partprune.c b/src/backend/partitioning/partprune.c
index 3f31ecc956..d978093831 100644
--- a/src/backend/partitioning/partprune.c
+++ b/src/backend/partitioning/partprune.c
@@ -48,7 +48,9 @@
#include "optimizer/appendinfo.h"
#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
+#include "optimizer/paramassign.h"
#include "optimizer/pathnode.h"
+#include "optimizer/restrictinfo.h"
#include "parser/parsetree.h"
#include "partitioning/partbounds.h"
#include "partitioning/partprune.h"
@@ -103,15 +105,16 @@ typedef enum PartClauseTarget
*
* gen_partprune_steps() initializes and returns an instance of this struct.
*
- * Note that has_mutable_op, has_mutable_arg, and has_exec_param are set if
- * we found any potentially-useful-for-pruning clause having those properties,
- * whether or not we actually used the clause in the steps list. This
- * definition allows us to skip the PARTTARGET_EXEC pass in some cases.
+ * Note that has_mutable_op, has_mutable_arg, has_exec_param and has_vars are
+ * set if we found any potentially-useful-for-pruning clause having those
+ * properties, whether or not we actually used the clause in the steps list.
+ * This definition allows us to skip the PARTTARGET_EXEC pass in some cases.
*/
typedef struct GeneratePruningStepsContext
{
/* Copies of input arguments for gen_partprune_steps: */
RelOptInfo *rel; /* the partitioned relation */
+ Bitmapset *available_rels; /* rels whose Vars may be used for pruning */
PartClauseTarget target; /* use-case we're generating steps for */
/* Result data: */
List *steps; /* list of PartitionPruneSteps */
@@ -119,6 +122,7 @@ typedef struct GeneratePruningStepsContext
bool has_mutable_arg; /* clauses include any mutable comparison
* values, *other than* exec params */
bool has_exec_param; /* clauses include any PARAM_EXEC params */
+ bool has_vars; /* clauses include any Vars from 'available_rels' */
bool contradictory; /* clauses were proven self-contradictory */
/* Working state: */
int next_step_id;
@@ -144,8 +148,10 @@ static List *make_partitionedrel_pruneinfo(PlannerInfo *root,
List *prunequal,
Bitmapset *partrelids,
int *relid_subplan_map,
+ Bitmapset *available_rels,
Bitmapset **matchedsubplans);
static void gen_partprune_steps(RelOptInfo *rel, List *clauses,
+ Bitmapset *available_rels,
PartClauseTarget target,
GeneratePruningStepsContext *context);
static List *gen_partprune_steps_internal(GeneratePruningStepsContext *context,
@@ -204,6 +210,10 @@ static PartClauseMatchStatus match_boolean_partition_clause(Oid partopfamily,
static void partkey_datum_from_expr(PartitionPruneContext *context,
Expr *expr, int stateidx,
Datum *value, bool *isnull);
+static bool contain_forbidden_var_clause(Node *node,
+ GeneratePruningStepsContext *context);
+static bool contain_forbidden_var_clause_walker(Node *node,
+ GeneratePruningStepsContext *context);
/*
@@ -216,11 +226,14 @@ static void partkey_datum_from_expr(PartitionPruneContext *context,
* of scan paths for its child rels.
* 'prunequal' is a list of potential pruning quals (i.e., restriction
* clauses that are applicable to the appendrel).
+ * 'available_rels' is the relid set of rels whose Vars may be used for
+ * pruning.
*/
PartitionPruneInfo *
make_partition_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
List *subpaths,
- List *prunequal)
+ List *prunequal,
+ Bitmapset *available_rels)
{
PartitionPruneInfo *pruneinfo;
Bitmapset *allmatchedsubplans = NULL;
@@ -313,6 +326,7 @@ make_partition_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
prunequal,
partrelids,
relid_subplan_map,
+ available_rels,
&matchedsubplans);
/* When pruning is possible, record the matched subplans */
@@ -360,6 +374,184 @@ make_partition_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
return pruneinfo;
}
+/*
+ * make_join_partition_pruneinfos
+ * Builds one JoinPartitionPruneInfo for each join at which join partition
+ * pruning is possible for this appendrel.
+ *
+ * 'parentrel' is the RelOptInfo for an appendrel, and 'subpaths' is the list
+ * of scan paths for its child rels.
+ */
+Bitmapset *
+make_join_partition_pruneinfos(PlannerInfo *root, RelOptInfo *parentrel,
+ Path *best_path, List *subpaths)
+{
+ Bitmapset *result = NULL;
+ ListCell *lc;
+
+ if (!IS_PARTITIONED_REL(parentrel))
+ return NULL;
+
+ foreach(lc, root->join_partition_prune_candidates)
+ {
+ JoinPartitionPruneCandidateInfo *candidate =
+ (JoinPartitionPruneCandidateInfo *) lfirst(lc);
+ PartitionPruneInfo *part_prune_info;
+ List *prunequal;
+ Relids joinrelids;
+ ListCell *l;
+ double prune_cost;
+
+ if (candidate == NULL)
+ continue;
+
+ /*
+ * Identify all joinclauses that are movable to this appendrel given
+ * this inner side relids. Only those clauses can be used for join
+ * partition pruning.
+ */
+ joinrelids = bms_union(parentrel->relids, candidate->inner_relids);
+ prunequal = NIL;
+ foreach(l, candidate->joinrestrictinfo)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+
+ if (join_clause_is_movable_into(rinfo,
+ parentrel->relids,
+ joinrelids))
+ prunequal = lappend(prunequal, rinfo);
+ }
+
+ if (prunequal == NIL)
+ continue;
+
+ /*
+ * Check the overhead of this pruning
+ */
+ prune_cost = compute_partprune_cost(root,
+ parentrel,
+ best_path->total_cost,
+ list_length(subpaths),
+ candidate->inner_relids,
+ candidate->inner_rows,
+ prunequal);
+ if (prune_cost > 0)
+ continue;
+
+ part_prune_info = make_partition_pruneinfo(root, parentrel,
+ subpaths,
+ prunequal,
+ candidate->inner_relids);
+
+ if (part_prune_info)
+ {
+ JoinPartitionPruneInfo *jpinfo;
+
+ jpinfo = makeNode(JoinPartitionPruneInfo);
+
+ jpinfo->part_prune_info = part_prune_info;
+ jpinfo->paramid = assign_special_exec_param(root);
+ jpinfo->nplans = list_length(subpaths);
+
+ candidate->joinpartprune_info_list =
+ lappend(candidate->joinpartprune_info_list, jpinfo);
+
+ result = bms_add_member(result, jpinfo->paramid);
+ }
+ }
+
+ return result;
+}
+
+/*
+ * prepare_join_partition_prune_candidate
+ * Check if join partition pruning is possible at this join and if so
+ * collect information required to build JoinPartitionPruneInfos.
+ *
+ * Note that we may build more than one JoinPartitionPruneInfo at one join, for
+ * different Append/MergeAppend paths.
+ */
+void
+prepare_join_partition_prune_candidate(PlannerInfo *root, JoinPath *jpath)
+{
+ JoinPartitionPruneCandidateInfo *candidate;
+
+ if (!enable_partition_pruning)
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ /*
+ * For now do not perform join partition pruning for parallel hashjoin.
+ */
+ if (jpath->path.parallel_workers > 0)
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ /*
+ * We cannot perform join partition pruning if the outer is the
+ * non-nullable side.
+ */
+ if (!(jpath->jointype == JOIN_INNER ||
+ jpath->jointype == JOIN_SEMI ||
+ jpath->jointype == JOIN_RIGHT ||
+ jpath->jointype == JOIN_RIGHT_ANTI))
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ /*
+ * For now we only support HashJoin.
+ */
+ if (jpath->path.pathtype != T_HashJoin)
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ candidate = makeNode(JoinPartitionPruneCandidateInfo);
+ candidate->joinrestrictinfo = jpath->joinrestrictinfo;
+ candidate->inner_relids = jpath->innerjoinpath->parent->relids;
+ candidate->inner_rows = jpath->innerjoinpath->parent->rows;
+ candidate->joinpartprune_info_list = NIL;
+
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, candidate);
+}
+
+/*
+ * get_join_partition_prune_candidate
+ * Pop out the JoinPartitionPruneCandidateInfo for this join and retrieve
+ * the JoinPartitionPruneInfos.
+ */
+List *
+get_join_partition_prune_candidate(PlannerInfo *root)
+{
+ JoinPartitionPruneCandidateInfo *candidate;
+ List *result;
+
+ candidate = llast(root->join_partition_prune_candidates);
+ root->join_partition_prune_candidates =
+ list_delete_last(root->join_partition_prune_candidates);
+
+ if (candidate == NULL)
+ return NIL;
+
+ result = candidate->joinpartprune_info_list;
+
+ pfree(candidate);
+
+ return result;
+}
+
/*
* add_part_relids
* Add new info to a list of Bitmapsets of partitioned relids.
@@ -428,6 +620,8 @@ add_part_relids(List *allpartrelids, Bitmapset *partrelids)
* partrelids: Set of RT indexes identifying relevant partitioned tables
* within a single partitioning hierarchy
* relid_subplan_map[]: maps child relation relids to subplan indexes
+ * available_rels: the relid set of rels whose Vars may be used for
+ * pruning.
* matchedsubplans: on success, receives the set of subplan indexes which
* were matched to this partition hierarchy
*
@@ -440,6 +634,7 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
List *prunequal,
Bitmapset *partrelids,
int *relid_subplan_map,
+ Bitmapset *available_rels,
Bitmapset **matchedsubplans)
{
RelOptInfo *targetpart = NULL;
@@ -539,8 +734,8 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
* pruning steps and detects whether there's any possibly-useful quals
* that would require per-scan pruning.
*/
- gen_partprune_steps(subpart, partprunequal, PARTTARGET_INITIAL,
- &context);
+ gen_partprune_steps(subpart, partprunequal, available_rels,
+ PARTTARGET_INITIAL, &context);
if (context.contradictory)
{
@@ -567,14 +762,15 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
initial_pruning_steps = NIL;
/*
- * If no exec Params appear in potentially-usable pruning clauses,
- * then there's no point in even thinking about per-scan pruning.
+ * If no exec Params or available Vars appear in potentially-usable
+ * pruning clauses, then there's no point in even thinking about
+ * per-scan pruning.
*/
- if (context.has_exec_param)
+ if (context.has_exec_param || context.has_vars)
{
/* ... OK, we'd better think about it */
- gen_partprune_steps(subpart, partprunequal, PARTTARGET_EXEC,
- &context);
+ gen_partprune_steps(subpart, partprunequal, available_rels,
+ PARTTARGET_EXEC, &context);
if (context.contradictory)
{
@@ -587,11 +783,14 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
/*
* Detect which exec Params actually got used; the fact that some
* were in available clauses doesn't mean we actually used them.
- * Skip per-scan pruning if there are none.
*/
execparamids = get_partkey_exec_paramids(exec_pruning_steps);
- if (bms_is_empty(execparamids))
+ /*
+ * Skip per-scan pruning if there are none used exec Params and
+ * there are none available Vars.
+ */
+ if (bms_is_empty(execparamids) && !context.has_vars)
exec_pruning_steps = NIL;
}
else
@@ -703,6 +902,9 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
* Process 'clauses' (typically a rel's baserestrictinfo list of clauses)
* and create a list of "partition pruning steps".
*
+ * 'available_rels' is the relid set of rels whose Vars may be used for
+ * pruning.
+ *
* 'target' tells whether to generate pruning steps for planning (use
* immutable clauses only), or for executor startup (use any allowable
* clause except ones containing PARAM_EXEC Params), or for executor
@@ -712,12 +914,13 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
* some subsidiary flags; see the GeneratePruningStepsContext typedef.
*/
static void
-gen_partprune_steps(RelOptInfo *rel, List *clauses, PartClauseTarget target,
- GeneratePruningStepsContext *context)
+gen_partprune_steps(RelOptInfo *rel, List *clauses, Bitmapset *available_rels,
+ PartClauseTarget target, GeneratePruningStepsContext *context)
{
/* Initialize all output values to zero/false/NULL */
memset(context, 0, sizeof(GeneratePruningStepsContext));
context->rel = rel;
+ context->available_rels = available_rels;
context->target = target;
/*
@@ -773,7 +976,7 @@ prune_append_rel_partitions(RelOptInfo *rel)
* If the clauses are found to be contradictory, we can return the empty
* set.
*/
- gen_partprune_steps(rel, clauses, PARTTARGET_PLANNER,
+ gen_partprune_steps(rel, clauses, NULL, PARTTARGET_PLANNER,
&gcontext);
if (gcontext.contradictory)
return NULL;
@@ -1957,9 +2160,10 @@ match_clause_to_partition_key(GeneratePruningStepsContext *context,
return PARTCLAUSE_UNSUPPORTED;
/*
- * We can never prune using an expression that contains Vars.
+ * We can never prune using an expression that contains Vars except
+ * for Vars belonging to context->available_rels.
*/
- if (contain_var_clause((Node *) expr))
+ if (contain_forbidden_var_clause((Node *) expr, context))
return PARTCLAUSE_UNSUPPORTED;
/*
@@ -2155,9 +2359,10 @@ match_clause_to_partition_key(GeneratePruningStepsContext *context,
return PARTCLAUSE_UNSUPPORTED;
/*
- * We can never prune using an expression that contains Vars.
+ * We can never prune using an expression that contains Vars except
+ * for Vars belonging to context->available_rels.
*/
- if (contain_var_clause((Node *) rightop))
+ if (contain_forbidden_var_clause((Node *) rightop, context))
return PARTCLAUSE_UNSUPPORTED;
/*
@@ -3727,3 +3932,54 @@ partkey_datum_from_expr(PartitionPruneContext *context,
*value = ExecEvalExprSwitchContext(exprstate, ectx, isnull);
}
}
+
+/*
+ * contain_forbidden_var_clause
+ * Recursively scan a clause to discover whether it contains any Var nodes
+ * (of the current query level) that do not belong to relations in
+ * context->available_rels.
+ *
+ * Returns true if any such varnode found.
+ *
+ * Does not examine subqueries, therefore must only be used after reduction
+ * of sublinks to subplans!
+ */
+static bool
+contain_forbidden_var_clause(Node *node, GeneratePruningStepsContext *context)
+{
+ return contain_forbidden_var_clause_walker(node, context);
+}
+
+static bool
+contain_forbidden_var_clause_walker(Node *node, GeneratePruningStepsContext *context)
+{
+ if (node == NULL)
+ return false;
+ if (IsA(node, Var))
+ {
+ Var *var = (Var *) node;
+
+ if (var->varlevelsup != 0)
+ return false;
+
+ if (!bms_is_member(var->varno, context->available_rels))
+ return true; /* abort the tree traversal and return true */
+
+ context->has_vars = true;
+
+ if (context->target != PARTTARGET_EXEC)
+ return true; /* abort the tree traversal and return true */
+
+ return false;
+ }
+ if (IsA(node, CurrentOfExpr))
+ return true;
+ if (IsA(node, PlaceHolderVar))
+ {
+ if (((PlaceHolderVar *) node)->phlevelsup == 0)
+ return true; /* abort the tree traversal and return true */
+ /* else fall through to check the contained expr */
+ }
+ return expression_tree_walker(node, contain_forbidden_var_clause_walker,
+ (void *) context);
+}
diff --git a/src/include/executor/execPartition.h b/src/include/executor/execPartition.h
index 15ec869ac8..720bcc1149 100644
--- a/src/include/executor/execPartition.h
+++ b/src/include/executor/execPartition.h
@@ -121,11 +121,26 @@ typedef struct PartitionPruneState
PartitionPruningData *partprunedata[FLEXIBLE_ARRAY_MEMBER];
} PartitionPruneState;
+/*
+ * JoinPartitionPruneState - State object required for plan nodes to perform
+ * join partition pruning.
+ */
+typedef struct JoinPartitionPruneState
+{
+ PartitionPruneState *part_prune_state;
+ int paramid;
+ int nplans;
+ bool finished;
+ Bitmapset *part_prune_result;
+} JoinPartitionPruneState;
+
extern PartitionPruneState *ExecInitPartitionPruning(PlanState *planstate,
int n_total_subplans,
PartitionPruneInfo *pruneinfo,
Bitmapset **initially_valid_subplans);
+extern List *ExecInitJoinpartpruneList(PlanState *planstate, List *joinpartprune_info_list);
extern Bitmapset *ExecFindMatchingSubPlans(PartitionPruneState *prunestate,
- bool initial_prune);
+ bool initial_prune,
+ PlanState *planstate);
#endif /* EXECPARTITION_H */
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 5d7f17dee0..0aeafcabff 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2678,6 +2678,9 @@ typedef struct HashState
/* Parallel hash state. */
struct ParallelHashJoinState *parallel_state;
+
+ /* Infos for join partition pruning. */
+ List *joinpartprune_state_list;
} HashState;
/* ----------------
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index ed85dc7414..d066b6105c 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -530,6 +530,9 @@ struct PlannerInfo
/* not-yet-assigned NestLoopParams */
List *curOuterParams;
+ /* a stack of JoinPartitionPruneInfos */
+ List *join_partition_prune_candidates;
+
/*
* These fields are workspace for setrefs.c. Each is an array
* corresponding to glob->subplans. (We could probably teach
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 24d46c76dc..00058a735e 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -276,6 +276,9 @@ typedef struct Append
/* Info for run-time subplan pruning; NULL if we're not doing that */
struct PartitionPruneInfo *part_prune_info;
+
+ /* Info for join partition pruning; NULL if we're not doing that */
+ Bitmapset *join_prune_paramids;
} Append;
/* ----------------
@@ -311,6 +314,9 @@ typedef struct MergeAppend
/* Info for run-time subplan pruning; NULL if we're not doing that */
struct PartitionPruneInfo *part_prune_info;
+
+ /* Info for join partition pruning; NULL if we're not doing that */
+ Bitmapset *join_prune_paramids;
} MergeAppend;
/* ----------------
@@ -1207,6 +1213,7 @@ typedef struct Hash
bool skewInherit; /* is outer join rel an inheritance tree? */
/* all other info is in the parent HashJoin node */
Cardinality rows_total; /* estimate total rows if parallel_aware */
+ List *joinpartprune_info_list; /* infos for join partition pruning */
} Hash;
/* ----------------
@@ -1553,6 +1560,35 @@ typedef struct PartitionPruneStepCombine
List *source_stepids;
} PartitionPruneStepCombine;
+/*
+ * JoinPartitionPruneCandidateInfo - Information required to build
+ * JoinPartitionPruneInfos.
+ */
+typedef struct JoinPartitionPruneCandidateInfo
+{
+ pg_node_attr(no_equal, no_query_jumble)
+
+ NodeTag type;
+ List *joinrestrictinfo;
+ Bitmapset *inner_relids;
+ double inner_rows;
+ List *joinpartprune_info_list;
+} JoinPartitionPruneCandidateInfo;
+
+/*
+ * JoinPartitionPruneInfo - Details required to allow the executor to prune
+ * partitions during join.
+ */
+typedef struct JoinPartitionPruneInfo
+{
+ pg_node_attr(no_equal, no_query_jumble)
+
+ NodeTag type;
+ PartitionPruneInfo *part_prune_info;
+ int paramid;
+ int nplans;
+} JoinPartitionPruneInfo;
+
/*
* Plan invalidation info
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 6d50afbf74..52de844f6d 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -211,5 +211,9 @@ extern void set_foreign_size_estimates(PlannerInfo *root, RelOptInfo *rel);
extern PathTarget *set_pathtarget_cost_width(PlannerInfo *root, PathTarget *target);
extern double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel,
Path *bitmapqual, int loop_count, Cost *cost, double *tuple);
+extern double compute_partprune_cost(PlannerInfo *root, RelOptInfo *appendrel,
+ Cost append_total_cost, int append_nplans,
+ Relids inner_relids, double inner_rows,
+ List *prunequal);
#endif /* COST_H */
diff --git a/src/include/partitioning/partprune.h b/src/include/partitioning/partprune.h
index 8636e04e37..899aa61b34 100644
--- a/src/include/partitioning/partprune.h
+++ b/src/include/partitioning/partprune.h
@@ -19,6 +19,8 @@
struct PlannerInfo; /* avoid including pathnodes.h here */
struct RelOptInfo;
+struct Path;
+struct JoinPath;
/*
@@ -73,7 +75,15 @@ typedef struct PartitionPruneContext
extern PartitionPruneInfo *make_partition_pruneinfo(struct PlannerInfo *root,
struct RelOptInfo *parentrel,
List *subpaths,
- List *prunequal);
+ List *prunequal,
+ Bitmapset *available_rels);
+extern Bitmapset *make_join_partition_pruneinfos(struct PlannerInfo *root,
+ struct RelOptInfo *parentrel,
+ struct Path *best_path,
+ List *subpaths);
+extern void prepare_join_partition_prune_candidate(struct PlannerInfo *root,
+ struct JoinPath *jpath);
+extern List *get_join_partition_prune_candidate(struct PlannerInfo *root);
extern Bitmapset *prune_append_rel_partitions(struct RelOptInfo *rel);
extern Bitmapset *get_matching_partitions(PartitionPruneContext *context,
List *pruning_steps);
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 9a4c48c055..a08e7a1f0a 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -3003,6 +3003,92 @@ order by tbl1.col1, tprt.col1;
------+------
(0 rows)
+-- join partition pruning
+-- The 'Memory Usage' from the Hash node can vary between machines. Let's just
+-- replace the number with an 'N'.
+-- We need to run EXPLAIN ANALYZE because we need to see '(never executed)'
+-- notations because that's the only way to verify runtime pruning.
+create function explain_join_partition_pruning(text) returns setof text
+language plpgsql as
+$$
+declare
+ ln text;
+begin
+ for ln in
+ execute format('explain (analyze, verbose, costs off, summary off, timing off) %s',
+ $1)
+ loop
+ ln := regexp_replace(ln, 'Memory Usage: \d+', 'Memory Usage: N');
+ return next ln;
+ end loop;
+end;
+$$;
+delete from tbl1;
+insert into tbl1 values (501), (505);
+analyze tbl1, tprt;
+set enable_nestloop = off;
+set enable_mergejoin = off;
+set enable_hashjoin = on;
+select explain_join_partition_pruning('
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;');
+ explain_join_partition_pruning
+--------------------------------------------------------------------------------
+ Hash Right Join (actual rows=2 loops=1)
+ Output: p1.col1, p2.col1, t.col1
+ Hash Cond: ((p1.col1 = t.col1) AND (p2.col1 = t.col1))
+ -> Hash Join (actual rows=3 loops=1)
+ Output: p1.col1, p2.col1
+ Hash Cond: (p1.col1 = p2.col1)
+ -> Append (actual rows=3 loops=1)
+ Join Partition Pruning: $0
+ -> Seq Scan on public.tprt_1 p1_1 (never executed)
+ Output: p1_1.col1
+ -> Seq Scan on public.tprt_2 p1_2 (actual rows=3 loops=1)
+ Output: p1_2.col1
+ -> Seq Scan on public.tprt_3 p1_3 (never executed)
+ Output: p1_3.col1
+ -> Seq Scan on public.tprt_4 p1_4 (never executed)
+ Output: p1_4.col1
+ -> Seq Scan on public.tprt_5 p1_5 (never executed)
+ Output: p1_5.col1
+ -> Seq Scan on public.tprt_6 p1_6 (never executed)
+ Output: p1_6.col1
+ -> Hash (actual rows=3 loops=1)
+ Output: p2.col1
+ Buckets: 1024 Batches: 1 Memory Usage: NkB
+ -> Append (actual rows=3 loops=1)
+ Join Partition Pruning: $1
+ -> Seq Scan on public.tprt_1 p2_1 (never executed)
+ Output: p2_1.col1
+ -> Seq Scan on public.tprt_2 p2_2 (actual rows=3 loops=1)
+ Output: p2_2.col1
+ -> Seq Scan on public.tprt_3 p2_3 (never executed)
+ Output: p2_3.col1
+ -> Seq Scan on public.tprt_4 p2_4 (never executed)
+ Output: p2_4.col1
+ -> Seq Scan on public.tprt_5 p2_5 (never executed)
+ Output: p2_5.col1
+ -> Seq Scan on public.tprt_6 p2_6 (never executed)
+ Output: p2_6.col1
+ -> Hash (actual rows=2 loops=1)
+ Output: t.col1
+ Buckets: 1024 Batches: 1 Memory Usage: NkB
+ Partition Prune: $0, $1
+ -> Seq Scan on public.tbl1 t (actual rows=2 loops=1)
+ Output: t.col1
+(43 rows)
+
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;
+ col1 | col1 | col1
+------+------+------
+ 501 | 501 | 501
+ 505 | 505 | 505
+(2 rows)
+
drop table tbl1, tprt;
-- Test with columns defined in varying orders between each level
create table part_abc (a int not null, b int not null, c int not null) partition by list (a);
diff --git a/src/test/regress/sql/partition_prune.sql b/src/test/regress/sql/partition_prune.sql
index 7bf3920827..fc5982edcf 100644
--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
@@ -727,6 +727,45 @@ select tbl1.col1, tprt.col1 from tbl1
inner join tprt on tbl1.col1 = tprt.col1
order by tbl1.col1, tprt.col1;
+-- join partition pruning
+
+-- The 'Memory Usage' from the Hash node can vary between machines. Let's just
+-- replace the number with an 'N'.
+-- We need to run EXPLAIN ANALYZE because we need to see '(never executed)'
+-- notations because that's the only way to verify runtime pruning.
+create function explain_join_partition_pruning(text) returns setof text
+language plpgsql as
+$$
+declare
+ ln text;
+begin
+ for ln in
+ execute format('explain (analyze, verbose, costs off, summary off, timing off) %s',
+ $1)
+ loop
+ ln := regexp_replace(ln, 'Memory Usage: \d+', 'Memory Usage: N');
+ return next ln;
+ end loop;
+end;
+$$;
+
+delete from tbl1;
+insert into tbl1 values (501), (505);
+analyze tbl1, tprt;
+
+set enable_nestloop = off;
+set enable_mergejoin = off;
+set enable_hashjoin = on;
+
+select explain_join_partition_pruning('
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;');
+
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;
+
drop table tbl1, tprt;
-- Test with columns defined in varying orders between each level
--
2.31.0
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Support run-time partition pruning for hash join
2023-11-07 07:55 Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
@ 2024-01-27 03:29 ` vignesh C <[email protected]>
2024-01-30 02:33 ` Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
0 siblings, 1 reply; 6+ messages in thread
From: vignesh C @ 2024-01-27 03:29 UTC (permalink / raw)
To: Richard Guo <[email protected]>; +Cc: Alexander Lakhin <[email protected]>; David Rowley <[email protected]>; Andy Fan <[email protected]>; pgsql-hackers
On Tue, 7 Nov 2023 at 13:25, Richard Guo <[email protected]> wrote:
>
>
> On Mon, Nov 6, 2023 at 11:00 PM Alexander Lakhin <[email protected]> wrote:
>>
>> Please look at a warning and an assertion failure triggered by the
>> following script:
>> set parallel_setup_cost = 0;
>> set parallel_tuple_cost = 0;
>> set min_parallel_table_scan_size = '1kB';
>>
>> create table t1 (i int) partition by range (i);
>> create table t1_1 partition of t1 for values from (1) to (2);
>> create table t1_2 partition of t1 for values from (2) to (3);
>> insert into t1 values (1), (2);
>>
>> create table t2(i int);
>> insert into t2 values (1), (2);
>> analyze t1, t2;
>>
>> select * from t1 right join t2 on t1.i = t2.i;
>>
>> 2023-11-06 14:11:37.398 UTC|law|regression|6548f419.392cf5|WARNING: Join partition pruning $0 has not been performed yet.
>> TRAP: failed Assert("node->as_prune_state"), File: "nodeAppend.c", Line: 846, PID: 3747061
>
>
> Thanks for the report! I failed to take care of the parallel-hashjoin
> case, and I have to admit that it's not clear to me yet how we should do
> join partition pruning in that case.
>
> For now I think it's better to just avoid performing join partition
> pruning for parallel hashjoin, so that the patch doesn't become too
> complex for review. We can always extend it in the future.
>
> I have done that in v5. Thanks for testing!
CFBot shows that the patch does not apply anymore as in [1]:
=== Applying patches on top of PostgreSQL commit ID
924d046dcf55887c98a1628675a30f4b0eebe556 ===
=== applying patch
./v5-0001-Support-run-time-partition-pruning-for-hash-join.patch
...
patching file src/include/nodes/plannodes.h
...
patching file src/include/optimizer/cost.h
Hunk #1 FAILED at 211.
1 out of 1 hunk FAILED -- saving rejects to file
src/include/optimizer/cost.h.rej
Please post an updated version for the same.
[1] - http://cfbot.cputube.org/patch_46_4512.log
Regards,
Vignesh
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Support run-time partition pruning for hash join
2023-11-07 07:55 Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
2024-01-27 03:29 ` Re: Support run-time partition pruning for hash join vignesh C <[email protected]>
@ 2024-01-30 02:33 ` Richard Guo <[email protected]>
2024-03-19 06:12 ` Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
0 siblings, 1 reply; 6+ messages in thread
From: Richard Guo @ 2024-01-30 02:33 UTC (permalink / raw)
To: vignesh C <[email protected]>; +Cc: Alexander Lakhin <[email protected]>; David Rowley <[email protected]>; Andy Fan <[email protected]>; pgsql-hackers
On Sat, Jan 27, 2024 at 11:29 AM vignesh C <[email protected]> wrote:
> CFBot shows that the patch does not apply anymore as in [1]:
>
> Please post an updated version for the same.
Attached is an updated patch. Nothing else has changed.
Thanks
Richard
Attachments:
[application/octet-stream] v6-0001-Support-run-time-partition-pruning-for-hash-join.patch (59.3K, ../../CAMbWs49Pg9TvDrWBHzBDNPe7XP1jTpHukG-nwpNEo-mmr9h4zA@mail.gmail.com/3-v6-0001-Support-run-time-partition-pruning-for-hash-join.patch)
download | inline diff:
From 05d18d47135ba086fe416c02abdaa44b69612c03 Mon Sep 17 00:00:00 2001
From: Richard Guo <[email protected]>
Date: Mon, 14 Aug 2023 14:55:26 +0800
Subject: [PATCH v6] Support run-time partition pruning for hash join
If we have a hash join with an Append node on the outer side, something
like
Hash Join
Hash Cond: (pt.a = t.a)
-> Append
-> Seq Scan on pt_p1 pt_1
-> Seq Scan on pt_p2 pt_2
-> Seq Scan on pt_p3 pt_3
-> Hash
-> Seq Scan on t
We can actually prune those subnodes of the Append that cannot possibly
contain any matching tuples from the other side of the join. To do
that, when building the Hash table, for each row from the inner side we
can compute the minimum set of subnodes that can possibly match the join
condition. When we have built the Hash table and start to execute the
Append node, we should have known which subnodes are survived and thus
can skip other subnodes.
This patch implements this idea.
---
src/backend/commands/explain.c | 61 ++++
src/backend/executor/execPartition.c | 127 +++++++-
src/backend/executor/nodeAppend.c | 32 +-
src/backend/executor/nodeHash.c | 75 +++++
src/backend/executor/nodeHashjoin.c | 10 +
src/backend/executor/nodeMergeAppend.c | 22 +-
src/backend/optimizer/path/costsize.c | 106 +++++++
src/backend/optimizer/plan/createplan.c | 49 ++-
src/backend/optimizer/plan/setrefs.c | 61 ++++
src/backend/partitioning/partprune.c | 298 ++++++++++++++++--
src/include/executor/execPartition.h | 17 +-
src/include/nodes/execnodes.h | 3 +
src/include/nodes/pathnodes.h | 3 +
src/include/nodes/plannodes.h | 36 +++
src/include/optimizer/cost.h | 4 +
src/include/partitioning/partprune.h | 12 +-
src/test/regress/expected/partition_prune.out | 86 +++++
src/test/regress/sql/partition_prune.sql | 39 +++
18 files changed, 992 insertions(+), 49 deletions(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 83d00a4663..04450b9c37 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -18,6 +18,7 @@
#include "commands/createas.h"
#include "commands/defrem.h"
#include "commands/prepare.h"
+#include "executor/execPartition.h"
#include "executor/nodeHash.h"
#include "foreign/fdwapi.h"
#include "jit/jit.h"
@@ -118,6 +119,9 @@ static void show_instrumentation_count(const char *qlabel, int which,
PlanState *planstate, ExplainState *es);
static void show_foreignscan_info(ForeignScanState *fsstate, ExplainState *es);
static void show_eval_params(Bitmapset *bms_params, ExplainState *es);
+static void show_join_pruning_result_info(Bitmapset *join_prune_paramids,
+ ExplainState *es);
+static void show_joinpartprune_info(HashState *hashstate, ExplainState *es);
static const char *explain_get_index_name(Oid indexId);
static bool peek_buffer_usage(ExplainState *es, const BufferUsage *usage);
static void show_buffer_usage(ExplainState *es, const BufferUsage *usage);
@@ -2104,9 +2108,17 @@ ExplainNode(PlanState *planstate, List *ancestors,
show_incremental_sort_info(castNode(IncrementalSortState, planstate),
es);
break;
+ case T_Append:
+ if (es->verbose)
+ show_join_pruning_result_info(((Append *) plan)->join_prune_paramids,
+ es);
+ break;
case T_MergeAppend:
show_merge_append_keys(castNode(MergeAppendState, planstate),
ancestors, es);
+ if (es->verbose)
+ show_join_pruning_result_info(((MergeAppend *) plan)->join_prune_paramids,
+ es);
break;
case T_Result:
show_upper_qual((List *) ((Result *) plan)->resconstantqual,
@@ -2122,6 +2134,8 @@ ExplainNode(PlanState *planstate, List *ancestors,
break;
case T_Hash:
show_hash_info(castNode(HashState, planstate), es);
+ if (es->verbose)
+ show_joinpartprune_info(castNode(HashState, planstate), es);
break;
case T_Memoize:
show_memoize_info(castNode(MemoizeState, planstate), ancestors,
@@ -3562,6 +3576,53 @@ show_eval_params(Bitmapset *bms_params, ExplainState *es)
ExplainPropertyList("Params Evaluated", params, es);
}
+/*
+ * Show join partition pruning results at Append/MergeAppend nodes.
+ */
+static void
+show_join_pruning_result_info(Bitmapset *join_prune_paramids, ExplainState *es)
+{
+ int paramid = -1;
+ List *params = NIL;
+
+ if (bms_is_empty(join_prune_paramids))
+ return;
+
+ while ((paramid = bms_next_member(join_prune_paramids, paramid)) >= 0)
+ {
+ char param[32];
+
+ snprintf(param, sizeof(param), "$%d", paramid);
+ params = lappend(params, pstrdup(param));
+ }
+
+ ExplainPropertyList("Join Partition Pruning", params, es);
+}
+
+/*
+ * Show join partition pruning infos at Hash nodes.
+ */
+static void
+show_joinpartprune_info(HashState *hashstate, ExplainState *es)
+{
+ List *params = NIL;
+ ListCell *lc;
+
+ if (!hashstate->joinpartprune_state_list)
+ return;
+
+ foreach(lc, hashstate->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+ char param[32];
+
+ snprintf(param, sizeof(param), "$%d", jpstate->paramid);
+ params = lappend(params, pstrdup(param));
+ }
+
+ ExplainPropertyList("Partition Prune", params, es);
+}
+
/*
* Fetch the name of an index in an EXPLAIN
*
diff --git a/src/backend/executor/execPartition.c b/src/backend/executor/execPartition.c
index b22040ae8e..95c791633c 100644
--- a/src/backend/executor/execPartition.c
+++ b/src/backend/executor/execPartition.c
@@ -199,6 +199,8 @@ static void find_matching_subplans_recurse(PartitionPruningData *prunedata,
PartitionedRelPruningData *pprune,
bool initial_prune,
Bitmapset **validsubplans);
+static bool get_join_prune_matching_subplans(PlanState *planstate,
+ Bitmapset **partset);
/*
@@ -1806,7 +1808,7 @@ ExecInitPartitionPruning(PlanState *planstate,
* Perform an initial partition prune pass, if required.
*/
if (prunestate->do_initial_prune)
- *initially_valid_subplans = ExecFindMatchingSubPlans(prunestate, true);
+ *initially_valid_subplans = ExecFindMatchingSubPlans(prunestate, true, NULL);
else
{
/* No pruning, so we'll need to initialize all subplans */
@@ -1836,6 +1838,37 @@ ExecInitPartitionPruning(PlanState *planstate,
return prunestate;
}
+/*
+ * ExecInitJoinpartpruneList
+ * Initialize data structures needed for join partition pruning
+ */
+List *
+ExecInitJoinpartpruneList(PlanState *planstate,
+ List *joinpartprune_info_list)
+{
+ ListCell *lc;
+ List *result = NIL;
+
+ foreach(lc, joinpartprune_info_list)
+ {
+ JoinPartitionPruneInfo *jpinfo = (JoinPartitionPruneInfo *) lfirst(lc);
+ JoinPartitionPruneState *jpstate = palloc(sizeof(JoinPartitionPruneState));
+
+ jpstate->part_prune_state =
+ CreatePartitionPruneState(planstate, jpinfo->part_prune_info);
+ Assert(jpstate->part_prune_state->do_exec_prune);
+
+ jpstate->paramid = jpinfo->paramid;
+ jpstate->nplans = jpinfo->nplans;
+ jpstate->finished = false;
+ jpstate->part_prune_result = NULL;
+
+ result = lappend(result, jpstate);
+ }
+
+ return result;
+}
+
/*
* CreatePartitionPruneState
* Build the data structure required for calling ExecFindMatchingSubPlans
@@ -2273,7 +2306,9 @@ PartitionPruneFixSubPlanMap(PartitionPruneState *prunestate,
/*
* ExecFindMatchingSubPlans
* Determine which subplans match the pruning steps detailed in
- * 'prunestate' for the current comparison expression values.
+ * 'prunestate' if any for the current comparison expression values, and
+ * meanwhile match the join partition pruning results if any stored in
+ * Append/MergeAppend node's join_prune_paramids.
*
* Pass initial_prune if PARAM_EXEC Params cannot yet be evaluated. This
* differentiates the initial executor-time pruning step from later
@@ -2281,11 +2316,30 @@ PartitionPruneFixSubPlanMap(PartitionPruneState *prunestate,
*/
Bitmapset *
ExecFindMatchingSubPlans(PartitionPruneState *prunestate,
- bool initial_prune)
+ bool initial_prune,
+ PlanState *planstate)
{
Bitmapset *result = NULL;
MemoryContext oldcontext;
int i;
+ Bitmapset *join_prune_partset = NULL;
+ bool do_join_prune;
+
+ /* Retrieve the join partition pruning results if any */
+ do_join_prune =
+ get_join_prune_matching_subplans(planstate, &join_prune_partset);
+
+ /*
+ * Either we're here on partition prune done according to the pruning steps
+ * detailed in 'prunestate', or we have done join partition prune.
+ */
+ Assert(do_join_prune || prunestate != NULL);
+
+ /*
+ * If there is no 'prunestate', then rely entirely on join pruning.
+ */
+ if (prunestate == NULL)
+ return join_prune_partset;
/*
* Either we're here on the initial prune done during pruning
@@ -2326,6 +2380,10 @@ ExecFindMatchingSubPlans(PartitionPruneState *prunestate,
/* Add in any subplans that partition pruning didn't account for */
result = bms_add_members(result, prunestate->other_subplans);
+ /* Intersect join partition pruning results */
+ if (do_join_prune)
+ result = bms_intersect(result, join_prune_partset);
+
MemoryContextSwitchTo(oldcontext);
/* Copy result out of the temp context before we reset it */
@@ -2396,3 +2454,66 @@ find_matching_subplans_recurse(PartitionPruningData *prunedata,
}
}
}
+
+/*
+ * get_join_prune_matching_subplans
+ * Retrieve the join partition pruning results if any stored in
+ * Append/MergeAppend node's join_prune_paramids. Return true if we can
+ * do join partition pruning, otherwise return false.
+ *
+ * Adds valid (non-prunable) subplan IDs to *partset
+ */
+static bool
+get_join_prune_matching_subplans(PlanState *planstate, Bitmapset **partset)
+{
+ Bitmapset *join_prune_paramids;
+ int nplans;
+ int paramid;
+
+ if (planstate == NULL)
+ return false;
+
+ if (IsA(planstate, AppendState))
+ {
+ join_prune_paramids =
+ ((Append *) planstate->plan)->join_prune_paramids;
+ nplans = ((AppendState *) planstate)->as_nplans;
+ }
+ else if (IsA(planstate, MergeAppendState))
+ {
+ join_prune_paramids =
+ ((MergeAppend *) planstate->plan)->join_prune_paramids;
+ nplans = ((MergeAppendState *) planstate)->ms_nplans;
+ }
+ else
+ {
+ elog(ERROR, "unrecognized node type: %d", (int) nodeTag(planstate));
+ return false;
+ }
+
+ if (bms_is_empty(join_prune_paramids))
+ return false;
+
+ Assert(nplans > 0);
+ *partset = bms_add_range(NULL, 0, nplans - 1);
+
+ paramid = -1;
+ while ((paramid = bms_next_member(join_prune_paramids, paramid)) >= 0)
+ {
+ ParamExecData *param;
+ JoinPartitionPruneState *jpstate;
+
+ param = &(planstate->state->es_param_exec_vals[paramid]);
+ Assert(param->execPlan == NULL);
+ Assert(!param->isnull);
+ jpstate = (JoinPartitionPruneState *) DatumGetPointer(param->value);
+
+ if (jpstate != NULL)
+ *partset = bms_intersect(*partset, jpstate->part_prune_result);
+ else /* the Hash node for this pruning has not been executed */
+ elog(WARNING, "Join partition pruning $%d has not been performed yet.",
+ paramid);
+ }
+
+ return true;
+}
diff --git a/src/backend/executor/nodeAppend.c b/src/backend/executor/nodeAppend.c
index c7059e7528..b68a1e2eb2 100644
--- a/src/backend/executor/nodeAppend.c
+++ b/src/backend/executor/nodeAppend.c
@@ -151,11 +151,13 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
nplans = bms_num_members(validsubplans);
/*
- * When no run-time pruning is required and there's at least one
- * subplan, we can fill as_valid_subplans immediately, preventing
- * later calls to ExecFindMatchingSubPlans.
+ * When no run-time pruning or join pruning is required and there's at
+ * least one subplan, we can fill as_valid_subplans immediately,
+ * preventing later calls to ExecFindMatchingSubPlans.
*/
- if (!prunestate->do_exec_prune && nplans > 0)
+ if (!prunestate->do_exec_prune &&
+ bms_is_empty(node->join_prune_paramids) &&
+ nplans > 0)
{
appendstate->as_valid_subplans = bms_add_range(NULL, 0, nplans - 1);
appendstate->as_valid_subplans_identified = true;
@@ -170,10 +172,18 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
* subplans as valid; they must also all be initialized.
*/
Assert(nplans > 0);
- appendstate->as_valid_subplans = validsubplans =
- bms_add_range(NULL, 0, nplans - 1);
- appendstate->as_valid_subplans_identified = true;
+ validsubplans = bms_add_range(NULL, 0, nplans - 1);
appendstate->as_prune_state = NULL;
+
+ /*
+ * When join pruning is not enabled we can fill as_valid_subplans
+ * immediately, preventing later calls to ExecFindMatchingSubPlans.
+ */
+ if (bms_is_empty(node->join_prune_paramids))
+ {
+ appendstate->as_valid_subplans = validsubplans;
+ appendstate->as_valid_subplans_identified = true;
+ }
}
/*
@@ -580,7 +590,7 @@ choose_next_subplan_locally(AppendState *node)
else if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
}
@@ -647,7 +657,7 @@ choose_next_subplan_for_leader(AppendState *node)
if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
/*
@@ -723,7 +733,7 @@ choose_next_subplan_for_worker(AppendState *node)
else if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
mark_invalid_subplans_as_finished(node);
@@ -876,7 +886,7 @@ ExecAppendAsyncBegin(AppendState *node)
if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
classify_matching_subplans(node);
diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index f90e16ede8..00138a61a2 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -31,6 +31,7 @@
#include "catalog/pg_statistic.h"
#include "commands/tablespace.h"
#include "executor/execdebug.h"
+#include "executor/execPartition.h"
#include "executor/hashjoin.h"
#include "executor/nodeHash.h"
#include "executor/nodeHashjoin.h"
@@ -48,6 +49,8 @@ static void ExecHashIncreaseNumBatches(HashJoinTable hashtable);
static void ExecHashIncreaseNumBuckets(HashJoinTable hashtable);
static void ExecParallelHashIncreaseNumBatches(HashJoinTable hashtable);
static void ExecParallelHashIncreaseNumBuckets(HashJoinTable hashtable);
+static void ExecJoinPartitionPrune(HashState *node);
+static void ExecStoreJoinPartitionPruneResult(HashState *node);
static void ExecHashBuildSkewHash(HashJoinTable hashtable, Hash *node,
int mcvsToUse);
static void ExecHashSkewTableInsert(HashJoinTable hashtable,
@@ -189,8 +192,14 @@ MultiExecPrivateHash(HashState *node)
}
hashtable->totalTuples += 1;
}
+
+ /* Perform join partition pruning */
+ ExecJoinPartitionPrune(node);
}
+ /* Store the surviving partitions for Append/MergeAppend nodes */
+ ExecStoreJoinPartitionPruneResult(node);
+
/* resize the hash table if needed (NTUP_PER_BUCKET exceeded) */
if (hashtable->nbuckets != hashtable->nbuckets_optimal)
ExecHashIncreaseNumBuckets(hashtable);
@@ -401,6 +410,12 @@ ExecInitHash(Hash *node, EState *estate, int eflags)
hashstate->hashkeys =
ExecInitExprList(node->hashkeys, (PlanState *) hashstate);
+ /*
+ * initialize join partition pruning infos
+ */
+ hashstate->joinpartprune_state_list =
+ ExecInitJoinpartpruneList(&hashstate->ps, node->joinpartprune_info_list);
+
return hashstate;
}
@@ -1610,6 +1625,56 @@ ExecParallelHashIncreaseNumBuckets(HashJoinTable hashtable)
}
}
+/*
+ * ExecJoinPartitionPrune
+ * Perform join partition pruning at this join for each
+ * JoinPartitionPruneState.
+ */
+static void
+ExecJoinPartitionPrune(HashState *node)
+{
+ ListCell *lc;
+
+ foreach(lc, node->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+ Bitmapset *matching_subPlans;
+
+ if (jpstate->finished)
+ continue;
+
+ matching_subPlans =
+ ExecFindMatchingSubPlans(jpstate->part_prune_state, false, NULL);
+ jpstate->part_prune_result =
+ bms_add_members(jpstate->part_prune_result, matching_subPlans);
+
+ if (bms_num_members(jpstate->part_prune_result) == jpstate->nplans)
+ jpstate->finished = true;
+ }
+}
+
+/*
+ * ExecStoreJoinPartitionPruneResult
+ * For each JoinPartitionPruneState, store the set of surviving partitions
+ * to make it available for the Append/MergeAppend node.
+ */
+static void
+ExecStoreJoinPartitionPruneResult(HashState *node)
+{
+ ListCell *lc;
+
+ foreach(lc, node->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+ ParamExecData *param;
+
+ param = &(node->ps.state->es_param_exec_vals[jpstate->paramid]);
+ Assert(param->execPlan == NULL);
+ Assert(!param->isnull);
+ param->value = PointerGetDatum(jpstate);
+ }
+}
+
/*
* ExecHashTableInsert
* insert a tuple into the hash table depending on the hash value
@@ -2354,6 +2419,16 @@ void
ExecReScanHash(HashState *node)
{
PlanState *outerPlan = outerPlanState(node);
+ ListCell *lc;
+
+ /* reset the state in JoinPartitionPruneStates */
+ foreach(lc, node->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+
+ jpstate->finished = false;
+ jpstate->part_prune_result = NULL;
+ }
/*
* if chgParam of subnode is not null then plan will be re-scanned by
diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c
index 1cbec4647c..4f84799929 100644
--- a/src/backend/executor/nodeHashjoin.c
+++ b/src/backend/executor/nodeHashjoin.c
@@ -311,6 +311,16 @@ ExecHashJoinImpl(PlanState *pstate, bool parallel)
*/
node->hj_FirstOuterTupleSlot = NULL;
}
+ else if (hashNode->joinpartprune_state_list != NIL)
+ {
+ /*
+ * Give the hash node a chance to run join partition
+ * pruning if there is any JoinPartitionPruneState that can
+ * be evaluated at it. So do not apply the empty-outer
+ * optimization in this case.
+ */
+ node->hj_FirstOuterTupleSlot = NULL;
+ }
else if (HJ_FILL_OUTER(node) ||
(outerNode->plan->startup_cost < hashNode->ps.plan->total_cost &&
!node->hj_OuterNotEmpty))
diff --git a/src/backend/executor/nodeMergeAppend.c b/src/backend/executor/nodeMergeAppend.c
index 0817868452..ec0ac29654 100644
--- a/src/backend/executor/nodeMergeAppend.c
+++ b/src/backend/executor/nodeMergeAppend.c
@@ -99,11 +99,13 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
nplans = bms_num_members(validsubplans);
/*
- * When no run-time pruning is required and there's at least one
- * subplan, we can fill ms_valid_subplans immediately, preventing
- * later calls to ExecFindMatchingSubPlans.
+ * When no run-time pruning or join pruning is required and there's at
+ * least one subplan, we can fill ms_valid_subplans immediately,
+ * preventing later calls to ExecFindMatchingSubPlans.
*/
- if (!prunestate->do_exec_prune && nplans > 0)
+ if (!prunestate->do_exec_prune &&
+ bms_is_empty(node->join_prune_paramids) &&
+ nplans > 0)
mergestate->ms_valid_subplans = bms_add_range(NULL, 0, nplans - 1);
}
else
@@ -115,9 +117,15 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
* subplans as valid; they must also all be initialized.
*/
Assert(nplans > 0);
- mergestate->ms_valid_subplans = validsubplans =
- bms_add_range(NULL, 0, nplans - 1);
+ validsubplans = bms_add_range(NULL, 0, nplans - 1);
mergestate->ms_prune_state = NULL;
+
+ /*
+ * When join pruning is not enabled we can fill ms_valid_subplans
+ * immediately, preventing later calls to ExecFindMatchingSubPlans.
+ */
+ if (bms_is_empty(node->join_prune_paramids))
+ mergestate->ms_valid_subplans = validsubplans;
}
mergeplanstates = (PlanState **) palloc(nplans * sizeof(PlanState *));
@@ -218,7 +226,7 @@ ExecMergeAppend(PlanState *pstate)
*/
if (node->ms_valid_subplans == NULL)
node->ms_valid_subplans =
- ExecFindMatchingSubPlans(node->ms_prune_state, false);
+ ExecFindMatchingSubPlans(node->ms_prune_state, false, &node->ps);
/*
* First time through: pull the first tuple from each valid subplan,
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 8b76e98529..ea3d5e57c1 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -173,6 +173,10 @@ static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel,
static bool has_indexed_join_quals(NestPath *path);
static double approx_tuple_count(PlannerInfo *root, JoinPath *path,
List *quals);
+static double get_joinrel_matching_outer_size(PlannerInfo *root,
+ RelOptInfo *outer_rel,
+ Relids inner_relids,
+ List *restrictlist);
static double calc_joinrel_size_estimate(PlannerInfo *root,
RelOptInfo *joinrel,
RelOptInfo *outer_rel,
@@ -5409,6 +5413,61 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
return nrows;
}
+/*
+ * get_joinrel_matching_outer_size
+ * Make a size estimate for the outer side that matches the inner side.
+ */
+static double
+get_joinrel_matching_outer_size(PlannerInfo *root,
+ RelOptInfo *outer_rel,
+ Relids inner_relids,
+ List *restrictlist)
+{
+ double nrows;
+ Selectivity fkselec;
+ Selectivity jselec;
+ SpecialJoinInfo *sjinfo;
+ SpecialJoinInfo sjinfo_data;
+
+ sjinfo = &sjinfo_data;
+ sjinfo->type = T_SpecialJoinInfo;
+ sjinfo->min_lefthand = outer_rel->relids;
+ sjinfo->min_righthand = inner_relids;
+ sjinfo->syn_lefthand = outer_rel->relids;
+ sjinfo->syn_righthand = inner_relids;
+ sjinfo->jointype = JOIN_SEMI;
+ sjinfo->ojrelid = 0;
+ sjinfo->commute_above_l = NULL;
+ sjinfo->commute_above_r = NULL;
+ sjinfo->commute_below_l = NULL;
+ sjinfo->commute_below_r = NULL;
+ /* we don't bother trying to make the remaining fields valid */
+ sjinfo->lhs_strict = false;
+ sjinfo->semi_can_btree = false;
+ sjinfo->semi_can_hash = false;
+ sjinfo->semi_operators = NIL;
+ sjinfo->semi_rhs_exprs = NIL;
+
+ fkselec = get_foreign_key_join_selectivity(root,
+ outer_rel->relids,
+ inner_relids,
+ sjinfo,
+ &restrictlist);
+ jselec = clauselist_selectivity(root,
+ restrictlist,
+ 0,
+ sjinfo->jointype,
+ sjinfo);
+
+ nrows = outer_rel->rows * fkselec * jselec;
+ nrows = clamp_row_est(nrows);
+
+ /* For safety, make sure result is not more than the base estimate */
+ if (nrows > outer_rel->rows)
+ nrows = outer_rel->rows;
+ return nrows;
+}
+
/*
* calc_joinrel_size_estimate
* Workhorse for set_joinrel_size_estimates and
@@ -6530,3 +6589,50 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel,
return pages_fetched;
}
+
+/*
+ * compute_partprune_cost
+ * Compute the overhead of join partition pruning.
+ */
+double
+compute_partprune_cost(PlannerInfo *root, RelOptInfo *appendrel,
+ Cost append_total_cost, int append_nplans,
+ Relids inner_relids, double inner_rows,
+ List *prunequal)
+{
+ Cost prune_cost;
+ Cost saved_cost;
+ double matching_outer_rows;
+ double unmatched_nplans;
+
+ switch (appendrel->part_scheme->strategy)
+ {
+
+ case PARTITION_STRATEGY_LIST:
+ case PARTITION_STRATEGY_RANGE:
+ prune_cost = cpu_operator_cost * LOG2(append_nplans) * inner_rows;
+ break;
+ case PARTITION_STRATEGY_HASH:
+ prune_cost = cpu_operator_cost * append_nplans * inner_rows;
+ break;
+ default:
+ elog(ERROR, "unexpected partition strategy: %d",
+ (int) appendrel->part_scheme->strategy);
+ break;
+ }
+
+ matching_outer_rows =
+ get_joinrel_matching_outer_size(root,
+ appendrel,
+ inner_relids,
+ prunequal);
+
+ /*
+ * We assume that each outer joined row occupies one new partition. This
+ * is really the worst case.
+ */
+ unmatched_nplans = append_nplans - Min(matching_outer_rows, append_nplans);
+ saved_cost = (unmatched_nplans / append_nplans) * append_total_cost;
+
+ return prune_cost - saved_cost;
+}
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 610f4a56d6..55cd3bb616 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -242,7 +242,8 @@ static Hash *make_hash(Plan *lefttree,
List *hashkeys,
Oid skewTable,
AttrNumber skewColumn,
- bool skewInherit);
+ bool skewInherit,
+ List *joinpartprune_info_list);
static MergeJoin *make_mergejoin(List *tlist,
List *joinclauses, List *otherclauses,
List *mergeclauses,
@@ -342,6 +343,7 @@ create_plan(PlannerInfo *root, Path *best_path)
/* Initialize this module's workspace in PlannerInfo */
root->curOuterRels = NULL;
root->curOuterParams = NIL;
+ root->join_partition_prune_candidates = NIL;
/* Recursively process the path tree, demanding the correct tlist result */
plan = create_plan_recurse(root, best_path, CP_EXACT_TLIST);
@@ -369,6 +371,8 @@ create_plan(PlannerInfo *root, Path *best_path)
if (root->curOuterParams != NIL)
elog(ERROR, "failed to assign all NestLoopParams to plan nodes");
+ Assert(root->join_partition_prune_candidates == NIL);
+
/*
* Reset plan_params to ensure param IDs used for nestloop params are not
* re-used later
@@ -1223,6 +1227,7 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
int nasyncplans = 0;
RelOptInfo *rel = best_path->path.parent;
PartitionPruneInfo *partpruneinfo = NULL;
+ Bitmapset *join_prune_paramids = NULL;
int nodenumsortkeys = 0;
AttrNumber *nodeSortColIdx = NULL;
Oid *nodeSortOperators = NULL;
@@ -1377,6 +1382,8 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
* If any quals exist, they may be useful to perform further partition
* pruning during execution. Gather information needed by the executor to
* do partition pruning.
+ *
+ * Also gather information needed by the executor to do join pruning.
*/
if (enable_partition_pruning)
{
@@ -1399,13 +1406,20 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
partpruneinfo =
make_partition_pruneinfo(root, rel,
best_path->subpaths,
- prunequal);
+ prunequal,
+ NULL);
+
+ join_prune_paramids =
+ make_join_partition_pruneinfos(root, rel,
+ (Path *) best_path,
+ best_path->subpaths);
}
plan->appendplans = subplans;
plan->nasyncplans = nasyncplans;
plan->first_partial_plan = best_path->first_partial_path;
plan->part_prune_info = partpruneinfo;
+ plan->join_prune_paramids = join_prune_paramids;
copy_generic_path_info(&plan->plan, (Path *) best_path);
@@ -1445,6 +1459,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
ListCell *subpaths;
RelOptInfo *rel = best_path->path.parent;
PartitionPruneInfo *partpruneinfo = NULL;
+ Bitmapset *join_prune_paramids = NULL;
/*
* We don't have the actual creation of the MergeAppend node split out
@@ -1541,6 +1556,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
* If any quals exist, they may be useful to perform further partition
* pruning during execution. Gather information needed by the executor to
* do partition pruning.
+ *
+ * Also gather information needed by the executor to do join pruning.
*/
if (enable_partition_pruning)
{
@@ -1554,11 +1571,18 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
if (prunequal != NIL)
partpruneinfo = make_partition_pruneinfo(root, rel,
best_path->subpaths,
- prunequal);
+ prunequal,
+ NULL);
+
+ join_prune_paramids =
+ make_join_partition_pruneinfos(root, rel,
+ (Path *) best_path,
+ best_path->subpaths);
}
node->mergeplans = subplans;
node->part_prune_info = partpruneinfo;
+ node->join_prune_paramids = join_prune_paramids;
/*
* If prepare_sort_from_pathkeys added sort columns, but we were told to
@@ -4743,6 +4767,13 @@ create_hashjoin_plan(PlannerInfo *root,
AttrNumber skewColumn = InvalidAttrNumber;
bool skewInherit = false;
ListCell *lc;
+ List *joinpartprune_info_list;
+
+ /*
+ * Collect information required to build JoinPartitionPruneInfos at this
+ * join.
+ */
+ prepare_join_partition_prune_candidate(root, &best_path->jpath);
/*
* HashJoin can project, so we don't have to demand exact tlists from the
@@ -4754,6 +4785,11 @@ create_hashjoin_plan(PlannerInfo *root,
outer_plan = create_plan_recurse(root, best_path->jpath.outerjoinpath,
(best_path->num_batches > 1) ? CP_SMALL_TLIST : 0);
+ /*
+ * Retrieve all the JoinPartitionPruneInfos for this join.
+ */
+ joinpartprune_info_list = get_join_partition_prune_candidate(root);
+
inner_plan = create_plan_recurse(root, best_path->jpath.innerjoinpath,
CP_SMALL_TLIST);
@@ -4859,7 +4895,8 @@ create_hashjoin_plan(PlannerInfo *root,
inner_hashkeys,
skewTable,
skewColumn,
- skewInherit);
+ skewInherit,
+ joinpartprune_info_list);
/*
* Set Hash node's startup & total costs equal to total cost of input
@@ -5986,7 +6023,8 @@ make_hash(Plan *lefttree,
List *hashkeys,
Oid skewTable,
AttrNumber skewColumn,
- bool skewInherit)
+ bool skewInherit,
+ List *joinpartprune_info_list)
{
Hash *node = makeNode(Hash);
Plan *plan = &node->plan;
@@ -6000,6 +6038,7 @@ make_hash(Plan *lefttree,
node->skewTable = skewTable;
node->skewColumn = skewColumn;
node->skewInherit = skewInherit;
+ node->joinpartprune_info_list = joinpartprune_info_list;
return node;
}
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index 22a1fa29f3..c83d3bc0ad 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -156,6 +156,11 @@ static Plan *set_mergeappend_references(PlannerInfo *root,
MergeAppend *mplan,
int rtoffset);
static void set_hash_references(PlannerInfo *root, Plan *plan, int rtoffset);
+static void set_joinpartitionprune_references(PlannerInfo *root,
+ List *joinpartprune_info_list,
+ indexed_tlist *outer_itlist,
+ int rtoffset,
+ double num_exec);
static Relids offset_relid_set(Relids relids, int rtoffset);
static Node *fix_scan_expr(PlannerInfo *root, Node *node,
int rtoffset, double num_exec);
@@ -1897,6 +1902,62 @@ set_hash_references(PlannerInfo *root, Plan *plan, int rtoffset)
/* Hash nodes don't have their own quals */
Assert(plan->qual == NIL);
+
+ set_joinpartitionprune_references(root,
+ hplan->joinpartprune_info_list,
+ outer_itlist,
+ rtoffset,
+ NUM_EXEC_TLIST(plan));
+}
+
+/*
+ * set_joinpartitionprune_references
+ * Do set_plan_references processing on JoinPartitionPruneInfos
+ */
+static void
+set_joinpartitionprune_references(PlannerInfo *root,
+ List *joinpartprune_info_list,
+ indexed_tlist *outer_itlist,
+ int rtoffset,
+ double num_exec)
+{
+ ListCell *l;
+
+ foreach(l, joinpartprune_info_list)
+ {
+ JoinPartitionPruneInfo *jpinfo = (JoinPartitionPruneInfo *) lfirst(l);
+ ListCell *l1;
+
+ foreach(l1, jpinfo->part_prune_info->prune_infos)
+ {
+ List *prune_infos = lfirst(l1);
+ ListCell *l2;
+
+ foreach(l2, prune_infos)
+ {
+ PartitionedRelPruneInfo *pinfo = lfirst(l2);
+
+ pinfo->rtindex += rtoffset;
+
+ pinfo->initial_pruning_steps = (List *)
+ fix_upper_expr(root,
+ (Node *) pinfo->initial_pruning_steps,
+ outer_itlist,
+ OUTER_VAR,
+ rtoffset,
+ NRM_EQUAL,
+ num_exec);
+ pinfo->exec_pruning_steps = (List *)
+ fix_upper_expr(root,
+ (Node *) pinfo->exec_pruning_steps,
+ outer_itlist,
+ OUTER_VAR,
+ rtoffset,
+ NRM_EQUAL,
+ num_exec);
+ }
+ }
+ }
}
/*
diff --git a/src/backend/partitioning/partprune.c b/src/backend/partitioning/partprune.c
index 6b635e8ad1..17725aa972 100644
--- a/src/backend/partitioning/partprune.c
+++ b/src/backend/partitioning/partprune.c
@@ -48,7 +48,9 @@
#include "optimizer/appendinfo.h"
#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
+#include "optimizer/paramassign.h"
#include "optimizer/pathnode.h"
+#include "optimizer/restrictinfo.h"
#include "parser/parsetree.h"
#include "partitioning/partbounds.h"
#include "partitioning/partprune.h"
@@ -103,15 +105,16 @@ typedef enum PartClauseTarget
*
* gen_partprune_steps() initializes and returns an instance of this struct.
*
- * Note that has_mutable_op, has_mutable_arg, and has_exec_param are set if
- * we found any potentially-useful-for-pruning clause having those properties,
- * whether or not we actually used the clause in the steps list. This
- * definition allows us to skip the PARTTARGET_EXEC pass in some cases.
+ * Note that has_mutable_op, has_mutable_arg, has_exec_param and has_vars are
+ * set if we found any potentially-useful-for-pruning clause having those
+ * properties, whether or not we actually used the clause in the steps list.
+ * This definition allows us to skip the PARTTARGET_EXEC pass in some cases.
*/
typedef struct GeneratePruningStepsContext
{
/* Copies of input arguments for gen_partprune_steps: */
RelOptInfo *rel; /* the partitioned relation */
+ Bitmapset *available_rels; /* rels whose Vars may be used for pruning */
PartClauseTarget target; /* use-case we're generating steps for */
/* Result data: */
List *steps; /* list of PartitionPruneSteps */
@@ -119,6 +122,7 @@ typedef struct GeneratePruningStepsContext
bool has_mutable_arg; /* clauses include any mutable comparison
* values, *other than* exec params */
bool has_exec_param; /* clauses include any PARAM_EXEC params */
+ bool has_vars; /* clauses include any Vars from 'available_rels' */
bool contradictory; /* clauses were proven self-contradictory */
/* Working state: */
int next_step_id;
@@ -144,8 +148,10 @@ static List *make_partitionedrel_pruneinfo(PlannerInfo *root,
List *prunequal,
Bitmapset *partrelids,
int *relid_subplan_map,
+ Bitmapset *available_rels,
Bitmapset **matchedsubplans);
static void gen_partprune_steps(RelOptInfo *rel, List *clauses,
+ Bitmapset *available_rels,
PartClauseTarget target,
GeneratePruningStepsContext *context);
static List *gen_partprune_steps_internal(GeneratePruningStepsContext *context,
@@ -204,6 +210,10 @@ static PartClauseMatchStatus match_boolean_partition_clause(Oid partopfamily,
static void partkey_datum_from_expr(PartitionPruneContext *context,
Expr *expr, int stateidx,
Datum *value, bool *isnull);
+static bool contain_forbidden_var_clause(Node *node,
+ GeneratePruningStepsContext *context);
+static bool contain_forbidden_var_clause_walker(Node *node,
+ GeneratePruningStepsContext *context);
/*
@@ -216,11 +226,14 @@ static void partkey_datum_from_expr(PartitionPruneContext *context,
* of scan paths for its child rels.
* 'prunequal' is a list of potential pruning quals (i.e., restriction
* clauses that are applicable to the appendrel).
+ * 'available_rels' is the relid set of rels whose Vars may be used for
+ * pruning.
*/
PartitionPruneInfo *
make_partition_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
List *subpaths,
- List *prunequal)
+ List *prunequal,
+ Bitmapset *available_rels)
{
PartitionPruneInfo *pruneinfo;
Bitmapset *allmatchedsubplans = NULL;
@@ -313,6 +326,7 @@ make_partition_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
prunequal,
partrelids,
relid_subplan_map,
+ available_rels,
&matchedsubplans);
/* When pruning is possible, record the matched subplans */
@@ -360,6 +374,184 @@ make_partition_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
return pruneinfo;
}
+/*
+ * make_join_partition_pruneinfos
+ * Builds one JoinPartitionPruneInfo for each join at which join partition
+ * pruning is possible for this appendrel.
+ *
+ * 'parentrel' is the RelOptInfo for an appendrel, and 'subpaths' is the list
+ * of scan paths for its child rels.
+ */
+Bitmapset *
+make_join_partition_pruneinfos(PlannerInfo *root, RelOptInfo *parentrel,
+ Path *best_path, List *subpaths)
+{
+ Bitmapset *result = NULL;
+ ListCell *lc;
+
+ if (!IS_PARTITIONED_REL(parentrel))
+ return NULL;
+
+ foreach(lc, root->join_partition_prune_candidates)
+ {
+ JoinPartitionPruneCandidateInfo *candidate =
+ (JoinPartitionPruneCandidateInfo *) lfirst(lc);
+ PartitionPruneInfo *part_prune_info;
+ List *prunequal;
+ Relids joinrelids;
+ ListCell *l;
+ double prune_cost;
+
+ if (candidate == NULL)
+ continue;
+
+ /*
+ * Identify all joinclauses that are movable to this appendrel given
+ * this inner side relids. Only those clauses can be used for join
+ * partition pruning.
+ */
+ joinrelids = bms_union(parentrel->relids, candidate->inner_relids);
+ prunequal = NIL;
+ foreach(l, candidate->joinrestrictinfo)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+
+ if (join_clause_is_movable_into(rinfo,
+ parentrel->relids,
+ joinrelids))
+ prunequal = lappend(prunequal, rinfo);
+ }
+
+ if (prunequal == NIL)
+ continue;
+
+ /*
+ * Check the overhead of this pruning
+ */
+ prune_cost = compute_partprune_cost(root,
+ parentrel,
+ best_path->total_cost,
+ list_length(subpaths),
+ candidate->inner_relids,
+ candidate->inner_rows,
+ prunequal);
+ if (prune_cost > 0)
+ continue;
+
+ part_prune_info = make_partition_pruneinfo(root, parentrel,
+ subpaths,
+ prunequal,
+ candidate->inner_relids);
+
+ if (part_prune_info)
+ {
+ JoinPartitionPruneInfo *jpinfo;
+
+ jpinfo = makeNode(JoinPartitionPruneInfo);
+
+ jpinfo->part_prune_info = part_prune_info;
+ jpinfo->paramid = assign_special_exec_param(root);
+ jpinfo->nplans = list_length(subpaths);
+
+ candidate->joinpartprune_info_list =
+ lappend(candidate->joinpartprune_info_list, jpinfo);
+
+ result = bms_add_member(result, jpinfo->paramid);
+ }
+ }
+
+ return result;
+}
+
+/*
+ * prepare_join_partition_prune_candidate
+ * Check if join partition pruning is possible at this join and if so
+ * collect information required to build JoinPartitionPruneInfos.
+ *
+ * Note that we may build more than one JoinPartitionPruneInfo at one join, for
+ * different Append/MergeAppend paths.
+ */
+void
+prepare_join_partition_prune_candidate(PlannerInfo *root, JoinPath *jpath)
+{
+ JoinPartitionPruneCandidateInfo *candidate;
+
+ if (!enable_partition_pruning)
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ /*
+ * For now do not perform join partition pruning for parallel hashjoin.
+ */
+ if (jpath->path.parallel_workers > 0)
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ /*
+ * We cannot perform join partition pruning if the outer is the
+ * non-nullable side.
+ */
+ if (!(jpath->jointype == JOIN_INNER ||
+ jpath->jointype == JOIN_SEMI ||
+ jpath->jointype == JOIN_RIGHT ||
+ jpath->jointype == JOIN_RIGHT_ANTI))
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ /*
+ * For now we only support HashJoin.
+ */
+ if (jpath->path.pathtype != T_HashJoin)
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ candidate = makeNode(JoinPartitionPruneCandidateInfo);
+ candidate->joinrestrictinfo = jpath->joinrestrictinfo;
+ candidate->inner_relids = jpath->innerjoinpath->parent->relids;
+ candidate->inner_rows = jpath->innerjoinpath->parent->rows;
+ candidate->joinpartprune_info_list = NIL;
+
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, candidate);
+}
+
+/*
+ * get_join_partition_prune_candidate
+ * Pop out the JoinPartitionPruneCandidateInfo for this join and retrieve
+ * the JoinPartitionPruneInfos.
+ */
+List *
+get_join_partition_prune_candidate(PlannerInfo *root)
+{
+ JoinPartitionPruneCandidateInfo *candidate;
+ List *result;
+
+ candidate = llast(root->join_partition_prune_candidates);
+ root->join_partition_prune_candidates =
+ list_delete_last(root->join_partition_prune_candidates);
+
+ if (candidate == NULL)
+ return NIL;
+
+ result = candidate->joinpartprune_info_list;
+
+ pfree(candidate);
+
+ return result;
+}
+
/*
* add_part_relids
* Add new info to a list of Bitmapsets of partitioned relids.
@@ -428,6 +620,8 @@ add_part_relids(List *allpartrelids, Bitmapset *partrelids)
* partrelids: Set of RT indexes identifying relevant partitioned tables
* within a single partitioning hierarchy
* relid_subplan_map[]: maps child relation relids to subplan indexes
+ * available_rels: the relid set of rels whose Vars may be used for
+ * pruning.
* matchedsubplans: on success, receives the set of subplan indexes which
* were matched to this partition hierarchy
*
@@ -440,6 +634,7 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
List *prunequal,
Bitmapset *partrelids,
int *relid_subplan_map,
+ Bitmapset *available_rels,
Bitmapset **matchedsubplans)
{
RelOptInfo *targetpart = NULL;
@@ -539,8 +734,8 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
* pruning steps and detects whether there's any possibly-useful quals
* that would require per-scan pruning.
*/
- gen_partprune_steps(subpart, partprunequal, PARTTARGET_INITIAL,
- &context);
+ gen_partprune_steps(subpart, partprunequal, available_rels,
+ PARTTARGET_INITIAL, &context);
if (context.contradictory)
{
@@ -567,14 +762,15 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
initial_pruning_steps = NIL;
/*
- * If no exec Params appear in potentially-usable pruning clauses,
- * then there's no point in even thinking about per-scan pruning.
+ * If no exec Params or available Vars appear in potentially-usable
+ * pruning clauses, then there's no point in even thinking about
+ * per-scan pruning.
*/
- if (context.has_exec_param)
+ if (context.has_exec_param || context.has_vars)
{
/* ... OK, we'd better think about it */
- gen_partprune_steps(subpart, partprunequal, PARTTARGET_EXEC,
- &context);
+ gen_partprune_steps(subpart, partprunequal, available_rels,
+ PARTTARGET_EXEC, &context);
if (context.contradictory)
{
@@ -587,11 +783,14 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
/*
* Detect which exec Params actually got used; the fact that some
* were in available clauses doesn't mean we actually used them.
- * Skip per-scan pruning if there are none.
*/
execparamids = get_partkey_exec_paramids(exec_pruning_steps);
- if (bms_is_empty(execparamids))
+ /*
+ * Skip per-scan pruning if there are none used exec Params and
+ * there are none available Vars.
+ */
+ if (bms_is_empty(execparamids) && !context.has_vars)
exec_pruning_steps = NIL;
}
else
@@ -703,6 +902,9 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
* Process 'clauses' (typically a rel's baserestrictinfo list of clauses)
* and create a list of "partition pruning steps".
*
+ * 'available_rels' is the relid set of rels whose Vars may be used for
+ * pruning.
+ *
* 'target' tells whether to generate pruning steps for planning (use
* immutable clauses only), or for executor startup (use any allowable
* clause except ones containing PARAM_EXEC Params), or for executor
@@ -712,12 +914,13 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
* some subsidiary flags; see the GeneratePruningStepsContext typedef.
*/
static void
-gen_partprune_steps(RelOptInfo *rel, List *clauses, PartClauseTarget target,
- GeneratePruningStepsContext *context)
+gen_partprune_steps(RelOptInfo *rel, List *clauses, Bitmapset *available_rels,
+ PartClauseTarget target, GeneratePruningStepsContext *context)
{
/* Initialize all output values to zero/false/NULL */
memset(context, 0, sizeof(GeneratePruningStepsContext));
context->rel = rel;
+ context->available_rels = available_rels;
context->target = target;
/*
@@ -773,7 +976,7 @@ prune_append_rel_partitions(RelOptInfo *rel)
* If the clauses are found to be contradictory, we can return the empty
* set.
*/
- gen_partprune_steps(rel, clauses, PARTTARGET_PLANNER,
+ gen_partprune_steps(rel, clauses, NULL, PARTTARGET_PLANNER,
&gcontext);
if (gcontext.contradictory)
return NULL;
@@ -1957,9 +2160,10 @@ match_clause_to_partition_key(GeneratePruningStepsContext *context,
return PARTCLAUSE_UNSUPPORTED;
/*
- * We can never prune using an expression that contains Vars.
+ * We can never prune using an expression that contains Vars except
+ * for Vars belonging to context->available_rels.
*/
- if (contain_var_clause((Node *) expr))
+ if (contain_forbidden_var_clause((Node *) expr, context))
return PARTCLAUSE_UNSUPPORTED;
/*
@@ -2155,9 +2359,10 @@ match_clause_to_partition_key(GeneratePruningStepsContext *context,
return PARTCLAUSE_UNSUPPORTED;
/*
- * We can never prune using an expression that contains Vars.
+ * We can never prune using an expression that contains Vars except
+ * for Vars belonging to context->available_rels.
*/
- if (contain_var_clause((Node *) rightop))
+ if (contain_forbidden_var_clause((Node *) rightop, context))
return PARTCLAUSE_UNSUPPORTED;
/*
@@ -3727,3 +3932,54 @@ partkey_datum_from_expr(PartitionPruneContext *context,
*value = ExecEvalExprSwitchContext(exprstate, ectx, isnull);
}
}
+
+/*
+ * contain_forbidden_var_clause
+ * Recursively scan a clause to discover whether it contains any Var nodes
+ * (of the current query level) that do not belong to relations in
+ * context->available_rels.
+ *
+ * Returns true if any such varnode found.
+ *
+ * Does not examine subqueries, therefore must only be used after reduction
+ * of sublinks to subplans!
+ */
+static bool
+contain_forbidden_var_clause(Node *node, GeneratePruningStepsContext *context)
+{
+ return contain_forbidden_var_clause_walker(node, context);
+}
+
+static bool
+contain_forbidden_var_clause_walker(Node *node, GeneratePruningStepsContext *context)
+{
+ if (node == NULL)
+ return false;
+ if (IsA(node, Var))
+ {
+ Var *var = (Var *) node;
+
+ if (var->varlevelsup != 0)
+ return false;
+
+ if (!bms_is_member(var->varno, context->available_rels))
+ return true; /* abort the tree traversal and return true */
+
+ context->has_vars = true;
+
+ if (context->target != PARTTARGET_EXEC)
+ return true; /* abort the tree traversal and return true */
+
+ return false;
+ }
+ if (IsA(node, CurrentOfExpr))
+ return true;
+ if (IsA(node, PlaceHolderVar))
+ {
+ if (((PlaceHolderVar *) node)->phlevelsup == 0)
+ return true; /* abort the tree traversal and return true */
+ /* else fall through to check the contained expr */
+ }
+ return expression_tree_walker(node, contain_forbidden_var_clause_walker,
+ (void *) context);
+}
diff --git a/src/include/executor/execPartition.h b/src/include/executor/execPartition.h
index c09bc83b2a..7e46f0baf6 100644
--- a/src/include/executor/execPartition.h
+++ b/src/include/executor/execPartition.h
@@ -121,11 +121,26 @@ typedef struct PartitionPruneState
PartitionPruningData *partprunedata[FLEXIBLE_ARRAY_MEMBER];
} PartitionPruneState;
+/*
+ * JoinPartitionPruneState - State object required for plan nodes to perform
+ * join partition pruning.
+ */
+typedef struct JoinPartitionPruneState
+{
+ PartitionPruneState *part_prune_state;
+ int paramid;
+ int nplans;
+ bool finished;
+ Bitmapset *part_prune_result;
+} JoinPartitionPruneState;
+
extern PartitionPruneState *ExecInitPartitionPruning(PlanState *planstate,
int n_total_subplans,
PartitionPruneInfo *pruneinfo,
Bitmapset **initially_valid_subplans);
+extern List *ExecInitJoinpartpruneList(PlanState *planstate, List *joinpartprune_info_list);
extern Bitmapset *ExecFindMatchingSubPlans(PartitionPruneState *prunestate,
- bool initial_prune);
+ bool initial_prune,
+ PlanState *planstate);
#endif /* EXECPARTITION_H */
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 444a5f0fd5..8f02af1f10 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2685,6 +2685,9 @@ typedef struct HashState
/* Parallel hash state. */
struct ParallelHashJoinState *parallel_state;
+
+ /* Infos for join partition pruning. */
+ List *joinpartprune_state_list;
} HashState;
/* ----------------
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 534692bee1..da7803448a 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -530,6 +530,9 @@ struct PlannerInfo
/* not-yet-assigned NestLoopParams */
List *curOuterParams;
+ /* a stack of JoinPartitionPruneInfos */
+ List *join_partition_prune_candidates;
+
/*
* These fields are workspace for setrefs.c. Each is an array
* corresponding to glob->subplans. (We could probably teach
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index b4ef6bc44c..964bc85123 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -275,6 +275,9 @@ typedef struct Append
/* Info for run-time subplan pruning; NULL if we're not doing that */
struct PartitionPruneInfo *part_prune_info;
+
+ /* Info for join partition pruning; NULL if we're not doing that */
+ Bitmapset *join_prune_paramids;
} Append;
/* ----------------
@@ -310,6 +313,9 @@ typedef struct MergeAppend
/* Info for run-time subplan pruning; NULL if we're not doing that */
struct PartitionPruneInfo *part_prune_info;
+
+ /* Info for join partition pruning; NULL if we're not doing that */
+ Bitmapset *join_prune_paramids;
} MergeAppend;
/* ----------------
@@ -1206,6 +1212,7 @@ typedef struct Hash
bool skewInherit; /* is outer join rel an inheritance tree? */
/* all other info is in the parent HashJoin node */
Cardinality rows_total; /* estimate total rows if parallel_aware */
+ List *joinpartprune_info_list; /* infos for join partition pruning */
} Hash;
/* ----------------
@@ -1552,6 +1559,35 @@ typedef struct PartitionPruneStepCombine
List *source_stepids;
} PartitionPruneStepCombine;
+/*
+ * JoinPartitionPruneCandidateInfo - Information required to build
+ * JoinPartitionPruneInfos.
+ */
+typedef struct JoinPartitionPruneCandidateInfo
+{
+ pg_node_attr(no_equal, no_query_jumble)
+
+ NodeTag type;
+ List *joinrestrictinfo;
+ Bitmapset *inner_relids;
+ double inner_rows;
+ List *joinpartprune_info_list;
+} JoinPartitionPruneCandidateInfo;
+
+/*
+ * JoinPartitionPruneInfo - Details required to allow the executor to prune
+ * partitions during join.
+ */
+typedef struct JoinPartitionPruneInfo
+{
+ pg_node_attr(no_equal, no_query_jumble)
+
+ NodeTag type;
+ PartitionPruneInfo *part_prune_info;
+ int paramid;
+ int nplans;
+} JoinPartitionPruneInfo;
+
/*
* Plan invalidation info
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index b1c51a4e70..5ccd3c62d4 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -212,5 +212,9 @@ extern PathTarget *set_pathtarget_cost_width(PlannerInfo *root, PathTarget *targ
extern double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel,
Path *bitmapqual, double loop_count,
Cost *cost_p, double *tuples_p);
+extern double compute_partprune_cost(PlannerInfo *root, RelOptInfo *appendrel,
+ Cost append_total_cost, int append_nplans,
+ Relids inner_relids, double inner_rows,
+ List *prunequal);
#endif /* COST_H */
diff --git a/src/include/partitioning/partprune.h b/src/include/partitioning/partprune.h
index bd490d154f..5187485c88 100644
--- a/src/include/partitioning/partprune.h
+++ b/src/include/partitioning/partprune.h
@@ -19,6 +19,8 @@
struct PlannerInfo; /* avoid including pathnodes.h here */
struct RelOptInfo;
+struct Path;
+struct JoinPath;
/*
@@ -73,7 +75,15 @@ typedef struct PartitionPruneContext
extern PartitionPruneInfo *make_partition_pruneinfo(struct PlannerInfo *root,
struct RelOptInfo *parentrel,
List *subpaths,
- List *prunequal);
+ List *prunequal,
+ Bitmapset *available_rels);
+extern Bitmapset *make_join_partition_pruneinfos(struct PlannerInfo *root,
+ struct RelOptInfo *parentrel,
+ struct Path *best_path,
+ List *subpaths);
+extern void prepare_join_partition_prune_candidate(struct PlannerInfo *root,
+ struct JoinPath *jpath);
+extern List *get_join_partition_prune_candidate(struct PlannerInfo *root);
extern Bitmapset *prune_append_rel_partitions(struct RelOptInfo *rel);
extern Bitmapset *get_matching_partitions(PartitionPruneContext *context,
List *pruning_steps);
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 9a4c48c055..a08e7a1f0a 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -3003,6 +3003,92 @@ order by tbl1.col1, tprt.col1;
------+------
(0 rows)
+-- join partition pruning
+-- The 'Memory Usage' from the Hash node can vary between machines. Let's just
+-- replace the number with an 'N'.
+-- We need to run EXPLAIN ANALYZE because we need to see '(never executed)'
+-- notations because that's the only way to verify runtime pruning.
+create function explain_join_partition_pruning(text) returns setof text
+language plpgsql as
+$$
+declare
+ ln text;
+begin
+ for ln in
+ execute format('explain (analyze, verbose, costs off, summary off, timing off) %s',
+ $1)
+ loop
+ ln := regexp_replace(ln, 'Memory Usage: \d+', 'Memory Usage: N');
+ return next ln;
+ end loop;
+end;
+$$;
+delete from tbl1;
+insert into tbl1 values (501), (505);
+analyze tbl1, tprt;
+set enable_nestloop = off;
+set enable_mergejoin = off;
+set enable_hashjoin = on;
+select explain_join_partition_pruning('
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;');
+ explain_join_partition_pruning
+--------------------------------------------------------------------------------
+ Hash Right Join (actual rows=2 loops=1)
+ Output: p1.col1, p2.col1, t.col1
+ Hash Cond: ((p1.col1 = t.col1) AND (p2.col1 = t.col1))
+ -> Hash Join (actual rows=3 loops=1)
+ Output: p1.col1, p2.col1
+ Hash Cond: (p1.col1 = p2.col1)
+ -> Append (actual rows=3 loops=1)
+ Join Partition Pruning: $0
+ -> Seq Scan on public.tprt_1 p1_1 (never executed)
+ Output: p1_1.col1
+ -> Seq Scan on public.tprt_2 p1_2 (actual rows=3 loops=1)
+ Output: p1_2.col1
+ -> Seq Scan on public.tprt_3 p1_3 (never executed)
+ Output: p1_3.col1
+ -> Seq Scan on public.tprt_4 p1_4 (never executed)
+ Output: p1_4.col1
+ -> Seq Scan on public.tprt_5 p1_5 (never executed)
+ Output: p1_5.col1
+ -> Seq Scan on public.tprt_6 p1_6 (never executed)
+ Output: p1_6.col1
+ -> Hash (actual rows=3 loops=1)
+ Output: p2.col1
+ Buckets: 1024 Batches: 1 Memory Usage: NkB
+ -> Append (actual rows=3 loops=1)
+ Join Partition Pruning: $1
+ -> Seq Scan on public.tprt_1 p2_1 (never executed)
+ Output: p2_1.col1
+ -> Seq Scan on public.tprt_2 p2_2 (actual rows=3 loops=1)
+ Output: p2_2.col1
+ -> Seq Scan on public.tprt_3 p2_3 (never executed)
+ Output: p2_3.col1
+ -> Seq Scan on public.tprt_4 p2_4 (never executed)
+ Output: p2_4.col1
+ -> Seq Scan on public.tprt_5 p2_5 (never executed)
+ Output: p2_5.col1
+ -> Seq Scan on public.tprt_6 p2_6 (never executed)
+ Output: p2_6.col1
+ -> Hash (actual rows=2 loops=1)
+ Output: t.col1
+ Buckets: 1024 Batches: 1 Memory Usage: NkB
+ Partition Prune: $0, $1
+ -> Seq Scan on public.tbl1 t (actual rows=2 loops=1)
+ Output: t.col1
+(43 rows)
+
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;
+ col1 | col1 | col1
+------+------+------
+ 501 | 501 | 501
+ 505 | 505 | 505
+(2 rows)
+
drop table tbl1, tprt;
-- Test with columns defined in varying orders between each level
create table part_abc (a int not null, b int not null, c int not null) partition by list (a);
diff --git a/src/test/regress/sql/partition_prune.sql b/src/test/regress/sql/partition_prune.sql
index 7bf3920827..fc5982edcf 100644
--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
@@ -727,6 +727,45 @@ select tbl1.col1, tprt.col1 from tbl1
inner join tprt on tbl1.col1 = tprt.col1
order by tbl1.col1, tprt.col1;
+-- join partition pruning
+
+-- The 'Memory Usage' from the Hash node can vary between machines. Let's just
+-- replace the number with an 'N'.
+-- We need to run EXPLAIN ANALYZE because we need to see '(never executed)'
+-- notations because that's the only way to verify runtime pruning.
+create function explain_join_partition_pruning(text) returns setof text
+language plpgsql as
+$$
+declare
+ ln text;
+begin
+ for ln in
+ execute format('explain (analyze, verbose, costs off, summary off, timing off) %s',
+ $1)
+ loop
+ ln := regexp_replace(ln, 'Memory Usage: \d+', 'Memory Usage: N');
+ return next ln;
+ end loop;
+end;
+$$;
+
+delete from tbl1;
+insert into tbl1 values (501), (505);
+analyze tbl1, tprt;
+
+set enable_nestloop = off;
+set enable_mergejoin = off;
+set enable_hashjoin = on;
+
+select explain_join_partition_pruning('
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;');
+
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;
+
drop table tbl1, tprt;
-- Test with columns defined in varying orders between each level
--
2.31.0
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Support run-time partition pruning for hash join
2023-11-07 07:55 Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
2024-01-27 03:29 ` Re: Support run-time partition pruning for hash join vignesh C <[email protected]>
2024-01-30 02:33 ` Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
@ 2024-03-19 06:12 ` Richard Guo <[email protected]>
2024-09-05 07:56 ` Re: Support run-time partition pruning for hash join Andrei Lepikhov <[email protected]>
0 siblings, 1 reply; 6+ messages in thread
From: Richard Guo @ 2024-03-19 06:12 UTC (permalink / raw)
To: vignesh C <[email protected]>; +Cc: Alexander Lakhin <[email protected]>; David Rowley <[email protected]>; Andy Fan <[email protected]>; pgsql-hackers
On Tue, Jan 30, 2024 at 10:33 AM Richard Guo <[email protected]> wrote:
> Attached is an updated patch. Nothing else has changed.
>
Here is another rebase over master so it applies again. Nothing else
has changed.
Thanks
Richard
Attachments:
[application/octet-stream] v7-0001-Support-run-time-partition-pruning-for-hash-join.patch (59.3K, ../../CAMbWs49Q=H7P_pE9gjpC0sFky7dAzWCxXczwpwFFkG_VmmHx4Q@mail.gmail.com/3-v7-0001-Support-run-time-partition-pruning-for-hash-join.patch)
download | inline diff:
From 465c96b2c84df1c6dd2ffa3001759c2f18ab3867 Mon Sep 17 00:00:00 2001
From: Richard Guo <[email protected]>
Date: Mon, 14 Aug 2023 14:55:26 +0800
Subject: [PATCH v7] Support run-time partition pruning for hash join
If we have a hash join with an Append node on the outer side, something
like
Hash Join
Hash Cond: (pt.a = t.a)
-> Append
-> Seq Scan on pt_p1 pt_1
-> Seq Scan on pt_p2 pt_2
-> Seq Scan on pt_p3 pt_3
-> Hash
-> Seq Scan on t
We can actually prune those subnodes of the Append that cannot possibly
contain any matching tuples from the other side of the join. To do
that, when building the Hash table, for each row from the inner side we
can compute the minimum set of subnodes that can possibly match the join
condition. When we have built the Hash table and start to execute the
Append node, we should have known which subnodes are survived and thus
can skip other subnodes.
This patch implements this idea.
---
src/backend/commands/explain.c | 61 ++++
src/backend/executor/execPartition.c | 127 +++++++-
src/backend/executor/nodeAppend.c | 32 +-
src/backend/executor/nodeHash.c | 75 +++++
src/backend/executor/nodeHashjoin.c | 10 +
src/backend/executor/nodeMergeAppend.c | 22 +-
src/backend/optimizer/path/costsize.c | 106 +++++++
src/backend/optimizer/plan/createplan.c | 49 ++-
src/backend/optimizer/plan/setrefs.c | 61 ++++
src/backend/partitioning/partprune.c | 298 ++++++++++++++++--
src/include/executor/execPartition.h | 17 +-
src/include/nodes/execnodes.h | 3 +
src/include/nodes/pathnodes.h | 3 +
src/include/nodes/plannodes.h | 36 +++
src/include/optimizer/cost.h | 4 +
src/include/partitioning/partprune.h | 12 +-
src/test/regress/expected/partition_prune.out | 86 +++++
src/test/regress/sql/partition_prune.sql | 39 +++
18 files changed, 992 insertions(+), 49 deletions(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index a9d5056af4..0a5591b95f 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -18,6 +18,7 @@
#include "commands/createas.h"
#include "commands/defrem.h"
#include "commands/prepare.h"
+#include "executor/execPartition.h"
#include "foreign/fdwapi.h"
#include "jit/jit.h"
#include "nodes/extensible.h"
@@ -117,6 +118,9 @@ static void show_instrumentation_count(const char *qlabel, int which,
PlanState *planstate, ExplainState *es);
static void show_foreignscan_info(ForeignScanState *fsstate, ExplainState *es);
static void show_eval_params(Bitmapset *bms_params, ExplainState *es);
+static void show_join_pruning_result_info(Bitmapset *join_prune_paramids,
+ ExplainState *es);
+static void show_joinpartprune_info(HashState *hashstate, ExplainState *es);
static const char *explain_get_index_name(Oid indexId);
static bool peek_buffer_usage(ExplainState *es, const BufferUsage *usage);
static void show_buffer_usage(ExplainState *es, const BufferUsage *usage);
@@ -2115,9 +2119,17 @@ ExplainNode(PlanState *planstate, List *ancestors,
show_incremental_sort_info(castNode(IncrementalSortState, planstate),
es);
break;
+ case T_Append:
+ if (es->verbose)
+ show_join_pruning_result_info(((Append *) plan)->join_prune_paramids,
+ es);
+ break;
case T_MergeAppend:
show_merge_append_keys(castNode(MergeAppendState, planstate),
ancestors, es);
+ if (es->verbose)
+ show_join_pruning_result_info(((MergeAppend *) plan)->join_prune_paramids,
+ es);
break;
case T_Result:
show_upper_qual((List *) ((Result *) plan)->resconstantqual,
@@ -2133,6 +2145,8 @@ ExplainNode(PlanState *planstate, List *ancestors,
break;
case T_Hash:
show_hash_info(castNode(HashState, planstate), es);
+ if (es->verbose)
+ show_joinpartprune_info(castNode(HashState, planstate), es);
break;
case T_Memoize:
show_memoize_info(castNode(MemoizeState, planstate), ancestors,
@@ -3573,6 +3587,53 @@ show_eval_params(Bitmapset *bms_params, ExplainState *es)
ExplainPropertyList("Params Evaluated", params, es);
}
+/*
+ * Show join partition pruning results at Append/MergeAppend nodes.
+ */
+static void
+show_join_pruning_result_info(Bitmapset *join_prune_paramids, ExplainState *es)
+{
+ int paramid = -1;
+ List *params = NIL;
+
+ if (bms_is_empty(join_prune_paramids))
+ return;
+
+ while ((paramid = bms_next_member(join_prune_paramids, paramid)) >= 0)
+ {
+ char param[32];
+
+ snprintf(param, sizeof(param), "$%d", paramid);
+ params = lappend(params, pstrdup(param));
+ }
+
+ ExplainPropertyList("Join Partition Pruning", params, es);
+}
+
+/*
+ * Show join partition pruning infos at Hash nodes.
+ */
+static void
+show_joinpartprune_info(HashState *hashstate, ExplainState *es)
+{
+ List *params = NIL;
+ ListCell *lc;
+
+ if (!hashstate->joinpartprune_state_list)
+ return;
+
+ foreach(lc, hashstate->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+ char param[32];
+
+ snprintf(param, sizeof(param), "$%d", jpstate->paramid);
+ params = lappend(params, pstrdup(param));
+ }
+
+ ExplainPropertyList("Partition Prune", params, es);
+}
+
/*
* Fetch the name of an index in an EXPLAIN
*
diff --git a/src/backend/executor/execPartition.c b/src/backend/executor/execPartition.c
index 64fcb012db..d715827972 100644
--- a/src/backend/executor/execPartition.c
+++ b/src/backend/executor/execPartition.c
@@ -196,6 +196,8 @@ static void find_matching_subplans_recurse(PartitionPruningData *prunedata,
PartitionedRelPruningData *pprune,
bool initial_prune,
Bitmapset **validsubplans);
+static bool get_join_prune_matching_subplans(PlanState *planstate,
+ Bitmapset **partset);
/*
@@ -1805,7 +1807,7 @@ ExecInitPartitionPruning(PlanState *planstate,
* Perform an initial partition prune pass, if required.
*/
if (prunestate->do_initial_prune)
- *initially_valid_subplans = ExecFindMatchingSubPlans(prunestate, true);
+ *initially_valid_subplans = ExecFindMatchingSubPlans(prunestate, true, NULL);
else
{
/* No pruning, so we'll need to initialize all subplans */
@@ -1835,6 +1837,37 @@ ExecInitPartitionPruning(PlanState *planstate,
return prunestate;
}
+/*
+ * ExecInitJoinpartpruneList
+ * Initialize data structures needed for join partition pruning
+ */
+List *
+ExecInitJoinpartpruneList(PlanState *planstate,
+ List *joinpartprune_info_list)
+{
+ ListCell *lc;
+ List *result = NIL;
+
+ foreach(lc, joinpartprune_info_list)
+ {
+ JoinPartitionPruneInfo *jpinfo = (JoinPartitionPruneInfo *) lfirst(lc);
+ JoinPartitionPruneState *jpstate = palloc(sizeof(JoinPartitionPruneState));
+
+ jpstate->part_prune_state =
+ CreatePartitionPruneState(planstate, jpinfo->part_prune_info);
+ Assert(jpstate->part_prune_state->do_exec_prune);
+
+ jpstate->paramid = jpinfo->paramid;
+ jpstate->nplans = jpinfo->nplans;
+ jpstate->finished = false;
+ jpstate->part_prune_result = NULL;
+
+ result = lappend(result, jpstate);
+ }
+
+ return result;
+}
+
/*
* CreatePartitionPruneState
* Build the data structure required for calling ExecFindMatchingSubPlans
@@ -2272,7 +2305,9 @@ PartitionPruneFixSubPlanMap(PartitionPruneState *prunestate,
/*
* ExecFindMatchingSubPlans
* Determine which subplans match the pruning steps detailed in
- * 'prunestate' for the current comparison expression values.
+ * 'prunestate' if any for the current comparison expression values, and
+ * meanwhile match the join partition pruning results if any stored in
+ * Append/MergeAppend node's join_prune_paramids.
*
* Pass initial_prune if PARAM_EXEC Params cannot yet be evaluated. This
* differentiates the initial executor-time pruning step from later
@@ -2280,11 +2315,30 @@ PartitionPruneFixSubPlanMap(PartitionPruneState *prunestate,
*/
Bitmapset *
ExecFindMatchingSubPlans(PartitionPruneState *prunestate,
- bool initial_prune)
+ bool initial_prune,
+ PlanState *planstate)
{
Bitmapset *result = NULL;
MemoryContext oldcontext;
int i;
+ Bitmapset *join_prune_partset = NULL;
+ bool do_join_prune;
+
+ /* Retrieve the join partition pruning results if any */
+ do_join_prune =
+ get_join_prune_matching_subplans(planstate, &join_prune_partset);
+
+ /*
+ * Either we're here on partition prune done according to the pruning steps
+ * detailed in 'prunestate', or we have done join partition prune.
+ */
+ Assert(do_join_prune || prunestate != NULL);
+
+ /*
+ * If there is no 'prunestate', then rely entirely on join pruning.
+ */
+ if (prunestate == NULL)
+ return join_prune_partset;
/*
* Either we're here on the initial prune done during pruning
@@ -2325,6 +2379,10 @@ ExecFindMatchingSubPlans(PartitionPruneState *prunestate,
/* Add in any subplans that partition pruning didn't account for */
result = bms_add_members(result, prunestate->other_subplans);
+ /* Intersect join partition pruning results */
+ if (do_join_prune)
+ result = bms_intersect(result, join_prune_partset);
+
MemoryContextSwitchTo(oldcontext);
/* Copy result out of the temp context before we reset it */
@@ -2395,3 +2453,66 @@ find_matching_subplans_recurse(PartitionPruningData *prunedata,
}
}
}
+
+/*
+ * get_join_prune_matching_subplans
+ * Retrieve the join partition pruning results if any stored in
+ * Append/MergeAppend node's join_prune_paramids. Return true if we can
+ * do join partition pruning, otherwise return false.
+ *
+ * Adds valid (non-prunable) subplan IDs to *partset
+ */
+static bool
+get_join_prune_matching_subplans(PlanState *planstate, Bitmapset **partset)
+{
+ Bitmapset *join_prune_paramids;
+ int nplans;
+ int paramid;
+
+ if (planstate == NULL)
+ return false;
+
+ if (IsA(planstate, AppendState))
+ {
+ join_prune_paramids =
+ ((Append *) planstate->plan)->join_prune_paramids;
+ nplans = ((AppendState *) planstate)->as_nplans;
+ }
+ else if (IsA(planstate, MergeAppendState))
+ {
+ join_prune_paramids =
+ ((MergeAppend *) planstate->plan)->join_prune_paramids;
+ nplans = ((MergeAppendState *) planstate)->ms_nplans;
+ }
+ else
+ {
+ elog(ERROR, "unrecognized node type: %d", (int) nodeTag(planstate));
+ return false;
+ }
+
+ if (bms_is_empty(join_prune_paramids))
+ return false;
+
+ Assert(nplans > 0);
+ *partset = bms_add_range(NULL, 0, nplans - 1);
+
+ paramid = -1;
+ while ((paramid = bms_next_member(join_prune_paramids, paramid)) >= 0)
+ {
+ ParamExecData *param;
+ JoinPartitionPruneState *jpstate;
+
+ param = &(planstate->state->es_param_exec_vals[paramid]);
+ Assert(param->execPlan == NULL);
+ Assert(!param->isnull);
+ jpstate = (JoinPartitionPruneState *) DatumGetPointer(param->value);
+
+ if (jpstate != NULL)
+ *partset = bms_intersect(*partset, jpstate->part_prune_result);
+ else /* the Hash node for this pruning has not been executed */
+ elog(WARNING, "Join partition pruning $%d has not been performed yet.",
+ paramid);
+ }
+
+ return true;
+}
diff --git a/src/backend/executor/nodeAppend.c b/src/backend/executor/nodeAppend.c
index ca0f54d676..cd5ec550fc 100644
--- a/src/backend/executor/nodeAppend.c
+++ b/src/backend/executor/nodeAppend.c
@@ -151,11 +151,13 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
nplans = bms_num_members(validsubplans);
/*
- * When no run-time pruning is required and there's at least one
- * subplan, we can fill as_valid_subplans immediately, preventing
- * later calls to ExecFindMatchingSubPlans.
+ * When no run-time pruning or join pruning is required and there's at
+ * least one subplan, we can fill as_valid_subplans immediately,
+ * preventing later calls to ExecFindMatchingSubPlans.
*/
- if (!prunestate->do_exec_prune && nplans > 0)
+ if (!prunestate->do_exec_prune &&
+ bms_is_empty(node->join_prune_paramids) &&
+ nplans > 0)
{
appendstate->as_valid_subplans = bms_add_range(NULL, 0, nplans - 1);
appendstate->as_valid_subplans_identified = true;
@@ -170,10 +172,18 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
* subplans as valid; they must also all be initialized.
*/
Assert(nplans > 0);
- appendstate->as_valid_subplans = validsubplans =
- bms_add_range(NULL, 0, nplans - 1);
- appendstate->as_valid_subplans_identified = true;
+ validsubplans = bms_add_range(NULL, 0, nplans - 1);
appendstate->as_prune_state = NULL;
+
+ /*
+ * When join pruning is not enabled we can fill as_valid_subplans
+ * immediately, preventing later calls to ExecFindMatchingSubPlans.
+ */
+ if (bms_is_empty(node->join_prune_paramids))
+ {
+ appendstate->as_valid_subplans = validsubplans;
+ appendstate->as_valid_subplans_identified = true;
+ }
}
/*
@@ -580,7 +590,7 @@ choose_next_subplan_locally(AppendState *node)
else if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
}
@@ -647,7 +657,7 @@ choose_next_subplan_for_leader(AppendState *node)
if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
/*
@@ -723,7 +733,7 @@ choose_next_subplan_for_worker(AppendState *node)
else if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
mark_invalid_subplans_as_finished(node);
@@ -876,7 +886,7 @@ ExecAppendAsyncBegin(AppendState *node)
if (!node->as_valid_subplans_identified)
{
node->as_valid_subplans =
- ExecFindMatchingSubPlans(node->as_prune_state, false);
+ ExecFindMatchingSubPlans(node->as_prune_state, false, &node->ps);
node->as_valid_subplans_identified = true;
classify_matching_subplans(node);
diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 61480733a1..39658b9fc5 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -30,6 +30,7 @@
#include "access/parallel.h"
#include "catalog/pg_statistic.h"
#include "commands/tablespace.h"
+#include "executor/execPartition.h"
#include "executor/executor.h"
#include "executor/hashjoin.h"
#include "executor/nodeHash.h"
@@ -47,6 +48,8 @@ static void ExecHashIncreaseNumBatches(HashJoinTable hashtable);
static void ExecHashIncreaseNumBuckets(HashJoinTable hashtable);
static void ExecParallelHashIncreaseNumBatches(HashJoinTable hashtable);
static void ExecParallelHashIncreaseNumBuckets(HashJoinTable hashtable);
+static void ExecJoinPartitionPrune(HashState *node);
+static void ExecStoreJoinPartitionPruneResult(HashState *node);
static void ExecHashBuildSkewHash(HashJoinTable hashtable, Hash *node,
int mcvsToUse);
static void ExecHashSkewTableInsert(HashJoinTable hashtable,
@@ -188,8 +191,14 @@ MultiExecPrivateHash(HashState *node)
}
hashtable->totalTuples += 1;
}
+
+ /* Perform join partition pruning */
+ ExecJoinPartitionPrune(node);
}
+ /* Store the surviving partitions for Append/MergeAppend nodes */
+ ExecStoreJoinPartitionPruneResult(node);
+
/* resize the hash table if needed (NTUP_PER_BUCKET exceeded) */
if (hashtable->nbuckets != hashtable->nbuckets_optimal)
ExecHashIncreaseNumBuckets(hashtable);
@@ -400,6 +409,12 @@ ExecInitHash(Hash *node, EState *estate, int eflags)
hashstate->hashkeys =
ExecInitExprList(node->hashkeys, (PlanState *) hashstate);
+ /*
+ * initialize join partition pruning infos
+ */
+ hashstate->joinpartprune_state_list =
+ ExecInitJoinpartpruneList(&hashstate->ps, node->joinpartprune_info_list);
+
return hashstate;
}
@@ -1609,6 +1624,56 @@ ExecParallelHashIncreaseNumBuckets(HashJoinTable hashtable)
}
}
+/*
+ * ExecJoinPartitionPrune
+ * Perform join partition pruning at this join for each
+ * JoinPartitionPruneState.
+ */
+static void
+ExecJoinPartitionPrune(HashState *node)
+{
+ ListCell *lc;
+
+ foreach(lc, node->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+ Bitmapset *matching_subPlans;
+
+ if (jpstate->finished)
+ continue;
+
+ matching_subPlans =
+ ExecFindMatchingSubPlans(jpstate->part_prune_state, false, NULL);
+ jpstate->part_prune_result =
+ bms_add_members(jpstate->part_prune_result, matching_subPlans);
+
+ if (bms_num_members(jpstate->part_prune_result) == jpstate->nplans)
+ jpstate->finished = true;
+ }
+}
+
+/*
+ * ExecStoreJoinPartitionPruneResult
+ * For each JoinPartitionPruneState, store the set of surviving partitions
+ * to make it available for the Append/MergeAppend node.
+ */
+static void
+ExecStoreJoinPartitionPruneResult(HashState *node)
+{
+ ListCell *lc;
+
+ foreach(lc, node->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+ ParamExecData *param;
+
+ param = &(node->ps.state->es_param_exec_vals[jpstate->paramid]);
+ Assert(param->execPlan == NULL);
+ Assert(!param->isnull);
+ param->value = PointerGetDatum(jpstate);
+ }
+}
+
/*
* ExecHashTableInsert
* insert a tuple into the hash table depending on the hash value
@@ -2353,6 +2418,16 @@ void
ExecReScanHash(HashState *node)
{
PlanState *outerPlan = outerPlanState(node);
+ ListCell *lc;
+
+ /* reset the state in JoinPartitionPruneStates */
+ foreach(lc, node->joinpartprune_state_list)
+ {
+ JoinPartitionPruneState *jpstate = (JoinPartitionPruneState *) lfirst(lc);
+
+ jpstate->finished = false;
+ jpstate->part_prune_result = NULL;
+ }
/*
* if chgParam of subnode is not null then plan will be re-scanned by
diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c
index dbf114cd5e..2a9d2c6482 100644
--- a/src/backend/executor/nodeHashjoin.c
+++ b/src/backend/executor/nodeHashjoin.c
@@ -310,6 +310,16 @@ ExecHashJoinImpl(PlanState *pstate, bool parallel)
*/
node->hj_FirstOuterTupleSlot = NULL;
}
+ else if (hashNode->joinpartprune_state_list != NIL)
+ {
+ /*
+ * Give the hash node a chance to run join partition
+ * pruning if there is any JoinPartitionPruneState that can
+ * be evaluated at it. So do not apply the empty-outer
+ * optimization in this case.
+ */
+ node->hj_FirstOuterTupleSlot = NULL;
+ }
else if (HJ_FILL_OUTER(node) ||
(outerNode->plan->startup_cost < hashNode->ps.plan->total_cost &&
!node->hj_OuterNotEmpty))
diff --git a/src/backend/executor/nodeMergeAppend.c b/src/backend/executor/nodeMergeAppend.c
index e1b9b984a7..df921ad5ad 100644
--- a/src/backend/executor/nodeMergeAppend.c
+++ b/src/backend/executor/nodeMergeAppend.c
@@ -99,11 +99,13 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
nplans = bms_num_members(validsubplans);
/*
- * When no run-time pruning is required and there's at least one
- * subplan, we can fill ms_valid_subplans immediately, preventing
- * later calls to ExecFindMatchingSubPlans.
+ * When no run-time pruning or join pruning is required and there's at
+ * least one subplan, we can fill ms_valid_subplans immediately,
+ * preventing later calls to ExecFindMatchingSubPlans.
*/
- if (!prunestate->do_exec_prune && nplans > 0)
+ if (!prunestate->do_exec_prune &&
+ bms_is_empty(node->join_prune_paramids) &&
+ nplans > 0)
mergestate->ms_valid_subplans = bms_add_range(NULL, 0, nplans - 1);
}
else
@@ -115,9 +117,15 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
* subplans as valid; they must also all be initialized.
*/
Assert(nplans > 0);
- mergestate->ms_valid_subplans = validsubplans =
- bms_add_range(NULL, 0, nplans - 1);
+ validsubplans = bms_add_range(NULL, 0, nplans - 1);
mergestate->ms_prune_state = NULL;
+
+ /*
+ * When join pruning is not enabled we can fill ms_valid_subplans
+ * immediately, preventing later calls to ExecFindMatchingSubPlans.
+ */
+ if (bms_is_empty(node->join_prune_paramids))
+ mergestate->ms_valid_subplans = validsubplans;
}
mergeplanstates = (PlanState **) palloc(nplans * sizeof(PlanState *));
@@ -218,7 +226,7 @@ ExecMergeAppend(PlanState *pstate)
*/
if (node->ms_valid_subplans == NULL)
node->ms_valid_subplans =
- ExecFindMatchingSubPlans(node->ms_prune_state, false);
+ ExecFindMatchingSubPlans(node->ms_prune_state, false, &node->ps);
/*
* First time through: pull the first tuple from each valid subplan,
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 83a0aed051..382413e666 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -172,6 +172,10 @@ static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel,
static bool has_indexed_join_quals(NestPath *path);
static double approx_tuple_count(PlannerInfo *root, JoinPath *path,
List *quals);
+static double get_joinrel_matching_outer_size(PlannerInfo *root,
+ RelOptInfo *outer_rel,
+ Relids inner_relids,
+ List *restrictlist);
static double calc_joinrel_size_estimate(PlannerInfo *root,
RelOptInfo *joinrel,
RelOptInfo *outer_rel,
@@ -5408,6 +5412,61 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
return nrows;
}
+/*
+ * get_joinrel_matching_outer_size
+ * Make a size estimate for the outer side that matches the inner side.
+ */
+static double
+get_joinrel_matching_outer_size(PlannerInfo *root,
+ RelOptInfo *outer_rel,
+ Relids inner_relids,
+ List *restrictlist)
+{
+ double nrows;
+ Selectivity fkselec;
+ Selectivity jselec;
+ SpecialJoinInfo *sjinfo;
+ SpecialJoinInfo sjinfo_data;
+
+ sjinfo = &sjinfo_data;
+ sjinfo->type = T_SpecialJoinInfo;
+ sjinfo->min_lefthand = outer_rel->relids;
+ sjinfo->min_righthand = inner_relids;
+ sjinfo->syn_lefthand = outer_rel->relids;
+ sjinfo->syn_righthand = inner_relids;
+ sjinfo->jointype = JOIN_SEMI;
+ sjinfo->ojrelid = 0;
+ sjinfo->commute_above_l = NULL;
+ sjinfo->commute_above_r = NULL;
+ sjinfo->commute_below_l = NULL;
+ sjinfo->commute_below_r = NULL;
+ /* we don't bother trying to make the remaining fields valid */
+ sjinfo->lhs_strict = false;
+ sjinfo->semi_can_btree = false;
+ sjinfo->semi_can_hash = false;
+ sjinfo->semi_operators = NIL;
+ sjinfo->semi_rhs_exprs = NIL;
+
+ fkselec = get_foreign_key_join_selectivity(root,
+ outer_rel->relids,
+ inner_relids,
+ sjinfo,
+ &restrictlist);
+ jselec = clauselist_selectivity(root,
+ restrictlist,
+ 0,
+ sjinfo->jointype,
+ sjinfo);
+
+ nrows = outer_rel->rows * fkselec * jselec;
+ nrows = clamp_row_est(nrows);
+
+ /* For safety, make sure result is not more than the base estimate */
+ if (nrows > outer_rel->rows)
+ nrows = outer_rel->rows;
+ return nrows;
+}
+
/*
* calc_joinrel_size_estimate
* Workhorse for set_joinrel_size_estimates and
@@ -6529,3 +6588,50 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel,
return pages_fetched;
}
+
+/*
+ * compute_partprune_cost
+ * Compute the overhead of join partition pruning.
+ */
+double
+compute_partprune_cost(PlannerInfo *root, RelOptInfo *appendrel,
+ Cost append_total_cost, int append_nplans,
+ Relids inner_relids, double inner_rows,
+ List *prunequal)
+{
+ Cost prune_cost;
+ Cost saved_cost;
+ double matching_outer_rows;
+ double unmatched_nplans;
+
+ switch (appendrel->part_scheme->strategy)
+ {
+
+ case PARTITION_STRATEGY_LIST:
+ case PARTITION_STRATEGY_RANGE:
+ prune_cost = cpu_operator_cost * LOG2(append_nplans) * inner_rows;
+ break;
+ case PARTITION_STRATEGY_HASH:
+ prune_cost = cpu_operator_cost * append_nplans * inner_rows;
+ break;
+ default:
+ elog(ERROR, "unexpected partition strategy: %d",
+ (int) appendrel->part_scheme->strategy);
+ break;
+ }
+
+ matching_outer_rows =
+ get_joinrel_matching_outer_size(root,
+ appendrel,
+ inner_relids,
+ prunequal);
+
+ /*
+ * We assume that each outer joined row occupies one new partition. This
+ * is really the worst case.
+ */
+ unmatched_nplans = append_nplans - Min(matching_outer_rows, append_nplans);
+ saved_cost = (unmatched_nplans / append_nplans) * append_total_cost;
+
+ return prune_cost - saved_cost;
+}
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 610f4a56d6..55cd3bb616 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -242,7 +242,8 @@ static Hash *make_hash(Plan *lefttree,
List *hashkeys,
Oid skewTable,
AttrNumber skewColumn,
- bool skewInherit);
+ bool skewInherit,
+ List *joinpartprune_info_list);
static MergeJoin *make_mergejoin(List *tlist,
List *joinclauses, List *otherclauses,
List *mergeclauses,
@@ -342,6 +343,7 @@ create_plan(PlannerInfo *root, Path *best_path)
/* Initialize this module's workspace in PlannerInfo */
root->curOuterRels = NULL;
root->curOuterParams = NIL;
+ root->join_partition_prune_candidates = NIL;
/* Recursively process the path tree, demanding the correct tlist result */
plan = create_plan_recurse(root, best_path, CP_EXACT_TLIST);
@@ -369,6 +371,8 @@ create_plan(PlannerInfo *root, Path *best_path)
if (root->curOuterParams != NIL)
elog(ERROR, "failed to assign all NestLoopParams to plan nodes");
+ Assert(root->join_partition_prune_candidates == NIL);
+
/*
* Reset plan_params to ensure param IDs used for nestloop params are not
* re-used later
@@ -1223,6 +1227,7 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
int nasyncplans = 0;
RelOptInfo *rel = best_path->path.parent;
PartitionPruneInfo *partpruneinfo = NULL;
+ Bitmapset *join_prune_paramids = NULL;
int nodenumsortkeys = 0;
AttrNumber *nodeSortColIdx = NULL;
Oid *nodeSortOperators = NULL;
@@ -1377,6 +1382,8 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
* If any quals exist, they may be useful to perform further partition
* pruning during execution. Gather information needed by the executor to
* do partition pruning.
+ *
+ * Also gather information needed by the executor to do join pruning.
*/
if (enable_partition_pruning)
{
@@ -1399,13 +1406,20 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags)
partpruneinfo =
make_partition_pruneinfo(root, rel,
best_path->subpaths,
- prunequal);
+ prunequal,
+ NULL);
+
+ join_prune_paramids =
+ make_join_partition_pruneinfos(root, rel,
+ (Path *) best_path,
+ best_path->subpaths);
}
plan->appendplans = subplans;
plan->nasyncplans = nasyncplans;
plan->first_partial_plan = best_path->first_partial_path;
plan->part_prune_info = partpruneinfo;
+ plan->join_prune_paramids = join_prune_paramids;
copy_generic_path_info(&plan->plan, (Path *) best_path);
@@ -1445,6 +1459,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
ListCell *subpaths;
RelOptInfo *rel = best_path->path.parent;
PartitionPruneInfo *partpruneinfo = NULL;
+ Bitmapset *join_prune_paramids = NULL;
/*
* We don't have the actual creation of the MergeAppend node split out
@@ -1541,6 +1556,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
* If any quals exist, they may be useful to perform further partition
* pruning during execution. Gather information needed by the executor to
* do partition pruning.
+ *
+ * Also gather information needed by the executor to do join pruning.
*/
if (enable_partition_pruning)
{
@@ -1554,11 +1571,18 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path,
if (prunequal != NIL)
partpruneinfo = make_partition_pruneinfo(root, rel,
best_path->subpaths,
- prunequal);
+ prunequal,
+ NULL);
+
+ join_prune_paramids =
+ make_join_partition_pruneinfos(root, rel,
+ (Path *) best_path,
+ best_path->subpaths);
}
node->mergeplans = subplans;
node->part_prune_info = partpruneinfo;
+ node->join_prune_paramids = join_prune_paramids;
/*
* If prepare_sort_from_pathkeys added sort columns, but we were told to
@@ -4743,6 +4767,13 @@ create_hashjoin_plan(PlannerInfo *root,
AttrNumber skewColumn = InvalidAttrNumber;
bool skewInherit = false;
ListCell *lc;
+ List *joinpartprune_info_list;
+
+ /*
+ * Collect information required to build JoinPartitionPruneInfos at this
+ * join.
+ */
+ prepare_join_partition_prune_candidate(root, &best_path->jpath);
/*
* HashJoin can project, so we don't have to demand exact tlists from the
@@ -4754,6 +4785,11 @@ create_hashjoin_plan(PlannerInfo *root,
outer_plan = create_plan_recurse(root, best_path->jpath.outerjoinpath,
(best_path->num_batches > 1) ? CP_SMALL_TLIST : 0);
+ /*
+ * Retrieve all the JoinPartitionPruneInfos for this join.
+ */
+ joinpartprune_info_list = get_join_partition_prune_candidate(root);
+
inner_plan = create_plan_recurse(root, best_path->jpath.innerjoinpath,
CP_SMALL_TLIST);
@@ -4859,7 +4895,8 @@ create_hashjoin_plan(PlannerInfo *root,
inner_hashkeys,
skewTable,
skewColumn,
- skewInherit);
+ skewInherit,
+ joinpartprune_info_list);
/*
* Set Hash node's startup & total costs equal to total cost of input
@@ -5986,7 +6023,8 @@ make_hash(Plan *lefttree,
List *hashkeys,
Oid skewTable,
AttrNumber skewColumn,
- bool skewInherit)
+ bool skewInherit,
+ List *joinpartprune_info_list)
{
Hash *node = makeNode(Hash);
Plan *plan = &node->plan;
@@ -6000,6 +6038,7 @@ make_hash(Plan *lefttree,
node->skewTable = skewTable;
node->skewColumn = skewColumn;
node->skewInherit = skewInherit;
+ node->joinpartprune_info_list = joinpartprune_info_list;
return node;
}
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index 42603dbc7c..573446b989 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -155,6 +155,11 @@ static Plan *set_mergeappend_references(PlannerInfo *root,
MergeAppend *mplan,
int rtoffset);
static void set_hash_references(PlannerInfo *root, Plan *plan, int rtoffset);
+static void set_joinpartitionprune_references(PlannerInfo *root,
+ List *joinpartprune_info_list,
+ indexed_tlist *outer_itlist,
+ int rtoffset,
+ double num_exec);
static Relids offset_relid_set(Relids relids, int rtoffset);
static Node *fix_scan_expr(PlannerInfo *root, Node *node,
int rtoffset, double num_exec);
@@ -1896,6 +1901,62 @@ set_hash_references(PlannerInfo *root, Plan *plan, int rtoffset)
/* Hash nodes don't have their own quals */
Assert(plan->qual == NIL);
+
+ set_joinpartitionprune_references(root,
+ hplan->joinpartprune_info_list,
+ outer_itlist,
+ rtoffset,
+ NUM_EXEC_TLIST(plan));
+}
+
+/*
+ * set_joinpartitionprune_references
+ * Do set_plan_references processing on JoinPartitionPruneInfos
+ */
+static void
+set_joinpartitionprune_references(PlannerInfo *root,
+ List *joinpartprune_info_list,
+ indexed_tlist *outer_itlist,
+ int rtoffset,
+ double num_exec)
+{
+ ListCell *l;
+
+ foreach(l, joinpartprune_info_list)
+ {
+ JoinPartitionPruneInfo *jpinfo = (JoinPartitionPruneInfo *) lfirst(l);
+ ListCell *l1;
+
+ foreach(l1, jpinfo->part_prune_info->prune_infos)
+ {
+ List *prune_infos = lfirst(l1);
+ ListCell *l2;
+
+ foreach(l2, prune_infos)
+ {
+ PartitionedRelPruneInfo *pinfo = lfirst(l2);
+
+ pinfo->rtindex += rtoffset;
+
+ pinfo->initial_pruning_steps = (List *)
+ fix_upper_expr(root,
+ (Node *) pinfo->initial_pruning_steps,
+ outer_itlist,
+ OUTER_VAR,
+ rtoffset,
+ NRM_EQUAL,
+ num_exec);
+ pinfo->exec_pruning_steps = (List *)
+ fix_upper_expr(root,
+ (Node *) pinfo->exec_pruning_steps,
+ outer_itlist,
+ OUTER_VAR,
+ rtoffset,
+ NRM_EQUAL,
+ num_exec);
+ }
+ }
+ }
}
/*
diff --git a/src/backend/partitioning/partprune.c b/src/backend/partitioning/partprune.c
index 9006afd9d2..c0cf7c3c86 100644
--- a/src/backend/partitioning/partprune.c
+++ b/src/backend/partitioning/partprune.c
@@ -48,7 +48,9 @@
#include "optimizer/appendinfo.h"
#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
+#include "optimizer/paramassign.h"
#include "optimizer/pathnode.h"
+#include "optimizer/restrictinfo.h"
#include "parser/parsetree.h"
#include "partitioning/partbounds.h"
#include "partitioning/partprune.h"
@@ -102,15 +104,16 @@ typedef enum PartClauseTarget
*
* gen_partprune_steps() initializes and returns an instance of this struct.
*
- * Note that has_mutable_op, has_mutable_arg, and has_exec_param are set if
- * we found any potentially-useful-for-pruning clause having those properties,
- * whether or not we actually used the clause in the steps list. This
- * definition allows us to skip the PARTTARGET_EXEC pass in some cases.
+ * Note that has_mutable_op, has_mutable_arg, has_exec_param and has_vars are
+ * set if we found any potentially-useful-for-pruning clause having those
+ * properties, whether or not we actually used the clause in the steps list.
+ * This definition allows us to skip the PARTTARGET_EXEC pass in some cases.
*/
typedef struct GeneratePruningStepsContext
{
/* Copies of input arguments for gen_partprune_steps: */
RelOptInfo *rel; /* the partitioned relation */
+ Bitmapset *available_rels; /* rels whose Vars may be used for pruning */
PartClauseTarget target; /* use-case we're generating steps for */
/* Result data: */
List *steps; /* list of PartitionPruneSteps */
@@ -118,6 +121,7 @@ typedef struct GeneratePruningStepsContext
bool has_mutable_arg; /* clauses include any mutable comparison
* values, *other than* exec params */
bool has_exec_param; /* clauses include any PARAM_EXEC params */
+ bool has_vars; /* clauses include any Vars from 'available_rels' */
bool contradictory; /* clauses were proven self-contradictory */
/* Working state: */
int next_step_id;
@@ -143,8 +147,10 @@ static List *make_partitionedrel_pruneinfo(PlannerInfo *root,
List *prunequal,
Bitmapset *partrelids,
int *relid_subplan_map,
+ Bitmapset *available_rels,
Bitmapset **matchedsubplans);
static void gen_partprune_steps(RelOptInfo *rel, List *clauses,
+ Bitmapset *available_rels,
PartClauseTarget target,
GeneratePruningStepsContext *context);
static List *gen_partprune_steps_internal(GeneratePruningStepsContext *context,
@@ -203,6 +209,10 @@ static PartClauseMatchStatus match_boolean_partition_clause(Oid partopfamily,
static void partkey_datum_from_expr(PartitionPruneContext *context,
Expr *expr, int stateidx,
Datum *value, bool *isnull);
+static bool contain_forbidden_var_clause(Node *node,
+ GeneratePruningStepsContext *context);
+static bool contain_forbidden_var_clause_walker(Node *node,
+ GeneratePruningStepsContext *context);
/*
@@ -215,11 +225,14 @@ static void partkey_datum_from_expr(PartitionPruneContext *context,
* of scan paths for its child rels.
* 'prunequal' is a list of potential pruning quals (i.e., restriction
* clauses that are applicable to the appendrel).
+ * 'available_rels' is the relid set of rels whose Vars may be used for
+ * pruning.
*/
PartitionPruneInfo *
make_partition_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
List *subpaths,
- List *prunequal)
+ List *prunequal,
+ Bitmapset *available_rels)
{
PartitionPruneInfo *pruneinfo;
Bitmapset *allmatchedsubplans = NULL;
@@ -312,6 +325,7 @@ make_partition_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
prunequal,
partrelids,
relid_subplan_map,
+ available_rels,
&matchedsubplans);
/* When pruning is possible, record the matched subplans */
@@ -359,6 +373,184 @@ make_partition_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
return pruneinfo;
}
+/*
+ * make_join_partition_pruneinfos
+ * Builds one JoinPartitionPruneInfo for each join at which join partition
+ * pruning is possible for this appendrel.
+ *
+ * 'parentrel' is the RelOptInfo for an appendrel, and 'subpaths' is the list
+ * of scan paths for its child rels.
+ */
+Bitmapset *
+make_join_partition_pruneinfos(PlannerInfo *root, RelOptInfo *parentrel,
+ Path *best_path, List *subpaths)
+{
+ Bitmapset *result = NULL;
+ ListCell *lc;
+
+ if (!IS_PARTITIONED_REL(parentrel))
+ return NULL;
+
+ foreach(lc, root->join_partition_prune_candidates)
+ {
+ JoinPartitionPruneCandidateInfo *candidate =
+ (JoinPartitionPruneCandidateInfo *) lfirst(lc);
+ PartitionPruneInfo *part_prune_info;
+ List *prunequal;
+ Relids joinrelids;
+ ListCell *l;
+ double prune_cost;
+
+ if (candidate == NULL)
+ continue;
+
+ /*
+ * Identify all joinclauses that are movable to this appendrel given
+ * this inner side relids. Only those clauses can be used for join
+ * partition pruning.
+ */
+ joinrelids = bms_union(parentrel->relids, candidate->inner_relids);
+ prunequal = NIL;
+ foreach(l, candidate->joinrestrictinfo)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+
+ if (join_clause_is_movable_into(rinfo,
+ parentrel->relids,
+ joinrelids))
+ prunequal = lappend(prunequal, rinfo);
+ }
+
+ if (prunequal == NIL)
+ continue;
+
+ /*
+ * Check the overhead of this pruning
+ */
+ prune_cost = compute_partprune_cost(root,
+ parentrel,
+ best_path->total_cost,
+ list_length(subpaths),
+ candidate->inner_relids,
+ candidate->inner_rows,
+ prunequal);
+ if (prune_cost > 0)
+ continue;
+
+ part_prune_info = make_partition_pruneinfo(root, parentrel,
+ subpaths,
+ prunequal,
+ candidate->inner_relids);
+
+ if (part_prune_info)
+ {
+ JoinPartitionPruneInfo *jpinfo;
+
+ jpinfo = makeNode(JoinPartitionPruneInfo);
+
+ jpinfo->part_prune_info = part_prune_info;
+ jpinfo->paramid = assign_special_exec_param(root);
+ jpinfo->nplans = list_length(subpaths);
+
+ candidate->joinpartprune_info_list =
+ lappend(candidate->joinpartprune_info_list, jpinfo);
+
+ result = bms_add_member(result, jpinfo->paramid);
+ }
+ }
+
+ return result;
+}
+
+/*
+ * prepare_join_partition_prune_candidate
+ * Check if join partition pruning is possible at this join and if so
+ * collect information required to build JoinPartitionPruneInfos.
+ *
+ * Note that we may build more than one JoinPartitionPruneInfo at one join, for
+ * different Append/MergeAppend paths.
+ */
+void
+prepare_join_partition_prune_candidate(PlannerInfo *root, JoinPath *jpath)
+{
+ JoinPartitionPruneCandidateInfo *candidate;
+
+ if (!enable_partition_pruning)
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ /*
+ * For now do not perform join partition pruning for parallel hashjoin.
+ */
+ if (jpath->path.parallel_workers > 0)
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ /*
+ * We cannot perform join partition pruning if the outer is the
+ * non-nullable side.
+ */
+ if (!(jpath->jointype == JOIN_INNER ||
+ jpath->jointype == JOIN_SEMI ||
+ jpath->jointype == JOIN_RIGHT ||
+ jpath->jointype == JOIN_RIGHT_ANTI))
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ /*
+ * For now we only support HashJoin.
+ */
+ if (jpath->path.pathtype != T_HashJoin)
+ {
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, NULL);
+ return;
+ }
+
+ candidate = makeNode(JoinPartitionPruneCandidateInfo);
+ candidate->joinrestrictinfo = jpath->joinrestrictinfo;
+ candidate->inner_relids = jpath->innerjoinpath->parent->relids;
+ candidate->inner_rows = jpath->innerjoinpath->parent->rows;
+ candidate->joinpartprune_info_list = NIL;
+
+ root->join_partition_prune_candidates =
+ lappend(root->join_partition_prune_candidates, candidate);
+}
+
+/*
+ * get_join_partition_prune_candidate
+ * Pop out the JoinPartitionPruneCandidateInfo for this join and retrieve
+ * the JoinPartitionPruneInfos.
+ */
+List *
+get_join_partition_prune_candidate(PlannerInfo *root)
+{
+ JoinPartitionPruneCandidateInfo *candidate;
+ List *result;
+
+ candidate = llast(root->join_partition_prune_candidates);
+ root->join_partition_prune_candidates =
+ list_delete_last(root->join_partition_prune_candidates);
+
+ if (candidate == NULL)
+ return NIL;
+
+ result = candidate->joinpartprune_info_list;
+
+ pfree(candidate);
+
+ return result;
+}
+
/*
* add_part_relids
* Add new info to a list of Bitmapsets of partitioned relids.
@@ -427,6 +619,8 @@ add_part_relids(List *allpartrelids, Bitmapset *partrelids)
* partrelids: Set of RT indexes identifying relevant partitioned tables
* within a single partitioning hierarchy
* relid_subplan_map[]: maps child relation relids to subplan indexes
+ * available_rels: the relid set of rels whose Vars may be used for
+ * pruning.
* matchedsubplans: on success, receives the set of subplan indexes which
* were matched to this partition hierarchy
*
@@ -439,6 +633,7 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
List *prunequal,
Bitmapset *partrelids,
int *relid_subplan_map,
+ Bitmapset *available_rels,
Bitmapset **matchedsubplans)
{
RelOptInfo *targetpart = NULL;
@@ -538,8 +733,8 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
* pruning steps and detects whether there's any possibly-useful quals
* that would require per-scan pruning.
*/
- gen_partprune_steps(subpart, partprunequal, PARTTARGET_INITIAL,
- &context);
+ gen_partprune_steps(subpart, partprunequal, available_rels,
+ PARTTARGET_INITIAL, &context);
if (context.contradictory)
{
@@ -566,14 +761,15 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
initial_pruning_steps = NIL;
/*
- * If no exec Params appear in potentially-usable pruning clauses,
- * then there's no point in even thinking about per-scan pruning.
+ * If no exec Params or available Vars appear in potentially-usable
+ * pruning clauses, then there's no point in even thinking about
+ * per-scan pruning.
*/
- if (context.has_exec_param)
+ if (context.has_exec_param || context.has_vars)
{
/* ... OK, we'd better think about it */
- gen_partprune_steps(subpart, partprunequal, PARTTARGET_EXEC,
- &context);
+ gen_partprune_steps(subpart, partprunequal, available_rels,
+ PARTTARGET_EXEC, &context);
if (context.contradictory)
{
@@ -586,11 +782,14 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
/*
* Detect which exec Params actually got used; the fact that some
* were in available clauses doesn't mean we actually used them.
- * Skip per-scan pruning if there are none.
*/
execparamids = get_partkey_exec_paramids(exec_pruning_steps);
- if (bms_is_empty(execparamids))
+ /*
+ * Skip per-scan pruning if there are none used exec Params and
+ * there are none available Vars.
+ */
+ if (bms_is_empty(execparamids) && !context.has_vars)
exec_pruning_steps = NIL;
}
else
@@ -702,6 +901,9 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
* Process 'clauses' (typically a rel's baserestrictinfo list of clauses)
* and create a list of "partition pruning steps".
*
+ * 'available_rels' is the relid set of rels whose Vars may be used for
+ * pruning.
+ *
* 'target' tells whether to generate pruning steps for planning (use
* immutable clauses only), or for executor startup (use any allowable
* clause except ones containing PARAM_EXEC Params), or for executor
@@ -711,12 +913,13 @@ make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
* some subsidiary flags; see the GeneratePruningStepsContext typedef.
*/
static void
-gen_partprune_steps(RelOptInfo *rel, List *clauses, PartClauseTarget target,
- GeneratePruningStepsContext *context)
+gen_partprune_steps(RelOptInfo *rel, List *clauses, Bitmapset *available_rels,
+ PartClauseTarget target, GeneratePruningStepsContext *context)
{
/* Initialize all output values to zero/false/NULL */
memset(context, 0, sizeof(GeneratePruningStepsContext));
context->rel = rel;
+ context->available_rels = available_rels;
context->target = target;
/*
@@ -772,7 +975,7 @@ prune_append_rel_partitions(RelOptInfo *rel)
* If the clauses are found to be contradictory, we can return the empty
* set.
*/
- gen_partprune_steps(rel, clauses, PARTTARGET_PLANNER,
+ gen_partprune_steps(rel, clauses, NULL, PARTTARGET_PLANNER,
&gcontext);
if (gcontext.contradictory)
return NULL;
@@ -2020,9 +2223,10 @@ match_clause_to_partition_key(GeneratePruningStepsContext *context,
return PARTCLAUSE_UNSUPPORTED;
/*
- * We can never prune using an expression that contains Vars.
+ * We can never prune using an expression that contains Vars except
+ * for Vars belonging to context->available_rels.
*/
- if (contain_var_clause((Node *) expr))
+ if (contain_forbidden_var_clause((Node *) expr, context))
return PARTCLAUSE_UNSUPPORTED;
/*
@@ -2218,9 +2422,10 @@ match_clause_to_partition_key(GeneratePruningStepsContext *context,
return PARTCLAUSE_UNSUPPORTED;
/*
- * We can never prune using an expression that contains Vars.
+ * We can never prune using an expression that contains Vars except
+ * for Vars belonging to context->available_rels.
*/
- if (contain_var_clause((Node *) rightop))
+ if (contain_forbidden_var_clause((Node *) rightop, context))
return PARTCLAUSE_UNSUPPORTED;
/*
@@ -3790,3 +3995,54 @@ partkey_datum_from_expr(PartitionPruneContext *context,
*value = ExecEvalExprSwitchContext(exprstate, ectx, isnull);
}
}
+
+/*
+ * contain_forbidden_var_clause
+ * Recursively scan a clause to discover whether it contains any Var nodes
+ * (of the current query level) that do not belong to relations in
+ * context->available_rels.
+ *
+ * Returns true if any such varnode found.
+ *
+ * Does not examine subqueries, therefore must only be used after reduction
+ * of sublinks to subplans!
+ */
+static bool
+contain_forbidden_var_clause(Node *node, GeneratePruningStepsContext *context)
+{
+ return contain_forbidden_var_clause_walker(node, context);
+}
+
+static bool
+contain_forbidden_var_clause_walker(Node *node, GeneratePruningStepsContext *context)
+{
+ if (node == NULL)
+ return false;
+ if (IsA(node, Var))
+ {
+ Var *var = (Var *) node;
+
+ if (var->varlevelsup != 0)
+ return false;
+
+ if (!bms_is_member(var->varno, context->available_rels))
+ return true; /* abort the tree traversal and return true */
+
+ context->has_vars = true;
+
+ if (context->target != PARTTARGET_EXEC)
+ return true; /* abort the tree traversal and return true */
+
+ return false;
+ }
+ if (IsA(node, CurrentOfExpr))
+ return true;
+ if (IsA(node, PlaceHolderVar))
+ {
+ if (((PlaceHolderVar *) node)->phlevelsup == 0)
+ return true; /* abort the tree traversal and return true */
+ /* else fall through to check the contained expr */
+ }
+ return expression_tree_walker(node, contain_forbidden_var_clause_walker,
+ (void *) context);
+}
diff --git a/src/include/executor/execPartition.h b/src/include/executor/execPartition.h
index c09bc83b2a..7e46f0baf6 100644
--- a/src/include/executor/execPartition.h
+++ b/src/include/executor/execPartition.h
@@ -121,11 +121,26 @@ typedef struct PartitionPruneState
PartitionPruningData *partprunedata[FLEXIBLE_ARRAY_MEMBER];
} PartitionPruneState;
+/*
+ * JoinPartitionPruneState - State object required for plan nodes to perform
+ * join partition pruning.
+ */
+typedef struct JoinPartitionPruneState
+{
+ PartitionPruneState *part_prune_state;
+ int paramid;
+ int nplans;
+ bool finished;
+ Bitmapset *part_prune_result;
+} JoinPartitionPruneState;
+
extern PartitionPruneState *ExecInitPartitionPruning(PlanState *planstate,
int n_total_subplans,
PartitionPruneInfo *pruneinfo,
Bitmapset **initially_valid_subplans);
+extern List *ExecInitJoinpartpruneList(PlanState *planstate, List *joinpartprune_info_list);
extern Bitmapset *ExecFindMatchingSubPlans(PartitionPruneState *prunestate,
- bool initial_prune);
+ bool initial_prune,
+ PlanState *planstate);
#endif /* EXECPARTITION_H */
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 9259352672..3cfd011a0a 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2684,6 +2684,9 @@ typedef struct HashState
/* Parallel hash state. */
struct ParallelHashJoinState *parallel_state;
+
+ /* Infos for join partition pruning. */
+ List *joinpartprune_state_list;
} HashState;
/* ----------------
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 534692bee1..da7803448a 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -530,6 +530,9 @@ struct PlannerInfo
/* not-yet-assigned NestLoopParams */
List *curOuterParams;
+ /* a stack of JoinPartitionPruneInfos */
+ List *join_partition_prune_candidates;
+
/*
* These fields are workspace for setrefs.c. Each is an array
* corresponding to glob->subplans. (We could probably teach
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index b4ef6bc44c..964bc85123 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -275,6 +275,9 @@ typedef struct Append
/* Info for run-time subplan pruning; NULL if we're not doing that */
struct PartitionPruneInfo *part_prune_info;
+
+ /* Info for join partition pruning; NULL if we're not doing that */
+ Bitmapset *join_prune_paramids;
} Append;
/* ----------------
@@ -310,6 +313,9 @@ typedef struct MergeAppend
/* Info for run-time subplan pruning; NULL if we're not doing that */
struct PartitionPruneInfo *part_prune_info;
+
+ /* Info for join partition pruning; NULL if we're not doing that */
+ Bitmapset *join_prune_paramids;
} MergeAppend;
/* ----------------
@@ -1206,6 +1212,7 @@ typedef struct Hash
bool skewInherit; /* is outer join rel an inheritance tree? */
/* all other info is in the parent HashJoin node */
Cardinality rows_total; /* estimate total rows if parallel_aware */
+ List *joinpartprune_info_list; /* infos for join partition pruning */
} Hash;
/* ----------------
@@ -1552,6 +1559,35 @@ typedef struct PartitionPruneStepCombine
List *source_stepids;
} PartitionPruneStepCombine;
+/*
+ * JoinPartitionPruneCandidateInfo - Information required to build
+ * JoinPartitionPruneInfos.
+ */
+typedef struct JoinPartitionPruneCandidateInfo
+{
+ pg_node_attr(no_equal, no_query_jumble)
+
+ NodeTag type;
+ List *joinrestrictinfo;
+ Bitmapset *inner_relids;
+ double inner_rows;
+ List *joinpartprune_info_list;
+} JoinPartitionPruneCandidateInfo;
+
+/*
+ * JoinPartitionPruneInfo - Details required to allow the executor to prune
+ * partitions during join.
+ */
+typedef struct JoinPartitionPruneInfo
+{
+ pg_node_attr(no_equal, no_query_jumble)
+
+ NodeTag type;
+ PartitionPruneInfo *part_prune_info;
+ int paramid;
+ int nplans;
+} JoinPartitionPruneInfo;
+
/*
* Plan invalidation info
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index b1c51a4e70..5ccd3c62d4 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -212,5 +212,9 @@ extern PathTarget *set_pathtarget_cost_width(PlannerInfo *root, PathTarget *targ
extern double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel,
Path *bitmapqual, double loop_count,
Cost *cost_p, double *tuples_p);
+extern double compute_partprune_cost(PlannerInfo *root, RelOptInfo *appendrel,
+ Cost append_total_cost, int append_nplans,
+ Relids inner_relids, double inner_rows,
+ List *prunequal);
#endif /* COST_H */
diff --git a/src/include/partitioning/partprune.h b/src/include/partitioning/partprune.h
index bd490d154f..5187485c88 100644
--- a/src/include/partitioning/partprune.h
+++ b/src/include/partitioning/partprune.h
@@ -19,6 +19,8 @@
struct PlannerInfo; /* avoid including pathnodes.h here */
struct RelOptInfo;
+struct Path;
+struct JoinPath;
/*
@@ -73,7 +75,15 @@ typedef struct PartitionPruneContext
extern PartitionPruneInfo *make_partition_pruneinfo(struct PlannerInfo *root,
struct RelOptInfo *parentrel,
List *subpaths,
- List *prunequal);
+ List *prunequal,
+ Bitmapset *available_rels);
+extern Bitmapset *make_join_partition_pruneinfos(struct PlannerInfo *root,
+ struct RelOptInfo *parentrel,
+ struct Path *best_path,
+ List *subpaths);
+extern void prepare_join_partition_prune_candidate(struct PlannerInfo *root,
+ struct JoinPath *jpath);
+extern List *get_join_partition_prune_candidate(struct PlannerInfo *root);
extern Bitmapset *prune_append_rel_partitions(struct RelOptInfo *rel);
extern Bitmapset *get_matching_partitions(PartitionPruneContext *context,
List *pruning_steps);
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 9c20a24982..7f51a3986e 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -3144,6 +3144,92 @@ order by tbl1.col1, tprt.col1;
------+------
(0 rows)
+-- join partition pruning
+-- The 'Memory Usage' from the Hash node can vary between machines. Let's just
+-- replace the number with an 'N'.
+-- We need to run EXPLAIN ANALYZE because we need to see '(never executed)'
+-- notations because that's the only way to verify runtime pruning.
+create function explain_join_partition_pruning(text) returns setof text
+language plpgsql as
+$$
+declare
+ ln text;
+begin
+ for ln in
+ execute format('explain (analyze, verbose, costs off, summary off, timing off) %s',
+ $1)
+ loop
+ ln := regexp_replace(ln, 'Memory Usage: \d+', 'Memory Usage: N');
+ return next ln;
+ end loop;
+end;
+$$;
+delete from tbl1;
+insert into tbl1 values (501), (505);
+analyze tbl1, tprt;
+set enable_nestloop = off;
+set enable_mergejoin = off;
+set enable_hashjoin = on;
+select explain_join_partition_pruning('
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;');
+ explain_join_partition_pruning
+--------------------------------------------------------------------------------
+ Hash Right Join (actual rows=2 loops=1)
+ Output: p1.col1, p2.col1, t.col1
+ Hash Cond: ((p1.col1 = t.col1) AND (p2.col1 = t.col1))
+ -> Hash Join (actual rows=3 loops=1)
+ Output: p1.col1, p2.col1
+ Hash Cond: (p1.col1 = p2.col1)
+ -> Append (actual rows=3 loops=1)
+ Join Partition Pruning: $0
+ -> Seq Scan on public.tprt_1 p1_1 (never executed)
+ Output: p1_1.col1
+ -> Seq Scan on public.tprt_2 p1_2 (actual rows=3 loops=1)
+ Output: p1_2.col1
+ -> Seq Scan on public.tprt_3 p1_3 (never executed)
+ Output: p1_3.col1
+ -> Seq Scan on public.tprt_4 p1_4 (never executed)
+ Output: p1_4.col1
+ -> Seq Scan on public.tprt_5 p1_5 (never executed)
+ Output: p1_5.col1
+ -> Seq Scan on public.tprt_6 p1_6 (never executed)
+ Output: p1_6.col1
+ -> Hash (actual rows=3 loops=1)
+ Output: p2.col1
+ Buckets: 1024 Batches: 1 Memory Usage: NkB
+ -> Append (actual rows=3 loops=1)
+ Join Partition Pruning: $1
+ -> Seq Scan on public.tprt_1 p2_1 (never executed)
+ Output: p2_1.col1
+ -> Seq Scan on public.tprt_2 p2_2 (actual rows=3 loops=1)
+ Output: p2_2.col1
+ -> Seq Scan on public.tprt_3 p2_3 (never executed)
+ Output: p2_3.col1
+ -> Seq Scan on public.tprt_4 p2_4 (never executed)
+ Output: p2_4.col1
+ -> Seq Scan on public.tprt_5 p2_5 (never executed)
+ Output: p2_5.col1
+ -> Seq Scan on public.tprt_6 p2_6 (never executed)
+ Output: p2_6.col1
+ -> Hash (actual rows=2 loops=1)
+ Output: t.col1
+ Buckets: 1024 Batches: 1 Memory Usage: NkB
+ Partition Prune: $0, $1
+ -> Seq Scan on public.tbl1 t (actual rows=2 loops=1)
+ Output: t.col1
+(43 rows)
+
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;
+ col1 | col1 | col1
+------+------+------
+ 501 | 501 | 501
+ 505 | 505 | 505
+(2 rows)
+
drop table tbl1, tprt;
-- Test with columns defined in varying orders between each level
create table part_abc (a int not null, b int not null, c int not null) partition by list (a);
diff --git a/src/test/regress/sql/partition_prune.sql b/src/test/regress/sql/partition_prune.sql
index a09b27d820..2d1e96d51e 100644
--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
@@ -764,6 +764,45 @@ select tbl1.col1, tprt.col1 from tbl1
inner join tprt on tbl1.col1 = tprt.col1
order by tbl1.col1, tprt.col1;
+-- join partition pruning
+
+-- The 'Memory Usage' from the Hash node can vary between machines. Let's just
+-- replace the number with an 'N'.
+-- We need to run EXPLAIN ANALYZE because we need to see '(never executed)'
+-- notations because that's the only way to verify runtime pruning.
+create function explain_join_partition_pruning(text) returns setof text
+language plpgsql as
+$$
+declare
+ ln text;
+begin
+ for ln in
+ execute format('explain (analyze, verbose, costs off, summary off, timing off) %s',
+ $1)
+ loop
+ ln := regexp_replace(ln, 'Memory Usage: \d+', 'Memory Usage: N');
+ return next ln;
+ end loop;
+end;
+$$;
+
+delete from tbl1;
+insert into tbl1 values (501), (505);
+analyze tbl1, tprt;
+
+set enable_nestloop = off;
+set enable_mergejoin = off;
+set enable_hashjoin = on;
+
+select explain_join_partition_pruning('
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;');
+
+select * from tprt p1
+ inner join tprt p2 on p1.col1 = p2.col1
+ right join tbl1 t on p1.col1 = t.col1 and p2.col1 = t.col1;
+
drop table tbl1, tprt;
-- Test with columns defined in varying orders between each level
--
2.31.0
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Support run-time partition pruning for hash join
2023-11-07 07:55 Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
2024-01-27 03:29 ` Re: Support run-time partition pruning for hash join vignesh C <[email protected]>
2024-01-30 02:33 ` Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
2024-03-19 06:12 ` Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
@ 2024-09-05 07:56 ` Andrei Lepikhov <[email protected]>
0 siblings, 0 replies; 6+ messages in thread
From: Andrei Lepikhov @ 2024-09-05 07:56 UTC (permalink / raw)
To: Richard Guo <[email protected]>; +Cc: Alexander Lakhin <[email protected]>; David Rowley <[email protected]>; Andy Fan <[email protected]>; pgsql-hackers; vignesh C <[email protected]>
On 19/3/2024 07:12, Richard Guo wrote:
>
> On Tue, Jan 30, 2024 at 10:33 AM Richard Guo <[email protected]
> <mailto:[email protected]>> wrote:
>
> Attached is an updated patch. Nothing else has changed.
>
>
> Here is another rebase over master so it applies again. Nothing else
> has changed.
The patch doesn't apply to the master now.
I wonder why this work was suppressed - it looks highly profitable in
the case of foreign partitions. And the idea of cost-based enablement
makes it a must-have, I think.
I have just skimmed through the patch and have a couple of questions:
1. It makes sense to calculate the cost and remember the minimum number
of pruned partitions when the cost of HJ with probing is still
profitable. Why don't we disable this probing in runtime if we see that
the number of potentially pruning partitions is already too low?
2. Maybe I misunderstood the code, but having matched a hashed tuple
with a partition, it makes sense for further tuples to reduce the number
of probing expressions because we already know that the partition will
not be pruned.
--
regards, Andrei Lepikhov
^ permalink raw reply [nested|flat] 6+ messages in thread
end of thread, other threads:[~2024-09-05 07:56 UTC | newest]
Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2020-11-11 08:01 [PATCH v27 4/9] Add Incremental View Maintenance support to pg_dump Yugo Nagata <[email protected]>
2023-11-07 07:55 Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
2024-01-27 03:29 ` Re: Support run-time partition pruning for hash join vignesh C <[email protected]>
2024-01-30 02:33 ` Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
2024-03-19 06:12 ` Re: Support run-time partition pruning for hash join Richard Guo <[email protected]>
2024-09-05 07:56 ` Re: Support run-time partition pruning for hash join Andrei Lepikhov <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox