Improve planner's handling of duplicated index column expressions.

It's potentially useful for an index to repeat the same indexable column
or expression in multiple index columns, if the columns have different
opclasses.  (If they share opclasses too, the duplicate column is pretty
useless, but nonetheless we've allowed such cases since 9.0.)  However,
the planner failed to cope with this, because createplan.c was relying on
simple equal() matching to figure out which index column each index qual
is intended for.  We do have that information available upstream in
indxpath.c, though, so the fix is to not flatten the multi-level indexquals
list when putting it into an IndexPath.  Then we can rely on the sublist
structure to identify target index columns in createplan.c.  There's a
similar issue for index ORDER BYs (the KNNGIST feature), so introduce a
multi-level-list representation for that too.  This adds a bit more
representational overhead, but we might more or less buy that back by not
having to search for matching index columns anymore in createplan.c;
likewise btcostestimate saves some cycles.

Per bug #6351 from Christian Rudolph.  Likely symptoms include the "btree
index keys must be ordered by attribute" failure shown there, as well as
"operator MMMM is not a member of opfamily NNNN".

Although this is a pre-existing problem that can be demonstrated in 9.0 and
9.1, I'm not going to back-patch it, because the API changes in the planner
seem likely to break things such as index plugins.  The corner cases where
this matters seem too narrow to justify possibly breaking things in a minor
release.

2 files changed, 25 insertions, 12 deletions

diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 74c060b9b66..b137142f3ea 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -659,18 +659,25 @@ typedef struct Path
  * AND semantics across the list.  Each clause is a RestrictInfo node from
  * the query's WHERE or JOIN conditions.
  *
- * 'indexquals' has the same structure as 'indexclauses', but it contains
- * the actual indexqual conditions that can be used with the index.
- * In simple cases this is identical to 'indexclauses', but when special
- * indexable operators appear in 'indexclauses', they are replaced by the
- * derived indexscannable conditions in 'indexquals'.
- *
- * 'indexorderbys', if not NIL, is a list of ORDER BY expressions that have
- * been found to be usable as ordering operators for an amcanorderbyop index.
- * Note that these are not RestrictInfos, just bare expressions, since they
- * generally won't yield booleans.  The list will match the path's pathkeys.
- * Also, unlike the case for quals, it's guaranteed that each expression has
- * the index key on the left side of the operator.
+ * 'indexquals' is a list of sub-lists of the actual index qual conditions
+ * that can be used with the index.  There is one possibly-empty sub-list
+ * for each index column (but empty sub-lists for trailing columns can be
+ * omitted).  The qual conditions are RestrictInfos, and in simple cases
+ * are the same RestrictInfos that appear in the flat indexclauses list.
+ * But when special indexable operators appear in 'indexclauses', they are
+ * replaced by their derived indexscannable conditions in 'indexquals'.
+ * Note that an entirely empty indexquals list denotes a full-index scan.
+ *
+ * 'indexorderbys', if not NIL, is a list of lists of lists of ORDER BY
+ * expressions that have been found to be usable as ordering operators for an
+ * amcanorderbyop index.  These are not RestrictInfos, just bare expressions,
+ * since they generally won't yield booleans.  Also, unlike the case for
+ * quals, it's guaranteed that each expression has the index key on the left
+ * side of the operator.  The top list has one entry per pathkey in the
+ * path's pathkeys, and the sub-lists have one sub-sublist per index column.
+ * This representation is a bit of overkill, since there will be only one
+ * actual expression per pathkey, but it's convenient because each sub-list
+ * has the same structure as the indexquals list.
  *
  * 'isjoininner' is TRUE if the path is a nestloop inner scan (that is,
  * some of the index conditions are join rather than restriction clauses).
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index c62f4a8122a..b0075d78654 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -61,6 +61,12 @@ extern List *expand_indexqual_conditions(IndexOptInfo *index,
 							List *clausegroups);
 extern void check_partial_indexes(PlannerInfo *root, RelOptInfo *rel);
 extern List *flatten_clausegroups_list(List *clausegroups);
+extern List *flatten_indexorderbys_list(List *indexorderbys);
+extern Expr *adjust_rowcompare_for_index(RowCompareExpr *clause,
+							IndexOptInfo *index,
+							int indexcol,
+							List **indexcolnos,
+							bool *var_on_left_p);
 
 /*
  * orindxpath.c