diff options
Diffstat (limited to 'src')
34 files changed, 1451 insertions, 623 deletions
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c index 6c8b02a156e..631c2817cc0 100644 --- a/src/backend/commands/explain.c +++ b/src/backend/commands/explain.c @@ -7,7 +7,7 @@ * Portions Copyright (c) 1994-5, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/commands/explain.c,v 1.100 2003/02/02 23:46:38 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/commands/explain.c,v 1.101 2003/02/08 20:20:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -775,12 +775,15 @@ show_scan_qual(List *qual, bool is_or_qual, const char *qlabel, */ if (outer_plan) { - if (intMember(OUTER, pull_varnos(node))) + Relids varnos = pull_varnos(node); + + if (bms_is_member(OUTER, varnos)) outercontext = deparse_context_for_subplan("outer", outer_plan->targetlist, es->rtable); else outercontext = NULL; + bms_free(varnos); } else outercontext = NULL; @@ -857,6 +860,7 @@ show_sort_keys(List *tlist, int nkeys, const char *qlabel, int keyno; List *tl; char *exprstr; + Relids varnos; int i; if (nkeys <= 0) @@ -874,7 +878,8 @@ show_sort_keys(List *tlist, int nkeys, const char *qlabel, * there are Vars with zero varno, use the tlist itself to determine * their names. */ - if (intMember(0, pull_varnos((Node *) tlist))) + varnos = pull_varnos((Node *) tlist); + if (bms_is_member(0, varnos)) { Node *outercontext; @@ -893,6 +898,7 @@ show_sort_keys(List *tlist, int nkeys, const char *qlabel, es->rtable); useprefix = length(es->rtable) > 1; } + bms_free(varnos); for (keyno = 1; keyno <= nkeys; keyno++) { diff --git a/src/backend/nodes/Makefile b/src/backend/nodes/Makefile index 0c5bab190dc..dd3f17f9e9b 100644 --- a/src/backend/nodes/Makefile +++ b/src/backend/nodes/Makefile @@ -4,7 +4,7 @@ # Makefile for backend/nodes # # IDENTIFICATION -# $Header: /cvsroot/pgsql/src/backend/nodes/Makefile,v 1.13 2000/08/31 16:10:06 petere Exp $ +# $Header: /cvsroot/pgsql/src/backend/nodes/Makefile,v 1.14 2003/02/08 20:20:53 tgl Exp $ # #------------------------------------------------------------------------- @@ -12,7 +12,7 @@ subdir = src/backend/nodes top_builddir = ../../.. include $(top_builddir)/src/Makefile.global -OBJS = nodeFuncs.o nodes.o list.o \ +OBJS = nodeFuncs.o nodes.o list.o bitmapset.o \ copyfuncs.o equalfuncs.o makefuncs.o \ outfuncs.o readfuncs.o print.o read.o diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c new file mode 100644 index 00000000000..5798b726497 --- /dev/null +++ b/src/backend/nodes/bitmapset.c @@ -0,0 +1,759 @@ +/*------------------------------------------------------------------------- + * + * bitmapset.c + * PostgreSQL generic bitmap set package + * + * A bitmap set can represent any set of nonnegative integers, although + * it is mainly intended for sets where the maximum value is not large, + * say at most a few hundred. By convention, a NULL pointer is always + * accepted by all operations to represent the empty set. (But beware + * that this is not the only representation of the empty set. Use + * bms_is_empty() in preference to testing for NULL.) + * + * + * Copyright (c) 2003, PostgreSQL Global Development Group + * + * IDENTIFICATION + * $Header: /cvsroot/pgsql/src/backend/nodes/bitmapset.c,v 1.1 2003/02/08 20:20:53 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "nodes/bitmapset.h" + + +#define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD) +#define BITNUM(x) ((x) % BITS_PER_BITMAPWORD) + +#define BITMAPSET_SIZE(nwords) \ + (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword)) + +/*---------- + * This is a well-known cute trick for isolating the rightmost one-bit + * in a word. It assumes two's complement arithmetic. Consider any + * nonzero value, and focus attention on the rightmost one. The value is + * then something like + * xxxxxx10000 + * where x's are unspecified bits. The two's complement negative is formed + * by inverting all the bits and adding one. Inversion gives + * yyyyyy01111 + * where each y is the inverse of the corresponding x. Incrementing gives + * yyyyyy10000 + * and then ANDing with the original value gives + * 00000010000 + * This works for all cases except original value = zero, where of course + * we get zero. + *---------- + */ +#define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x))) + +#define HAS_MULTIPLE_ONES(x) ((bitmapword) RIGHTMOST_ONE(x) != (x)) + + +/* + * Lookup tables to avoid need for bit-by-bit groveling + * + * rightmost_one_pos[x] gives the bit number (0-7) of the rightmost one bit + * in a nonzero byte value x. The entry for x=0 is never used. + * + * number_of_ones[x] gives the number of one-bits (0-8) in a byte value x. + * + * We could make these tables larger and reduce the number of iterations + * in the functions that use them, but bytewise shifts and masks are + * especially fast on many machines, so working a byte at a time seems best. + */ + +static const uint8 rightmost_one_pos[256] = { + 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 +}; + +static const uint8 number_of_ones[256] = { + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 +}; + + +/* + * bms_copy - make a palloc'd copy of a bitmapset + */ +Bitmapset * +bms_copy(const Bitmapset *a) +{ + Bitmapset *result; + size_t size; + + if (a == NULL) + return NULL; + size = BITMAPSET_SIZE(a->nwords); + result = (Bitmapset *) palloc(size); + memcpy(result, a, size); + return result; +} + +/* + * bms_equal - are two bitmapsets equal? + * + * This is logical not physical equality; in particular, a NULL pointer will + * be reported as equal to a palloc'd value containing no members. + */ +bool +bms_equal(const Bitmapset *a, const Bitmapset *b) +{ + const Bitmapset *shorter; + const Bitmapset *longer; + int shortlen; + int longlen; + int i; + + /* Handle cases where either input is NULL */ + if (a == NULL) + { + if (b == NULL) + return true; + return bms_is_empty(b); + } + else if (b == NULL) + { + return bms_is_empty(a); + } + /* Identify shorter and longer input */ + if (a->nwords <= b->nwords) + { + shorter = a; + longer = b; + } + else + { + shorter = b; + longer = a; + } + /* And process */ + shortlen = shorter->nwords; + for (i = 0; i < shortlen; i++) + { + if (shorter->words[i] != longer->words[i]) + return false; + } + longlen = longer->nwords; + for (; i < longlen; i++) + { + if (longer->words[i] != 0) + return false; + } + return true; +} + +/* + * bms_make_singleton - build a bitmapset containing a single member + */ +Bitmapset * +bms_make_singleton(int x) +{ + Bitmapset *result; + int wordnum, + bitnum; + + if (x < 0) + elog(ERROR, "bms_make_singleton: negative set member not allowed"); + wordnum = WORDNUM(x); + bitnum = BITNUM(x); + result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1)); + result->nwords = wordnum + 1; + result->words[wordnum] = ((bitmapword) 1 << bitnum); + return result; +} + +/* + * bms_free - free a bitmapset + * + * Same as pfree except for allowing NULL input + */ +void +bms_free(Bitmapset *a) +{ + if (a) + pfree(a); +} + + +/* + * These operations all make a freshly palloc'd result, + * leaving their inputs untouched + */ + + +/* + * bms_union - set union + */ +Bitmapset * +bms_union(const Bitmapset *a, const Bitmapset *b) +{ + Bitmapset *result; + const Bitmapset *other; + int otherlen; + int i; + + /* Handle cases where either input is NULL */ + if (a == NULL) + return bms_copy(b); + if (b == NULL) + return bms_copy(a); + /* Identify shorter and longer input; copy the longer one */ + if (a->nwords <= b->nwords) + { + result = bms_copy(b); + other = a; + } + else + { + result = bms_copy(a); + other = b; + } + /* And union the shorter input into the result */ + otherlen = other->nwords; + for (i = 0; i < otherlen; i++) + { + result->words[i] |= other->words[i]; + } + return result; +} + +/* + * bms_intersect - set intersection + */ +Bitmapset * +bms_intersect(const Bitmapset *a, const Bitmapset *b) +{ + Bitmapset *result; + const Bitmapset *other; + int resultlen; + int i; + + /* Handle cases where either input is NULL */ + if (a == NULL || b == NULL) + return NULL; + /* Identify shorter and longer input; copy the shorter one */ + if (a->nwords <= b->nwords) + { + result = bms_copy(a); + other = b; + } + else + { + result = bms_copy(b); + other = a; + } + /* And intersect the longer input with the result */ + resultlen = result->nwords; + for (i = 0; i < resultlen; i++) + { + result->words[i] &= other->words[i]; + } + return result; +} + +/* + * bms_difference - set difference (ie, A without members of B) + */ +Bitmapset * +bms_difference(const Bitmapset *a, const Bitmapset *b) +{ + Bitmapset *result; + int shortlen; + int i; + + /* Handle cases where either input is NULL */ + if (a == NULL) + return NULL; + if (b == NULL) + return bms_copy(a); + /* Copy the left input */ + result = bms_copy(a); + /* And remove b's bits from result */ + shortlen = Min(a->nwords, b->nwords); + for (i = 0; i < shortlen; i++) + { + result->words[i] &= ~ b->words[i]; + } + return result; +} + +/* + * bms_is_subset - is A a subset of B? + */ +bool +bms_is_subset(const Bitmapset *a, const Bitmapset *b) +{ + int shortlen; + int longlen; + int i; + + /* Handle cases where either input is NULL */ + if (a == NULL) + return true; /* empty set is a subset of anything */ + if (b == NULL) + return bms_is_empty(a); + /* Check common words */ + shortlen = Min(a->nwords, b->nwords); + for (i = 0; i < shortlen; i++) + { + if ((a->words[i] & ~ b->words[i]) != 0) + return false; + } + /* Check extra words */ + if (a->nwords > b->nwords) + { + longlen = a->nwords; + for (; i < longlen; i++) + { + if (a->words[i] != 0) + return false; + } + } + return true; +} + +/* + * bms_is_member - is X a member of A? + */ +bool +bms_is_member(int x, const Bitmapset *a) +{ + int wordnum, + bitnum; + + /* XXX better to just return false for x<0 ? */ + if (x < 0) + elog(ERROR, "bms_is_member: negative set member not allowed"); + if (a == NULL) + return false; + wordnum = WORDNUM(x); + bitnum = BITNUM(x); + if (wordnum >= a->nwords) + return false; + if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0) + return true; + return false; +} + +/* + * bms_overlap - do sets overlap (ie, have a nonempty intersection)? + */ +bool +bms_overlap(const Bitmapset *a, const Bitmapset *b) +{ + int shortlen; + int i; + + /* Handle cases where either input is NULL */ + if (a == NULL || b == NULL) + return false; + /* Check words in common */ + shortlen = Min(a->nwords, b->nwords); + for (i = 0; i < shortlen; i++) + { + if ((a->words[i] & b->words[i]) != 0) + return true; + } + return false; +} + +/* + * bms_singleton_member - return the sole integer member of set + * + * Raises error if |a| is not 1. + */ +int +bms_singleton_member(const Bitmapset *a) +{ + int result = -1; + int nwords; + int wordnum; + + if (a == NULL) + elog(ERROR, "bms_singleton_member: set is empty"); + nwords = a->nwords; + for (wordnum = 0; wordnum < nwords; wordnum++) + { + bitmapword w = a->words[wordnum]; + + if (w != 0) + { + if (result >= 0 || HAS_MULTIPLE_ONES(w)) + elog(ERROR, "bms_singleton_member: set has multiple members"); + result = wordnum * BITS_PER_BITMAPWORD; + while ((w & 255) == 0) + { + w >>= 8; + result += 8; + } + result += rightmost_one_pos[w & 255]; + } + } + if (result < 0) + elog(ERROR, "bms_singleton_member: set is empty"); + return result; +} + +/* + * bms_num_members - count members of set + */ +int +bms_num_members(const Bitmapset *a) +{ + int result = 0; + int nwords; + int wordnum; + + if (a == NULL) + return 0; + nwords = a->nwords; + for (wordnum = 0; wordnum < nwords; wordnum++) + { + bitmapword w = a->words[wordnum]; + + /* we assume here that bitmapword is an unsigned type */ + while (w != 0) + { + result += number_of_ones[w & 255]; + w >>= 8; + } + } + return result; +} + +/* + * bms_membership - does a set have zero, one, or multiple members? + * + * This is faster than making an exact count with bms_num_members(). + */ +BMS_Membership +bms_membership(const Bitmapset *a) +{ + BMS_Membership result = BMS_EMPTY_SET; + int nwords; + int wordnum; + + if (a == NULL) + return BMS_EMPTY_SET; + nwords = a->nwords; + for (wordnum = 0; wordnum < nwords; wordnum++) + { + bitmapword w = a->words[wordnum]; + + if (w != 0) + { + if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w)) + return BMS_MULTIPLE; + result = BMS_SINGLETON; + } + } + return result; +} + +/* + * bms_is_empty - is a set empty? + * + * This is even faster than bms_membership(). + */ +bool +bms_is_empty(const Bitmapset *a) +{ + int nwords; + int wordnum; + + if (a == NULL) + return true; + nwords = a->nwords; + for (wordnum = 0; wordnum < nwords; wordnum++) + { + bitmapword w = a->words[wordnum]; + + if (w != 0) + return false; + } + return true; +} + + +/* + * These operations all "recycle" their non-const inputs, ie, either + * return the modified input or pfree it if it can't hold the result. + * + * These should generally be used in the style + * + * foo = bms_add_member(foo, x); + */ + + +/* + * bms_add_member - add a specified member to set + * + * Input set is modified or recycled! + */ +Bitmapset * +bms_add_member(Bitmapset *a, int x) +{ + int wordnum, + bitnum; + + if (x < 0) + elog(ERROR, "bms_add_member: negative set member not allowed"); + if (a == NULL) + return bms_make_singleton(x); + wordnum = WORDNUM(x); + bitnum = BITNUM(x); + if (wordnum >= a->nwords) + { + /* Slow path: make a larger set and union the input set into it */ + Bitmapset *result; + int nwords; + int i; + + result = bms_make_singleton(x); + nwords = a->nwords; + for (i = 0; i < nwords; i++) + { + result->words[i] |= a->words[i]; + } + pfree(a); + return result; + } + /* Fast path: x fits in existing set */ + a->words[wordnum] |= ((bitmapword) 1 << bitnum); + return a; +} + +/* + * bms_del_member - remove a specified member from set + * + * No error if x is not currently a member of set + * + * Input set is modified in-place! + */ +Bitmapset * +bms_del_member(Bitmapset *a, int x) +{ + int wordnum, + bitnum; + + if (x < 0) + elog(ERROR, "bms_del_member: negative set member not allowed"); + if (a == NULL) + return NULL; + wordnum = WORDNUM(x); + bitnum = BITNUM(x); + if (wordnum < a->nwords) + { + a->words[wordnum] &= ~ ((bitmapword) 1 << bitnum); + } + return a; +} + +/* + * bms_add_members - like bms_union, but left input is recycled + */ +Bitmapset * +bms_add_members(Bitmapset *a, const Bitmapset *b) +{ + Bitmapset *result; + const Bitmapset *other; + int otherlen; + int i; + + /* Handle cases where either input is NULL */ + if (a == NULL) + return bms_copy(b); + if (b == NULL) + return a; + /* Identify shorter and longer input; copy the longer one if needed */ + if (a->nwords < b->nwords) + { + result = bms_copy(b); + other = a; + } + else + { + result = a; + other = b; + } + /* And union the shorter input into the result */ + otherlen = other->nwords; + for (i = 0; i < otherlen; i++) + { + result->words[i] |= other->words[i]; + } + if (result != a) + pfree(a); + return result; +} + +/* + * bms_int_members - like bms_intersect, but left input is recycled + */ +Bitmapset * +bms_int_members(Bitmapset *a, const Bitmapset *b) +{ + int shortlen; + int i; + + /* Handle cases where either input is NULL */ + if (a == NULL) + return NULL; + if (b == NULL) + { + pfree(a); + return NULL; + } + /* Intersect b into a; we need never copy */ + shortlen = Min(a->nwords, b->nwords); + for (i = 0; i < shortlen; i++) + { + a->words[i] &= b->words[i]; + } + for (; i < a->nwords; i++) + { + a->words[i] = 0; + } + return a; +} + +/* + * bms_del_members - like bms_difference, but left input is recycled + */ +Bitmapset * +bms_del_members(Bitmapset *a, const Bitmapset *b) +{ + int shortlen; + int i; + + /* Handle cases where either input is NULL */ + if (a == NULL) + return NULL; + if (b == NULL) + return a; + /* Remove b's bits from a; we need never copy */ + shortlen = Min(a->nwords, b->nwords); + for (i = 0; i < shortlen; i++) + { + a->words[i] &= ~ b->words[i]; + } + return a; +} + +/* + * bms_join - like bms_union, but *both* inputs are recycled + */ +Bitmapset * +bms_join(Bitmapset *a, Bitmapset *b) +{ + Bitmapset *result; + Bitmapset *other; + int otherlen; + int i; + + /* Handle cases where either input is NULL */ + if (a == NULL) + return b; + if (b == NULL) + return a; + /* Identify shorter and longer input; use longer one as result */ + if (a->nwords < b->nwords) + { + result = b; + other = a; + } + else + { + result = a; + other = b; + } + /* And union the shorter input into the result */ + otherlen = other->nwords; + for (i = 0; i < otherlen; i++) + { + result->words[i] |= other->words[i]; + } + if (other != result) /* pure paranoia */ + pfree(other); + return result; +} + +/*---------- + * bms_first_member - find and remove first member of a set + * + * Returns -1 if set is empty. NB: set is destructively modified! + * + * This is intended as support for iterating through the members of a set. + * The typical pattern is + * + * tmpset = bms_copy(inputset); + * while ((x = bms_first_member(tmpset)) >= 0) + * { + * process member x; + * } + * bms_free(tmpset); + *---------- + */ +int +bms_first_member(Bitmapset *a) +{ + int nwords; + int wordnum; + + if (a == NULL) + return -1; + nwords = a->nwords; + for (wordnum = 0; wordnum < nwords; wordnum++) + { + bitmapword w = a->words[wordnum]; + + if (w != 0) + { + int result; + + w = RIGHTMOST_ONE(w); + a->words[wordnum] &= ~ w; + + result = wordnum * BITS_PER_BITMAPWORD; + while ((w & 255) == 0) + { + w >>= 8; + result += 8; + } + result += rightmost_one_pos[w & 255]; + return result; + } + } + return -1; +} diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index 8437ed82a5a..55b4eeaf4b7 100644 --- a/src/backend/nodes/copyfuncs.c +++ b/src/backend/nodes/copyfuncs.c @@ -15,7 +15,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.239 2003/02/03 21:15:43 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.240 2003/02/08 20:20:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -47,6 +47,10 @@ #define COPY_INTLIST_FIELD(fldname) \ (newnode->fldname = listCopy(from->fldname)) +/* Copy a field that is a pointer to a Bitmapset */ +#define COPY_BITMAPSET_FIELD(fldname) \ + (newnode->fldname = bms_copy(from->fldname)) + /* Copy a field that is a pointer to a C string, or perhaps NULL */ #define COPY_STRING_FIELD(fldname) \ (newnode->fldname = from->fldname ? pstrdup(from->fldname) : (char *) NULL) @@ -1058,8 +1062,8 @@ _copyRestrictInfo(RestrictInfo *from) COPY_NODE_FIELD(subclauseindices); /* XXX probably bad */ COPY_SCALAR_FIELD(eval_cost); COPY_SCALAR_FIELD(this_selec); - COPY_INTLIST_FIELD(left_relids); - COPY_INTLIST_FIELD(right_relids); + COPY_BITMAPSET_FIELD(left_relids); + COPY_BITMAPSET_FIELD(right_relids); COPY_SCALAR_FIELD(mergejoinoperator); COPY_SCALAR_FIELD(left_sortop); COPY_SCALAR_FIELD(right_sortop); @@ -1088,7 +1092,7 @@ _copyJoinInfo(JoinInfo *from) { JoinInfo *newnode = makeNode(JoinInfo); - COPY_INTLIST_FIELD(unjoined_relids); + COPY_BITMAPSET_FIELD(unjoined_relids); COPY_NODE_FIELD(jinfo_restrictinfo); return newnode; @@ -1102,8 +1106,8 @@ _copyInClauseInfo(InClauseInfo *from) { InClauseInfo *newnode = makeNode(InClauseInfo); - COPY_INTLIST_FIELD(lefthand); - COPY_INTLIST_FIELD(righthand); + COPY_BITMAPSET_FIELD(lefthand); + COPY_BITMAPSET_FIELD(righthand); COPY_NODE_FIELD(sub_targetlist); return newnode; diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c index 7916ca0fca6..b347f779bd5 100644 --- a/src/backend/nodes/equalfuncs.c +++ b/src/backend/nodes/equalfuncs.c @@ -18,7 +18,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.183 2003/02/03 21:15:44 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.184 2003/02/08 20:20:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -59,6 +59,13 @@ return false; \ } while (0) +/* Compare a field that is a pointer to a Bitmapset */ +#define COMPARE_BITMAPSET_FIELD(fldname) \ + do { \ + if (!bms_equal(a->fldname, b->fldname)) \ + return false; \ + } while (0) + /* Compare a field that is a pointer to a C string, or perhaps NULL */ #define COMPARE_STRING_FIELD(fldname) \ do { \ @@ -486,7 +493,7 @@ _equalRestrictInfo(RestrictInfo *a, RestrictInfo *b) static bool _equalJoinInfo(JoinInfo *a, JoinInfo *b) { - COMPARE_INTLIST_FIELD(unjoined_relids); + COMPARE_BITMAPSET_FIELD(unjoined_relids); COMPARE_NODE_FIELD(jinfo_restrictinfo); return true; @@ -495,8 +502,8 @@ _equalJoinInfo(JoinInfo *a, JoinInfo *b) static bool _equalInClauseInfo(InClauseInfo *a, InClauseInfo *b) { - COMPARE_INTLIST_FIELD(lefthand); - COMPARE_INTLIST_FIELD(righthand); + COMPARE_BITMAPSET_FIELD(lefthand); + COMPARE_BITMAPSET_FIELD(righthand); COMPARE_NODE_FIELD(sub_targetlist); return true; diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c index 1fbfd1efa88..7fe3eedb2f7 100644 --- a/src/backend/nodes/list.c +++ b/src/backend/nodes/list.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.46 2003/01/27 20:51:49 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.47 2003/02/08 20:20:54 tgl Exp $ * * NOTES * XXX a few of the following functions are duplicated to handle @@ -249,21 +249,6 @@ llast(List *l) } /* - * llasti - * - * As above, but for integer lists - */ -int -llasti(List *l) -{ - if (l == NIL) - elog(ERROR, "llasti: empty list"); - while (lnext(l) != NIL) - l = lnext(l); - return lfirsti(l); -} - -/* * freeList * * Free the List nodes of a list @@ -305,35 +290,6 @@ equali(List *list1, List *list2) } /* - * sameseti - * - * Returns t if two integer lists contain the same elements - * (but unlike equali(), they need not be in the same order) - * - * Caution: this routine could be fooled if list1 contains - * duplicate elements. It is intended to be used on lists - * containing only nonduplicate elements, eg Relids lists. - */ -bool -sameseti(List *list1, List *list2) -{ - List *temp; - - if (list1 == NIL) - return list2 == NIL; - if (list2 == NIL) - return false; - if (length(list1) != length(list2)) - return false; - foreach(temp, list1) - { - if (!intMember(lfirsti(temp), list2)) - return false; - } - return true; -} - -/* * Generate the union of two lists, * ie, l1 plus all members of l2 that are not already in l1. * @@ -397,7 +353,6 @@ set_ptrUnion(List *l1, List *l2) * The result is a fresh List, but it points to the same member nodes * as were in the inputs. */ -#ifdef NOT_USED List * set_intersect(List *l1, List *l2) { @@ -411,7 +366,6 @@ set_intersect(List *l1, List *l2) } return retval; } -#endif List * set_intersecti(List *l1, List *l2) @@ -664,6 +618,7 @@ set_ptrDifference(List *l1, List *l2) /* * Reverse a list, non-destructively */ +#ifdef NOT_USED List * lreverse(List *l) { @@ -674,39 +629,4 @@ lreverse(List *l) result = lcons(lfirst(i), result); return result; } - -/* - * Return t if two integer lists have any members in common. - */ -bool -overlap_setsi(List *list1, List *list2) -{ - List *x; - - foreach(x, list1) - { - int e = lfirsti(x); - - if (intMember(e, list2)) - return true; - } - return false; -} - -/* - * Return t if all members of integer list list1 appear in list2. - */ -bool -is_subseti(List *list1, List *list2) -{ - List *x; - - foreach(x, list1) - { - int e = lfirsti(x); - - if (!intMember(e, list2)) - return false; - } - return true; -} +#endif diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index ea6305512ce..b4aefc78002 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/nodes/outfuncs.c,v 1.195 2003/02/03 21:15:44 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/nodes/outfuncs.c,v 1.196 2003/02/08 20:20:54 tgl Exp $ * * NOTES * Every node type that can appear in stored rules' parsetrees *must* @@ -96,6 +96,11 @@ (appendStringInfo(str, " :" CppAsString(fldname) " "), \ _outOidList(str, node->fldname)) +/* Write a bitmapset field */ +#define WRITE_BITMAPSET_FIELD(fldname) \ + (appendStringInfo(str, " :" CppAsString(fldname) " "), \ + _outBitmapset(str, node->fldname)) + #define booltostr(x) ((x) ? "true" : "false") @@ -173,6 +178,29 @@ _outOidList(StringInfo str, List *list) } /* + * _outBitmapset - + * converts a bitmap set of integers + * + * Note: for historical reasons, the output is formatted exactly like + * an integer List would be. + */ +static void +_outBitmapset(StringInfo str, Bitmapset *bms) +{ + Bitmapset *tmpset; + int x; + + appendStringInfoChar(str, '('); + tmpset = bms_copy(bms); + while ((x = bms_first_member(tmpset)) >= 0) + { + appendStringInfo(str, " %d", x); + } + bms_free(tmpset); + appendStringInfoChar(str, ')'); +} + +/* * Print the value of a Datum given its type. */ static void @@ -963,8 +991,8 @@ _outRestrictInfo(StringInfo str, RestrictInfo *node) WRITE_NODE_FIELD(clause); WRITE_BOOL_FIELD(ispusheddown); WRITE_NODE_FIELD(subclauseindices); - WRITE_INTLIST_FIELD(left_relids); - WRITE_INTLIST_FIELD(right_relids); + WRITE_BITMAPSET_FIELD(left_relids); + WRITE_BITMAPSET_FIELD(right_relids); WRITE_OID_FIELD(mergejoinoperator); WRITE_OID_FIELD(left_sortop); WRITE_OID_FIELD(right_sortop); @@ -976,7 +1004,7 @@ _outJoinInfo(StringInfo str, JoinInfo *node) { WRITE_NODE_TYPE("JOININFO"); - WRITE_INTLIST_FIELD(unjoined_relids); + WRITE_BITMAPSET_FIELD(unjoined_relids); WRITE_NODE_FIELD(jinfo_restrictinfo); } @@ -985,8 +1013,8 @@ _outInClauseInfo(StringInfo str, InClauseInfo *node) { WRITE_NODE_TYPE("INCLAUSEINFO"); - WRITE_INTLIST_FIELD(lefthand); - WRITE_INTLIST_FIELD(righthand); + WRITE_BITMAPSET_FIELD(lefthand); + WRITE_BITMAPSET_FIELD(righthand); WRITE_NODE_FIELD(sub_targetlist); } diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 6c40a16e32a..c168ecd3b62 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.95 2003/01/25 23:10:27 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.96 2003/02/08 20:20:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -79,7 +79,7 @@ make_one_rel(Query *root) /* * The result should join all the query's base rels. */ - Assert(length(rel->relids) == length(root->base_rel_list)); + Assert(bms_num_members(rel->relids) == length(root->base_rel_list)); return rel; } @@ -98,12 +98,11 @@ set_base_rel_pathlists(Query *root) foreach(rellist, root->base_rel_list) { RelOptInfo *rel = (RelOptInfo *) lfirst(rellist); - Index rti; + Index rti = rel->relid; RangeTblEntry *rte; List *inheritlist; - Assert(length(rel->relids) == 1); /* better be base rel */ - rti = lfirsti(rel->relids); + Assert(rti > 0); /* better be base rel */ rte = rt_fetch(rti, root->rtable); if (rel->rtekind == RTE_SUBQUERY) @@ -696,14 +695,19 @@ recurse_push_qual(Node *setOp, Query *topquery, static void print_relids(Relids relids) { - List *l; + Relids tmprelids; + int x; + bool first = true; - foreach(l, relids) + tmprelids = bms_copy(relids); + while ((x = bms_first_member(tmprelids)) >= 0) { - printf("%d", lfirsti(l)); - if (lnext(l)) + if (!first) printf(" "); + printf("%d", x); + first = false; } + bms_free(tmprelids); } static void diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 56282406129..40621f97624 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -49,7 +49,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.104 2003/01/28 22:13:33 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.105 2003/02/08 20:20:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -124,7 +124,7 @@ cost_seqscan(Path *path, Query *root, Cost cpu_per_tuple; /* Should only be applied to base relations */ - Assert(length(baserel->relids) == 1); + Assert(baserel->relid > 0); Assert(baserel->rtekind == RTE_RELATION); if (!enable_seqscan) @@ -241,7 +241,7 @@ cost_index(Path *path, Query *root, /* Should only be applied to base relations */ Assert(IsA(baserel, RelOptInfo) && IsA(index, IndexOptInfo)); - Assert(length(baserel->relids) == 1); + Assert(baserel->relid > 0); Assert(baserel->rtekind == RTE_RELATION); if (!enable_indexscan) @@ -397,7 +397,7 @@ cost_tidscan(Path *path, Query *root, int ntuples = length(tideval); /* Should only be applied to base relations */ - Assert(length(baserel->relids) == 1); + Assert(baserel->relid > 0); Assert(baserel->rtekind == RTE_RELATION); if (!enable_tidscan) @@ -427,7 +427,7 @@ cost_functionscan(Path *path, Query *root, RelOptInfo *baserel) Cost cpu_per_tuple; /* Should only be applied to base relations that are functions */ - Assert(length(baserel->relids) == 1); + Assert(baserel->relid > 0); Assert(baserel->rtekind == RTE_FUNCTION); /* @@ -886,7 +886,7 @@ cost_mergejoin(MergePath *path, Query *root) &firstclause->left_mergescansel, &firstclause->right_mergescansel); - if (is_subseti(firstclause->left_relids, outer_path->parent->relids)) + if (bms_is_subset(firstclause->left_relids, outer_path->parent->relids)) { /* left side of clause is outer */ outerscansel = firstclause->left_mergescansel; @@ -1116,8 +1116,8 @@ cost_hashjoin(HashPath *path, Query *root) * planning a large query, we cache the bucketsize estimate in the * RestrictInfo node to avoid repeated lookups of statistics. */ - if (is_subseti(restrictinfo->right_relids, - inner_path->parent->relids)) + if (bms_is_subset(restrictinfo->right_relids, + inner_path->parent->relids)) { /* righthand side is inner */ thisbucketsize = restrictinfo->right_bucketsize; @@ -1133,8 +1133,8 @@ cost_hashjoin(HashPath *path, Query *root) } else { - Assert(is_subseti(restrictinfo->left_relids, - inner_path->parent->relids)); + Assert(bms_is_subset(restrictinfo->left_relids, + inner_path->parent->relids)); /* lefthand side is inner */ thisbucketsize = restrictinfo->left_bucketsize; if (thisbucketsize < 0) @@ -1635,12 +1635,12 @@ set_baserel_size_estimates(Query *root, RelOptInfo *rel) double temp; /* Should only be applied to base relations */ - Assert(length(rel->relids) == 1); + Assert(rel->relid > 0); temp = rel->tuples * restrictlist_selectivity(root, rel->baserestrictinfo, - lfirsti(rel->relids), + rel->relid, JOIN_INNER); /* @@ -1803,7 +1803,7 @@ set_function_size_estimates(Query *root, RelOptInfo *rel) double temp; /* Should only be applied to base relations that are functions */ - Assert(length(rel->relids) == 1); + Assert(rel->relid > 0); Assert(rel->rtekind == RTE_FUNCTION); /* @@ -1818,7 +1818,7 @@ set_function_size_estimates(Query *root, RelOptInfo *rel) temp = rel->tuples * restrictlist_selectivity(root, rel->baserestrictinfo, - lfirsti(rel->relids), + rel->relid, JOIN_INNER); /* diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 98e4d59f2df..5d16067c756 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.134 2003/01/28 22:13:33 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.135 2003/02/08 20:20:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -133,7 +133,7 @@ create_index_paths(Query *root, RelOptInfo *rel) { List *restrictinfo_list = rel->baserestrictinfo; List *joininfo_list = rel->joininfo; - Relids all_join_outerrelids = NIL; + Relids all_join_outerrelids = NULL; List *ilist; foreach(ilist, rel->indexlist) @@ -151,7 +151,7 @@ create_index_paths(Query *root, RelOptInfo *rel) */ if (index->indpred != NIL) if (!pred_test(index->indpred, restrictinfo_list, joininfo_list, - lfirsti(rel->relids))) + rel->relid)) continue; /* @@ -227,15 +227,15 @@ create_index_paths(Query *root, RelOptInfo *rel) /* * 6. Examine join clauses to see which ones are potentially - * usable with this index, and generate a list of all other relids - * that participate in such join clauses. We'll use this list later + * usable with this index, and generate the set of all other relids + * that participate in such join clauses. We'll use this set later * to recognize outer rels that are equivalent for joining purposes. - * We compute both per-index and overall-for-relation lists. + * We compute both per-index and overall-for-relation sets. */ join_outerrelids = indexable_outerrelids(rel, index); index->outer_relids = join_outerrelids; - all_join_outerrelids = set_unioni(all_join_outerrelids, - join_outerrelids); + all_join_outerrelids = bms_add_members(all_join_outerrelids, + join_outerrelids); } rel->index_outer_relids = all_join_outerrelids; @@ -609,7 +609,7 @@ group_clauses_by_indexkey_for_join(RelOptInfo *rel, IndexOptInfo *index, JoinInfo *joininfo = (JoinInfo *) lfirst(i); List *j; - if (!is_subseti(joininfo->unjoined_relids, outer_relids)) + if (!bms_is_subset(joininfo->unjoined_relids, outer_relids)) continue; foreach(j, joininfo->jinfo_restrictinfo) @@ -820,27 +820,27 @@ match_join_clause_to_indexkey(RelOptInfo *rel, */ if (match_index_to_operand(indexkey, leftop, rel, index)) { - List *othervarnos = pull_varnos(rightop); + Relids othervarnos = pull_varnos(rightop); bool isIndexable; isIndexable = - !intMember(lfirsti(rel->relids), othervarnos) && + !bms_overlap(rel->relids, othervarnos) && !contain_volatile_functions(rightop) && is_indexable_operator(clause, opclass, true); - freeList(othervarnos); + bms_free(othervarnos); return isIndexable; } if (match_index_to_operand(indexkey, rightop, rel, index)) { - List *othervarnos = pull_varnos(leftop); + Relids othervarnos = pull_varnos(leftop); bool isIndexable; isIndexable = - !intMember(lfirsti(rel->relids), othervarnos) && + !bms_overlap(rel->relids, othervarnos) && !contain_volatile_functions(leftop) && is_indexable_operator(clause, opclass, false); - freeList(othervarnos); + bms_free(othervarnos); return isIndexable; } @@ -1312,14 +1312,14 @@ pred_test_simple_clause(Expr *predicate, Node *clause) /* * indexable_outerrelids * Finds all other relids that participate in any indexable join clause - * for the specified index. Returns a list of relids. + * for the specified index. Returns a set of relids. * * 'rel' is the relation for which 'index' is defined */ static Relids indexable_outerrelids(RelOptInfo *rel, IndexOptInfo *index) { - Relids outer_relids = NIL; + Relids outer_relids = NULL; List *i; foreach(i, rel->joininfo) @@ -1368,8 +1368,8 @@ indexable_outerrelids(RelOptInfo *rel, IndexOptInfo *index) if (match_found) { - outer_relids = set_unioni(outer_relids, - joininfo->unjoined_relids); + outer_relids = bms_add_members(outer_relids, + joininfo->unjoined_relids); } } @@ -1419,7 +1419,7 @@ best_inner_indexscan(Query *root, RelOptInfo *rel, /* * If there are no indexable joinclauses for this rel, exit quickly. */ - if (!rel->index_outer_relids) + if (bms_is_empty(rel->index_outer_relids)) return NULL; /* * Otherwise, we have to do path selection in the memory context of @@ -1433,9 +1433,10 @@ best_inner_indexscan(Query *root, RelOptInfo *rel, * to find the set of outer relids actually relevant for this index. * If there are none, again we can fail immediately. */ - outer_relids = set_intersecti(rel->index_outer_relids, outer_relids); - if (!outer_relids) + outer_relids = bms_intersect(rel->index_outer_relids, outer_relids); + if (bms_is_empty(outer_relids)) { + bms_free(outer_relids); MemoryContextSwitchTo(oldcontext); return NULL; } @@ -1448,10 +1449,10 @@ best_inner_indexscan(Query *root, RelOptInfo *rel, foreach(jlist, rel->index_inner_paths) { info = (InnerIndexscanInfo *) lfirst(jlist); - if (sameseti(info->other_relids, outer_relids) && + if (bms_equal(info->other_relids, outer_relids) && info->isouterjoin == isouterjoin) { - freeList(outer_relids); + bms_free(outer_relids); MemoryContextSwitchTo(oldcontext); return info->best_innerpath; } @@ -1470,24 +1471,25 @@ best_inner_indexscan(Query *root, RelOptInfo *rel, Relids index_outer_relids; Path *path = NULL; - /* skip quickly if index has no useful join clauses */ - if (!index->outer_relids) - continue; /* identify set of relevant outer relids for this index */ - index_outer_relids = set_intersecti(index->outer_relids, outer_relids); - if (!index_outer_relids) + index_outer_relids = bms_intersect(index->outer_relids, outer_relids); + /* skip if none */ + if (bms_is_empty(index_outer_relids)) + { + bms_free(index_outer_relids); continue; + } /* * Look to see if we already computed the result for this index. */ foreach(jlist, index->inner_paths) { info = (InnerIndexscanInfo *) lfirst(jlist); - if (sameseti(info->other_relids, index_outer_relids) && + if (bms_equal(info->other_relids, index_outer_relids) && info->isouterjoin == isouterjoin) { path = info->best_innerpath; - freeList(index_outer_relids); /* not needed anymore */ + bms_free(index_outer_relids); /* not needed anymore */ break; } } @@ -1607,7 +1609,7 @@ make_innerjoin_index_path(Query *root, restrictlist_selectivity(root, set_ptrUnion(rel->baserestrictinfo, clausegroup), - lfirsti(rel->relids), + rel->relid, JOIN_INNER); /* Like costsize.c, force estimate to be at least one row */ if (pathnode->rows < 1.0) @@ -1649,7 +1651,7 @@ match_index_to_operand(int indexkey, * Simple index. */ if (operand && IsA(operand, Var) && - lfirsti(rel->relids) == ((Var *) operand)->varno && + rel->relid == ((Var *) operand)->varno && indexkey == ((Var *) operand)->varattno) return true; else @@ -1665,7 +1667,6 @@ match_index_to_operand(int indexkey, static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel, IndexOptInfo *index) { - int relvarno = lfirsti(rel->relids); FuncExpr *function; List *funcargs; int *indexKeys = index->indexkeys; @@ -1705,7 +1706,7 @@ function_index_operand(Expr *funcOpnd, RelOptInfo *rel, IndexOptInfo *index) return false; if (indexKeys[i] == 0) return false; - if (var->varno != relvarno || var->varattno != indexKeys[i]) + if (var->varno != rel->relid || var->varattno != indexKeys[i]) return false; i++; diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index 00b029f5f13..c8175b81e39 100644 --- a/src/backend/optimizer/path/joinpath.c +++ b/src/backend/optimizer/path/joinpath.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.77 2003/01/27 20:51:51 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.78 2003/02/08 20:20:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -689,7 +689,7 @@ hash_inner_and_outer(Query *root, { RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i); - if (restrictinfo->left_relids == NIL || + if (restrictinfo->left_relids == NULL || restrictinfo->hashjoinoperator == InvalidOid) continue; /* not hashjoinable */ @@ -703,13 +703,13 @@ hash_inner_and_outer(Query *root, /* * Check if clause is usable with these input rels. */ - if (is_subseti(restrictinfo->left_relids, outerrel->relids) && - is_subseti(restrictinfo->right_relids, innerrel->relids)) + if (bms_is_subset(restrictinfo->left_relids, outerrel->relids) && + bms_is_subset(restrictinfo->right_relids, innerrel->relids)) { /* righthand side is inner */ } - else if (is_subseti(restrictinfo->left_relids, innerrel->relids) && - is_subseti(restrictinfo->right_relids, outerrel->relids)) + else if (bms_is_subset(restrictinfo->left_relids, innerrel->relids) && + bms_is_subset(restrictinfo->right_relids, outerrel->relids)) { /* lefthand side is inner */ } @@ -808,12 +808,12 @@ select_mergejoin_clauses(RelOptInfo *joinrel, switch (jointype) { case JOIN_RIGHT: - if (restrictinfo->left_relids == NIL || + if (restrictinfo->left_relids == NULL || restrictinfo->mergejoinoperator == InvalidOid) return NIL; /* not mergejoinable */ break; case JOIN_FULL: - if (restrictinfo->left_relids == NIL || + if (restrictinfo->left_relids == NULL || restrictinfo->mergejoinoperator == InvalidOid) elog(ERROR, "FULL JOIN is only supported with mergejoinable join conditions"); break; @@ -823,7 +823,7 @@ select_mergejoin_clauses(RelOptInfo *joinrel, } } - if (restrictinfo->left_relids == NIL || + if (restrictinfo->left_relids == NULL || restrictinfo->mergejoinoperator == InvalidOid) continue; /* not mergejoinable */ @@ -832,13 +832,13 @@ select_mergejoin_clauses(RelOptInfo *joinrel, * needed on each side of the clause must be available from one or * the other of the input rels. */ - if (is_subseti(restrictinfo->left_relids, outerrel->relids) && - is_subseti(restrictinfo->right_relids, innerrel->relids)) + if (bms_is_subset(restrictinfo->left_relids, outerrel->relids) && + bms_is_subset(restrictinfo->right_relids, innerrel->relids)) { /* righthand side is inner */ } - else if (is_subseti(restrictinfo->left_relids, innerrel->relids) && - is_subseti(restrictinfo->right_relids, outerrel->relids)) + else if (bms_is_subset(restrictinfo->left_relids, innerrel->relids) && + bms_is_subset(restrictinfo->right_relids, outerrel->relids)) { /* lefthand side is inner */ } diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c index 704afda37f8..260b0cf6cd0 100644 --- a/src/backend/optimizer/path/joinrels.c +++ b/src/backend/optimizer/path/joinrels.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.59 2003/01/20 18:54:51 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.60 2003/02/08 20:20:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -151,7 +151,7 @@ make_rels_by_joins(Query *root, int level, List **joinrels) { RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2); - if (nonoverlap_setsi(old_rel->relids, new_rel->relids)) + if (!bms_overlap(old_rel->relids, new_rel->relids)) { List *i; @@ -164,8 +164,8 @@ make_rels_by_joins(Query *root, int level, List **joinrels) { JoinInfo *joininfo = (JoinInfo *) lfirst(i); - if (is_subseti(joininfo->unjoined_relids, - new_rel->relids)) + if (bms_is_subset(joininfo->unjoined_relids, + new_rel->relids)) { RelOptInfo *jrel; @@ -268,7 +268,7 @@ make_rels_by_clause_joins(Query *root, { RelOptInfo *other_rel = (RelOptInfo *) lfirst(j); - if (is_subseti(unjoined_relids, other_rel->relids)) + if (bms_is_subset(unjoined_relids, other_rel->relids)) { RelOptInfo *jrel; @@ -312,7 +312,7 @@ make_rels_by_clauseless_joins(Query *root, { RelOptInfo *other_rel = (RelOptInfo *) lfirst(i); - if (nonoverlap_setsi(other_rel->relids, old_rel->relids)) + if (!bms_overlap(other_rel->relids, old_rel->relids)) { RelOptInfo *jrel; @@ -406,15 +406,15 @@ RelOptInfo * make_join_rel(Query *root, RelOptInfo *rel1, RelOptInfo *rel2, JoinType jointype) { - List *joinrelids; + Relids joinrelids; RelOptInfo *joinrel; List *restrictlist; /* We should never try to join two overlapping sets of rels. */ - Assert(nonoverlap_setsi(rel1->relids, rel2->relids)); + Assert(!bms_overlap(rel1->relids, rel2->relids)); /* Construct Relids set that identifies the joinrel. */ - joinrelids = nconc(listCopy(rel1->relids), listCopy(rel2->relids)); + joinrelids = bms_union(rel1->relids, rel2->relids); /* * If we are implementing IN clauses as joins, there are some joins @@ -433,15 +433,12 @@ make_join_rel(Query *root, RelOptInfo *rel1, RelOptInfo *rel2, /* * Cannot join if proposed join contains part, but only * part, of the RHS, *and* it contains rels not in the RHS. - * - * Singleton RHS cannot be a problem, so skip expensive tests. */ - if (length(ininfo->righthand) > 1 && - overlap_setsi(ininfo->righthand, joinrelids) && - !is_subseti(ininfo->righthand, joinrelids) && - !is_subseti(joinrelids, ininfo->righthand)) + if (bms_overlap(ininfo->righthand, joinrelids) && + !bms_is_subset(ininfo->righthand, joinrelids) && + !bms_is_subset(joinrelids, ininfo->righthand)) { - freeList(joinrelids); + bms_free(joinrelids); return NULL; } @@ -449,19 +446,19 @@ make_join_rel(Query *root, RelOptInfo *rel1, RelOptInfo *rel2, * No issue unless we are looking at a join of the IN's RHS * to other stuff. */ - if (! (length(ininfo->righthand) < length(joinrelids) && - is_subseti(ininfo->righthand, joinrelids))) + if (! (bms_is_subset(ininfo->righthand, joinrelids) && + !bms_equal(ininfo->righthand, joinrelids))) continue; /* * If we already joined IN's RHS to any part of its LHS in either * input path, then this join is not constrained (the necessary * work was done at a lower level). */ - if (overlap_setsi(ininfo->lefthand, rel1->relids) && - is_subseti(ininfo->righthand, rel1->relids)) + if (bms_overlap(ininfo->lefthand, rel1->relids) && + bms_is_subset(ininfo->righthand, rel1->relids)) continue; - if (overlap_setsi(ininfo->lefthand, rel2->relids) && - is_subseti(ininfo->righthand, rel2->relids)) + if (bms_overlap(ininfo->lefthand, rel2->relids) && + bms_is_subset(ininfo->righthand, rel2->relids)) continue; /* * JOIN_IN technique will work if outerrel includes LHS and @@ -477,31 +474,31 @@ make_join_rel(Query *root, RelOptInfo *rel1, RelOptInfo *rel2, */ if (jointype != JOIN_INNER) { - freeList(joinrelids); + bms_free(joinrelids); return NULL; } - if (is_subseti(ininfo->lefthand, rel1->relids) && - sameseti(ininfo->righthand, rel2->relids)) + if (bms_is_subset(ininfo->lefthand, rel1->relids) && + bms_equal(ininfo->righthand, rel2->relids)) { jointype = JOIN_IN; } - else if (is_subseti(ininfo->lefthand, rel2->relids) && - sameseti(ininfo->righthand, rel1->relids)) + else if (bms_is_subset(ininfo->lefthand, rel2->relids) && + bms_equal(ininfo->righthand, rel1->relids)) { jointype = JOIN_REVERSE_IN; } - else if (sameseti(ininfo->righthand, rel1->relids)) + else if (bms_equal(ininfo->righthand, rel1->relids)) { jointype = JOIN_UNIQUE_OUTER; } - else if (sameseti(ininfo->righthand, rel2->relids)) + else if (bms_equal(ininfo->righthand, rel2->relids)) { jointype = JOIN_UNIQUE_INNER; } else { /* invalid join path */ - freeList(joinrelids); + bms_free(joinrelids); return NULL; } } @@ -579,7 +576,7 @@ make_join_rel(Query *root, RelOptInfo *rel1, RelOptInfo *rel2, break; } - freeList(joinrelids); + bms_free(joinrelids); return joinrel; } diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index b99a44a4404..c72a635535c 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -11,7 +11,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.45 2003/01/24 03:58:35 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.46 2003/02/08 20:20:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -198,7 +198,7 @@ generate_implied_equalities(Query *root) * Collect info about relids mentioned in each item. For this * routine we only really care whether there are any at all in * each item, but process_implied_equality() needs the exact - * lists, so we may as well pull them here. + * sets, so we may as well pull them here. */ relids = (Relids *) palloc(nitems * sizeof(Relids)); have_consts = false; @@ -208,7 +208,7 @@ generate_implied_equalities(Query *root) PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1); relids[i1] = pull_varnos(item1->key); - if (relids[i1] == NIL) + if (bms_is_empty(relids[i1])) have_consts = true; i1++; } @@ -221,12 +221,14 @@ generate_implied_equalities(Query *root) foreach(ptr1, curset) { PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1); + bool i1_is_variable = !bms_is_empty(relids[i1]); List *ptr2; int i2 = i1 + 1; foreach(ptr2, lnext(ptr1)) { PathKeyItem *item2 = (PathKeyItem *) lfirst(ptr2); + bool i2_is_variable = !bms_is_empty(relids[i2]); /* * If it's "const = const" then just ignore it altogether. @@ -235,7 +237,7 @@ generate_implied_equalities(Query *root) * propagating the comparison to Vars will cause us to * produce zero rows out, as expected.) */ - if (relids[i1] != NIL || relids[i2] != NIL) + if (i1_is_variable || i2_is_variable) { /* * Tell process_implied_equality to delete the clause, @@ -243,8 +245,9 @@ generate_implied_equalities(Query *root) * present in the list. */ bool delete_it = (have_consts && - relids[i1] != NIL && - relids[i2] != NIL); + i1_is_variable && + i2_is_variable); + process_implied_equality(root, item1->key, item2->key, item1->sortop, item2->sortop, @@ -689,7 +692,7 @@ static Var * find_indexkey_var(Query *root, RelOptInfo *rel, AttrNumber varattno) { List *temp; - int relid; + Index relid; Oid reloid, vartypeid; int32 type_mod; @@ -702,7 +705,8 @@ find_indexkey_var(Query *root, RelOptInfo *rel, AttrNumber varattno) return tle_var; } - relid = lfirsti(rel->relids); + relid = rel->relid; + Assert(relid > 0); reloid = getrelid(relid, root->rtable); vartypeid = get_atttype(reloid, varattno); type_mod = get_atttypmod(reloid, varattno); @@ -953,12 +957,12 @@ make_pathkeys_for_mergeclauses(Query *root, cache_mergeclause_pathkeys(root, restrictinfo); - if (is_subseti(restrictinfo->left_relids, rel->relids)) + if (bms_is_subset(restrictinfo->left_relids, rel->relids)) { /* Rel is left side of mergeclause */ pathkey = restrictinfo->left_pathkey; } - else if (is_subseti(restrictinfo->right_relids, rel->relids)) + else if (bms_is_subset(restrictinfo->right_relids, rel->relids)) { /* Rel is right side of mergeclause */ pathkey = restrictinfo->right_pathkey; diff --git a/src/backend/optimizer/path/tidpath.c b/src/backend/optimizer/path/tidpath.c index f11ff81ea41..761f03b967c 100644 --- a/src/backend/optimizer/path/tidpath.c +++ b/src/backend/optimizer/path/tidpath.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/tidpath.c,v 1.13 2002/12/12 15:49:32 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/tidpath.c,v 1.14 2003/02/08 20:20:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -25,7 +25,7 @@ #include "parser/parse_coerce.h" #include "utils/lsyscache.h" -static List *TidqualFromRestrictinfo(List *relids, List *restrictinfo); +static List *TidqualFromRestrictinfo(Relids relids, List *restrictinfo); static bool isEvaluable(int varno, Node *node); static Node *TidequalClause(int varno, OpExpr *node); static List *TidqualFromExpr(int varno, Expr *expr); @@ -198,7 +198,7 @@ TidqualFromExpr(int varno, Expr *expr) } static List * -TidqualFromRestrictinfo(List *relids, List *restrictinfo) +TidqualFromRestrictinfo(Relids relids, List *restrictinfo) { List *lst, *rlst = NIL; @@ -206,9 +206,9 @@ TidqualFromRestrictinfo(List *relids, List *restrictinfo) Node *node; Expr *expr; - if (length(relids) != 1) + if (bms_membership(relids) != BMS_SINGLETON) return NIL; - varno = lfirsti(relids); + varno = bms_singleton_member(relids); foreach(lst, restrictinfo) { node = lfirst(lst); diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index d78dd2c1e83..8bb651ae5cc 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -10,7 +10,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.134 2003/02/03 15:07:07 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.135 2003/02/08 20:20:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -65,13 +65,14 @@ static HashJoin *create_hashjoin_plan(Query *root, static void fix_indxqual_references(List *indexquals, IndexPath *index_path, List **fixed_indexquals, List **recheck_indexquals); -static void fix_indxqual_sublist(List *indexqual, int baserelid, - IndexOptInfo *index, - List **fixed_quals, List **recheck_quals); +static void fix_indxqual_sublist(List *indexqual, + Relids baserelids, int baserelid, + IndexOptInfo *index, + List **fixed_quals, List **recheck_quals); static Node *fix_indxqual_operand(Node *node, int baserelid, IndexOptInfo *index, Oid *opclass); -static List *get_switched_clauses(List *clauses, List *outerrelids); +static List *get_switched_clauses(List *clauses, Relids outerrelids); static List *order_qual_clauses(Query *root, List *clauses); static void copy_path_costsize(Plan *dest, Path *src); static void copy_plan_costsize(Plan *dest, Plan *src); @@ -100,7 +101,7 @@ static MergeJoin *make_mergejoin(List *tlist, Plan *lefttree, Plan *righttree, JoinType jointype); static Sort *make_sort_from_pathkeys(Query *root, Plan *lefttree, - List *relids, List *pathkeys); + Relids relids, List *pathkeys); /* @@ -502,7 +503,7 @@ create_unique_plan(Query *root, UniquePath *best_path) { InClauseInfo *ininfo = (InClauseInfo *) lfirst(l); - if (sameseti(ininfo->righthand, best_path->path.parent->relids)) + if (bms_equal(ininfo->righthand, best_path->path.parent->relids)) { sub_targetlist = ininfo->sub_targetlist; break; @@ -601,14 +602,12 @@ static SeqScan * create_seqscan_plan(Path *best_path, List *tlist, List *scan_clauses) { SeqScan *scan_plan; - Index scan_relid; + Index scan_relid = best_path->parent->relid; - /* there should be exactly one base rel involved... */ - Assert(length(best_path->parent->relids) == 1); + /* it should be a base rel... */ + Assert(scan_relid > 0); Assert(best_path->parent->rtekind == RTE_RELATION); - scan_relid = (Index) lfirsti(best_path->parent->relids); - scan_plan = make_seqscan(tlist, scan_clauses, scan_relid); @@ -638,7 +637,7 @@ create_indexscan_plan(Query *root, List *scan_clauses) { List *indxqual = best_path->indexqual; - Index baserelid; + Index baserelid = best_path->path.parent->relid; List *qpqual; Expr *indxqual_or_expr = NULL; List *fixed_indxqual; @@ -647,12 +646,10 @@ create_indexscan_plan(Query *root, List *ixinfo; IndexScan *scan_plan; - /* there should be exactly one base rel involved... */ - Assert(length(best_path->path.parent->relids) == 1); + /* it should be a base rel... */ + Assert(baserelid > 0); Assert(best_path->path.parent->rtekind == RTE_RELATION); - baserelid = lfirsti(best_path->path.parent->relids); - /* * Build list of index OIDs. */ @@ -763,14 +760,12 @@ static TidScan * create_tidscan_plan(TidPath *best_path, List *tlist, List *scan_clauses) { TidScan *scan_plan; - Index scan_relid; + Index scan_relid = best_path->path.parent->relid; - /* there should be exactly one base rel involved... */ - Assert(length(best_path->path.parent->relids) == 1); + /* it should be a base rel... */ + Assert(scan_relid > 0); Assert(best_path->path.parent->rtekind == RTE_RELATION); - scan_relid = (Index) lfirsti(best_path->path.parent->relids); - scan_plan = make_tidscan(tlist, scan_clauses, scan_relid, @@ -790,15 +785,12 @@ static SubqueryScan * create_subqueryscan_plan(Path *best_path, List *tlist, List *scan_clauses) { SubqueryScan *scan_plan; - Index scan_relid; + Index scan_relid = best_path->parent->relid; - /* there should be exactly one base rel involved... */ - Assert(length(best_path->parent->relids) == 1); - /* and it must be a subquery */ + /* it should be a subquery base rel... */ + Assert(scan_relid > 0); Assert(best_path->parent->rtekind == RTE_SUBQUERY); - scan_relid = (Index) lfirsti(best_path->parent->relids); - scan_plan = make_subqueryscan(tlist, scan_clauses, scan_relid, @@ -816,15 +808,12 @@ static FunctionScan * create_functionscan_plan(Path *best_path, List *tlist, List *scan_clauses) { FunctionScan *scan_plan; - Index scan_relid; + Index scan_relid = best_path->parent->relid; - /* there should be exactly one base rel involved... */ - Assert(length(best_path->parent->relids) == 1); - /* and it must be a function */ + /* it should be a function base rel... */ + Assert(scan_relid > 0); Assert(best_path->parent->rtekind == RTE_FUNCTION); - scan_relid = (Index) lfirsti(best_path->parent->relids); - scan_plan = make_functionscan(tlist, scan_clauses, scan_relid); copy_path_costsize(&scan_plan->scan.plan, best_path); @@ -1055,7 +1044,8 @@ fix_indxqual_references(List *indexquals, IndexPath *index_path, { List *fixed_quals = NIL; List *recheck_quals = NIL; - int baserelid = lfirsti(index_path->path.parent->relids); + Relids baserelids = index_path->path.parent->relids; + int baserelid = index_path->path.parent->relid; List *ixinfo = index_path->indexinfo; List *i; @@ -1066,7 +1056,7 @@ fix_indxqual_references(List *indexquals, IndexPath *index_path, List *fixed_qual; List *recheck_qual; - fix_indxqual_sublist(indexqual, baserelid, index, + fix_indxqual_sublist(indexqual, baserelids, baserelid, index, &fixed_qual, &recheck_qual); fixed_quals = lappend(fixed_quals, fixed_qual); if (recheck_qual != NIL) @@ -1092,7 +1082,9 @@ fix_indxqual_references(List *indexquals, IndexPath *index_path, * the index is lossy for this operator type. */ static void -fix_indxqual_sublist(List *indexqual, int baserelid, IndexOptInfo *index, +fix_indxqual_sublist(List *indexqual, + Relids baserelids, int baserelid, + IndexOptInfo *index, List **fixed_quals, List **recheck_quals) { List *fixed_qual = NIL; @@ -1103,7 +1095,7 @@ fix_indxqual_sublist(List *indexqual, int baserelid, IndexOptInfo *index, { OpExpr *clause = (OpExpr *) lfirst(i); OpExpr *newclause; - List *leftvarnos; + Relids leftvarnos; Oid opclass; if (!IsA(clause, OpExpr) || length(clause->args) != 2) @@ -1124,9 +1116,9 @@ fix_indxqual_sublist(List *indexqual, int baserelid, IndexOptInfo *index, * (only) the base relation. */ leftvarnos = pull_varnos((Node *) lfirst(newclause->args)); - if (length(leftvarnos) != 1 || lfirsti(leftvarnos) != baserelid) + if (!bms_equal(leftvarnos, baserelids)) CommuteClause(newclause); - freeList(leftvarnos); + bms_free(leftvarnos); /* * Now, determine which index attribute this is, change the @@ -1222,7 +1214,7 @@ fix_indxqual_operand(Node *node, int baserelid, IndexOptInfo *index, * a modified list is returned. */ static List * -get_switched_clauses(List *clauses, List *outerrelids) +get_switched_clauses(List *clauses, Relids outerrelids) { List *t_list = NIL; List *i; @@ -1233,7 +1225,7 @@ get_switched_clauses(List *clauses, List *outerrelids) OpExpr *clause = (OpExpr *) restrictinfo->clause; Assert(is_opclause(clause)); - if (is_subseti(restrictinfo->right_relids, outerrelids)) + if (bms_is_subset(restrictinfo->right_relids, outerrelids)) { /* * Duplicate just enough of the structure to allow commuting @@ -1628,7 +1620,7 @@ make_sort(Query *root, List *tlist, Plan *lefttree, int keycount) */ static Sort * make_sort_from_pathkeys(Query *root, Plan *lefttree, - List *relids, List *pathkeys) + Relids relids, List *pathkeys) { List *tlist = lefttree->targetlist; List *sort_tlist; @@ -1671,7 +1663,7 @@ make_sort_from_pathkeys(Query *root, Plan *lefttree, foreach(j, keysublist) { pathkey = lfirst(j); - if (is_subseti(pull_varnos(pathkey->key), relids)) + if (bms_is_subset(pull_varnos(pathkey->key), relids)) break; } if (!j) diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index 3a824d55d72..86ffc2906f0 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.83 2003/01/24 03:58:43 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.84 2003/02/08 20:20:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -165,18 +165,18 @@ add_vars_to_targetlist(Query *root, List *vars) * of an outer join since the qual might eliminate matching rows and cause a * NULL row to be incorrectly emitted by the join. Therefore, rels appearing * within the nullable side(s) of an outer join are marked with - * outerjoinset = list of Relids used at the outer join node. - * This list will be added to the list of rels referenced by quals using such + * outerjoinset = set of Relids used at the outer join node. + * This set will be added to the set of rels referenced by quals using such * a rel, thereby forcing them up the join tree to the right level. * * To ease the calculation of these values, distribute_quals_to_rels() returns - * the list of base Relids involved in its own level of join. This is just an + * the set of base Relids involved in its own level of join. This is just an * internal convenience; no outside callers pay attention to the result. */ Relids distribute_quals_to_rels(Query *root, Node *jtnode) { - Relids result = NIL; + Relids result = NULL; if (jtnode == NULL) return result; @@ -185,7 +185,7 @@ distribute_quals_to_rels(Query *root, Node *jtnode) int varno = ((RangeTblRef *) jtnode)->rtindex; /* No quals to deal with, just return correct result */ - result = makeListi1(varno); + result = bms_make_singleton(varno); } else if (IsA(jtnode, FromExpr)) { @@ -195,14 +195,12 @@ distribute_quals_to_rels(Query *root, Node *jtnode) /* * First, recurse to handle child joins. - * - * Note: we assume it's impossible to see same RT index from more - * than one subtree, so nconc() is OK rather than set_unioni(). */ foreach(l, f->fromlist) { - result = nconc(result, - distribute_quals_to_rels(root, lfirst(l))); + result = bms_add_members(result, + distribute_quals_to_rels(root, + lfirst(l))); } /* @@ -226,7 +224,7 @@ distribute_quals_to_rels(Query *root, Node *jtnode) * recurse to handle sub-JOINs. Their join quals will be placed * without regard for whether this level is an outer join, which * is correct. Then, if we are an outer join, we mark baserels - * contained within the nullable side(s) with our own rel list; + * contained within the nullable side(s) with our own rel set; * this will restrict placement of subsequent quals using those * rels, including our own quals and quals above us in the join * tree. Finally we place our own join quals. @@ -234,7 +232,7 @@ distribute_quals_to_rels(Query *root, Node *jtnode) leftids = distribute_quals_to_rels(root, j->larg); rightids = distribute_quals_to_rels(root, j->rarg); - result = nconc(listCopy(leftids), rightids); + result = bms_union(leftids, rightids); isouterjoin = false; switch (j->jointype) @@ -286,18 +284,19 @@ distribute_quals_to_rels(Query *root, Node *jtnode) static void mark_baserels_for_outer_join(Query *root, Relids rels, Relids outerrels) { - List *relid; + Relids tmprelids; + int relno; - foreach(relid, rels) + tmprelids = bms_copy(rels); + while ((relno = bms_first_member(tmprelids)) >= 0) { - int relno = lfirsti(relid); RelOptInfo *rel = find_base_rel(root, relno); /* * Since we do this bottom-up, any outer-rels previously marked * should be within the new outer join set. */ - Assert(is_subseti(rel->outerjoinset, outerrels)); + Assert(bms_is_subset(rel->outerjoinset, outerrels)); /* * Presently the executor cannot support FOR UPDATE marking of @@ -308,7 +307,7 @@ mark_baserels_for_outer_join(Query *root, Relids rels, Relids outerrels) * It's sufficient to make this check once per rel, so do it only * if rel wasn't already known nullable. */ - if (rel->outerjoinset == NIL) + if (rel->outerjoinset == NULL) { if (intMember(relno, root->rowMarks)) elog(ERROR, "SELECT FOR UPDATE cannot be applied to the nullable side of an OUTER JOIN"); @@ -316,6 +315,7 @@ mark_baserels_for_outer_join(Query *root, Relids rels, Relids outerrels) rel->outerjoinset = outerrels; } + bms_free(tmprelids); } /* @@ -332,7 +332,7 @@ mark_baserels_for_outer_join(Query *root, Relids rels, Relids outerrels) * (this indicates the clause came from a FromExpr, not a JoinExpr) * 'isouterjoin': TRUE if the qual came from an OUTER JOIN's ON-clause * 'isdeduced': TRUE if the qual came from implied-equality deduction - * 'qualscope': list of baserels the qual's syntactic scope covers + * 'qualscope': set of baserels the qual's syntactic scope covers * * 'qualscope' identifies what level of JOIN the qual came from. For a top * level qual (WHERE qual), qualscope lists all baserel ids and in addition @@ -346,6 +346,7 @@ distribute_qual_to_rels(Query *root, Node *clause, Relids qualscope) { RestrictInfo *restrictinfo = makeNode(RestrictInfo); + RelOptInfo *rel; Relids relids; List *vars; bool can_be_equijoin; @@ -354,8 +355,8 @@ distribute_qual_to_rels(Query *root, Node *clause, restrictinfo->subclauseindices = NIL; restrictinfo->eval_cost.startup = -1; /* not computed until needed */ restrictinfo->this_selec = -1; /* not computed until needed */ - restrictinfo->left_relids = NIL; /* set below, if join clause */ - restrictinfo->right_relids = NIL; + restrictinfo->left_relids = NULL; /* set below, if join clause */ + restrictinfo->right_relids = NULL; restrictinfo->mergejoinoperator = InvalidOid; restrictinfo->left_sortop = InvalidOid; restrictinfo->right_sortop = InvalidOid; @@ -377,7 +378,7 @@ distribute_qual_to_rels(Query *root, Node *clause, * Cross-check: clause should contain no relids not within its scope. * Otherwise the parser messed up. */ - if (!is_subseti(relids, qualscope)) + if (!bms_is_subset(relids, qualscope)) elog(ERROR, "JOIN qualification may not refer to other relations"); /* @@ -387,7 +388,7 @@ distribute_qual_to_rels(Query *root, Node *clause, * it will happen for variable-free JOIN/ON clauses. We don't have to * be real smart about such a case, we just have to be correct. */ - if (relids == NIL) + if (bms_is_empty(relids)) relids = qualscope; /* @@ -400,9 +401,9 @@ distribute_qual_to_rels(Query *root, Node *clause, * have all the rels it mentions, and (2) we are at or above any outer * joins that can null any of these rels and are below the syntactic * location of the given qual. To enforce the latter, scan the base - * rels listed in relids, and merge their outer-join lists into the + * rels listed in relids, and merge their outer-join sets into the * clause's own reference list. At the time we are called, the - * outerjoinset list of each baserel will show exactly those outer + * outerjoinset of each baserel will show exactly those outer * joins that are below the qual in the join tree. * * If the qual came from implied-equality deduction, we can evaluate the @@ -411,7 +412,7 @@ distribute_qual_to_rels(Query *root, Node *clause, */ if (isdeduced) { - Assert(sameseti(relids, qualscope)); + Assert(bms_equal(relids, qualscope)); can_be_equijoin = true; } else if (isouterjoin) @@ -421,22 +422,20 @@ distribute_qual_to_rels(Query *root, Node *clause, } else { - Relids newrelids = relids; - List *relid; + /* copy to ensure we don't change caller's qualscope set */ + Relids newrelids = bms_copy(relids); + Relids tmprelids; + int relno; - /* - * We rely on set_unioni to be nondestructive of its input - * lists... - */ can_be_equijoin = true; - foreach(relid, relids) + tmprelids = bms_copy(relids); + while ((relno = bms_first_member(tmprelids)) >= 0) { - RelOptInfo *rel = find_base_rel(root, lfirsti(relid)); + RelOptInfo *rel = find_base_rel(root, relno); - if (rel->outerjoinset && - !is_subseti(rel->outerjoinset, relids)) + if (!bms_is_subset(rel->outerjoinset, relids)) { - newrelids = set_unioni(newrelids, rel->outerjoinset); + newrelids = bms_add_members(newrelids, rel->outerjoinset); /* * Because application of the qual will be delayed by @@ -446,9 +445,10 @@ distribute_qual_to_rels(Query *root, Node *clause, can_be_equijoin = false; } } + bms_free(tmprelids); relids = newrelids; /* Should still be a subset of current scope ... */ - Assert(is_subseti(relids, qualscope)); + Assert(bms_is_subset(relids, qualscope)); } /* @@ -458,102 +458,104 @@ distribute_qual_to_rels(Query *root, Node *clause, * same joinrel. A qual originating from WHERE is always considered * "pushed down". */ - restrictinfo->ispusheddown = ispusheddown || !sameseti(relids, - qualscope); + restrictinfo->ispusheddown = ispusheddown || !bms_equal(relids, + qualscope); - if (length(relids) == 1) + switch (bms_membership(relids)) { - /* - * There is only one relation participating in 'clause', so - * 'clause' is a restriction clause for that relation. - */ - RelOptInfo *rel = find_base_rel(root, lfirsti(relids)); - - /* - * Check for a "mergejoinable" clause even though it's not a join - * clause. This is so that we can recognize that "a.x = a.y" - * makes x and y eligible to be considered equal, even when they - * belong to the same rel. Without this, we would not recognize - * that "a.x = a.y AND a.x = b.z AND a.y = c.q" allows us to - * consider z and q equal after their rels are joined. - */ - if (can_be_equijoin) - check_mergejoinable(restrictinfo); + case BMS_SINGLETON: + /* + * There is only one relation participating in 'clause', so + * 'clause' is a restriction clause for that relation. + */ + rel = find_base_rel(root, bms_singleton_member(relids)); - /* - * If the clause was deduced from implied equality, check to see - * whether it is redundant with restriction clauses we already - * have for this rel. Note we cannot apply this check to - * user-written clauses, since we haven't found the canonical - * pathkey sets yet while processing user clauses. (NB: no - * comparable check is done in the join-clause case; redundancy - * will be detected when the join clause is moved into a join - * rel's restriction list.) - */ - if (!isdeduced || - !qual_is_redundant(root, restrictinfo, rel->baserestrictinfo)) - { - /* Add clause to rel's restriction list */ - rel->baserestrictinfo = lappend(rel->baserestrictinfo, - restrictinfo); - } - } - else if (relids != NIL) - { - /* - * 'clause' is a join clause, since there is more than one rel in - * the relid list. Set additional RestrictInfo fields for - * joining. First, does it look like a normal join clause, i.e., - * a binary operator relating expressions that come from distinct - * relations? If so we might be able to use it in a join algorithm. - */ - if (is_opclause(clause) && length(((OpExpr *) clause)->args) == 2) - { - List *left_relids; - List *right_relids; + /* + * Check for a "mergejoinable" clause even though it's not a join + * clause. This is so that we can recognize that "a.x = a.y" + * makes x and y eligible to be considered equal, even when they + * belong to the same rel. Without this, we would not recognize + * that "a.x = a.y AND a.x = b.z AND a.y = c.q" allows us to + * consider z and q equal after their rels are joined. + */ + if (can_be_equijoin) + check_mergejoinable(restrictinfo); - left_relids = pull_varnos(get_leftop((Expr *) clause)); - right_relids = pull_varnos(get_rightop((Expr *) clause)); - if (left_relids && right_relids && - nonoverlap_setsi(left_relids, right_relids)) + /* + * If the clause was deduced from implied equality, check to see + * whether it is redundant with restriction clauses we already + * have for this rel. Note we cannot apply this check to + * user-written clauses, since we haven't found the canonical + * pathkey sets yet while processing user clauses. (NB: no + * comparable check is done in the join-clause case; redundancy + * will be detected when the join clause is moved into a join + * rel's restriction list.) + */ + if (!isdeduced || + !qual_is_redundant(root, restrictinfo, rel->baserestrictinfo)) { - restrictinfo->left_relids = left_relids; - restrictinfo->right_relids = right_relids; + /* Add clause to rel's restriction list */ + rel->baserestrictinfo = lappend(rel->baserestrictinfo, + restrictinfo); + } + break; + case BMS_MULTIPLE: + /* + * 'clause' is a join clause, since there is more than one rel in + * the relid set. Set additional RestrictInfo fields for + * joining. First, does it look like a normal join clause, i.e., + * a binary operator relating expressions that come from distinct + * relations? If so we might be able to use it in a join + * algorithm. + */ + if (is_opclause(clause) && length(((OpExpr *) clause)->args) == 2) + { + Relids left_relids; + Relids right_relids; + + left_relids = pull_varnos(get_leftop((Expr *) clause)); + right_relids = pull_varnos(get_rightop((Expr *) clause)); + if (!bms_is_empty(left_relids) && + !bms_is_empty(right_relids) && + !bms_overlap(left_relids, right_relids)) + { + restrictinfo->left_relids = left_relids; + restrictinfo->right_relids = right_relids; + } } - } - /* - * Now check for hash or mergejoinable operators. - * - * We don't bother setting the hashjoin info if we're not going - * to need it. We do want to know about mergejoinable ops in all - * cases, however, because we use mergejoinable ops for other - * purposes such as detecting redundant clauses. - */ - check_mergejoinable(restrictinfo); - if (enable_hashjoin) - check_hashjoinable(restrictinfo); + /* + * Now check for hash or mergejoinable operators. + * + * We don't bother setting the hashjoin info if we're not going + * to need it. We do want to know about mergejoinable ops in all + * cases, however, because we use mergejoinable ops for other + * purposes such as detecting redundant clauses. + */ + check_mergejoinable(restrictinfo); + if (enable_hashjoin) + check_hashjoinable(restrictinfo); - /* - * Add clause to the join lists of all the relevant relations. - */ - add_join_clause_to_rels(root, restrictinfo, relids); + /* + * Add clause to the join lists of all the relevant relations. + */ + add_join_clause_to_rels(root, restrictinfo, relids); - /* - * Add vars used in the join clause to targetlists of their - * relations, so that they will be emitted by the plan nodes that - * scan those relations (else they won't be available at the join - * node!). - */ - add_vars_to_targetlist(root, vars); - } - else - { - /* - * 'clause' references no rels, and therefore we have no place to - * attach it. Shouldn't get here if callers are working properly. - */ - elog(ERROR, "distribute_qual_to_rels: can't cope with variable-free clause"); + /* + * Add vars used in the join clause to targetlists of their + * relations, so that they will be emitted by the plan nodes that + * scan those relations (else they won't be available at the join + * node!). + */ + add_vars_to_targetlist(root, vars); + break; + default: + /* + * 'clause' references no rels, and therefore we have no place to + * attach it. Shouldn't get here if callers are working properly. + */ + elog(ERROR, "distribute_qual_to_rels: can't cope with variable-free clause"); + break; } /* @@ -589,6 +591,7 @@ process_implied_equality(Query *root, bool delete_it) { Relids relids; + BMS_Membership membership; RelOptInfo *rel1; List *restrictlist; List *itm; @@ -598,27 +601,43 @@ process_implied_equality(Query *root, Form_pg_operator pgopform; Expr *clause; - /* Get list of relids referenced in the two expressions */ - relids = set_unioni(item1_relids, item2_relids); + /* Get set of relids referenced in the two expressions */ + relids = bms_union(item1_relids, item2_relids); + membership = bms_membership(relids); /* * generate_implied_equalities() shouldn't call me on two constants. */ - Assert(relids != NIL); + Assert(membership != BMS_EMPTY_SET); /* * If the exprs involve a single rel, we need to look at that rel's * baserestrictinfo list. If multiple rels, any one will have a * joininfo node for the rest, and we can scan any of 'em. */ - rel1 = find_base_rel(root, lfirsti(relids)); - if (lnext(relids) == NIL) + if (membership == BMS_SINGLETON) + { + rel1 = find_base_rel(root, bms_singleton_member(relids)); restrictlist = rel1->baserestrictinfo; + } else { - JoinInfo *joininfo = find_joininfo_node(rel1, lnext(relids)); + Relids other_rels; + int first_rel; + JoinInfo *joininfo; + + /* Copy relids, find and remove one member */ + other_rels = bms_copy(relids); + first_rel = bms_first_member(other_rels); + + rel1 = find_base_rel(root, first_rel); + + /* use remaining members to find join node */ + joininfo = find_joininfo_node(rel1, other_rels); restrictlist = joininfo ? joininfo->jinfo_restrictinfo : NIL; + + bms_free(other_rels); } /* @@ -642,7 +661,7 @@ process_implied_equality(Query *root, /* found a matching clause */ if (delete_it) { - if (lnext(relids) == NIL) + if (membership == BMS_SINGLETON) { /* delete it from local restrictinfo list */ rel1->baserestrictinfo = lremove(restrictinfo, diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index 9f56a9f38d5..a2c8053b5dc 100644 --- a/src/backend/optimizer/plan/subselect.c +++ b/src/backend/optimizer/plan/subselect.c @@ -7,7 +7,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.69 2003/01/28 22:13:35 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.70 2003/02/08 20:20:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -607,7 +607,7 @@ Node * convert_IN_to_join(Query *parse, SubLink *sublink) { Query *subselect = (Query *) sublink->subselect; - List *left_varnos; + Relids left_varnos; int rtindex; RangeTblEntry *rte; RangeTblRef *rtr; @@ -635,7 +635,7 @@ convert_IN_to_join(Query *parse, SubLink *sublink) * query, else it's not gonna be a join. */ left_varnos = pull_varnos((Node *) sublink->lefthand); - if (left_varnos == NIL) + if (bms_is_empty(left_varnos)) return NULL; /* * The left-hand expressions mustn't be volatile. (Perhaps we should @@ -666,7 +666,7 @@ convert_IN_to_join(Query *parse, SubLink *sublink) */ ininfo = makeNode(InClauseInfo); ininfo->lefthand = left_varnos; - ininfo->righthand = makeListi1(rtindex); + ininfo->righthand = bms_make_singleton(rtindex); parse->in_info_list = lcons(ininfo, parse->in_info_list); /* * Build the result qual expressions. As a side effect, diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c index 68fbb1e1f53..5b89c85c3d5 100644 --- a/src/backend/optimizer/prep/prepjointree.c +++ b/src/backend/optimizer/prep/prepjointree.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.2 2003/01/25 23:10:27 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.3 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -236,7 +236,7 @@ pull_up_subqueries(Query *parse, Node *jtnode, bool below_outer_join) parse->rowMarks = nconc(parse->rowMarks, subquery->rowMarks); /* - * We also have to fix the relid lists of any parent InClauseInfo + * We also have to fix the relid sets of any parent InClauseInfo * nodes. (This could perhaps be done by ResolveNew, but it * would clutter that routine's API unreasonably.) */ @@ -611,10 +611,10 @@ preprocess_jointree(Query *parse, Node *jtnode) } /* - * fix_in_clause_relids: update RT-index lists of InClauseInfo nodes + * fix_in_clause_relids: update RT-index sets of InClauseInfo nodes * * When we pull up a subquery, any InClauseInfo references to the subquery's - * RT index have to be replaced by the list of substituted relids. + * RT index have to be replaced by the set of substituted relids. * * We assume we may modify the InClauseInfo nodes in-place. */ @@ -627,26 +627,26 @@ fix_in_clause_relids(List *in_info_list, int varno, Relids subrelids) { InClauseInfo *ininfo = (InClauseInfo *) lfirst(l); - if (intMember(varno, ininfo->lefthand)) + if (bms_is_member(varno, ininfo->lefthand)) { - ininfo->lefthand = lremovei(varno, ininfo->lefthand); - ininfo->lefthand = nconc(ininfo->lefthand, listCopy(subrelids)); + ininfo->lefthand = bms_del_member(ininfo->lefthand, varno); + ininfo->lefthand = bms_add_members(ininfo->lefthand, subrelids); } - if (intMember(varno, ininfo->righthand)) + if (bms_is_member(varno, ininfo->righthand)) { - ininfo->righthand = lremovei(varno, ininfo->righthand); - ininfo->righthand = nconc(ininfo->righthand, listCopy(subrelids)); + ininfo->righthand = bms_del_member(ininfo->righthand, varno); + ininfo->righthand = bms_add_members(ininfo->righthand, subrelids); } } } /* - * get_relids_in_jointree: get list of base RT indexes present in a jointree + * get_relids_in_jointree: get set of base RT indexes present in a jointree */ -List * +Relids get_relids_in_jointree(Node *jtnode) { - Relids result = NIL; + Relids result = NULL; if (jtnode == NULL) return result; @@ -654,21 +654,17 @@ get_relids_in_jointree(Node *jtnode) { int varno = ((RangeTblRef *) jtnode)->rtindex; - result = makeListi1(varno); + result = bms_make_singleton(varno); } else if (IsA(jtnode, FromExpr)) { FromExpr *f = (FromExpr *) jtnode; List *l; - /* - * Note: we assume it's impossible to see same RT index from more - * than one subtree, so nconc() is OK rather than set_unioni(). - */ foreach(l, f->fromlist) { - result = nconc(result, - get_relids_in_jointree(lfirst(l))); + result = bms_join(result, + get_relids_in_jointree(lfirst(l))); } } else if (IsA(jtnode, JoinExpr)) @@ -677,7 +673,7 @@ get_relids_in_jointree(Node *jtnode) /* join's own RT index is not wanted in result */ result = get_relids_in_jointree(j->larg); - result = nconc(result, get_relids_in_jointree(j->rarg)); + result = bms_join(result, get_relids_in_jointree(j->rarg)); } else elog(ERROR, "get_relids_in_jointree: unexpected node type %d", @@ -686,12 +682,12 @@ get_relids_in_jointree(Node *jtnode) } /* - * get_relids_for_join: get list of base RT indexes making up a join + * get_relids_for_join: get set of base RT indexes making up a join * * NB: this will not work reliably after preprocess_jointree() is run, * since that may eliminate join nodes from the jointree. */ -List * +Relids get_relids_for_join(Query *parse, int joinrelid) { Node *jtnode; diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c index 97e4d56a9f4..2ee7ede1834 100644 --- a/src/backend/optimizer/prep/prepunion.c +++ b/src/backend/optimizer/prep/prepunion.c @@ -14,7 +14,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepunion.c,v 1.88 2003/01/20 18:54:54 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepunion.c,v 1.89 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -62,7 +62,7 @@ static List *generate_append_tlist(List *colTypes, bool flag, List *refnames_tlist); static Node *adjust_inherited_attrs_mutator(Node *node, adjust_inherited_attrs_context *context); -static List *adjust_rtindex_list(List *relids, Index oldrelid, Index newrelid); +static Relids adjust_relid_set(Relids relids, Index oldrelid, Index newrelid); static List *adjust_inherited_tlist(List *tlist, Oid new_relid); @@ -604,7 +604,7 @@ tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK) /* * find_all_inheritors - - * Returns an integer list of relids including the given rel plus + * Returns an integer list of relation OIDs including the given rel plus * all relations that inherit from it, directly or indirectly. */ List * @@ -662,6 +662,8 @@ find_all_inheritors(Oid parentrel) * its inh flag cleared, whether or not there were any children. This * ensures we won't expand the same RTE twice, which would otherwise occur * for the case of an inherited UPDATE/DELETE target relation. + * + * XXX probably should convert the result type to Relids? */ List * expand_inherted_rtentry(Query *parse, Index rti, bool dup_parent) @@ -840,13 +842,13 @@ adjust_inherited_attrs_mutator(Node *node, ininfo = (InClauseInfo *) expression_tree_mutator(node, adjust_inherited_attrs_mutator, (void *) context); - /* now fix InClauseInfo's rtindex lists */ - ininfo->lefthand = adjust_rtindex_list(ininfo->lefthand, - context->old_rt_index, - context->new_rt_index); - ininfo->righthand = adjust_rtindex_list(ininfo->righthand, - context->old_rt_index, - context->new_rt_index); + /* now fix InClauseInfo's relid sets */ + ininfo->lefthand = adjust_relid_set(ininfo->lefthand, + context->old_rt_index, + context->new_rt_index); + ininfo->righthand = adjust_relid_set(ininfo->righthand, + context->old_rt_index, + context->new_rt_index); return (Node *) ininfo; } @@ -873,14 +875,14 @@ adjust_inherited_attrs_mutator(Node *node, newinfo->subclauseindices = NIL; /* - * Adjust left/right relids lists too. + * Adjust left/right relid sets too. */ - newinfo->left_relids = adjust_rtindex_list(oldinfo->left_relids, - context->old_rt_index, - context->new_rt_index); - newinfo->right_relids = adjust_rtindex_list(oldinfo->right_relids, - context->old_rt_index, - context->new_rt_index); + newinfo->left_relids = adjust_relid_set(oldinfo->left_relids, + context->old_rt_index, + context->new_rt_index); + newinfo->right_relids = adjust_relid_set(oldinfo->right_relids, + context->old_rt_index, + context->new_rt_index); newinfo->eval_cost.startup = -1; /* reset these too */ newinfo->this_selec = -1; @@ -928,18 +930,18 @@ adjust_inherited_attrs_mutator(Node *node, } /* - * Substitute newrelid for oldrelid in a list of RT indexes + * Substitute newrelid for oldrelid in a Relid set */ -static List * -adjust_rtindex_list(List *relids, Index oldrelid, Index newrelid) +static Relids +adjust_relid_set(Relids relids, Index oldrelid, Index newrelid) { - if (intMember(oldrelid, relids)) + if (bms_is_member(oldrelid, relids)) { /* Ensure we have a modifiable copy */ - relids = listCopy(relids); + relids = bms_copy(relids); /* Remove old, add new */ - relids = lremovei(oldrelid, relids); - relids = lconsi(newrelid, relids); + relids = bms_del_member(relids, oldrelid); + relids = bms_add_member(relids, newrelid); } return relids; } diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c index a2449cb07af..bd5706b5e21 100644 --- a/src/backend/optimizer/util/clauses.c +++ b/src/backend/optimizer/util/clauses.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.127 2003/02/04 00:50:00 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.128 2003/02/08 20:20:55 tgl Exp $ * * HISTORY * AUTHOR DATE MAJOR EVENT @@ -885,7 +885,7 @@ has_distinct_on_clause(Query *query) * clause_get_relids_vars * Retrieves distinct relids and vars appearing within a clause. * - * '*relids' is set to an integer list of all distinct "varno"s appearing + * '*relids' is set to the set of all distinct "varno"s appearing * in Vars within the clause. * '*vars' is set to a list of all distinct Vars appearing within the clause. * Var nodes are considered distinct if they have different varno @@ -899,7 +899,7 @@ void clause_get_relids_vars(Node *clause, Relids *relids, List **vars) { List *clvars = pull_var_clause(clause, false); - List *varno_list = NIL; + Relids varnos = NULL; List *var_list = NIL; List *i; @@ -908,8 +908,7 @@ clause_get_relids_vars(Node *clause, Relids *relids, List **vars) Var *var = (Var *) lfirst(i); List *vi; - if (!intMember(var->varno, varno_list)) - varno_list = lconsi(var->varno, varno_list); + varnos = bms_add_member(varnos, var->varno); foreach(vi, var_list) { Var *in_list = (Var *) lfirst(vi); @@ -923,7 +922,7 @@ clause_get_relids_vars(Node *clause, Relids *relids, List **vars) } freeList(clvars); - *relids = varno_list; + *relids = varnos; *vars = var_list; } @@ -936,10 +935,10 @@ clause_get_relids_vars(Node *clause, Relids *relids, List **vars) int NumRelids(Node *clause) { - List *varno_list = pull_varnos(clause); - int result = length(varno_list); + Relids varnos = pull_varnos(clause); + int result = bms_num_members(varnos); - freeList(varno_list); + bms_free(varnos); return result; } diff --git a/src/backend/optimizer/util/joininfo.c b/src/backend/optimizer/util/joininfo.c index 79a9f7a3bac..599dcf44d9b 100644 --- a/src/backend/optimizer/util/joininfo.c +++ b/src/backend/optimizer/util/joininfo.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/joininfo.c,v 1.33 2003/01/24 03:58:43 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/joininfo.c,v 1.34 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -35,7 +35,7 @@ find_joininfo_node(RelOptInfo *this_rel, Relids join_relids) { JoinInfo *joininfo = (JoinInfo *) lfirst(i); - if (sameseti(join_relids, joininfo->unjoined_relids)) + if (bms_equal(join_relids, joininfo->unjoined_relids)) return joininfo; } return NULL; @@ -86,23 +86,20 @@ add_join_clause_to_rels(Query *root, RestrictInfo *restrictinfo, Relids join_relids) { - List *join_relid; + Relids tmprelids; + int cur_relid; /* For every relid, find the joininfo, and add the proper join entries */ - foreach(join_relid, join_relids) + tmprelids = bms_copy(join_relids); + while ((cur_relid = bms_first_member(tmprelids)) >= 0) { - int cur_relid = lfirsti(join_relid); - Relids unjoined_relids = NIL; + Relids unjoined_relids; JoinInfo *joininfo; - List *otherrel; /* Get the relids not equal to the current relid */ - foreach(otherrel, join_relids) - { - if (lfirsti(otherrel) != cur_relid) - unjoined_relids = lappendi(unjoined_relids, lfirsti(otherrel)); - } - Assert(unjoined_relids != NIL); + unjoined_relids = bms_copy(join_relids); + unjoined_relids = bms_del_member(unjoined_relids, cur_relid); + Assert(!bms_is_empty(unjoined_relids)); /* * Find or make the joininfo node for this combination of rels, @@ -113,11 +110,12 @@ add_join_clause_to_rels(Query *root, joininfo->jinfo_restrictinfo = lappend(joininfo->jinfo_restrictinfo, restrictinfo); /* - * Can't freeList(unjoined_relids) because new joininfo node may - * link to it. We could avoid leaking memory by doing listCopy() + * Can't bms_free(unjoined_relids) because new joininfo node may + * link to it. We could avoid leaking memory by doing bms_copy() * in make_joininfo_node, but for now speed seems better. */ } + bms_free(tmprelids); } /* @@ -136,23 +134,20 @@ remove_join_clause_from_rels(Query *root, RestrictInfo *restrictinfo, Relids join_relids) { - List *join_relid; + Relids tmprelids; + int cur_relid; /* For every relid, find the joininfo */ - foreach(join_relid, join_relids) + tmprelids = bms_copy(join_relids); + while ((cur_relid = bms_first_member(tmprelids)) >= 0) { - int cur_relid = lfirsti(join_relid); - Relids unjoined_relids = NIL; + Relids unjoined_relids; JoinInfo *joininfo; - List *otherrel; /* Get the relids not equal to the current relid */ - foreach(otherrel, join_relids) - { - if (lfirsti(otherrel) != cur_relid) - unjoined_relids = lappendi(unjoined_relids, lfirsti(otherrel)); - } - Assert(unjoined_relids != NIL); + unjoined_relids = bms_copy(join_relids); + unjoined_relids = bms_del_member(unjoined_relids, cur_relid); + Assert(!bms_is_empty(unjoined_relids)); /* * Find the joininfo node for this combination of rels; it should @@ -168,6 +163,7 @@ remove_join_clause_from_rels(Query *root, Assert(ptrMember(restrictinfo, joininfo->jinfo_restrictinfo)); joininfo->jinfo_restrictinfo = lremove(restrictinfo, joininfo->jinfo_restrictinfo); - freeList(unjoined_relids); + bms_free(unjoined_relids); } + bms_free(tmprelids); } diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index c11b928b861..8a59730aef5 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.86 2003/01/27 20:51:54 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.87 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -560,7 +560,7 @@ create_unique_path(Query *root, RelOptInfo *rel, Path *subpath) { InClauseInfo *ininfo = (InClauseInfo *) lfirst(l); - if (sameseti(ininfo->righthand, rel->relids)) + if (bms_equal(ininfo->righthand, rel->relids)) { sub_targetlist = ininfo->sub_targetlist; break; diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c index 3e0bbe69225..1f62a45648a 100644 --- a/src/backend/optimizer/util/plancat.c +++ b/src/backend/optimizer/util/plancat.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/plancat.c,v 1.77 2003/02/03 15:07:07 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/plancat.c,v 1.78 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -52,7 +52,7 @@ void get_relation_info(Oid relationObjectId, RelOptInfo *rel) { Relation relation; - Index varno = lfirsti(rel->relids); + Index varno = rel->relid; bool hasindex; List *varlist = NIL; List *indexinfos = NIL; @@ -175,7 +175,7 @@ get_relation_info(Oid relationObjectId, RelOptInfo *rel) } /* initialize cached join info to empty */ - info->outer_relids = NIL; + info->outer_relids = NULL; info->inner_paths = NIL; index_close(indexRelation); diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index ebfaa4924d4..5b875dfe155 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.46 2003/02/03 15:07:07 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.47 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -54,9 +54,7 @@ build_base_rel(Query *root, int relid) foreach(rels, root->base_rel_list) { rel = (RelOptInfo *) lfirst(rels); - - /* length(rel->relids) == 1 for all members of base_rel_list */ - if (lfirsti(rel->relids) == relid) + if (relid == rel->relid) elog(ERROR, "build_base_rel: rel already exists"); } @@ -64,8 +62,7 @@ build_base_rel(Query *root, int relid) foreach(rels, root->other_rel_list) { rel = (RelOptInfo *) lfirst(rels); - - if (lfirsti(rel->relids) == relid) + if (relid == rel->relid) elog(ERROR, "build_base_rel: rel already exists as 'other' rel"); } @@ -92,9 +89,7 @@ build_other_rel(Query *root, int relid) foreach(rels, root->other_rel_list) { rel = (RelOptInfo *) lfirst(rels); - - /* length(rel->relids) == 1 for all members of other_rel_list */ - if (lfirsti(rel->relids) == relid) + if (relid == rel->relid) return rel; } @@ -102,8 +97,7 @@ build_other_rel(Query *root, int relid) foreach(rels, root->base_rel_list) { rel = (RelOptInfo *) lfirst(rels); - - if (lfirsti(rel->relids) == relid) + if (relid == rel->relid) elog(ERROR, "build_other_rel: rel already exists as base rel"); } @@ -133,7 +127,7 @@ make_base_rel(Query *root, int relid) RangeTblEntry *rte = rt_fetch(relid, root->rtable); rel->reloptkind = RELOPT_BASEREL; - rel->relids = makeListi1(relid); + rel->relids = bms_make_singleton(relid); rel->rows = 0; rel->width = 0; rel->targetlist = NIL; @@ -142,6 +136,7 @@ make_base_rel(Query *root, int relid) rel->cheapest_total_path = NULL; rel->cheapest_unique_path = NULL; rel->pruneable = true; + rel->relid = relid; rel->rtekind = rte->rtekind; rel->varlist = NIL; rel->indexlist = NIL; @@ -151,9 +146,9 @@ make_base_rel(Query *root, int relid) rel->baserestrictinfo = NIL; rel->baserestrictcost.startup = 0; rel->baserestrictcost.per_tuple = 0; - rel->outerjoinset = NIL; + rel->outerjoinset = NULL; rel->joininfo = NIL; - rel->index_outer_relids = NIL; + rel->index_outer_relids = NULL; rel->index_inner_paths = NIL; /* Check type of rtable entry */ @@ -190,17 +185,14 @@ find_base_rel(Query *root, int relid) foreach(rels, root->base_rel_list) { rel = (RelOptInfo *) lfirst(rels); - - /* length(rel->relids) == 1 for all members of base_rel_list */ - if (lfirsti(rel->relids) == relid) + if (relid == rel->relid) return rel; } foreach(rels, root->other_rel_list) { rel = (RelOptInfo *) lfirst(rels); - - if (lfirsti(rel->relids) == relid) + if (relid == rel->relid) return rel; } @@ -211,7 +203,7 @@ find_base_rel(Query *root, int relid) /* * find_join_rel - * Returns relation entry corresponding to 'relids' (a list of RT indexes), + * Returns relation entry corresponding to 'relids' (a set of RT indexes), * or NULL if none exists. This is for join relations. * * Note: there is probably no good reason for this to be called from @@ -227,7 +219,7 @@ find_join_rel(Query *root, Relids relids) { RelOptInfo *rel = (RelOptInfo *) lfirst(joinrels); - if (sameseti(rel->relids, relids)) + if (bms_equal(rel->relids, relids)) return rel; } @@ -239,7 +231,7 @@ find_join_rel(Query *root, Relids relids) * Returns relation entry corresponding to the union of two given rels, * creating a new relation entry if none already exists. * - * 'joinrelids' is the Relids list that uniquely identifies the join + * 'joinrelids' is the Relids set that uniquely identifies the join * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be * joined * 'jointype': type of join (inner/outer) @@ -252,7 +244,7 @@ find_join_rel(Query *root, Relids relids) */ RelOptInfo * build_join_rel(Query *root, - List *joinrelids, + Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, JoinType jointype, @@ -288,7 +280,7 @@ build_join_rel(Query *root, */ joinrel = makeNode(RelOptInfo); joinrel->reloptkind = RELOPT_JOINREL; - joinrel->relids = listCopy(joinrelids); + joinrel->relids = bms_copy(joinrelids); joinrel->rows = 0; joinrel->width = 0; joinrel->targetlist = NIL; @@ -297,6 +289,7 @@ build_join_rel(Query *root, joinrel->cheapest_total_path = NULL; joinrel->cheapest_unique_path = NULL; joinrel->pruneable = true; + joinrel->relid = 0; /* indicates not a baserel */ joinrel->rtekind = RTE_JOIN; joinrel->varlist = NIL; joinrel->indexlist = NIL; @@ -306,9 +299,9 @@ build_join_rel(Query *root, joinrel->baserestrictinfo = NIL; joinrel->baserestrictcost.startup = 0; joinrel->baserestrictcost.per_tuple = 0; - joinrel->outerjoinset = NIL; + joinrel->outerjoinset = NULL; joinrel->joininfo = NIL; - joinrel->index_outer_relids = NIL; + joinrel->index_outer_relids = NULL; joinrel->index_inner_paths = NIL; /* @@ -494,7 +487,7 @@ subbuild_joinrel_restrictlist(RelOptInfo *joinrel, { JoinInfo *joininfo = (JoinInfo *) lfirst(xjoininfo); - if (is_subseti(joininfo->unjoined_relids, joinrel->relids)) + if (bms_is_subset(joininfo->unjoined_relids, joinrel->relids)) { /* * Clauses in this JoinInfo list become restriction clauses @@ -529,15 +522,16 @@ subbuild_joinrel_joinlist(RelOptInfo *joinrel, JoinInfo *joininfo = (JoinInfo *) lfirst(xjoininfo); Relids new_unjoined_relids; - new_unjoined_relids = set_differencei(joininfo->unjoined_relids, - joinrel->relids); - if (new_unjoined_relids == NIL) + new_unjoined_relids = bms_difference(joininfo->unjoined_relids, + joinrel->relids); + if (bms_is_empty(new_unjoined_relids)) { /* * Clauses in this JoinInfo list become restriction clauses * for the joinrel, since they refer to no outside rels. So we * can ignore them in this routine. */ + bms_free(new_unjoined_relids); } else { diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c index 4fad46889fd..929f5561dbc 100644 --- a/src/backend/optimizer/util/var.c +++ b/src/backend/optimizer/util/var.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/var.c,v 1.48 2003/02/06 22:21:11 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/var.c,v 1.49 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -24,7 +24,7 @@ typedef struct { - List *varlist; + Relids varnos; int sublevels_up; } pull_varnos_context; @@ -58,13 +58,12 @@ static bool pull_var_clause_walker(Node *node, pull_var_clause_context *context); static Node *flatten_join_alias_vars_mutator(Node *node, flatten_join_alias_vars_context *context); -static List *alias_rtindex_list(Query *root, List *rtlist); +static Relids alias_relid_set(Query *root, Relids relids); /* - * pull_varnos - * - * Create a list of all the distinct varnos present in a parsetree. + * pull_varnos + * Create a set of all the distinct varnos present in a parsetree. * Only varnos that reference level-zero rtable entries are considered. * * NOTE: this is used on not-yet-planned expressions. It may therefore find @@ -72,12 +71,12 @@ static List *alias_rtindex_list(Query *root, List *rtlist); * references to the desired rtable level! But when we find a completed * SubPlan, we only need to look at the parameters passed to the subplan. */ -List * +Relids pull_varnos(Node *node) { pull_varnos_context context; - context.varlist = NIL; + context.varnos = NULL; context.sublevels_up = 0; /* @@ -89,7 +88,7 @@ pull_varnos(Node *node) (void *) &context, 0); - return context.varlist; + return context.varnos; } static bool @@ -101,9 +100,8 @@ pull_varnos_walker(Node *node, pull_varnos_context *context) { Var *var = (Var *) node; - if (var->varlevelsup == context->sublevels_up && - !intMember(var->varno, context->varlist)) - context->varlist = lconsi(var->varno, context->varlist); + if (var->varlevelsup == context->sublevels_up) + context->varnos = bms_add_member(context->varnos, var->varno); return false; } if (IsA(node, Query)) @@ -430,13 +428,13 @@ flatten_join_alias_vars_mutator(Node *node, ininfo = (InClauseInfo *) expression_tree_mutator(node, flatten_join_alias_vars_mutator, (void *) context); - /* now fix InClauseInfo's rtindex lists */ + /* now fix InClauseInfo's relid sets */ if (context->sublevels_up == 0) { - ininfo->lefthand = alias_rtindex_list(context->root, - ininfo->lefthand); - ininfo->righthand = alias_rtindex_list(context->root, - ininfo->righthand); + ininfo->lefthand = alias_relid_set(context->root, + ininfo->lefthand); + ininfo->righthand = alias_relid_set(context->root, + ininfo->righthand); } return (Node *) ininfo; } @@ -462,25 +460,26 @@ flatten_join_alias_vars_mutator(Node *node, } /* - * alias_rtindex_list: in a list of RT indexes, replace joins by their + * alias_relid_set: in a set of RT indexes, replace joins by their * underlying base relids */ -static List * -alias_rtindex_list(Query *root, List *rtlist) +static Relids +alias_relid_set(Query *root, Relids relids) { - List *result = NIL; - List *l; + Relids result = NULL; + Relids tmprelids; + int rtindex; - foreach(l, rtlist) + tmprelids = bms_copy(relids); + while ((rtindex = bms_first_member(tmprelids)) >= 0) { - int rtindex = lfirsti(l); - RangeTblEntry *rte; + RangeTblEntry *rte = rt_fetch(rtindex, root->rtable); - rte = rt_fetch(rtindex, root->rtable); if (rte->rtekind == RTE_JOIN) - result = nconc(result, get_relids_for_join(root, rtindex)); + result = bms_join(result, get_relids_for_join(root, rtindex)); else - result = lappendi(result, rtindex); + result = bms_add_member(result, rtindex); } + bms_free(tmprelids); return result; } diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c index 5d729216751..93bde2ae472 100644 --- a/src/backend/parser/parse_clause.c +++ b/src/backend/parser/parse_clause.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/parser/parse_clause.c,v 1.103 2002/12/16 18:39:22 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/parser/parse_clause.c,v 1.104 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -301,8 +301,8 @@ transformJoinOnClause(ParseState *pstate, JoinExpr *j, { Node *result; List *save_namespace; - List *clause_varnos, - *l; + Relids clause_varnos; + int varno; /* * This is a tad tricky, for two reasons. First, the namespace that @@ -333,17 +333,15 @@ transformJoinOnClause(ParseState *pstate, JoinExpr *j, * here.) */ clause_varnos = pull_varnos(result); - foreach(l, clause_varnos) + while ((varno = bms_first_member(clause_varnos)) >= 0) { - int varno = lfirsti(l); - if (!intMember(varno, containedRels)) { elog(ERROR, "JOIN/ON clause refers to \"%s\", which is not part of JOIN", rt_fetch(varno, pstate->p_rtable)->eref->aliasname); } } - freeList(clause_varnos); + bms_free(clause_varnos); return result; } @@ -490,7 +488,7 @@ transformRangeFunction(ParseState *pstate, RangeFunction *r) * no local Var references in the transformed expression. (Outer * references are OK, and are ignored here.) */ - if (pull_varnos(funcexpr) != NIL) + if (!bms_is_empty(pull_varnos(funcexpr))) elog(ERROR, "FROM function expression may not refer to other relations of same query level"); /* diff --git a/src/backend/rewrite/rewriteManip.c b/src/backend/rewrite/rewriteManip.c index 44604289663..3943b9d2378 100644 --- a/src/backend/rewrite/rewriteManip.c +++ b/src/backend/rewrite/rewriteManip.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/rewrite/rewriteManip.c,v 1.70 2003/01/20 18:54:59 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/rewrite/rewriteManip.c,v 1.71 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -24,6 +24,8 @@ static bool checkExprHasAggs_walker(Node *node, void *context); static bool checkExprHasSubLink_walker(Node *node, void *context); +static Relids offset_relid_set(Relids relids, int offset); +static Relids adjust_relid_set(Relids relids, int oldrelid, int newrelid); /* @@ -143,16 +145,10 @@ OffsetVarNodes_walker(Node *node, OffsetVarNodes_context *context) if (context->sublevels_up == 0) { - List *rt; - - foreach(rt, ininfo->lefthand) - { - lfirsti(rt) += context->offset; - } - foreach(rt, ininfo->righthand) - { - lfirsti(rt) += context->offset; - } + ininfo->lefthand = offset_relid_set(ininfo->lefthand, + context->offset); + ininfo->righthand = offset_relid_set(ininfo->righthand, + context->offset); } /* fall through to examine children */ } @@ -210,6 +206,22 @@ OffsetVarNodes(Node *node, int offset, int sublevels_up) OffsetVarNodes_walker(node, &context); } +static Relids +offset_relid_set(Relids relids, int offset) +{ + Relids result = NULL; + Relids tmprelids; + int rtindex; + + tmprelids = bms_copy(relids); + while ((rtindex = bms_first_member(tmprelids)) >= 0) + { + result = bms_add_member(result, rtindex + offset); + } + bms_free(tmprelids); + return result; +} + /* * ChangeVarNodes - adjust Var nodes for a specific change of RT index * @@ -272,18 +284,12 @@ ChangeVarNodes_walker(Node *node, ChangeVarNodes_context *context) if (context->sublevels_up == 0) { - List *rt; - - foreach(rt, ininfo->lefthand) - { - if (lfirsti(rt) == context->rt_index) - lfirsti(rt) = context->new_index; - } - foreach(rt, ininfo->righthand) - { - if (lfirsti(rt) == context->rt_index) - lfirsti(rt) = context->new_index; - } + ininfo->lefthand = adjust_relid_set(ininfo->lefthand, + context->rt_index, + context->new_index); + ininfo->righthand = adjust_relid_set(ininfo->righthand, + context->rt_index, + context->new_index); } /* fall through to examine children */ } @@ -346,6 +352,23 @@ ChangeVarNodes(Node *node, int rt_index, int new_index, int sublevels_up) } /* + * Substitute newrelid for oldrelid in a Relid set + */ +static Relids +adjust_relid_set(Relids relids, int oldrelid, int newrelid) +{ + if (bms_is_member(oldrelid, relids)) + { + /* Ensure we have a modifiable copy */ + relids = bms_copy(relids); + /* Remove old, add new */ + relids = bms_del_member(relids, oldrelid); + relids = bms_add_member(relids, newrelid); + } + return relids; +} + +/* * IncrementVarSublevelsUp - adjust Var nodes when pushing them down in tree * * Find all Var nodes in the given tree having varlevelsup >= min_sublevels_up, @@ -468,8 +491,8 @@ rangeTableEntry_used_walker(Node *node, InClauseInfo *ininfo = (InClauseInfo *) node; if (context->sublevels_up == 0 && - (intMember(context->rt_index, ininfo->lefthand) || - intMember(context->rt_index, ininfo->righthand))) + (bms_is_member(context->rt_index, ininfo->lefthand) || + bms_is_member(context->rt_index, ininfo->righthand))) return true; /* fall through to examine children */ } diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index d099262c46f..5955252b087 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -15,7 +15,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/utils/adt/selfuncs.c,v 1.131 2003/01/28 22:13:35 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/utils/adt/selfuncs.c,v 1.132 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -3822,7 +3822,7 @@ genericcostestimate(Query *root, RelOptInfo *rel, /* Estimate the fraction of main-table tuples that will be visited */ *indexSelectivity = clauselist_selectivity(root, selectivityQuals, - lfirsti(rel->relids), + rel->relid, JOIN_INNER); /* @@ -3909,7 +3909,7 @@ btcostestimate(PG_FUNCTION_ARGS) Oid relid; HeapTuple tuple; - relid = getrelid(lfirsti(rel->relids), root->rtable); + relid = getrelid(rel->relid, root->rtable); Assert(relid != InvalidOid); tuple = SearchSysCache(STATRELATT, ObjectIdGetDatum(relid), diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h new file mode 100644 index 00000000000..4e06d7a284a --- /dev/null +++ b/src/include/nodes/bitmapset.h @@ -0,0 +1,80 @@ +/*------------------------------------------------------------------------- + * + * bitmapset.h + * PostgreSQL generic bitmap set package + * + * A bitmap set can represent any set of nonnegative integers, although + * it is mainly intended for sets where the maximum value is not large, + * say at most a few hundred. By convention, a NULL pointer is always + * accepted by all operations to represent the empty set. (But beware + * that this is not the only representation of the empty set. Use + * bms_is_empty() in preference to testing for NULL.) + * + * + * Copyright (c) 2003, PostgreSQL Global Development Group + * + * $Id: bitmapset.h,v 1.1 2003/02/08 20:20:55 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#ifndef BITMAPSET_H +#define BITMAPSET_H + +/* + * Data representation + */ + +/* The unit size can be adjusted by changing these three declarations: */ +#define BITS_PER_BITMAPWORD 32 +typedef uint32 bitmapword; /* must be an unsigned type */ +typedef int32 signedbitmapword; /* must be the matching signed type */ + +typedef struct Bitmapset { + int nwords; /* number of words in array */ + bitmapword words[1]; /* really [nwords] */ +} Bitmapset; /* VARIABLE LENGTH STRUCT */ + + +/* result of bms_membership */ +typedef enum +{ + BMS_EMPTY_SET, /* 0 members */ + BMS_SINGLETON, /* 1 member */ + BMS_MULTIPLE /* >1 member */ +} BMS_Membership; + + +/* + * function prototypes in nodes/bitmapset.c + */ + +extern Bitmapset *bms_copy(const Bitmapset *a); +extern bool bms_equal(const Bitmapset *a, const Bitmapset *b); +extern Bitmapset *bms_make_singleton(int x); +extern void bms_free(Bitmapset *a); + +extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b); +extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b); +extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b); +extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b); +extern bool bms_is_member(int x, const Bitmapset *a); +extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b); +extern int bms_singleton_member(const Bitmapset *a); +extern int bms_num_members(const Bitmapset *a); +/* optimized tests when we don't need to know exact membership count: */ +extern BMS_Membership bms_membership(const Bitmapset *a); +extern bool bms_is_empty(const Bitmapset *a); + +/* these routines recycle (modify or free) their non-const inputs: */ + +extern Bitmapset *bms_add_member(Bitmapset *a, int x); +extern Bitmapset *bms_del_member(Bitmapset *a, int x); +extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b); +extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b); +extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b); +extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b); + +/* support for iterating through the integer elements of a set: */ +extern int bms_first_member(Bitmapset *a); + +#endif /* BITMAPSET_H */ diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h index d629cd49e6c..b32dbf552a8 100644 --- a/src/include/nodes/pg_list.h +++ b/src/include/nodes/pg_list.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $Id: pg_list.h,v 1.33 2003/01/27 20:51:54 tgl Exp $ + * $Id: pg_list.h,v 1.34 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -114,7 +114,6 @@ typedef struct List */ extern int length(List *list); extern void *llast(List *list); -extern int llasti(List *list); extern List *nconc(List *list1, List *list2); extern List *lcons(void *datum, List *list); extern List *lconsi(int datum, List *list); @@ -136,20 +135,16 @@ extern void *nth(int n, List *l); extern int nthi(int n, List *l); extern void set_nth(List *l, int n, void *elem); -extern List *set_difference(List *list1, List *list2); -extern List *set_differencei(List *list1, List *list2); -extern List *set_ptrDifference(List *list1, List *list2); -extern List *lreverse(List *l); extern List *set_union(List *list1, List *list2); extern List *set_unioni(List *list1, List *list2); extern List *set_ptrUnion(List *list1, List *list2); +extern List *set_intersect(List *l1, List *l2); extern List *set_intersecti(List *list1, List *list2); +extern List *set_difference(List *list1, List *list2); +extern List *set_differencei(List *list1, List *list2); +extern List *set_ptrDifference(List *list1, List *list2); extern bool equali(List *list1, List *list2); -extern bool sameseti(List *list1, List *list2); -extern bool overlap_setsi(List *list1, List *list2); -#define nonoverlap_setsi(list1, list2) (!overlap_setsi(list1, list2)) -extern bool is_subseti(List *list1, List *list2); extern void freeList(List *list); diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index 807c70073de..03240d64153 100644 --- a/src/include/nodes/relation.h +++ b/src/include/nodes/relation.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $Id: relation.h,v 1.78 2003/02/03 15:07:08 tgl Exp $ + * $Id: relation.h,v 1.79 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -15,16 +15,16 @@ #define RELATION_H #include "access/sdir.h" +#include "nodes/bitmapset.h" #include "nodes/parsenodes.h" + /* * Relids - * List of relation identifiers (indexes into the rangetable). - * - * Note: these are lists of integers, not Nodes. + * Set of relation identifiers (indexes into the rangetable). */ -typedef List *Relids; +typedef Bitmapset *Relids; /* * When looking for a "cheapest path", this enum specifies whether we want @@ -83,7 +83,7 @@ typedef struct QualCost * Parts of this data structure are specific to various scan and join * mechanisms. It didn't seem worth creating new node types for them. * - * relids - List of base-relation identifiers; it is a base relation + * relids - Set of base-relation identifiers; it is a base relation * if there is just one, a join relation if more than one * rows - estimated number of tuples in the relation after restriction * clauses have been applied (ie, output rows of a plan for it) @@ -104,6 +104,8 @@ typedef struct QualCost * * If the relation is a base relation it will have these fields set: * + * relid - RTE index (this is redundant with the relids field, but + * is provided for convenience of access) * rtekind - distinguishes plain relation, subquery, or function RTE * varlist - list of Vars for physical columns (only if table) * indexlist - list of IndexOptInfo nodes for relation's indexes @@ -128,12 +130,12 @@ typedef struct QualCost * baserestrictcost - Estimated cost of evaluating the baserestrictinfo * clauses at a single tuple (only used for base rels) * outerjoinset - For a base rel: if the rel appears within the nullable - * side of an outer join, the list of all relids - * participating in the highest such outer join; else NIL. + * side of an outer join, the set of all relids + * participating in the highest such outer join; else NULL. * Otherwise, unused. * joininfo - List of JoinInfo nodes, containing info about each join * clause in which this relation participates - * index_outer_relids - only used for base rels; list of outer relids + * index_outer_relids - only used for base rels; set of outer relids * that participate in indexable joinclauses for this rel * index_inner_paths - only used for base rels; list of InnerIndexscanInfo * nodes showing best indexpaths for various subsets of @@ -174,8 +176,7 @@ typedef struct RelOptInfo RelOptKind reloptkind; /* all relations included in this RelOptInfo */ - Relids relids; /* integer list of base relids (rangetable - * indexes) */ + Relids relids; /* set of base relids (rangetable indexes) */ /* size estimates generated by planner */ double rows; /* estimated number of result tuples */ @@ -190,6 +191,7 @@ typedef struct RelOptInfo bool pruneable; /* information about a base rel (not set for join rels!) */ + Index relid; RTEKind rtekind; /* RELATION, SUBQUERY, or FUNCTION */ List *varlist; List *indexlist; @@ -201,7 +203,7 @@ typedef struct RelOptInfo List *baserestrictinfo; /* RestrictInfo structures (if * base rel) */ QualCost baserestrictcost; /* cost of evaluating the above */ - Relids outerjoinset; /* integer list of base relids */ + Relids outerjoinset; /* set of base relids */ List *joininfo; /* JoinInfo structures */ /* cached info about inner indexscan paths for relation: */ @@ -585,11 +587,11 @@ typedef struct RestrictInfo /* * If the clause looks useful for joining --- that is, it is a binary * opclause with nonoverlapping sets of relids referenced in the left - * and right sides --- then these two fields are set to lists of the - * referenced relids. Otherwise they are both NIL. + * and right sides --- then these two fields are set to sets of the + * referenced relids. Otherwise they are both NULL. */ - List *left_relids; /* relids in left side of join clause */ - List *right_relids; /* relids in right side of join clause */ + Relids left_relids; /* relids in left side of join clause */ + Relids right_relids; /* relids in right side of join clause */ /* valid if clause is mergejoinable, else InvalidOid: */ Oid mergejoinoperator; /* copy of clause operator */ @@ -683,8 +685,8 @@ typedef struct InnerIndexscanInfo typedef struct InClauseInfo { NodeTag type; - List *lefthand; /* base relids in lefthand expressions */ - List *righthand; /* base relids coming from the subselect */ + Relids lefthand; /* base relids in lefthand expressions */ + Relids righthand; /* base relids coming from the subselect */ List *sub_targetlist; /* targetlist of original RHS subquery */ /* * Note: sub_targetlist is just a list of Vars or expressions; diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index 759b18c2499..e842a699b17 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $Id: pathnode.h,v 1.48 2003/01/20 18:55:05 tgl Exp $ + * $Id: pathnode.h,v 1.49 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -16,6 +16,7 @@ #include "nodes/relation.h" + /* * prototypes for pathnode.c */ @@ -77,10 +78,10 @@ extern void build_base_rel(Query *root, int relid); extern RelOptInfo *build_other_rel(Query *root, int relid); extern RelOptInfo *find_base_rel(Query *root, int relid); extern RelOptInfo *build_join_rel(Query *root, - List *joinrelids, - RelOptInfo *outer_rel, - RelOptInfo *inner_rel, - JoinType jointype, - List **restrictlist_ptr); + Relids joinrelids, + RelOptInfo *outer_rel, + RelOptInfo *inner_rel, + JoinType jointype, + List **restrictlist_ptr); #endif /* PATHNODE_H */ diff --git a/src/include/optimizer/prep.h b/src/include/optimizer/prep.h index 458539a8174..103e4630cfa 100644 --- a/src/include/optimizer/prep.h +++ b/src/include/optimizer/prep.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $Id: prep.h,v 1.35 2003/01/25 23:10:30 tgl Exp $ + * $Id: prep.h,v 1.36 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -16,6 +16,8 @@ #include "nodes/parsenodes.h" #include "nodes/plannodes.h" +#include "nodes/relation.h" + /* * prototypes for prepjointree.c @@ -27,8 +29,8 @@ extern Node *pull_up_IN_clauses(Query *parse, Node *node); extern Node *pull_up_subqueries(Query *parse, Node *jtnode, bool below_outer_join); extern Node *preprocess_jointree(Query *parse, Node *jtnode); -extern List *get_relids_in_jointree(Node *jtnode); -extern List *get_relids_for_join(Query *parse, int joinrelid); +extern Relids get_relids_in_jointree(Node *jtnode); +extern Relids get_relids_for_join(Query *parse, int joinrelid); /* * prototypes for prepqual.c diff --git a/src/include/optimizer/var.h b/src/include/optimizer/var.h index b207acac593..3c84020ef92 100644 --- a/src/include/optimizer/var.h +++ b/src/include/optimizer/var.h @@ -7,17 +7,17 @@ * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $Id: var.h,v 1.25 2003/01/20 18:55:06 tgl Exp $ + * $Id: var.h,v 1.26 2003/02/08 20:20:55 tgl Exp $ * *------------------------------------------------------------------------- */ #ifndef VAR_H #define VAR_H -#include "nodes/parsenodes.h" +#include "nodes/relation.h" -extern List *pull_varnos(Node *node); +extern Relids pull_varnos(Node *node); extern bool contain_var_reference(Node *node, int varno, int varattno, int levelsup); extern bool contain_whole_tuple_var(Node *node, int varno, int levelsup); |