public inbox for [email protected]
help / color / mirror / Atom feedFrom: Richard Guo <[email protected]>
To: Ashutosh Bapat <[email protected]>
Cc: Anastasia Lubennikova <[email protected]>
Cc: Pg Hackers <[email protected]>
Cc: Richard Guo <[email protected]>
Cc: [email protected]
Subject: Re: A problem about partitionwise join
Date: Wed, 21 Jul 2021 16:44:53 +0800
Message-ID: <CAMbWs48C0ux9mc+AS7D7DP6CyJxjQS=2mxQTpMJJKEeTua5wbQ@mail.gmail.com> (raw)
In-Reply-To: <CAExHW5vx89LbqphcusNR3AJ+kihWXDo0gv7eJVu6+nsafwow-Q@mail.gmail.com>
References: <CAN_9JTzo_2F5dKLqXVtDX5V6dwqB0Xk+ihstpKEt3a1LT6X78A@mail.gmail.com>
<CAMbWs4-zhLVU-uH42_N_v-LQF+VTGruVadQr6A_amhjmugB9-g@mail.gmail.com>
<160467632488.7362.12712548134124442813.pgcf@coridan.postgresql.org>
<CAMbWs49wRS5CkrjEOZxCVLO+Vm5YE_XHrYh8FCQbyvW-OUoMCg@mail.gmail.com>
<CAExHW5vx89LbqphcusNR3AJ+kihWXDo0gv7eJVu6+nsafwow-Q@mail.gmail.com>
On Fri, Nov 27, 2020 at 8:05 PM Ashutosh Bapat <[email protected]>
wrote:
> On Tue, Nov 10, 2020 at 2:43 PM Richard Guo <[email protected]>
> wrote:
> > Thanks Anastasia. I've rebased the patch with latest master.
> >
> > To recap, the problem we are fixing here is when generating join clauses
> > from equivalence classes, we only select the joinclause with the 'best
> > score', or the first joinclause with a score of 3. This may cause us to
> > miss some joinclause on partition keys and thus fail to generate
> > partitionwise join.
> >
> > The initial idea for the fix is to create all the RestrictInfos from ECs
> > in order to check whether there exist equi-join conditions involving
> > pairs of matching partition keys of the relations being joined for all
> > partition keys. And then Tom proposed a much better idea which leverages
> > function exprs_known_equal() to tell whether the partkeys can be found
> > in the same eclass, which is the current implementation in the latest
> > patch.
> >
>
> In the example you gave earlier, the equi join on partition key was
> there but it was replaced by individual constant assignment clauses.
> So if we keep the original restrictclause in there with a new flag
> indicating that it's redundant, have_partkey_equi_join will still be
> able to use it without much change. Depending upon where all we need
> to use avoid restrictclauses with the redundant flag, this might be an
> easier approach. However, with Tom's idea partition-wise join may be
> used even when there is no equi-join between partition keys but there
> are clauses like pk = const for all tables involved and const is the
> same for all such tables.
>
Correct. So with Tom's idea partition-wise join can cope with clauses
such as 'foo.k1 = bar.k1 and foo.k2 = 16 and bar.k2 = 16'.
>
> In the spirit of small improvement made to the performance of
> have_partkey_equi_join(), pk_has_clause should be renamed as
> pk_known_equal and pks_known_equal as num_equal_pks.
>
Thanks for the suggestion. Will do that in the new version of patch.
>
> The loop traversing the partition keys at a given position, may be
> optimized further if we pass lists to exprs_known_equal() which in
> turns checks whether one expression from each list is member of a
> given EC. This will avoid traversing all equivalence classes for each
> partition key expression, which can be a huge improvement when there
> are many ECs. But I think if one of the partition key expression at a
> given position is member of an equivalence class all the other
> partition key expressions at that position should be part of that
> equivalence class since there should be an equi-join between those. So
> the loop in loop may not be required to start with.
>
Good point. Quote from one of Tom's earlier emails,
"It seems at least plausible that in the cases we care about, all the
partkeys on each side would be in the same eclasses anyway, so that
comparing the first members of each list would be sufficient."
But I'm not sure if this holds true in all cases. However, since each
base relation within the join contributes only one partexpr, the number
of partexprs would only be equal to the join degree. Thus the loop in
loop may not be a big problem?
PS. Sorry for delaying so long time!
Thanks
Richard
Attachments:
[application/octet-stream] v5-0001-Fix-up-partitionwise-join.patch (14.6K, ../CAMbWs48C0ux9mc+AS7D7DP6CyJxjQS=2mxQTpMJJKEeTua5wbQ@mail.gmail.com/3-v5-0001-Fix-up-partitionwise-join.patch)
download | inline diff:
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 6f1abbe47d..aa05c60bd8 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -2375,15 +2375,17 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
* Detect whether two expressions are known equal due to equivalence
* relationships.
*
- * Actually, this only shows that the expressions are equal according
- * to some opfamily's notion of equality --- but we only use it for
- * selectivity estimation, so a fuzzy idea of equality is OK.
+ * If opfamily is given, the expressions must be known equal per the semantics
+ * of that opfamily (note it has to be a btree opfamily, since those are the
+ * only opfamilies equivclass.c deals with). If opfamily is InvalidOid, we'll
+ * return true if they're equal according to any opfamily, which is fuzzy but
+ * OK for estimation purposes.
*
* Note: does not bother to check for "equal(item1, item2)"; caller must
* check that case if it's possible to pass identical items.
*/
bool
-exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
+exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2, Oid opfamily)
{
ListCell *lc1;
@@ -2398,6 +2400,17 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
if (ec->ec_has_volatile)
continue;
+ /*
+ * It's okay to consider ec_broken ECs here. Brokenness just means we
+ * couldn't derive all the implied clauses we'd have liked to; it does
+ * not invalidate our knowledge that the members are equal.
+ */
+
+ /* Ignore if this EC doesn't use specified opfamily */
+ if (OidIsValid(opfamily) &&
+ !list_member_oid(ec->ec_opfamilies, opfamily))
+ continue;
+
foreach(lc2, ec->ec_members)
{
EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
@@ -2426,8 +2439,7 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
* (In principle there might be more than one matching eclass if multiple
* collations are involved, but since collation doesn't matter for equality,
* we ignore that fine point here.) This is much like exprs_known_equal,
- * except that we insist on the comparison operator matching the eclass, so
- * that the result is definite not approximate.
+ * except for the format of the input.
*
* On success, we also set fkinfo->eclass[colno] to the matching eclass,
* and set fkinfo->fk_eclass_member[colno] to the eclass member for the
@@ -2468,7 +2480,7 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
/* Never match to a volatile EC */
if (ec->ec_has_volatile)
continue;
- /* Note: it seems okay to match to "broken" eclasses here */
+ /* It's okay to consider "broken" ECs here, see exprs_known_equal */
foreach(lc2, ec->ec_members)
{
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index e105a4d5f1..40b47ca85e 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -56,10 +56,10 @@ static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel,
static void set_foreign_rel_properties(RelOptInfo *joinrel,
RelOptInfo *outer_rel, RelOptInfo *inner_rel);
static void add_join_rel(PlannerInfo *root, RelOptInfo *joinrel);
-static void build_joinrel_partition_info(RelOptInfo *joinrel,
+static void build_joinrel_partition_info(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *outer_rel, RelOptInfo *inner_rel,
List *restrictlist, JoinType jointype);
-static bool have_partkey_equi_join(RelOptInfo *joinrel,
+static bool have_partkey_equi_join(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *rel1, RelOptInfo *rel2,
JoinType jointype, List *restrictlist);
static int match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel,
@@ -718,8 +718,8 @@ build_join_rel(PlannerInfo *root,
joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel);
/* Store the partition information. */
- build_joinrel_partition_info(joinrel, outer_rel, inner_rel, restrictlist,
- sjinfo->jointype);
+ build_joinrel_partition_info(root, joinrel, outer_rel, inner_rel,
+ restrictlist, sjinfo->jointype);
/*
* Set estimates of the joinrel's size.
@@ -884,8 +884,8 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
joinrel->has_eclass_joins = parent_joinrel->has_eclass_joins;
/* Is the join between partitions itself partitioned? */
- build_joinrel_partition_info(joinrel, outer_rel, inner_rel, restrictlist,
- jointype);
+ build_joinrel_partition_info(root, joinrel, outer_rel, inner_rel,
+ restrictlist, jointype);
/* Child joinrel is parallel safe if parent is parallel safe. */
joinrel->consider_parallel = parent_joinrel->consider_parallel;
@@ -1642,9 +1642,9 @@ find_param_path_info(RelOptInfo *rel, Relids required_outer)
* partitioned join relation.
*/
static void
-build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel,
- RelOptInfo *inner_rel, List *restrictlist,
- JoinType jointype)
+build_joinrel_partition_info(PlannerInfo *root, RelOptInfo *joinrel,
+ RelOptInfo *outer_rel, RelOptInfo *inner_rel,
+ List *restrictlist, JoinType jointype)
{
PartitionScheme part_scheme;
@@ -1670,7 +1670,7 @@ build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel,
!outer_rel->consider_partitionwise_join ||
!inner_rel->consider_partitionwise_join ||
outer_rel->part_scheme != inner_rel->part_scheme ||
- !have_partkey_equi_join(joinrel, outer_rel, inner_rel,
+ !have_partkey_equi_join(root, joinrel, outer_rel, inner_rel,
jointype, restrictlist))
{
Assert(!IS_PARTITIONED_REL(joinrel));
@@ -1713,15 +1713,14 @@ build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel,
* partition keys.
*/
static bool
-have_partkey_equi_join(RelOptInfo *joinrel,
+have_partkey_equi_join(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *rel1, RelOptInfo *rel2,
JoinType jointype, List *restrictlist)
{
PartitionScheme part_scheme = rel1->part_scheme;
+ bool pk_known_equal[PARTITION_MAX_KEYS];
+ int num_equal_pks;
ListCell *lc;
- int cnt_pks;
- bool pk_has_clause[PARTITION_MAX_KEYS];
- bool strict_op;
/*
* This function must only be called when the joined relations have same
@@ -1730,13 +1729,19 @@ have_partkey_equi_join(RelOptInfo *joinrel,
Assert(rel1->part_scheme == rel2->part_scheme);
Assert(part_scheme);
- memset(pk_has_clause, 0, sizeof(pk_has_clause));
+ /* We use a bool array to track which partkey columns are known equal */
+ memset(pk_known_equal, 0, sizeof(pk_known_equal));
+ /* ... as well as a count of how many are known equal */
+ num_equal_pks = 0;
+
+ /* First, look through the join's restriction clauses */
foreach(lc, restrictlist)
{
RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
OpExpr *opexpr;
Expr *expr1;
Expr *expr2;
+ bool strict_op;
int ipk1;
int ipk2;
@@ -1796,11 +1801,15 @@ have_partkey_equi_join(RelOptInfo *joinrel,
if (ipk1 != ipk2)
continue;
+ /* Ignore clause if we already proved these keys equal. */
+ if (pk_known_equal[ipk1])
+ continue;
+
/*
* The clause allows partitionwise join only if it uses the same
* operator family as that specified by the partition key.
*/
- if (rel1->part_scheme->strategy == PARTITION_STRATEGY_HASH)
+ if (part_scheme->strategy == PARTITION_STRATEGY_HASH)
{
if (!OidIsValid(rinfo->hashjoinoperator) ||
!op_in_opfamily(rinfo->hashjoinoperator,
@@ -1812,17 +1821,89 @@ have_partkey_equi_join(RelOptInfo *joinrel,
continue;
/* Mark the partition key as having an equi-join clause. */
- pk_has_clause[ipk1] = true;
+ pk_known_equal[ipk1] = true;
+
+ /* We can stop examining clauses once we prove all keys equal. */
+ if (++num_equal_pks == part_scheme->partnatts)
+ return true;
}
- /* Check whether every partition key has an equi-join condition. */
- for (cnt_pks = 0; cnt_pks < part_scheme->partnatts; cnt_pks++)
+ /*
+ * Also check to see if any keys are known equal by equivclass.c. In most
+ * cases there would have been a join restriction clause generated from
+ * any EC that had such knowledge, but there might be no such clause, or
+ * it might happen to constrain other members of the ECs than the ones we
+ * are looking for.
+ */
+ for (int ipk = 0; ipk < part_scheme->partnatts; ipk++)
{
- if (!pk_has_clause[cnt_pks])
- return false;
+ Oid btree_opfamily;
+
+ /* Ignore if we already proved these keys equal. */
+ if (pk_known_equal[ipk])
+ continue;
+
+ /*
+ * We need a btree opfamily to ask equivclass.c about. If the
+ * partopfamily is a hash opfamily, look up its equality operator, and
+ * select some btree opfamily that that operator is part of. (Any
+ * such opfamily should be good enough, since equivclass.c will track
+ * multiple opfamilies as appropriate.)
+ */
+ if (part_scheme->strategy == PARTITION_STRATEGY_HASH)
+ {
+ Oid eq_op;
+ List *eq_opfamilies;
+
+ eq_op = get_opfamily_member(part_scheme->partopfamily[ipk],
+ part_scheme->partopcintype[ipk],
+ part_scheme->partopcintype[ipk],
+ HTEqualStrategyNumber);
+ if (!OidIsValid(eq_op))
+ break; /* we're not going to succeed */
+ eq_opfamilies = get_mergejoin_opfamilies(eq_op);
+ if (eq_opfamilies == NIL)
+ break; /* we're not going to succeed */
+ btree_opfamily = linitial_oid(eq_opfamilies);
+ }
+ else
+ btree_opfamily = part_scheme->partopfamily[ipk];
+
+ /*
+ * We consider only non-nullable partition keys here; nullable ones
+ * would not be treated as part of the same equivalence classes as
+ * non-nullable ones.
+ */
+ foreach(lc, rel1->partexprs[ipk])
+ {
+ Node *expr1 = (Node *) lfirst(lc);
+ ListCell *lc2;
+
+ foreach(lc2, rel2->partexprs[ipk])
+ {
+ Node *expr2 = (Node *) lfirst(lc2);
+
+ if (exprs_known_equal(root, expr1, expr2, btree_opfamily))
+ {
+ pk_known_equal[ipk] = true;
+ break;
+ }
+ }
+ if (pk_known_equal[ipk])
+ break;
+ }
+
+ if (pk_known_equal[ipk])
+ {
+ /* We can stop examining keys once we prove all keys equal. */
+ if (++num_equal_pks == part_scheme->partnatts)
+ return true;
+ }
+ else
+ break; /* no chance to succeed, give up */
}
- return true;
+ return false;
}
/*
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 0c8c05f6c2..090ce8656e 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3265,10 +3265,11 @@ add_unique_group_var(PlannerInfo *root, List *varinfos,
/*
* Drop known-equal vars, but only if they belong to different
- * relations (see comments for estimate_num_groups)
+ * relations (see comments for estimate_num_groups). We aren't too
+ * fussy about the semantics of "equal" here.
*/
if (vardata->rel != varinfo->rel &&
- exprs_known_equal(root, var, varinfo->var))
+ exprs_known_equal(root, var, varinfo->var, InvalidOid))
{
if (varinfo->ndistinct <= ndistinct)
{
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index f1d111063c..e6488d3f37 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -157,7 +157,8 @@ extern List *generate_join_implied_equalities_for_ecs(PlannerInfo *root,
Relids join_relids,
Relids outer_relids,
RelOptInfo *inner_rel);
-extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2);
+extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2,
+ Oid opfamily);
extern EquivalenceClass *match_eclasses_to_foreign_key_col(PlannerInfo *root,
ForeignKeyOptInfo *fkinfo,
int colno);
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index 27f7525b3e..2bdee1f804 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -62,6 +62,45 @@ SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.b AND t1.b =
450 | 0450 | 450 | 0450
(4 rows)
+-- inner join with partially-redundant join clauses
+EXPLAIN (COSTS OFF)
+SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.a AND t1.a = t2.b ORDER BY t1.a, t2.b;
+ QUERY PLAN
+---------------------------------------------------------------
+ Sort
+ Sort Key: t1.a
+ -> Append
+ -> Merge Join
+ Merge Cond: (t1_1.a = t2_1.a)
+ -> Index Scan using iprt1_p1_a on prt1_p1 t1_1
+ -> Sort
+ Sort Key: t2_1.b
+ -> Seq Scan on prt2_p1 t2_1
+ Filter: (a = b)
+ -> Hash Join
+ Hash Cond: (t1_2.a = t2_2.a)
+ -> Seq Scan on prt1_p2 t1_2
+ -> Hash
+ -> Seq Scan on prt2_p2 t2_2
+ Filter: (a = b)
+ -> Hash Join
+ Hash Cond: (t1_3.a = t2_3.a)
+ -> Seq Scan on prt1_p3 t1_3
+ -> Hash
+ -> Seq Scan on prt2_p3 t2_3
+ Filter: (a = b)
+(22 rows)
+
+SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.a AND t1.a = t2.b ORDER BY t1.a, t2.b;
+ a | c | b | c
+----+------+----+------
+ 0 | 0000 | 0 | 0000
+ 6 | 0006 | 6 | 0006
+ 12 | 0012 | 12 | 0012
+ 18 | 0018 | 18 | 0018
+ 24 | 0024 | 24 | 0024
+(5 rows)
+
-- left outer join, with whole-row reference; partitionwise join does not apply
EXPLAIN (COSTS OFF)
SELECT t1, t2 FROM prt1 t1 LEFT JOIN prt2 t2 ON t1.a = t2.b WHERE t1.b = 0 ORDER BY t1.a, t2.b;
diff --git a/src/test/regress/sql/partition_join.sql b/src/test/regress/sql/partition_join.sql
index d97b5b69ff..6b7d6899dd 100644
--- a/src/test/regress/sql/partition_join.sql
+++ b/src/test/regress/sql/partition_join.sql
@@ -34,6 +34,11 @@ EXPLAIN (COSTS OFF)
SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.b AND t1.b = 0 ORDER BY t1.a, t2.b;
SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.b AND t1.b = 0 ORDER BY t1.a, t2.b;
+-- inner join with partially-redundant join clauses
+EXPLAIN (COSTS OFF)
+SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.a AND t1.a = t2.b ORDER BY t1.a, t2.b;
+SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.a AND t1.a = t2.b ORDER BY t1.a, t2.b;
+
-- left outer join, with whole-row reference; partitionwise join does not apply
EXPLAIN (COSTS OFF)
SELECT t1, t2 FROM prt1 t1 LEFT JOIN prt2 t2 ON t1.a = t2.b WHERE t1.b = 0 ORDER BY t1.a, t2.b;
view thread (32+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: A problem about partitionwise join
In-Reply-To: <CAMbWs48C0ux9mc+AS7D7DP6CyJxjQS=2mxQTpMJJKEeTua5wbQ@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox