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.

4 files changed, 43 insertions, 2 deletions

diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index 36198b8edd..18457e0ad9 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -2459,3 +2459,27 @@ RESET enable_seqscan;
 RESET enable_indexscan;
 RESET enable_bitmapscan;
 DROP TABLE onek_with_null;
+--
+-- Check behavior with duplicate index column contents
+--
+CREATE TABLE dupindexcols AS
+  SELECT unique1 as id, stringu2::text as f1 FROM tenk1;
+CREATE INDEX dupindexcols_i ON dupindexcols (f1, id, f1 text_pattern_ops);
+VACUUM ANALYZE dupindexcols;
+EXPLAIN (COSTS OFF)
+  SELECT count(*) FROM dupindexcols
+    WHERE f1 > 'LX' and id < 1000 and f1 ~<~ 'YX';
+                                   QUERY PLAN                                    
+---------------------------------------------------------------------------------
+ Aggregate
+   ->  Index Only Scan using dupindexcols_i on dupindexcols
+         Index Cond: ((f1 > 'LX'::text) AND (id < 1000) AND (f1 ~<~ 'YX'::text))
+(3 rows)
+
+SELECT count(*) FROM dupindexcols
+  WHERE f1 > 'LX' and id < 1000 and f1 ~<~ 'YX';
+ count 
+-------
+   500
+(1 row)
+
diff --git a/src/test/regress/expected/sanity_check.out b/src/test/regress/expected/sanity_check.out
index 9cae9d8bf1..05ac11cfb0 100644
--- a/src/test/regress/expected/sanity_check.out
+++ b/src/test/regress/expected/sanity_check.out
@@ -39,6 +39,7 @@ SELECT relname, relhasindex
  default_tbl             | f
  defaultexpr_tbl         | f
  dept                    | f
+ dupindexcols            | t
  e_star                  | f
  emp                     | f
  equipment_r             | f
@@ -164,7 +165,7 @@ SELECT relname, relhasindex
  timetz_tbl              | f
  tinterval_tbl           | f
  varchar_tbl             | f
-(153 rows)
+(154 rows)
 
 --
 -- another sanity check: every system catalog that has OIDs should have
diff --git a/src/test/regress/output/misc.source b/src/test/regress/output/misc.source
index b57c5546de..03aa10df08 100644
--- a/src/test/regress/output/misc.source
+++ b/src/test/regress/output/misc.source
@@ -610,6 +610,7 @@ SELECT user_relns() AS user_relns
  default_tbl
  defaultexpr_tbl
  dept
+ dupindexcols
  e_star
  emp
  equipment_r
@@ -685,7 +686,7 @@ SELECT user_relns() AS user_relns
  toyemp
  varchar_tbl
  xacttest
-(107 rows)
+(108 rows)
 
 SELECT name(equipment(hobby_construct(text 'skywalking', text 'mer')));
  name 
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index babde51d2c..8c60cb6145 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -804,3 +804,18 @@ RESET enable_indexscan;
 RESET enable_bitmapscan;
 
 DROP TABLE onek_with_null;
+
+--
+-- Check behavior with duplicate index column contents
+--
+
+CREATE TABLE dupindexcols AS
+  SELECT unique1 as id, stringu2::text as f1 FROM tenk1;
+CREATE INDEX dupindexcols_i ON dupindexcols (f1, id, f1 text_pattern_ops);
+VACUUM ANALYZE dupindexcols;
+
+EXPLAIN (COSTS OFF)
+  SELECT count(*) FROM dupindexcols
+    WHERE f1 > 'LX' and id < 1000 and f1 ~<~ 'YX';
+SELECT count(*) FROM dupindexcols
+  WHERE f1 > 'LX' and id < 1000 and f1 ~<~ 'YX';