diff options
| -rw-r--r-- | src/backend/nodes/Makefile | 1 | ||||
| -rw-r--r-- | src/backend/nodes/README | 1 | ||||
| -rw-r--r-- | src/backend/nodes/meson.build | 1 | ||||
| -rw-r--r-- | src/backend/nodes/multibitmapset.c | 162 | ||||
| -rw-r--r-- | src/backend/optimizer/prep/prepjointree.c | 20 | ||||
| -rw-r--r-- | src/backend/optimizer/util/clauses.c | 39 | ||||
| -rw-r--r-- | src/include/nodes/multibitmapset.h | 39 |
7 files changed, 238 insertions, 25 deletions
diff --git a/src/backend/nodes/Makefile b/src/backend/nodes/Makefile index d7b4261b474..4368c30fdbb 100644 --- a/src/backend/nodes/Makefile +++ b/src/backend/nodes/Makefile @@ -21,6 +21,7 @@ OBJS = \ extensible.o \ list.o \ makefuncs.o \ + multibitmapset.o \ nodeFuncs.o \ nodes.o \ outfuncs.o \ diff --git a/src/backend/nodes/README b/src/backend/nodes/README index 64937fe254b..489a67eb899 100644 --- a/src/backend/nodes/README +++ b/src/backend/nodes/README @@ -58,6 +58,7 @@ FILES IN THIS DIRECTORY (src/backend/nodes/) Specialized manipulation functions: bitmapset.c - Bitmapset support list.c - generic list support + multibitmapset.c - List-of-Bitmapset support params.c - Param support tidbitmap.c - TIDBitmap support value.c - support for value nodes diff --git a/src/backend/nodes/meson.build b/src/backend/nodes/meson.build index 8e0d4039f24..c4f3897ef22 100644 --- a/src/backend/nodes/meson.build +++ b/src/backend/nodes/meson.build @@ -3,6 +3,7 @@ backend_sources += files( 'extensible.c', 'list.c', 'makefuncs.c', + 'multibitmapset.c', 'nodeFuncs.c', 'nodes.c', 'params.c', diff --git a/src/backend/nodes/multibitmapset.c b/src/backend/nodes/multibitmapset.c new file mode 100644 index 00000000000..924225c68fc --- /dev/null +++ b/src/backend/nodes/multibitmapset.c @@ -0,0 +1,162 @@ +/*------------------------------------------------------------------------- + * + * multibitmapset.c + * Lists of Bitmapsets + * + * A multibitmapset is useful in situations where members of a set can + * be identified by two small integers; for example, varno and varattno + * of a group of Vars within a query. The implementation is a List of + * Bitmapsets, so that the empty set can be represented by NIL. (But, + * as with Bitmapsets, that's not the only allowed representation.) + * The zero-based index of a List element is the first identifying value, + * and the (also zero-based) index of a bit within that Bitmapset is + * the second identifying value. There is no expectation that the + * Bitmapsets should all be the same size. + * + * The available operations on multibitmapsets are intended to parallel + * those on bitmapsets, for example union and intersection. So far only + * a small fraction of that has been built out; we'll add more as needed. + * + * + * Copyright (c) 2022, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/backend/nodes/multibitmapset.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "nodes/multibitmapset.h" + + +/* + * mbms_add_member + * Add a new member to a multibitmapset. + * + * The new member is identified by "listidx", the zero-based index of the + * List element it should go into, and "bitidx", which specifies the bit + * number to be set therein. + * + * This is like bms_add_member, but for multibitmapsets. + */ +List * +mbms_add_member(List *a, int listidx, int bitidx) +{ + Bitmapset *bms; + ListCell *lc; + + if (listidx < 0 || bitidx < 0) + elog(ERROR, "negative multibitmapset member index not allowed"); + /* Add empty elements as needed */ + while (list_length(a) <= listidx) + a = lappend(a, NULL); + /* Update the target element */ + lc = list_nth_cell(a, listidx); + bms = lfirst_node(Bitmapset, lc); + bms = bms_add_member(bms, bitidx); + lfirst(lc) = bms; + return a; +} + +/* + * mbms_add_members + * Add all members of set b to set a. + * + * This is a UNION operation, but the left input is modified in-place. + * + * This is like bms_add_members, but for multibitmapsets. + */ +List * +mbms_add_members(List *a, const List *b) +{ + ListCell *lca, + *lcb; + + /* Add empty elements to a, as needed */ + while (list_length(a) < list_length(b)) + a = lappend(a, NULL); + /* forboth will stop at the end of the shorter list, which is fine */ + forboth(lca, a, lcb, b) + { + Bitmapset *bmsa = lfirst_node(Bitmapset, lca); + const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb); + + bmsa = bms_add_members(bmsa, bmsb); + lfirst(lca) = bmsa; + } + return a; +} + +/* + * mbms_int_members + * Reduce set a to its intersection with set b. + * + * This is an INTERSECT operation, but the left input is modified in-place. + * + * This is like bms_int_members, but for multibitmapsets. + */ +List * +mbms_int_members(List *a, const List *b) +{ + ListCell *lca, + *lcb; + + /* Remove any elements of a that are no longer of use */ + a = list_truncate(a, list_length(b)); + /* forboth will stop at the end of the shorter list, which is fine */ + forboth(lca, a, lcb, b) + { + Bitmapset *bmsa = lfirst_node(Bitmapset, lca); + const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb); + + bmsa = bms_int_members(bmsa, bmsb); + lfirst(lca) = bmsa; + } + return a; +} + +/* + * mbms_is_member + * Is listidx/bitidx a member of A? + * + * This is like bms_is_member, but for multibitmapsets. + */ +bool +mbms_is_member(int listidx, int bitidx, const List *a) +{ + const Bitmapset *bms; + + /* XXX better to just return false for negative indexes? */ + if (listidx < 0 || bitidx < 0) + elog(ERROR, "negative multibitmapset member index not allowed"); + if (listidx >= list_length(a)) + return false; + bms = list_nth_node(Bitmapset, a, listidx); + return bms_is_member(bitidx, bms); +} + +/* + * mbms_overlap_sets + * Identify the bitmapsets having common members in a and b. + * + * The result is a bitmapset of the list indexes of bitmapsets that overlap. + */ +Bitmapset * +mbms_overlap_sets(const List *a, const List *b) +{ + Bitmapset *result = NULL; + ListCell *lca, + *lcb; + + /* forboth will stop at the end of the shorter list, which is fine */ + forboth(lca, a, lcb, b) + { + const Bitmapset *bmsa = lfirst_node(Bitmapset, lca); + const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb); + + if (bms_overlap(bmsa, bmsb)) + result = bms_add_member(result, foreach_current_index(lca)); + } + return result; +} diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c index b4b9099eb6b..f4cdb879c2c 100644 --- a/src/backend/optimizer/prep/prepjointree.c +++ b/src/backend/optimizer/prep/prepjointree.c @@ -28,6 +28,7 @@ #include "catalog/pg_type.h" #include "funcapi.h" #include "nodes/makefuncs.h" +#include "nodes/multibitmapset.h" #include "nodes/nodeFuncs.h" #include "optimizer/clauses.h" #include "optimizer/optimizer.h" @@ -2769,7 +2770,7 @@ reduce_outer_joins_pass1(Node *jtnode) * state: state data collected by phase 1 for this node * root: toplevel planner state * nonnullable_rels: set of base relids forced non-null by upper quals - * forced_null_vars: list of Vars forced null by upper quals + * forced_null_vars: multibitmapset of Vars forced null by upper quals */ static void reduce_outer_joins_pass2(Node *jtnode, @@ -2799,8 +2800,8 @@ reduce_outer_joins_pass2(Node *jtnode, pass_nonnullable_rels = bms_add_members(pass_nonnullable_rels, nonnullable_rels); pass_forced_null_vars = find_forced_null_vars(f->quals); - pass_forced_null_vars = list_concat(pass_forced_null_vars, - forced_null_vars); + pass_forced_null_vars = mbms_add_members(pass_forced_null_vars, + forced_null_vars); /* And recurse --- but only into interesting subtrees */ Assert(list_length(f->fromlist) == list_length(state->sub_states)); forboth(l, f->fromlist, s, state->sub_states) @@ -2897,7 +2898,7 @@ reduce_outer_joins_pass2(Node *jtnode, if (jointype == JOIN_LEFT) { List *nonnullable_vars; - List *overlap; + Bitmapset *overlap; /* Find Vars in j->quals that must be non-null in joined rows */ nonnullable_vars = find_nonnullable_vars(j->quals); @@ -2907,11 +2908,8 @@ reduce_outer_joins_pass2(Node *jtnode, * forced_null_vars overlap: we need to know if the overlap * includes any RHS variables. */ - overlap = list_intersection(nonnullable_vars, - forced_null_vars); - if (overlap != NIL && - bms_overlap(pull_varnos(root, (Node *) overlap), - right_state->relids)) + overlap = mbms_overlap_sets(nonnullable_vars, forced_null_vars); + if (bms_overlap(overlap, right_state->relids)) jointype = JOIN_ANTI; } @@ -2964,8 +2962,8 @@ reduce_outer_joins_pass2(Node *jtnode, /* OK to merge upper and local constraints */ local_nonnullable_rels = bms_add_members(local_nonnullable_rels, nonnullable_rels); - local_forced_null_vars = list_concat(local_forced_null_vars, - forced_null_vars); + local_forced_null_vars = mbms_add_members(local_forced_null_vars, + forced_null_vars); } } else diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c index 317c10c2b9f..33790a4f463 100644 --- a/src/backend/optimizer/util/clauses.c +++ b/src/backend/optimizer/util/clauses.c @@ -31,6 +31,7 @@ #include "funcapi.h" #include "miscadmin.h" #include "nodes/makefuncs.h" +#include "nodes/multibitmapset.h" #include "nodes/nodeFuncs.h" #include "nodes/subscripting.h" #include "nodes/supportnodes.h" @@ -1566,7 +1567,7 @@ find_nonnullable_rels_walker(Node *node, bool top_level) * find_nonnullable_vars * Determine which Vars are forced nonnullable by given clause. * - * Returns a list of all level-zero Vars that are referenced in the clause in + * Returns the set of all level-zero Vars that are referenced in the clause in * such a way that the clause cannot possibly return TRUE if any of these Vars * is NULL. (It is OK to err on the side of conservatism; hence the analysis * here is simplistic.) @@ -1578,8 +1579,9 @@ find_nonnullable_rels_walker(Node *node, bool top_level) * the expression to have been AND/OR flattened and converted to implicit-AND * format. * - * The result is a palloc'd List, but we have not copied the member Var nodes. - * Also, we don't bother trying to eliminate duplicate entries. + * Attnos of the identified Vars are returned in a multibitmapset (a List of + * Bitmapsets). List indexes correspond to relids (varnos), while the per-rel + * Bitmapsets hold varattnos offset by FirstLowInvalidHeapAttributeNumber. * * top_level is true while scanning top-level AND/OR structure; here, showing * the result is either FALSE or NULL is good enough. top_level is false when @@ -1608,7 +1610,9 @@ find_nonnullable_vars_walker(Node *node, bool top_level) Var *var = (Var *) node; if (var->varlevelsup == 0) - result = list_make1(var); + result = mbms_add_member(result, + var->varno, + var->varattno - FirstLowInvalidHeapAttributeNumber); } else if (IsA(node, List)) { @@ -1623,9 +1627,9 @@ find_nonnullable_vars_walker(Node *node, bool top_level) */ foreach(l, (List *) node) { - result = list_concat(result, - find_nonnullable_vars_walker(lfirst(l), - top_level)); + result = mbms_add_members(result, + find_nonnullable_vars_walker(lfirst(l), + top_level)); } } else if (IsA(node, FuncExpr)) @@ -1657,7 +1661,12 @@ find_nonnullable_vars_walker(Node *node, bool top_level) switch (expr->boolop) { case AND_EXPR: - /* At top level we can just recurse (to the List case) */ + + /* + * At top level we can just recurse (to the List case), since + * the result should be the union of what we can prove in each + * arm. + */ if (top_level) { result = find_nonnullable_vars_walker((Node *) expr->args, @@ -1689,7 +1698,7 @@ find_nonnullable_vars_walker(Node *node, bool top_level) if (result == NIL) /* first subresult? */ result = subresult; else - result = list_intersection(result, subresult); + result = mbms_int_members(result, subresult); /* * If the intersection is empty, we can stop looking. This @@ -1788,8 +1797,8 @@ find_nonnullable_vars_walker(Node *node, bool top_level) * side of conservatism; hence the analysis here is simplistic. In fact, * we only detect simple "var IS NULL" tests at the top level.) * - * The result is a palloc'd List, but we have not copied the member Var nodes. - * Also, we don't bother trying to eliminate duplicate entries. + * As with find_nonnullable_vars, we return the varattnos of the identified + * Vars in a multibitmapset. */ List * find_forced_null_vars(Node *node) @@ -1804,7 +1813,9 @@ find_forced_null_vars(Node *node) var = find_forced_null_var(node); if (var) { - result = list_make1(var); + result = mbms_add_member(result, + var->varno, + var->varattno - FirstLowInvalidHeapAttributeNumber); } /* Otherwise, handle AND-conditions */ else if (IsA(node, List)) @@ -1815,8 +1826,8 @@ find_forced_null_vars(Node *node) */ foreach(l, (List *) node) { - result = list_concat(result, - find_forced_null_vars(lfirst(l))); + result = mbms_add_members(result, + find_forced_null_vars((Node *) lfirst(l))); } } else if (IsA(node, BoolExpr)) diff --git a/src/include/nodes/multibitmapset.h b/src/include/nodes/multibitmapset.h new file mode 100644 index 00000000000..8c6695aeda7 --- /dev/null +++ b/src/include/nodes/multibitmapset.h @@ -0,0 +1,39 @@ +/*------------------------------------------------------------------------- + * + * multibitmapset.h + * Lists of Bitmapsets + * + * A multibitmapset is useful in situations where members of a set can + * be identified by two small integers; for example, varno and varattno + * of a group of Vars within a query. The implementation is a List of + * Bitmapsets, so that the empty set can be represented by NIL. (But, + * as with Bitmapsets, that's not the only allowed representation.) + * The zero-based index of a List element is the first identifying value, + * and the (also zero-based) index of a bit within that Bitmapset is + * the second identifying value. There is no expectation that the + * Bitmapsets should all be the same size. + * + * The available operations on multibitmapsets are intended to parallel + * those on bitmapsets, for example union and intersection. So far only + * a small fraction of that has been built out; we'll add more as needed. + * + * + * Copyright (c) 2022, PostgreSQL Global Development Group + * + * src/include/nodes/multibitmapset.h + * + *------------------------------------------------------------------------- + */ +#ifndef MULTIBITMAPSET_H +#define MULTIBITMAPSET_H + +#include "nodes/bitmapset.h" +#include "nodes/pg_list.h" + +extern List *mbms_add_member(List *a, int listidx, int bitidx); +extern List *mbms_add_members(List *a, const List *b); +extern List *mbms_int_members(List *a, const List *b); +extern bool mbms_is_member(int listidx, int bitidx, const List *a); +extern Bitmapset *mbms_overlap_sets(const List *a, const List *b); + +#endif /* MULTIBITMAPSET_H */ |