Planning a change of representation in the planner

Currently, the planner spends a good deal of time pushing around lists
of small integers, because it uses such lists to identify join
relations.  For example, given SELECT ... FROM a, b, c WHERE ...
the list (1,2) (or equivalently (2,1)) would represent the join of
a and b.

This representation is pretty clearly a hangover from the days when the
Postgres planner was written in Lisp :-(.  It's inefficient --- common
operations like union, intersection, and is-subset tests require O(N^2)
steps.  And it's error-prone: I just had my nose rubbed once again in
the nasty things that happen if you accidentally get some duplicate
entries in a relation ID list.  (It's nasty because some but not all of
the low-level list-as-set operations depend on the assumption that the
elements of a given list are distinct.)

I'm thinking of replacing this representation by a
variable-length-bitmap representation.  Basically it would be like
struct bitmapset {    int nwords;        /* number of words in array */    int array[1];      /* really [nwords] */};

Each array element would hold 32 bits; the integer i is a member of
the set iff (array[i/32] >> (i%32)) & 1 == 1.  For sets containing no
elements over 31 (which would account for the vast majority of queries)
only a single word would be needed in the array.  Operations like set
union, intersection, and subset test could process 32 bits at a time ---
they'd reduce to trivial C operations like |=, &=, & ~, applied once per
word.  There would be a few things that would be slower (like iterating
through the actual integer elements of a set) but AFAICT this
representation is much better suited to the planner's needs than the
list method.

I've been thinking of doing this for a while just on efficiency grounds,
but kept putting it off because I don't expect much of any performance
gain on simple queries.  (You need a dozen or so tables in a query
before the inefficiencies of the list representation really start to
hurt.)  But tonight I'm thinking I'll do it anyway, because it'll also
be impervious to duplicate-element bugs.

Comments?
        regards, tom lane