Postgres picks suboptimal index after building of an extended statistics

From 8a4ad08d61a5d14a45ef5e182f002e918f0eaccc Mon Sep 17 00:00:00 2001
From: Andrey Lepikhov <a.lepikhov@postgrespro.ru>
Date: Wed, 23 Jun 2021 12:05:24 +0500
Subject: [PATCH] In the case of an unique one row btree index scan only one
 row can be returned. In the genericcostestimate() routine we must arrange the
 index selectivity value in accordance with this knowledge.

---
 src/backend/utils/adt/selfuncs.c | 78 ++++++++++++++++++++------------
 1 file changed, 48 insertions(+), 30 deletions(-)

diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 0c8c05f6c2..9538c4a5b4 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6369,15 +6369,9 @@ genericcostestimate(PlannerInfo *root,
 	double		num_scans;
 	double		qual_op_cost;
 	double		qual_arg_cost;
-	List	   *selectivityQuals;
 	ListCell   *l;
 
-	/*
-	 * If the index is partial, AND the index predicate with the explicitly
-	 * given indexquals to produce a more accurate idea of the index
-	 * selectivity.
-	 */
-	selectivityQuals = add_predicate_to_index_quals(index, indexQuals);
+	numIndexTuples = costs->numIndexTuples;
 
 	/*
 	 * Check for ScalarArrayOpExpr index quals, and estimate the number of
@@ -6398,36 +6392,59 @@ genericcostestimate(PlannerInfo *root,
 		}
 	}
 
-	/* Estimate the fraction of main-table tuples that will be visited */
-	indexSelectivity = clauselist_selectivity(root, selectivityQuals,
-											  index->rel->relid,
-											  JOIN_INNER,
-											  NULL);
+	if (numIndexTuples >= 0.0)
+	{
+		List		*selectivityQuals;
 
-	/*
-	 * If caller didn't give us an estimate, estimate the number of index
-	 * tuples that will be visited.  We do it in this rather peculiar-looking
-	 * way in order to get the right answer for partial indexes.
-	 */
-	numIndexTuples = costs->numIndexTuples;
-	if (numIndexTuples <= 0.0)
+		/*
+		 * If the index is partial, AND the index predicate with the explicitly
+		 * given indexquals to produce a more accurate idea of the index
+		 * selectivity.
+		 */
+		selectivityQuals = add_predicate_to_index_quals(index, indexQuals);
+
+		/* Estimate the fraction of main-table tuples that will be visited */
+		indexSelectivity = clauselist_selectivity(root, selectivityQuals,
+												  index->rel->relid,
+												  JOIN_INNER,
+												  NULL);
+
+		/*
+		 * If caller didn't give us an estimate, estimate the number of index
+		 * tuples that will be visited.  We do it in this rather peculiar-looking
+		 * way in order to get the right answer for partial indexes.
+		 */
+		if (numIndexTuples == 0.0)
+		{
+			numIndexTuples = indexSelectivity * index->rel->tuples;
+
+			/*
+			 * The above calculation counts all the tuples visited across all
+			 * scans induced by ScalarArrayOpExpr nodes.  We want to consider the
+			 * average per-indexscan number, so adjust.  This is a handy place to
+			 * round to integer, too.  (If caller supplied tuple estimate, it's
+			 * responsible for handling these considerations.)
+			 */
+			numIndexTuples = rint(numIndexTuples / num_sa_scans);
+		}
+	}
+	else
 	{
-		numIndexTuples = indexSelectivity * index->rel->tuples;
+		Assert(numIndexTuples == -1.0);
 
 		/*
-		 * The above calculation counts all the tuples visited across all
-		 * scans induced by ScalarArrayOpExpr nodes.  We want to consider the
-		 * average per-indexscan number, so adjust.  This is a handy place to
-		 * round to integer, too.  (If caller supplied tuple estimate, it's
-		 * responsible for handling these considerations.)
+		 * Unique one row scan can select no more than one row. It needs to
+		 * manually set the selectivity of the index. The value of numIndexTuples
+		 * will be corrected later.
 		 */
-		numIndexTuples = rint(numIndexTuples / num_sa_scans);
+		indexSelectivity = 1.0 / index->rel->tuples;
 	}
 
 	/*
 	 * We can bound the number of tuples by the index size in any case. Also,
 	 * always estimate at least one tuple is touched, even when
 	 * indexSelectivity estimate is tiny.
+	 * Also, one row single scan case need to fix the numIndexTuples value here.
 	 */
 	if (numIndexTuples > index->tuples)
 		numIndexTuples = index->tuples;
@@ -6710,16 +6727,17 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 
 	/*
 	 * If index is unique and we found an '=' clause for each column, we can
-	 * just assume numIndexTuples = 1 and skip the expensive
-	 * clauselist_selectivity calculations.  However, a ScalarArrayOp or
-	 * NullTest invalidates that theory, even though it sets eqQualHere.
+	 * skip the expensive clauselist_selectivity calculations and assume
+	 * numIndexTuples = -1.0 in order to tell the generic cost estimator to skip
+	 * such expensive calculations too. However, a ScalarArrayOp or NullTest
+	 * invalidates that theory, even though it sets eqQualHere.
 	 */
 	if (index->unique &&
 		indexcol == index->nkeycolumns - 1 &&
 		eqQualHere &&
 		!found_saop &&
 		!found_is_null_op)
-		numIndexTuples = 1.0;
+		numIndexTuples = -1.0;
 	else
 	{
 		List	   *selectivityQuals;
-- 
2.25.1

From 41ce6007cd552afd1a73983f0b9c9cac0e125d58 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <a.lepikhov@postgrespro.ru>
Date: Mon, 30 Aug 2021 11:21:57 +0500
Subject: [PATCH] Estimating number of fetched rows in a btree index we save
 selectivity estimation in the costs structure. It will be used by the
 genericcostestimate routine as a top bound for estimation of total tuples,
 visited in the main table.

This code fix the problem with unique index, when we know for sure
that no more than one tuple can be fetched, but clauselist_selectivity
gives us much less accurate estimation because of many possible reasons.
A regression test is added as a demonstration of the problem.
---
 src/backend/utils/adt/selfuncs.c        | 18 ++++++++++--
 src/test/regress/expected/stats_ext.out | 38 +++++++++++++++++++++++++
 src/test/regress/sql/stats_ext.sql      | 34 ++++++++++++++++++++++
 3 files changed, 88 insertions(+), 2 deletions(-)

diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index c2aeb4b947..dd1cadad61 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6074,6 +6074,14 @@ genericcostestimate(PlannerInfo *root,
 		 */
 		numIndexTuples = rint(numIndexTuples / num_sa_scans);
 	}
+	else if (costs->indexSelectivity > 0. &&
+		indexSelectivity > costs->indexSelectivity)
+		/*
+		 * If caller give us an estimation of amount of fetched index tuples,
+		 * it could give the selectivity estimation. In this case amount of
+		 * returned tuples can't be more than amount of fetched tuples.
+		 */
+		indexSelectivity = costs->indexSelectivity;
 
 	/*
 	 * We can bound the number of tuples by the index size in any case. Also,
@@ -6258,6 +6266,7 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 	bool		found_is_null_op;
 	double		num_sa_scans;
 	ListCell   *lc;
+	Selectivity btreeSelectivity;
 
 	/*
 	 * For a btree scan, only leading '=' quals plus inequality quals for the
@@ -6362,19 +6371,23 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 	/*
 	 * If index is unique and we found an '=' clause for each column, we can
 	 * just assume numIndexTuples = 1 and skip the expensive
-	 * clauselist_selectivity calculations.  However, a ScalarArrayOp or
+	 * clauselist_selectivity calculations. However, a ScalarArrayOp or
 	 * NullTest invalidates that theory, even though it sets eqQualHere.
+	 * Value of btreeSelectivity is used as a top bound for selectivity
+	 * estimation of returned tuples in the genericcostestimate routine.
 	 */
 	if (index->unique &&
 		indexcol == index->nkeycolumns - 1 &&
 		eqQualHere &&
 		!found_saop &&
 		!found_is_null_op)
+	{
 		numIndexTuples = 1.0;
+		btreeSelectivity = 1. / index->rel->tuples;
+	}
 	else
 	{
 		List	   *selectivityQuals;
-		Selectivity btreeSelectivity;
 
 		/*
 		 * If the index is partial, AND the index predicate with the
@@ -6402,6 +6415,7 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 	 */
 	MemSet(&costs, 0, sizeof(costs));
 	costs.numIndexTuples = numIndexTuples;
+	costs.indexSelectivity = btreeSelectivity;
 
 	genericcostestimate(root, path, loop_count, &costs);
 
diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out
index 7524e65142..b90463821f 100644
--- a/src/test/regress/expected/stats_ext.out
+++ b/src/test/regress/expected/stats_ext.out
@@ -1602,3 +1602,41 @@ NOTICE:  drop cascades to 2 other objects
 DETAIL:  drop cascades to table tststats.priv_test_tbl
 drop cascades to view tststats.priv_test_view
 DROP USER regress_stats_user1;
+-- Reproduction of the problem with picking of suboptimal index.
+SET enable_bitmapscan = 'off';
+-- Table with specific distribution of values
+CREATE TABLE tbl42 AS (
+	SELECT
+		gs % 10 AS x,
+		(gs % 10 + (gs/10::int4) % 10) % 10 AS y,
+		(gs / 100)::int4 AS z
+	FROM generate_series(1,1000) AS gs
+);
+INSERT INTO tbl42 (
+	SELECT gs,gs,gs FROM generate_series(1000,2000) AS gs
+);
+CREATE UNIQUE INDEX good ON tbl42 (x,y,z);
+CREATE INDEX bad ON tbl42(x);
+ANALYZE tbl42;
+-- Optimizer picks optimal, a primary key unique index
+EXPLAIN (COSTS OFF)
+SELECT * FROM tbl42 WHERE x=1 AND y=1 AND z=1;
+                   QUERY PLAN                    
+-------------------------------------------------
+ Index Only Scan using good on tbl42
+   Index Cond: ((x = 1) AND (y = 1) AND (z = 1))
+(2 rows)
+
+CREATE STATISTICS aestat(dependencies,ndistinct) ON x,y,z FROM tbl42;
+ANALYZE tbl42;
+-- Optimizer picks suboptimal index
+EXPLAIN (COSTS OFF)
+SELECT * FROM tbl42 WHERE x=1 AND y=1 AND z=1;
+                   QUERY PLAN                    
+-------------------------------------------------
+ Index Only Scan using good on tbl42
+   Index Cond: ((x = 1) AND (y = 1) AND (z = 1))
+(2 rows)
+
+-- Clean up
+DROP TABLE tbl42 CASCADE;
diff --git a/src/test/regress/sql/stats_ext.sql b/src/test/regress/sql/stats_ext.sql
index 906503bd0b..f274f53996 100644
--- a/src/test/regress/sql/stats_ext.sql
+++ b/src/test/regress/sql/stats_ext.sql
@@ -877,3 +877,37 @@ DROP FUNCTION op_leak(int, int);
 RESET SESSION AUTHORIZATION;
 DROP SCHEMA tststats CASCADE;
 DROP USER regress_stats_user1;
+
+
+-- Reproduction of the problem with picking of suboptimal index.
+SET enable_bitmapscan = 'off';
+
+-- Table with specific distribution of values
+CREATE TABLE tbl42 AS (
+	SELECT
+		gs % 10 AS x,
+		(gs % 10 + (gs/10::int4) % 10) % 10 AS y,
+		(gs / 100)::int4 AS z
+	FROM generate_series(1,1000) AS gs
+);
+INSERT INTO tbl42 (
+	SELECT gs,gs,gs FROM generate_series(1000,2000) AS gs
+);
+
+CREATE UNIQUE INDEX good ON tbl42 (x,y,z);
+CREATE INDEX bad ON tbl42(x);
+ANALYZE tbl42;
+
+-- Optimizer picks optimal, a primary key unique index
+EXPLAIN (COSTS OFF)
+SELECT * FROM tbl42 WHERE x=1 AND y=1 AND z=1;
+
+CREATE STATISTICS aestat(dependencies,ndistinct) ON x,y,z FROM tbl42;
+ANALYZE tbl42;
+
+-- Optimizer picks suboptimal index
+EXPLAIN (COSTS OFF)
+SELECT * FROM tbl42 WHERE x=1 AND y=1 AND z=1;
+
+-- Clean up
+DROP TABLE tbl42 CASCADE;
-- 
2.33.0

From 463c085852be921199b7a6d0987378d55145e41c Mon Sep 17 00:00:00 2001
From: Andrey Lepikhov <a.lepikhov@postgrespro.ru>
Date: Mon, 11 Jul 2022 12:25:43 +0500
Subject: [PATCH] Use Index path with the best selectivity estimation

---
 src/backend/optimizer/util/pathnode.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 483c4f4137..a8d7f22343 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -207,6 +207,20 @@ compare_path_costs_fuzzily(Path *path1, Path *path2, double fuzz_factor)
 		/* ... but path2 fuzzily worse on startup, so path1 wins */
 		return COSTS_BETTER1;
 	}
+	if (IsA(path1, IndexPath) && IsA(path2, IndexPath))
+	{
+		/*
+		 * Couldn't differ value of the paths. Last chance - if these paths
+		 * are index paths - use the path with the lower selectivity value.
+		 */
+		if (((IndexPath *) path1)->indexselectivity <
+			((IndexPath *) path2)->indexselectivity)
+			return COSTS_BETTER1;
+
+		if (((IndexPath *) path1)->indexselectivity >
+			((IndexPath *) path2)->indexselectivity)
+			return COSTS_BETTER2;
+	}
 	/* fuzzily the same on both costs */
 	return COSTS_EQUAL;
 
-- 
2.34.1

From 21677861e101eed22c829e0b14290a56786a12c2 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <a.lepikhov@postgrespro.ru>
Date: Wed, 22 Nov 2023 12:01:39 +0700
Subject: [PATCH] Use an index path with the best selectivity estimation

---
 src/backend/optimizer/util/pathnode.c         | 40 +++++++++++++++++
 .../expected/drop-index-concurrently-1.out    | 16 ++++---
 src/test/regress/expected/functional_deps.out | 43 +++++++++++++++++++
 src/test/regress/expected/join.out            | 40 +++++++++--------
 src/test/regress/sql/functional_deps.sql      | 36 ++++++++++++++++
 5 files changed, 149 insertions(+), 26 deletions(-)

diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 0b1d17b9d3..32aca83d67 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -454,6 +454,46 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 		costcmp = compare_path_costs_fuzzily(new_path, old_path,
 											 STD_FUZZ_FACTOR);
 
+		/*
+		 * Apply some heuristics on index paths.
+		 */
+		if (IsA(new_path, IndexPath) && IsA(old_path, IndexPath))
+		{
+			IndexPath *inp = (IndexPath *) new_path;
+			IndexPath *iop = (IndexPath *) old_path;
+
+			if (new_path->rows <= 1.0 && old_path->rows <= 1.0)
+			{
+				if (inp->indexinfo->unique && !iop->indexinfo->unique)
+					/*
+					 * When both paths are predicted to produce only one tuple,
+					 * the optimiser should prefer choosing a unique index scan
+					 * in all cases.
+					 */
+					costcmp = COSTS_BETTER1;
+				else if (costcmp != COSTS_DIFFERENT)
+					/*
+					 * If the optimiser doesn't have an obviously stable choice
+					 * of unique index, increase the chance of avoiding mistakes
+					 * by choosing an index with smaller selectivity.
+					 * This option makes decision more conservative and looks
+					 * debatable.
+					 */
+					costcmp = (inp->indexselectivity < iop->indexselectivity) ?
+												COSTS_BETTER1 : COSTS_BETTER2;
+			}
+			else if (costcmp == COSTS_EQUAL)
+				/*
+				 * The optimizer can't differ the value of two index paths.
+				 * To avoid making a decision that is based on only an index
+				 * order in the list, use some rational strategy based on
+				 * selectivity: prefer touching fewer tuples on the disk to
+				 * filtering them after.
+				 */
+				costcmp = (inp->indexselectivity < iop->indexselectivity) ?
+												COSTS_BETTER1 : COSTS_BETTER2;
+		}
+
 		/*
 		 * If the two paths compare differently for startup and total cost,
 		 * then we want to keep both, and we can skip comparing pathkeys and
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out b/src/test/isolation/expected/drop-index-concurrently-1.out
index 1cb2250891..2392cdb033 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -12,13 +12,15 @@ step preps: PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDE
 step begin: BEGIN;
 step disableseq: SET enable_seqscan = false;
 step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan;
-QUERY PLAN                                    
-----------------------------------------------
-Sort                                          
-  Sort Key: id                                
-  ->  Index Scan using test_dc_data on test_dc
-        Index Cond: (data = 34)               
-(4 rows)
+QUERY PLAN                                   
+---------------------------------------------
+Sort                                         
+  Sort Key: id                               
+  ->  Bitmap Heap Scan on test_dc            
+        Recheck Cond: (data = 34)            
+        ->  Bitmap Index Scan on test_dc_data
+              Index Cond: (data = 34)        
+(6 rows)
 
 step enableseq: SET enable_seqscan = true;
 step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan;
diff --git a/src/test/regress/expected/functional_deps.out b/src/test/regress/expected/functional_deps.out
index 32381b8ae7..61af99a041 100644
--- a/src/test/regress/expected/functional_deps.out
+++ b/src/test/regress/expected/functional_deps.out
@@ -230,3 +230,46 @@ EXECUTE foo;
 ALTER TABLE articles DROP CONSTRAINT articles_pkey RESTRICT;
 EXECUTE foo;  -- fail
 ERROR:  column "articles.keywords" must appear in the GROUP BY clause or be used in an aggregate function
+/*
+ * Corner cases of PostgreSQL optimizer:
+ *
+ * Correlations between columns aren't found by DBMS.
+ * Selectivities multiplication of many columns increases total selectivity
+ * error. If such non-true selectivity is so small, that rows estimation
+ * give us absolute minimum (1) then the optimizer can't choose between different
+ * indexes and uses first from the index list (last created).
+ */
+\set scale 100000
+CREATE TABLE t AS (
+    SELECT  c1 AS c1, -- selectivity(c1)*selectivity(c2)*nrows <= 1
+            c1 AS c2,
+			-- Create two columns with different selectivity.
+            (c1 % 2) AS c3, -- missing from a good index.
+            (c1 % 4) AS c4 -- missing from a bad index.
+    FROM generate_series(1,:scale) AS c1
+);
+UPDATE t SET c1=1,c2=1,c3=1,c4=2 WHERE c1<:scale/1000;
+CREATE INDEX bad ON t (c1,c2,c3);
+CREATE INDEX good ON t (c1,c2,c4);
+ANALYZE t; -- update stat on the indexes.
+EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1;
+                     QUERY PLAN                     
+----------------------------------------------------
+ Index Scan using good on t
+   Index Cond: ((c1 = 1) AND (c2 = 1) AND (c4 = 1))
+   Filter: (c3 = 1)
+(3 rows)
+
+-- Set the bad index to the first position in the index list.
+DROP INDEX bad;
+CREATE INDEX bad ON t (c1,c2,c3);
+ANALYZE t;
+EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1;
+                     QUERY PLAN                     
+----------------------------------------------------
+ Index Scan using good on t
+   Index Cond: ((c1 = 1) AND (c2 = 1) AND (c4 = 1))
+   Filter: (c3 = 1)
+(3 rows)
+
+DROP TABLE t CASCADE;
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 2c73270143..32b33fabd3 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -8629,14 +8629,15 @@ analyze j2;
 explain (costs off) select * from j1
 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2
 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1;
-               QUERY PLAN                
------------------------------------------
+                       QUERY PLAN                        
+---------------------------------------------------------
  Merge Join
-   Merge Cond: (j1.id1 = j2.id1)
-   Join Filter: (j2.id2 = j1.id2)
-   ->  Index Scan using j1_id1_idx on j1
-   ->  Index Scan using j2_id1_idx on j2
-(5 rows)
+   Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2))
+   ->  Index Only Scan using j1_pkey on j1
+         Filter: ((id1 % 1000) = 1)
+   ->  Index Only Scan using j2_pkey on j2
+         Filter: ((id1 % 1000) = 1)
+(6 rows)
 
 select * from j1
 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2
@@ -8651,15 +8652,16 @@ where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1;
 explain (costs off) select * from j1
 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2
 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 = any (array[1]);
-                     QUERY PLAN                     
-----------------------------------------------------
+                       QUERY PLAN                        
+---------------------------------------------------------
  Merge Join
-   Merge Cond: (j1.id1 = j2.id1)
-   Join Filter: (j2.id2 = j1.id2)
-   ->  Index Scan using j1_id1_idx on j1
-   ->  Index Scan using j2_id1_idx on j2
+   Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2))
+   ->  Index Only Scan using j1_pkey on j1
+         Filter: ((id1 % 1000) = 1)
+   ->  Index Only Scan using j2_pkey on j2
          Index Cond: (id1 = ANY ('{1}'::integer[]))
-(6 rows)
+         Filter: ((id1 % 1000) = 1)
+(7 rows)
 
 select * from j1
 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2
@@ -8674,12 +8676,12 @@ where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 = any (array[1]);
 explain (costs off) select * from j1
 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2
 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 >= any (array[1,5]);
-                      QUERY PLAN                       
--------------------------------------------------------
+                       QUERY PLAN                        
+---------------------------------------------------------
  Merge Join
-   Merge Cond: (j1.id1 = j2.id1)
-   Join Filter: (j2.id2 = j1.id2)
-   ->  Index Scan using j1_id1_idx on j1
+   Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2))
+   ->  Index Only Scan using j1_pkey on j1
+         Filter: ((id1 % 1000) = 1)
    ->  Index Only Scan using j2_pkey on j2
          Index Cond: (id1 >= ANY ('{1,5}'::integer[]))
          Filter: ((id1 % 1000) = 1)
diff --git a/src/test/regress/sql/functional_deps.sql b/src/test/regress/sql/functional_deps.sql
index 406490b995..f617ee9269 100644
--- a/src/test/regress/sql/functional_deps.sql
+++ b/src/test/regress/sql/functional_deps.sql
@@ -208,3 +208,39 @@ EXECUTE foo;
 ALTER TABLE articles DROP CONSTRAINT articles_pkey RESTRICT;
 
 EXECUTE foo;  -- fail
+
+/*
+ * Corner cases of PostgreSQL optimizer:
+ *
+ * Correlations between columns aren't found by DBMS.
+ * Selectivities multiplication of many columns increases total selectivity
+ * error. If such non-true selectivity is so small, that rows estimation
+ * give us absolute minimum (1) then the optimizer can't choose between different
+ * indexes and uses first from the index list (last created).
+ */
+\set scale 100000
+
+CREATE TABLE t AS (
+    SELECT  c1 AS c1, -- selectivity(c1)*selectivity(c2)*nrows <= 1
+            c1 AS c2,
+			-- Create two columns with different selectivity.
+            (c1 % 2) AS c3, -- missing from a good index.
+            (c1 % 4) AS c4 -- missing from a bad index.
+    FROM generate_series(1,:scale) AS c1
+);
+UPDATE t SET c1=1,c2=1,c3=1,c4=2 WHERE c1<:scale/1000;
+
+CREATE INDEX bad ON t (c1,c2,c3);
+CREATE INDEX good ON t (c1,c2,c4);
+ANALYZE t; -- update stat on the indexes.
+
+EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1;
+
+-- Set the bad index to the first position in the index list.
+DROP INDEX bad;
+CREATE INDEX bad ON t (c1,c2,c3);
+ANALYZE t;
+
+EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1;
+
+DROP TABLE t CASCADE;
-- 
2.43.0

From 604899b6afe70eccbbdbf69ce254f37808c598db Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <a.lepikhov@postgrespro.ru>
Date: Mon, 27 Nov 2023 11:23:48 +0700
Subject: [PATCH] Choose an index path with the best selectivity estimation.

In the case when optimizer predicts only one row prefer choosing UNIQUE indexes
In other cases, if optimizer treats indexes as equal, make a last attempt
selecting the index with less selectivity - this decision takes away dependency
on the order of indexes in an index list (good for reproduction of some issues)
and proposes one more objective argument to choose specific index.
---
 src/backend/optimizer/util/pathnode.c         | 42 ++++++++++++++++++
 .../expected/drop-index-concurrently-1.out    | 16 ++++---
 src/test/regress/expected/functional_deps.out | 43 +++++++++++++++++++
 src/test/regress/expected/join.out            | 40 +++++++++--------
 src/test/regress/sql/functional_deps.sql      | 36 ++++++++++++++++
 5 files changed, 151 insertions(+), 26 deletions(-)

diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 0b1d17b9d3..4b5aedd579 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -454,6 +454,48 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 		costcmp = compare_path_costs_fuzzily(new_path, old_path,
 											 STD_FUZZ_FACTOR);
 
+		/*
+		 * Apply some heuristics on index paths.
+		 */
+		if (IsA(new_path, IndexPath) && IsA(old_path, IndexPath))
+		{
+			IndexPath *inp = (IndexPath *) new_path;
+			IndexPath *iop = (IndexPath *) old_path;
+
+			if (new_path->rows <= 1.0 && old_path->rows <= 1.0)
+			{
+				/*
+				 * When both paths are predicted to produce only one tuple,
+				 * the optimiser should prefer choosing a unique index scan
+				 * in all cases.
+				 */
+				if (inp->indexinfo->unique && !iop->indexinfo->unique)
+					costcmp = COSTS_BETTER1;
+				else if (!inp->indexinfo->unique && iop->indexinfo->unique)
+					costcmp = COSTS_BETTER2;
+				else if (costcmp != COSTS_DIFFERENT)
+					/*
+					 * If the optimiser doesn't have an obviously stable choice
+					 * of unique index, increase the chance of avoiding mistakes
+					 * by choosing an index with smaller selectivity.
+					 * This option makes decision more conservative and looks
+					 * debatable.
+					 */
+					costcmp = (inp->indexselectivity < iop->indexselectivity) ?
+												COSTS_BETTER1 : COSTS_BETTER2;
+			}
+			else if (costcmp == COSTS_EQUAL)
+				/*
+				 * The optimizer can't differ the value of two index paths.
+				 * To avoid making a decision that is based on only an index
+				 * order in the list, use some rational strategy based on
+				 * selectivity: prefer touching fewer tuples on the disk to
+				 * filtering them after.
+				 */
+				costcmp = (inp->indexselectivity < iop->indexselectivity) ?
+												COSTS_BETTER1 : COSTS_BETTER2;
+		}
+
 		/*
 		 * If the two paths compare differently for startup and total cost,
 		 * then we want to keep both, and we can skip comparing pathkeys and
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out b/src/test/isolation/expected/drop-index-concurrently-1.out
index 1cb2250891..2392cdb033 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -12,13 +12,15 @@ step preps: PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDE
 step begin: BEGIN;
 step disableseq: SET enable_seqscan = false;
 step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan;
-QUERY PLAN                                    
-----------------------------------------------
-Sort                                          
-  Sort Key: id                                
-  ->  Index Scan using test_dc_data on test_dc
-        Index Cond: (data = 34)               
-(4 rows)
+QUERY PLAN                                   
+---------------------------------------------
+Sort                                         
+  Sort Key: id                               
+  ->  Bitmap Heap Scan on test_dc            
+        Recheck Cond: (data = 34)            
+        ->  Bitmap Index Scan on test_dc_data
+              Index Cond: (data = 34)        
+(6 rows)
 
 step enableseq: SET enable_seqscan = true;
 step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan;
diff --git a/src/test/regress/expected/functional_deps.out b/src/test/regress/expected/functional_deps.out
index 32381b8ae7..61af99a041 100644
--- a/src/test/regress/expected/functional_deps.out
+++ b/src/test/regress/expected/functional_deps.out
@@ -230,3 +230,46 @@ EXECUTE foo;
 ALTER TABLE articles DROP CONSTRAINT articles_pkey RESTRICT;
 EXECUTE foo;  -- fail
 ERROR:  column "articles.keywords" must appear in the GROUP BY clause or be used in an aggregate function
+/*
+ * Corner cases of PostgreSQL optimizer:
+ *
+ * Correlations between columns aren't found by DBMS.
+ * Selectivities multiplication of many columns increases total selectivity
+ * error. If such non-true selectivity is so small, that rows estimation
+ * give us absolute minimum (1) then the optimizer can't choose between different
+ * indexes and uses first from the index list (last created).
+ */
+\set scale 100000
+CREATE TABLE t AS (
+    SELECT  c1 AS c1, -- selectivity(c1)*selectivity(c2)*nrows <= 1
+            c1 AS c2,
+			-- Create two columns with different selectivity.
+            (c1 % 2) AS c3, -- missing from a good index.
+            (c1 % 4) AS c4 -- missing from a bad index.
+    FROM generate_series(1,:scale) AS c1
+);
+UPDATE t SET c1=1,c2=1,c3=1,c4=2 WHERE c1<:scale/1000;
+CREATE INDEX bad ON t (c1,c2,c3);
+CREATE INDEX good ON t (c1,c2,c4);
+ANALYZE t; -- update stat on the indexes.
+EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1;
+                     QUERY PLAN                     
+----------------------------------------------------
+ Index Scan using good on t
+   Index Cond: ((c1 = 1) AND (c2 = 1) AND (c4 = 1))
+   Filter: (c3 = 1)
+(3 rows)
+
+-- Set the bad index to the first position in the index list.
+DROP INDEX bad;
+CREATE INDEX bad ON t (c1,c2,c3);
+ANALYZE t;
+EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1;
+                     QUERY PLAN                     
+----------------------------------------------------
+ Index Scan using good on t
+   Index Cond: ((c1 = 1) AND (c2 = 1) AND (c4 = 1))
+   Filter: (c3 = 1)
+(3 rows)
+
+DROP TABLE t CASCADE;
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 2c73270143..32b33fabd3 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -8629,14 +8629,15 @@ analyze j2;
 explain (costs off) select * from j1
 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2
 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1;
-               QUERY PLAN                
------------------------------------------
+                       QUERY PLAN                        
+---------------------------------------------------------
  Merge Join
-   Merge Cond: (j1.id1 = j2.id1)
-   Join Filter: (j2.id2 = j1.id2)
-   ->  Index Scan using j1_id1_idx on j1
-   ->  Index Scan using j2_id1_idx on j2
-(5 rows)
+   Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2))
+   ->  Index Only Scan using j1_pkey on j1
+         Filter: ((id1 % 1000) = 1)
+   ->  Index Only Scan using j2_pkey on j2
+         Filter: ((id1 % 1000) = 1)
+(6 rows)
 
 select * from j1
 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2
@@ -8651,15 +8652,16 @@ where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1;
 explain (costs off) select * from j1
 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2
 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 = any (array[1]);
-                     QUERY PLAN                     
-----------------------------------------------------
+                       QUERY PLAN                        
+---------------------------------------------------------
  Merge Join
-   Merge Cond: (j1.id1 = j2.id1)
-   Join Filter: (j2.id2 = j1.id2)
-   ->  Index Scan using j1_id1_idx on j1
-   ->  Index Scan using j2_id1_idx on j2
+   Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2))
+   ->  Index Only Scan using j1_pkey on j1
+         Filter: ((id1 % 1000) = 1)
+   ->  Index Only Scan using j2_pkey on j2
          Index Cond: (id1 = ANY ('{1}'::integer[]))
-(6 rows)
+         Filter: ((id1 % 1000) = 1)
+(7 rows)
 
 select * from j1
 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2
@@ -8674,12 +8676,12 @@ where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 = any (array[1]);
 explain (costs off) select * from j1
 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2
 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 >= any (array[1,5]);
-                      QUERY PLAN                       
--------------------------------------------------------
+                       QUERY PLAN                        
+---------------------------------------------------------
  Merge Join
-   Merge Cond: (j1.id1 = j2.id1)
-   Join Filter: (j2.id2 = j1.id2)
-   ->  Index Scan using j1_id1_idx on j1
+   Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2))
+   ->  Index Only Scan using j1_pkey on j1
+         Filter: ((id1 % 1000) = 1)
    ->  Index Only Scan using j2_pkey on j2
          Index Cond: (id1 >= ANY ('{1,5}'::integer[]))
          Filter: ((id1 % 1000) = 1)
diff --git a/src/test/regress/sql/functional_deps.sql b/src/test/regress/sql/functional_deps.sql
index 406490b995..f617ee9269 100644
--- a/src/test/regress/sql/functional_deps.sql
+++ b/src/test/regress/sql/functional_deps.sql
@@ -208,3 +208,39 @@ EXECUTE foo;
 ALTER TABLE articles DROP CONSTRAINT articles_pkey RESTRICT;
 
 EXECUTE foo;  -- fail
+
+/*
+ * Corner cases of PostgreSQL optimizer:
+ *
+ * Correlations between columns aren't found by DBMS.
+ * Selectivities multiplication of many columns increases total selectivity
+ * error. If such non-true selectivity is so small, that rows estimation
+ * give us absolute minimum (1) then the optimizer can't choose between different
+ * indexes and uses first from the index list (last created).
+ */
+\set scale 100000
+
+CREATE TABLE t AS (
+    SELECT  c1 AS c1, -- selectivity(c1)*selectivity(c2)*nrows <= 1
+            c1 AS c2,
+			-- Create two columns with different selectivity.
+            (c1 % 2) AS c3, -- missing from a good index.
+            (c1 % 4) AS c4 -- missing from a bad index.
+    FROM generate_series(1,:scale) AS c1
+);
+UPDATE t SET c1=1,c2=1,c3=1,c4=2 WHERE c1<:scale/1000;
+
+CREATE INDEX bad ON t (c1,c2,c3);
+CREATE INDEX good ON t (c1,c2,c4);
+ANALYZE t; -- update stat on the indexes.
+
+EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1;
+
+-- Set the bad index to the first position in the index list.
+DROP INDEX bad;
+CREATE INDEX bad ON t (c1,c2,c3);
+ANALYZE t;
+
+EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1;
+
+DROP TABLE t CASCADE;
-- 
2.43.0