Design notes for EquivalenceClasses

Attached is some material from an updated src/backend/optimizer/README
that describes the optimization principles that the EquivalenceClass
rewrite is depending on. Can anyone see any holes in the logic?

I'm particularly interested in the discussion of allowing
EquivalenceClasses to be deduced from clauses below an outer join.
This is something our current code doesn't do at all, which is bad
because what had been a well-optimized view might fall apart the
moment you left-join to it. I just today decided that I understood
how to do that, and haven't finished revising the patch to support it.
So if anyone sees a reason it won't work, please speak up ...

regards, tom lane

EquivalenceClasses
------------------

During the deconstruct_jointree() scan of the query's qual clauses, we look
for mergejoinable equality clauses A = B whose applicability is not delayed
by an outer join; these are called "equivalence clauses". When we find
one, we create an EquivalenceClass containing the expressions A and B to
record this knowledge. If we later find another equivalence clause B = C,
we add C to the existing EquivalenceClass for {A B}; this may require
merging two existing EquivalenceClasses. At the end of the scan, we have
sets of values that are known all transitively equal to each other. We can
therefore use a comparison of any pair of the values as a restriction or
join clause (when these values are available at the scan or join, of
course); furthermore, we need test only one such comparison, not all of
them. Therefore, equivalence clauses are removed from the standard qual
distribution process. Instead, when preparing a restriction or join clause
list, we examine each EquivalenceClass to see if it can contribute a
clause, and if so we select an appropriate pair of values to compare. For
example, if we are trying to join A's relation to C's, we can generate the
clause A = C, even though this appeared nowhere explicitly in the original
query. This may allow us to explore join paths that otherwise would have
been rejected as requiring Cartesian-product joins.

Sometimes an EquivalenceClass may contain a pseudo-constant expression
(i.e., one not containing Vars or Aggs of the current query level, nor
volatile functions). In this case we do not follow the policy of
dynamically generating join clauses: instead, we dynamically generate
restriction clauses "var = const" wherever one of the variable members of
the class can first be computed. For example, if we have A = B and B = 42,
we effectively generate the restriction clauses A = 42 and B = 42, and then
we need not bother with explicitly testing the join clause A = B when the
relations are joined. In effect, all the class members can be tested at
relation-scan level and there's never a need for join tests.

The precise technical interpretation of an EquivalenceClass is that it
asserts that at any plan node where more than one of its member values
can be computed, output rows in which the values are not all equal may
be discarded without affecting the query result. (We require all levels
of the plan to enforce EquivalenceClasses, hence a node need not recheck
equality of values that were computable by one of its children.) For an
ordinary EquivalenceClass that is "valid everywhere", we can further infer
that the values are all non-null, because all mergejoinable operators are
strict. However, we also allow equivalence clauses that appear below the
nullable side of an outer join to form EquivalenceClasses; for these
classes, the interpretation is that either all the values are equal, or
all (except pseudo-constants) have gone to null. (This requires a
limitation that non-constant members be strict, else they might not go
to null when the other members do.) Consider for example

SELECT *
FROM a LEFT JOIN
(SELECT * FROM b JOIN c ON b.y = c.z WHERE b.y = 10) ss
ON a.x = ss.y
WHERE a.x = 42;

We can form the below-outer-join EquivalenceClass {b.y c.z 10} and thereby
apply c.z = 10 while scanning c. (The reason we disallow outerjoin-delayed
clauses from forming EquivalenceClasses is exactly that we want to be able
to push any derived clauses as far down as possible.) But once above the
outer join it's no longer necessarily the case that b.y = 10, and thus we
cannot use such EquivalenceClasses to conclude that sorting is unnecessary
(see discussion of PathKeys below). In this example, notice also that
a.x = ss.y (really a.x = b.y) is not an equivalence clause because its
applicability to b is restricted by the outer join; thus we do not make
the mistake of concluding b.y = 42, even though we do have an equivalence
class for {a.x 42}.

To aid in determining the sort ordering(s) that can work with a mergejoin,
we mark each mergejoinable clause with the EquivalenceClasses of its left
and right inputs. For an equivalence clause, these are of course the same
EquivalenceClass. For a non-equivalence mergejoinable clause (such as an
outer-join qualification), we generate two separate EquivalenceClasses for
the left and right inputs. This may result in creating single-item
equivalence "classes", though of course these are still subject to merging
if other equivalence clauses are later found to bear on the same
expressions.

Another way that we may form a single-item EquivalenceClass is in creation
of a PathKey to represent a desired sort order (see below). This is a bit
different from the above cases because such an EquivalenceClass might
contain an aggregate function or volatile expression. (A clause containing
a volatile function will never be considered mergejoinable, even if its top
operator is mergejoinable, so there is no way for a volatile expression to
get into EquivalenceClasses otherwise. Aggregates are disallowed in WHERE
altogether, so will never be found in a mergejoinable clause.) This is just
a convenience to maintain a uniform PathKey representation: such an
EquivalenceClass will never be merged with any other.

An EquivalenceClass also contains a list of btree opfamily OIDs, which
determines what the equalities it represents actually "mean". All the
equivalence clauses that contribute to an EquivalenceClass must have
equality operators that belong to the same set of opfamilies. (Note: most
of the time, a particular equality operator belongs to only one family, but
it's possible that it belongs to more than one. We keep track of all the
families to ensure that we can make use of an index belonging to any one of
the families for mergejoin purposes.)

PathKeys
--------

The PathKeys data structure represents what is known about the sort order
of the tuples generated by a particular Path. A path's pathkeys field is a
list of PathKey nodes, where the n'th item represents the n'th sort key of
the result. Each PathKey contains these fields:

* a reference to an EquivalenceClass
* a btree opfamily OID (must match one of those in the EC)
* a sort direction (ascending or descending)
* a nulls-first-or-last flag

The EquivalenceClass represents the value being sorted on. Since the
various members of an EquivalenceClass are known equal according to the
opfamily, we can consider a path sorted by any one of them to be sorted by
any other too; this is what justifies referencing the whole
EquivalenceClass rather than just one member of it.

In single/base relation RelOptInfo's, the Paths represent various ways
of scanning the relation and the resulting ordering of the tuples.
Sequential scan Paths have NIL pathkeys, indicating no known ordering.
Index scans have Path.pathkeys that represent the chosen index's ordering,
if any. A single-key index would create a single-PathKey list, while a
multi-column index generates a list with one element per index column.
(Actually, since an index can be scanned either forward or backward, there
are two possible sort orders and two possible PathKey lists it can
generate.)

Note that a bitmap scan or multi-pass indexscan (OR clause scan) has NIL
pathkeys since we can say nothing about the overall order of its result.
Also, an indexscan on an unordered type of index generates NIL pathkeys.
However, we can always create a pathkey by doing an explicit sort. The
pathkeys for a Sort plan's output just represent the sort key fields and
the ordering operators used.

Things get more interesting when we consider joins. Suppose we do a
mergejoin between A and B using the mergeclause A.X = B.Y. The output
of the mergejoin is sorted by X --- but it is also sorted by Y. Again,
this can be represented by a PathKey referencing an EquivalenceClass
containing both X and Y.

With a little further thought, it becomes apparent that nestloop joins
can also produce sorted output. For example, if we do a nestloop join
between outer relation A and inner relation B, then any pathkeys relevant
to A are still valid for the join result: we have not altered the order of
the tuples from A. Even more interesting, if there was an equivalence clause
A.X=B.Y, and A.X was a pathkey for the outer relation A, then we can assert
that B.Y is a pathkey for the join result; X was ordered before and still
is, and the joined values of Y are equal to the joined values of X, so Y
must now be ordered too. This is true even though we used neither an
explicit sort nor a mergejoin on Y. (Note: hash joins cannot be counted
on to preserve the order of their outer relation, because the executor
might decide to "batch" the join, so we always set pathkeys to NIL for
a hashjoin path.) Exception: a RIGHT or FULL join doesn't preserve the
ordering of its outer relation, because it might insert nulls at random
points in the ordering.

In general, we can justify using EquivalenceClasses as the basis for
pathkeys because, whenever we scan a relation containing multiple
EquivalenceClass members or join two relations each containing
EquivalenceClass members, we apply restriction or join clauses derived from
the EquivalenceClass. This guarantees that any two values listed in the
EquivalenceClass are in fact equal in all tuples emitted by the scan or
join, and therefore that if the tuples are sorted by one of the values,
they can be considered sorted by any other as well. It does not matter
whether the test clause is used as a mergeclause, or merely enforced
after-the-fact as a qpqual filter.

Note that there is no particular difficulty in labeling a path's sort
order with a PathKey referencing an EquivalenceClass that contains
variables not yet joined into the path's output. We can simply ignore
such entries as not being relevant (yet). This makes it possible to
use the same EquivalenceClasses throughout the join planning process.
In fact, by being careful not to generate multiple identical PathKey
objects, we can reduce comparison of EquivalenceClasses and PathKeys
to simple pointer comparison, which is a huge savings because add_path
has to make a large number of PathKey comparisons in deciding whether
competing Paths are equivalently sorted.

Pathkeys are also useful to represent an ordering that we wish to achieve,
since they are easily compared to the pathkeys of a potential candidate
path. So, SortClause lists are turned into pathkeys lists for use inside
the optimizer.

Because we have to generate pathkeys lists from the sort clauses before
we've finished EquivalenceClass merging, we cannot use the pointer-equality
method of comparing PathKeys in the earliest stages of the planning
process. Instead, we generate "non canonical" PathKeys that reference
single-element EquivalenceClasses that might get merged later. After we
complete EquivalenceClass merging, we replace these with "canonical"
PathKeys that reference only fully-merged classes, and after that we make
sure we don't generate more than one copy of each "canonical" PathKey.
Then it is safe to use pointer comparison on canonical PathKeys.

An additional refinement we can make is to insist that canonical pathkey
lists (sort orderings) do not mention the same pathkey more than once.
For example, a pathkey list (A B A) is redundant --- the second
occurrence of A does not change the ordering, since the data must already
be sorted by A. Although a user probably wouldn't write ORDER BY A,B,A
directly, such redundancies are more probable once equivalence classes
have been considered. Also, the system is likely to generate redundant
pathkey lists when computing the sort ordering needed for a mergejoin. By
eliminating the redundancy, we save time and improve planning, since the
planner will more easily recognize equivalent orderings as being equivalent.

Another interesting property is that if the underlying EquivalenceClass
contains a constant, then the pathkey is completely redundant and need not
be sorted by at all! Every value of the other members must be equal to the
constant, or (if above an outer join that has nulled them all) they may all
be null; in either case there is no need to sort. (The assumption that all
the non-const members go to null at the same plan level is critical here,
else they might not represent the same sort order.)