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 ---------------------------(end of broadcast)--------------------------- TIP 2: Don't 'kill -9' the postmaster