From eb6e080b3053c4b45d97989f420e08e310b362c1 Mon Sep 17 00:00:00 2001 From: Yuya Watari Date: Mon, 8 Aug 2022 15:51:36 +0900 Subject: [PATCH 3/3] Implement optimizations based on Bitmapset --- contrib/postgres_fdw/postgres_fdw.c | 17 +- src/backend/optimizer/path/allpaths.c | 2 +- src/backend/optimizer/path/equivclass.c | 200 +++++++++++++--------- src/backend/optimizer/path/indxpath.c | 10 +- src/backend/optimizer/path/pathkeys.c | 27 +-- src/backend/optimizer/plan/planner.c | 2 + src/backend/optimizer/prep/prepjointree.c | 2 + src/backend/optimizer/util/relnode.c | 8 + src/include/nodes/pathnodes.h | 12 ++ src/include/optimizer/paths.h | 152 +++++++++++++++- 10 files changed, 329 insertions(+), 103 deletions(-) diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c index 6bbf10d679..d2b69a4171 100644 --- a/contrib/postgres_fdw/postgres_fdw.c +++ b/contrib/postgres_fdw/postgres_fdw.c @@ -7413,17 +7413,19 @@ EquivalenceMember * find_em_for_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel) { int i = -1; + Bitmapset *matching_ems = + get_eclass_members_indexes_for_subsets_of_relids(root, ec, rel->relids); - while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0) + while ((i = bms_next_member(matching_ems, i)) >= 0) { EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i); + Assert(bms_is_subset(em->em_relids, rel->relids)); /* * Note we require !bms_is_empty, else we'd accept constant * expressions which are not suitable for the purpose. */ - if (bms_is_subset(em->em_relids, rel->relids) && - !bms_is_empty(em->em_relids) && + if (!bms_is_empty(em->em_relids) && is_foreign_expr(root, rel, em->em_expr)) return em; } @@ -7456,6 +7458,7 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec, Expr *expr = (Expr *) lfirst(lc1); Index sgref = get_pathtarget_sortgroupref(target, i); int j; + Bitmapset *matching_ems; /* Ignore non-sort expressions */ if (sgref == 0 || @@ -7472,7 +7475,9 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec, /* Locate an EquivalenceClass member matching this expr, if any */ j = -1; - while ((j = bms_next_member(ec->ec_member_indexes, j)) >= 0) + /* Ignore child members */ + matching_ems = get_eclass_members_indexes_for_not_children(root, ec); + while ((j = bms_next_member(matching_ems, j)) >= 0) { EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, j); Expr *em_expr; @@ -7481,9 +7486,7 @@ find_em_for_rel_target(PlannerInfo *root, EquivalenceClass *ec, if (em->em_is_const) continue; - /* Ignore child members */ - if (em->em_is_child) - continue; + Assert(!em->em_is_child); /* Match if same expression (after stripping relabel) */ em_expr = em->em_expr; diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 9b6a5b08dc..394ae1483f 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -2755,7 +2755,7 @@ set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) (Expr *) var, NULL, /* below outer joins */ Int8LessOperator, - rel->relids, + rel, false); } diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index 90c96de7d8..44505c0c36 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -378,19 +378,30 @@ process_equivalence(PlannerInfo *root, EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i); int em_index = list_length(root->eq_members); int j; + bool relids_is_empty; ec1->ec_member_indexes = bms_add_member(ec1->ec_member_indexes, em_index); root->eq_members = lappend(root->eq_members, em); j = -1; + relids_is_empty = true; while ((j = bms_next_member(em->em_relids, j)) > 0) { RelOptInfo *rel = root->simple_rel_array[j]; + + relids_is_empty = false; + rel->eclass_referencing_member_indexes = + bms_add_member(rel->eclass_referencing_member_indexes, em_index); if (bms_equal(rel->relids, em->em_relids)) { rel->eclass_member_indexes = bms_add_member(rel->eclass_member_indexes, em_index); } } + + if (relids_is_empty) + { + root->eq_empty_relids_indexes = bms_add_member(root->eq_empty_relids_indexes, em_index); + } } ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources); ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives); @@ -576,6 +587,7 @@ add_eq_member(PlannerInfo *root, EquivalenceClass *ec, Expr *expr, EquivalenceMember *em = makeNode(EquivalenceMember); int em_index; int i; + bool relids_is_empty; em->em_expr = expr; em->em_relids = relids; @@ -606,17 +618,32 @@ add_eq_member(PlannerInfo *root, EquivalenceClass *ec, Expr *expr, em_index = list_length(root->eq_members); ec->ec_member_indexes = bms_add_member(ec->ec_member_indexes, em_index); root->eq_members = lappend(root->eq_members, em); + if (!is_child) + { + root->eq_not_children_indexes = bms_add_member(root->eq_not_children_indexes, + em_index); + } i = -1; + relids_is_empty = true; while ((i = bms_next_member(relids, i)) > 0) { RelOptInfo *rel = root->simple_rel_array[i]; + + relids_is_empty = false; + rel->eclass_referencing_member_indexes = + bms_add_member(rel->eclass_referencing_member_indexes, em_index); if (bms_equal(rel->relids, relids)) { rel->eclass_member_indexes = bms_add_member(rel->eclass_member_indexes, em_index); } } + if (relids_is_empty) + { + root->eq_empty_relids_indexes = bms_add_member(root->eq_empty_relids_indexes, em_index); + } + return em; } @@ -667,7 +694,7 @@ get_eclass_for_sort_expr(PlannerInfo *root, Oid opcintype, Oid collation, Index sortref, - Relids rel, + RelOptInfo *rel, bool create_it) { Relids expr_relids; @@ -688,6 +715,7 @@ get_eclass_for_sort_expr(PlannerInfo *root, { EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1); int i; + Bitmapset *matching_ems; /* * Never match to a volatile EC, except when we are looking at another @@ -702,17 +730,16 @@ get_eclass_for_sort_expr(PlannerInfo *root, if (!equal(opfamilies, cur_ec->ec_opfamilies)) continue; + /* + * Ignore child members unless they match the request. + */ + matching_ems = + get_eclass_members_indexes_for_relids_or_not_children(root, cur_ec, rel); i = -1; - while ((i = bms_next_member(cur_ec->ec_member_indexes, i)) >= 0) + while ((i = bms_next_member(matching_ems, i)) >= 0) { EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i); - - /* - * Ignore child members unless they match the request. - */ - if (cur_em->em_is_child && - !bms_equal(cur_em->em_relids, rel)) - continue; + Assert(!cur_em->em_is_child || bms_equal(cur_em->em_relids, rel->relids)); /* * If below an outer join, don't match constants: they're not as @@ -809,13 +836,13 @@ get_eclass_for_sort_expr(PlannerInfo *root, while ((i = bms_next_member(newec->ec_relids, i)) > 0) { - RelOptInfo *rel = root->simple_rel_array[i]; + RelOptInfo *rel2 = root->simple_rel_array[i]; - Assert(rel->reloptkind == RELOPT_BASEREL || - rel->reloptkind == RELOPT_DEADREL); + Assert(rel2->reloptkind == RELOPT_BASEREL || + rel2->reloptkind == RELOPT_DEADREL); - rel->eclass_indexes = bms_add_member(rel->eclass_indexes, - ec_index); + rel2->eclass_indexes = bms_add_member(rel2->eclass_indexes, + ec_index); } } @@ -843,13 +870,19 @@ find_ec_member_matching_expr(PlannerInfo *root, Relids relids) { int i; + Bitmapset *matching_ems; /* We ignore binary-compatible relabeling on both ends */ while (expr && IsA(expr, RelabelType)) expr = ((RelabelType *) expr)->arg; + /* + * Ignore child members unless they belong to the requested rel. + */ + matching_ems = + get_eclass_members_indexes_for_subsets_of_relids_or_not_children(root, ec, relids); i = -1; - while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0) + while ((i = bms_next_member(matching_ems, i)) >= 0) { EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i); Expr *emexpr; @@ -861,12 +894,7 @@ find_ec_member_matching_expr(PlannerInfo *root, if (em->em_is_const) continue; - /* - * Ignore child members unless they belong to the requested rel. - */ - if (em->em_is_child && - !bms_is_subset(em->em_relids, relids)) - continue; + Assert(!em->em_is_child || bms_is_subset(em->em_relids, relids)); /* * Match if same expression (after stripping relabel). @@ -912,7 +940,13 @@ find_computable_ec_member(PlannerInfo *root, { int i = -1; - while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0) + /* + * Ignore child members unless they belong to the requested rel. + */ + Bitmapset *matching_ems = + get_eclass_members_indexes_for_subsets_of_relids_or_not_children(root, ec, relids); + + while ((i = bms_next_member(matching_ems, i)) >= 0) { EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i); List *exprvars; @@ -925,12 +959,7 @@ find_computable_ec_member(PlannerInfo *root, if (em->em_is_const) continue; - /* - * Ignore child members unless they belong to the requested rel. - */ - if (em->em_is_child && - !bms_is_subset(em->em_relids, relids)) - continue; + Assert(!em->em_is_child || bms_is_subset(em->em_relids, relids)); /* * Match if all Vars and quasi-Vars are available in "exprs". @@ -1610,6 +1639,7 @@ generate_join_implied_equalities_normal(PlannerInfo *root, List *inner_members = NIL; ListCell *lc1; int i; + Bitmapset *matching_ems; /* * First, scan the EC to identify member values that are computable at the @@ -1620,18 +1650,17 @@ generate_join_implied_equalities_normal(PlannerInfo *root, * as well as to at least one input member, plus enforce at least one * outer-rel member equal to at least one inner-rel member. */ + /* + * We don't need to check explicitly for child EC members. This test + * against join_relids will cause them to be ignored except when + * considering a child inner rel, which is what we want. + */ + matching_ems = get_eclass_members_indexes_for_subsets_of_relids(root, ec, join_relids); i = -1; - while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0) + while ((i = bms_next_member(matching_ems, i)) >= 0) { EquivalenceMember *cur_em = (EquivalenceMember *)list_nth(root->eq_members, i); - - /* - * We don't need to check explicitly for child EC members. This test - * against join_relids will cause them to be ignored except when - * considering a child inner rel, which is what we want. - */ - if (!bms_is_subset(cur_em->em_relids, join_relids)) - continue; /* not computable yet, or wrong child */ + Assert(bms_is_subset(cur_em->em_relids, join_relids)); if (bms_is_subset(cur_em->em_relids, outer_relids)) outer_members = lappend(outer_members, cur_em); @@ -2392,12 +2421,16 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo) if (matchleft && matchright) { cur_ec->ec_member_indexes = bms_del_member(cur_ec->ec_member_indexes, coal_idx); + root->eq_not_children_indexes = bms_del_member(root->eq_not_children_indexes, + coal_idx); /* Remove the member from each of the relations */ i = -1; while ((i = bms_next_member(coal_em->em_relids, i)) > 0) { RelOptInfo *rel = root->simple_rel_array[i]; + rel->eclass_referencing_member_indexes = + bms_del_member(rel->eclass_referencing_member_indexes, coal_idx); if (bms_equal(rel->relids, coal_em->em_relids)) { rel->eclass_member_indexes = bms_del_member(rel->eclass_member_indexes, coal_idx); @@ -2442,18 +2475,20 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2) bool item1member = false; bool item2member = false; int i; + Bitmapset *matching_ems; /* Never match to a volatile EC */ if (ec->ec_has_volatile) continue; i = -1; - while ((i = bms_next_member(ec->ec_member_indexes, i)) >= 0) + /* ignore children here */ + matching_ems = get_eclass_members_indexes_for_not_children(root, ec); + while ((i = bms_next_member(matching_ems, i)) >= 0) { EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i); + Assert(!em->em_is_child); - if (em->em_is_child) - continue; /* ignore children here */ if (equal(item1, em->em_expr)) item1member = true; else if (equal(item2, em->em_expr)) @@ -2514,6 +2549,7 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root, EquivalenceMember *item1_em = NULL; EquivalenceMember *item2_em = NULL; int j; + Bitmapset *matching_ems; /* Never match to a volatile EC */ if (ec->ec_has_volatile) @@ -2521,13 +2557,14 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root, /* Note: it seems okay to match to "broken" eclasses here */ j = -1; - while ((j = bms_next_member(ec->ec_member_indexes, j)) >= 0) + /* ignore children here */ + matching_ems = get_eclass_members_indexes_for_not_children(root, ec); + while ((j = bms_next_member(matching_ems, j)) >= 0) { EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, j); Var *var; - if (em->em_is_child) - continue; /* ignore children here */ + Assert(!em->em_is_child); /* EM must be a Var, possibly with RelabelType */ var = (Var *) em->em_expr; @@ -2636,8 +2673,9 @@ add_child_rel_equivalences(PlannerInfo *root, while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0) { EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i); - int num_members; + int final_member; int j; + Bitmapset *matching_ems; /* * If this EC contains a volatile expression, then generating child @@ -2656,28 +2694,28 @@ add_child_rel_equivalences(PlannerInfo *root, * Use bms_prev_member(..., -1) to get the final member first and * abort the loop when we go beyond that? */ - num_members = bms_num_members(cur_ec->ec_member_indexes); + final_member = bms_prev_member(cur_ec->ec_member_indexes, -1); + + /* + * We consider only original EC members here, not + * already-transformed child members. Otherwise, if some original + * member expression references more than one appendrel, we'd get + * an O(N^2) explosion of useless derived expressions for + * combinations of children. (But add_child_join_rel_equivalences + * may add targeted combinations for partitionwise-join purposes.) + */ + /* ignore children here */ + matching_ems = get_eclass_members_indexes_for_not_children(root, cur_ec); j = -1; - for (int pos = 0; pos < num_members; pos++) + while ((j = bms_next_member(matching_ems, j)) >= 0 && j <= final_member) { EquivalenceMember *cur_em; - - j = bms_next_member(cur_ec->ec_member_indexes, j); cur_em = (EquivalenceMember *) list_nth(root->eq_members, j); if (cur_em->em_is_const) continue; /* ignore consts here */ - /* - * We consider only original EC members here, not - * already-transformed child members. Otherwise, if some original - * member expression references more than one appendrel, we'd get - * an O(N^2) explosion of useless derived expressions for - * combinations of children. (But add_child_join_rel_equivalences - * may add targeted combinations for partitionwise-join purposes.) - */ - if (cur_em->em_is_child) - continue; /* ignore children here */ + Assert(!cur_em->em_is_child); /* Does this member reference child's topmost parent rel? */ if (bms_overlap(cur_em->em_relids, top_parent_relids)) @@ -2780,8 +2818,9 @@ add_child_join_rel_equivalences(PlannerInfo *root, while ((i = bms_next_member(matching_ecs, i)) >= 0) { EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i); - int num_members; + int final_member; int j; + Bitmapset *matching_ems; /* * If this EC contains a volatile expression, then generating child @@ -2800,24 +2839,24 @@ add_child_join_rel_equivalences(PlannerInfo *root, * Use bms_prev_member(..., -1) to get the final member first and * abort the loop when we go beyond that? */ - num_members = bms_num_members(cur_ec->ec_member_indexes); + final_member = bms_prev_member(cur_ec->ec_member_indexes, -1); + + /* + * We consider only original EC members here, not + * already-transformed child members. + */ + /* ignore children here */ + matching_ems = get_eclass_members_indexes_for_not_children(root, cur_ec); j = -1; - for (int pos = 0; pos < num_members; pos++) + while ((j = bms_next_member(matching_ems, j)) >= 0 && j <= final_member) { EquivalenceMember *cur_em; - - j = bms_next_member(cur_ec->ec_member_indexes, j); cur_em = (EquivalenceMember *) list_nth(root->eq_members, j); if (cur_em->em_is_const) continue; /* ignore consts here */ - /* - * We consider only original EC members here, not - * already-transformed child members. - */ - if (cur_em->em_is_child) - continue; /* ignore children here */ + Assert(!cur_em->em_is_child); /* * We may ignore expressions that reference a single baserel, @@ -2939,6 +2978,7 @@ generate_implied_equalities_for_column(PlannerInfo *root, EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i); EquivalenceMember *cur_em; int j; + Bitmapset *matching_ems; /* Sanity check eclass_indexes only contain ECs for rel */ Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids)); @@ -2962,13 +3002,14 @@ generate_implied_equalities_for_column(PlannerInfo *root, * match. See also get_eclass_for_sort_expr.) */ cur_em = NULL; + matching_ems = get_eclass_members_indexes_for_relids(root, cur_ec, rel); j = -1; - while ((j = bms_next_member(cur_ec->ec_member_indexes, j)) >= 0) + while ((j = bms_next_member(matching_ems, j)) >= 0) { cur_em = (EquivalenceMember *) list_nth(root->eq_members, j); - if (bms_equal(cur_em->em_relids, rel->relids) && - callback(root, rel, cur_ec, cur_em, callback_arg)) + Assert(bms_equal(cur_em->em_relids, rel->relids)); + if (callback(root, rel, cur_ec, cur_em, callback_arg)) break; cur_em = NULL; } @@ -2981,14 +3022,15 @@ generate_implied_equalities_for_column(PlannerInfo *root, * joinclauses. */ j = -1; - while ((j = bms_next_member(cur_ec->ec_member_indexes, j)) >= 0) + /* ignore children here */ + matching_ems = get_eclass_members_indexes_for_not_children(root, cur_ec); + while ((j = bms_next_member(matching_ems, j)) >= 0) { EquivalenceMember *other_em = (EquivalenceMember *) list_nth(root->eq_members, j); Oid eq_op; RestrictInfo *rinfo; - if (other_em->em_is_child) - continue; /* ignore children here */ + Assert(!other_em->em_is_child); /* Make sure it'll be a join to a different rel */ if (other_em == cur_em || @@ -3161,6 +3203,7 @@ eclass_useful_for_merging(PlannerInfo *root, { Relids relids; int i; + Bitmapset *matching_ems; Assert(!eclass->ec_merged); @@ -3192,13 +3235,14 @@ eclass_useful_for_merging(PlannerInfo *root, return false; /* To join, we need a member not in the given rel */ + /* ignore children here */ + matching_ems = get_eclass_members_indexes_for_not_children(root, eclass); i = -1; - while ((i = bms_next_member(eclass->ec_member_indexes, i)) >= 0) + while ((i = bms_next_member(matching_ems, i)) >= 0) { EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(root->eq_members, i); - if (cur_em->em_is_child) - continue; /* ignore children here */ + Assert(!cur_em->em_is_child); if (!bms_overlap(cur_em->em_relids, relids)) return true; diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 4c18ada572..843b7c7be3 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -3093,6 +3093,7 @@ match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index, PathKey *pathkey = (PathKey *) lfirst(lc1); bool found = false; int i; + Bitmapset *matching_ems; /* * Note: for any failure to match, we just return NIL immediately. @@ -3117,14 +3118,15 @@ match_pathkeys_to_index(PlannerInfo *root, IndexOptInfo *index, * here. See also get_eclass_for_sort_expr.) */ i = -1; - while ((i = bms_next_member(pathkey->pk_eclass->ec_member_indexes, i)) >= 0) + /* No possibility of match if it references other relations */ + matching_ems = + get_eclass_members_indexes_for_relids(root, pathkey->pk_eclass, index->rel); + while ((i = bms_next_member(matching_ems, i)) >= 0) { EquivalenceMember *member = (EquivalenceMember *) list_nth(root->eq_members, i); int indexcol; - /* No possibility of match if it references other relations */ - if (!bms_equal(member->em_relids, index->rel->relids)) - continue; + Assert(bms_equal(member->em_relids, index->rel->relids)); /* * We allow any column of the index to match each pathkey; they diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index de864023b2..6fcf0ccb01 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -212,7 +212,7 @@ make_pathkey_from_sortinfo(PlannerInfo *root, bool reverse_sort, bool nulls_first, Index sortref, - Relids rel, + RelOptInfo *rel, bool create_it) { int16 strategy; @@ -1134,7 +1134,7 @@ build_index_pathkeys(PlannerInfo *root, reverse_sort, nulls_first, 0, - index->rel->relids, + index->rel, false); if (cpathkey) @@ -1290,7 +1290,7 @@ build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel, ScanDirectionIsBackward(scandir), ScanDirectionIsBackward(scandir), 0, - partrel->relids, + partrel, false); @@ -1343,7 +1343,7 @@ build_expression_pathkey(PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opno, - Relids rel, + RelOptInfo *rel, bool create_it) { List *pathkeys; @@ -1455,7 +1455,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel, sub_member->em_datatype, sub_eclass->ec_collation, 0, - rel->relids, + rel, false); /* @@ -1491,8 +1491,11 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel, */ int best_score = -1; int j = -1; + /* ignore children here */ + Bitmapset *matching_ems = + get_eclass_members_indexes_for_not_children(rel->subroot, sub_eclass); - while ((j = bms_next_member(sub_eclass->ec_member_indexes, j)) >= 0) + while ((j = bms_next_member(matching_ems, j)) >= 0) { EquivalenceMember *sub_member = (EquivalenceMember *) list_nth(rel->subroot->eq_members, j); Expr *sub_expr = sub_member->em_expr; @@ -1500,8 +1503,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel, Oid sub_expr_coll = sub_eclass->ec_collation; ListCell *k; - if (sub_member->em_is_child) - continue; /* ignore children here */ + Assert(!sub_member->em_is_child); foreach(k, subquery_tlist) { @@ -1537,7 +1539,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel, sub_expr_type, sub_expr_coll, 0, - rel->relids, + rel, false); /* @@ -1966,6 +1968,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root, EquivalenceClass *oeclass; int score; int i; + Bitmapset *matching_ems; /* get the outer eclass */ update_mergeclause_eclasses(root, rinfo); @@ -1987,12 +1990,14 @@ select_outer_pathkeys_for_merge(PlannerInfo *root, /* compute score */ score = 0; i = -1; - while ((i = bms_next_member(oeclass->ec_member_indexes, i)) >= 0) + matching_ems = get_eclass_members_indexes_for_not_children(root, oeclass); + while ((i = bms_next_member(matching_ems, i)) >= 0) { EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, i); + Assert(!em->em_is_child); /* Potential future join partner? */ - if (!em->em_is_const && !em->em_is_child && + if (!em->em_is_const && !bms_overlap(em->em_relids, joinrel->relids)) score++; } diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index d0bc9a467d..e71f115fd6 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -620,6 +620,8 @@ subquery_planner(PlannerGlobal *glob, Query *parse, root->multiexpr_params = NIL; root->eq_classes = NIL; root->eq_members = NIL; + root->eq_not_children_indexes = NULL; + root->eq_empty_relids_indexes = NULL; root->ec_merging_done = false; root->all_result_relids = parse->resultRelation ? bms_make_singleton(parse->resultRelation) : NULL; diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c index f3e6c19fc7..90a5dcae72 100644 --- a/src/backend/optimizer/prep/prepjointree.c +++ b/src/backend/optimizer/prep/prepjointree.c @@ -999,6 +999,8 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, subroot->multiexpr_params = NIL; subroot->eq_classes = NIL; subroot->eq_members = NIL; + subroot->eq_not_children_indexes = NULL; + subroot->eq_empty_relids_indexes = NULL; subroot->ec_merging_done = false; subroot->all_result_relids = NULL; subroot->leaf_result_relids = NULL; diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 520409f4ba..101742959a 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -231,6 +231,8 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent) rel->tuples = 0; rel->allvisfrac = 0; rel->eclass_indexes = NULL; + rel->eclass_member_indexes = NULL; + rel->eclass_referencing_member_indexes = NULL; rel->subroot = NULL; rel->subplan_params = NIL; rel->rel_parallel_workers = -1; /* set up in get_relation_info */ @@ -645,6 +647,8 @@ build_join_rel(PlannerInfo *root, joinrel->tuples = 0; joinrel->allvisfrac = 0; joinrel->eclass_indexes = NULL; + joinrel->eclass_member_indexes = NULL; + joinrel->eclass_referencing_member_indexes = NULL; joinrel->subroot = NULL; joinrel->subplan_params = NIL; joinrel->rel_parallel_workers = -1; @@ -828,6 +832,8 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, joinrel->tuples = 0; joinrel->allvisfrac = 0; joinrel->eclass_indexes = NULL; + joinrel->eclass_member_indexes = NULL; + joinrel->eclass_referencing_member_indexes = NULL; joinrel->subroot = NULL; joinrel->subplan_params = NIL; joinrel->amflags = 0; @@ -1242,6 +1248,8 @@ fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids) upperrel->cheapest_total_path = NULL; upperrel->cheapest_unique_path = NULL; upperrel->cheapest_parameterized_paths = NIL; + upperrel->eclass_member_indexes = NULL; /* TODO: Is this necessary? */ + upperrel->eclass_referencing_member_indexes = NULL; /* TODO: Is this necessary? */ root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel); diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 34f2f39012..1cc23eec09 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -303,6 +303,12 @@ struct PlannerInfo /* list of each EquivalenceMember */ List *eq_members; + /* indexes of EquivalenceMembers which are not children */ + Bitmapset *eq_not_children_indexes; + + /* indexes of EquivalenceMembers whose relids are empty */ + Bitmapset *eq_empty_relids_indexes; + /* set true once ECs are canonical */ bool ec_merging_done; @@ -891,6 +897,12 @@ typedef struct RelOptInfo */ Bitmapset *eclass_member_indexes; + /* + * Indexes in PlannerInfo's eq_members list of EMs that reference this rel + * TODO: Its variable name should be more refined. + */ + Bitmapset *eclass_referencing_member_indexes; + PlannerInfo *subroot; /* if subquery */ List *subplan_params; /* if subquery */ /* wanted number of parallel workers */ diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index c9482f86cb..d9dff21c1e 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -134,7 +134,7 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root, Oid opcintype, Oid collation, Index sortref, - Relids rel, + RelOptInfo *rel, bool create_it); extern EquivalenceMember *find_ec_member_matching_expr(PlannerInfo *root, EquivalenceClass *ec, @@ -189,6 +189,154 @@ extern bool is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist); extern bool is_redundant_with_indexclauses(RestrictInfo *rinfo, List *indexclauses); +/* + * TODO: The following helper functions are placed in this header file to help + * compiler inline them. + */ + +/* + * get_eclass_members_indexes_for_relids + * Build and return a Bitmapset containing the indexes into root's + * eq_members list for all EquivalenceMembers whose em_relids is equal to + * the given RelOptInfo's relids + */ +static inline Bitmapset * +get_eclass_members_indexes_for_relids(PlannerInfo *root, + EquivalenceClass *ec, + RelOptInfo *rel) +{ + if (rel == NULL) + return bms_intersect(ec->ec_member_indexes, root->eq_empty_relids_indexes); + else + return bms_intersect(ec->ec_member_indexes, rel->eclass_member_indexes); +} + +/* + * get_eclass_members_indexes_for_not_children + * Build and return a Bitmapset containing the indexes into root's + * eq_members list for all EquivalenceMembers whose em_is_child is false + */ +static inline Bitmapset * +get_eclass_members_indexes_for_not_children(PlannerInfo *root, EquivalenceClass *ec) +{ + return bms_intersect(ec->ec_member_indexes, root->eq_not_children_indexes); +} + +/* + * get_eclass_members_indexes_for_relids_or_not_children + * Build and return a Bitmapset containing the indexes into root's + * eq_members list for all EquivalenceMembers whose em_relids is equal to + * the given RelOptInfo's relids, or em_is_child is false + */ +static inline Bitmapset * +get_eclass_members_indexes_for_relids_or_not_children(PlannerInfo *root, + EquivalenceClass *ec, + RelOptInfo *rel) +{ + Bitmapset *em_indexes; + + if (rel == NULL) + em_indexes = bms_union(root->eq_not_children_indexes, root->eq_empty_relids_indexes); + else + em_indexes = bms_union(root->eq_not_children_indexes, rel->eclass_member_indexes); + + em_indexes = bms_int_members(em_indexes, ec->ec_member_indexes); + + return em_indexes; +} + +/* + * get_eclass_members_indexes_for_subsets_of_relids + * Build and return a Bitmapset containing the indexes into root's + * eq_members list for all EquivalenceMembers whose em_relids is a subset + * of the given relids + */ +static inline Bitmapset * +get_eclass_members_indexes_for_subsets_of_relids(PlannerInfo *root, + EquivalenceClass *ec, + Relids relids) +{ + Bitmapset *em_indexes; + int i; + + if (relids == NULL) + return bms_intersect(ec->ec_member_indexes, root->eq_empty_relids_indexes); + + em_indexes = NULL; + i = -1; + while ((i = bms_next_member(relids, i)) >= 0) + { + RelOptInfo *rel = root->simple_rel_array[i]; + + /* Retrieve candidates that we want to get */ + Bitmapset *em_candidates = bms_intersect(ec->ec_member_indexes, + rel->eclass_referencing_member_indexes); + int j; + + /* Check if the candidates satisfy the condition */ + j = -1; + while ((j = bms_next_member(em_candidates, j)) >= 0) + { + EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, j); + + if (bms_is_subset(em->em_relids, relids)) + { + /* Satisfies, so add it to the result Bitmapset */ + em_indexes = bms_add_member(em_indexes, j); + } + } + } + + return em_indexes; +} + +/* + * get_eclass_members_indexes_for_subsets_of_relids_or_not_children + * Build and return a Bitmapset containing the indexes into root's + * eq_members list for all EquivalenceMembers whose em_relids is a subset + * of the given relids, or em_is_child is false + */ +static inline Bitmapset * +get_eclass_members_indexes_for_subsets_of_relids_or_not_children(PlannerInfo *root, + EquivalenceClass *ec, + Relids relids) +{ + Bitmapset *em_indexes; + int i; + + if (relids == NULL) + return bms_int_members(bms_union(root->eq_empty_relids_indexes, + root->eq_not_children_indexes), + ec->ec_member_indexes); + + em_indexes = bms_intersect(ec->ec_member_indexes, root->eq_not_children_indexes); + i = -1; + while ((i = bms_next_member(relids, i)) >= 0) + { + RelOptInfo *rel = root->simple_rel_array[i]; + + /* Retrieve candidates that we want to get */ + Bitmapset *em_candidates = bms_intersect(ec->ec_member_indexes, + rel->eclass_referencing_member_indexes); + int j; + + /* Check if the candidates satisfy the condition */ + j = -1; + while ((j = bms_next_member(em_candidates, j)) >= 0) + { + EquivalenceMember *em = (EquivalenceMember *) list_nth(root->eq_members, j); + + if (bms_is_subset(em->em_relids, relids)) + { + /* Satisfies, so add it to the result Bitmapset */ + em_indexes = bms_add_member(em_indexes, j); + } + } + } + + return em_indexes; +} + /* * pathkeys.c * utilities for matching and building path keys @@ -226,7 +374,7 @@ extern List *build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel, ScanDirection scandir, bool *partialkeys); extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opno, - Relids rel, bool create_it); + RelOptInfo *rel, bool create_it); extern List *convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *subquery_pathkeys, List *subquery_tlist); -- 2.35.3.windows.1