Some notes about redesigning planner data structures

I've been looking at improving the planner so that it can handle things
like backwards-order mergejoins, and I'm starting to realize that the
old assumption that mergejoinable operators had only one associated sort
ordering is wired into even more places than I thought. In particular,
the PathKeys data structure (see src/backend/optimizer/README if you
don't know about it) seems to need revisions. As it stands we'd have to
generate a lot of redundant PathKeys.

What I'm toying with doing is splitting PathKeys into two layers of data
structure. The lower layer would take over the function of representing
that we know a bunch of variables have been equated to each other, and
the upper layer would handle the task of representing a specific sort
order. This would be implemented as two new node types:

EquivalenceClass: contains a btree opfamily OID and a list of
expressions. This asserts that all the expressions have been equated by
mergejoinable operators in that opfamily, so we can transitively
conclude that they are all equal (according to that opfamily's notion of
equality). We might wish to make the list include not just the raw
expressions but additional data (eg their relation memberships), to
ease searching the list.

PathKey: contains a pointer to an EquivalenceClass, a sort direction
(BTLessStrategyNumber or BTGreaterStrategyNumber), and a nulls-first flag.
This represents a single-column sort ordering. We continue to represent
the total ordering of a Path as a list of PathKeys.

A possible objection to this is that it ties the planner's handling of
sort ordering even more tightly to btree, but actually I think that's
not a big problem. We could handle opfamilies belonging to multiple
orderable index types as long as they all use btree's strategy numbers.
In any case, with no new orderable index types on the horizon, I'm not
all that worried about this.

During any one planner run, we will keep all the EquivalenceClasses and
PathKeys that have been created in lists dangling from PlannerInfo, and
be careful not to make duplicate PathKey objects. This allows us to
keep using simple pointer equality to compare PathKeys. This means that
we have to finish merging EquivalenceClasses before we can make any
PathKeys, but I think that will be OK.

The RestrictInfo for a mergejoinable opclause will no longer store
PathKeys for its left and right sides, but rather EquivalenceClass
references. (In the simple case the left and right EquivalenceClasses
would be the same class, but if we couldn't consider the opclause an
equijoin, they'd be different classes, possibly with only one member.
This is really the same thing that happens now with PathKeys.)

One issue is that the same operator could possibly be equality in more
than one opfamily. We could generate separate EquivalenceClasses for
each such opfamily and store lists of pointers in the RestrictInfos, but
that seems a bit messy. An alternative is to allow a list of opfamily
OIDs in an EquivalenceClass, but then there comes the question of what
to do if some equality operators contributing to the EC are members of
more opfamilies than others. Can we legitimately conclude that any such
omissions are oversights and assume the entries should have been there?
If so, we could take the union of the observed opfamily lists as the
opfamily list for the EquivalenceClass. If not, we could just not
combine EquivalenceClasses for operators that have different opfamily
membership sets, but that would lose some amount of useful knowledge.

An idea that seems really attractive if we do this is to get rid of the
explicit generate_implied_equalities step, in favor of dynamically
generating an appropriate join condition whenever a join between two
relations having elements in an EquivalenceClass is made. The
RestrictInfos for the original clauses giving rise to the EC wouldn't
get put into join condition lists directly, only indirectly through this
process. This'd eliminate the need for detecting and removing redundant
clauses as we currently do it, since only one of the possible join
conditions associated with a particular EquivalenceClass would be
generated and inserted into a join condition list.

One of the things I don't like about generate_implied_equalities is that
it has to fail if there's no cross-type equality operator for a
particular datatype combination. Currently we tell people they'd better
make sure that mergejoinable operators come in complete cross-type sets,
but that's not real attractive. This approach can improve the
situation: rather than failing if we can't generate *all* the equality
combinations implied by a particular equivalence set, we need only fail
if we can't generate *any* of the valid combinations for a particular
join. What's more, "failure" need no longer mean elog(ERROR), it just
means we reject that particular join path as invalid. (We can be sure
we will still be able to find some solution to the join problem, since
at least the join path directly implied by the original clauses will
work.)

Thoughts?

regards, tom lane