v24-0002-Teach-generate_bitmap_or_paths-to-build-BitmapOr-pat.patch

From 37831eb47fe890d41e5f66bedc5d616c0f1ad570 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <a.lepikhov@postgrespro.ru>
Date: Wed, 13 Mar 2024 12:26:02 +0700
Subject: [PATCH 2/2] Teach generate_bitmap_or_paths to build BitmapOr paths
 over SAOP clauses.

Likewise OR clauses, discover SAOP array and try to split its elements
between smaller sized arrays to fit a set of partial indexes.
---
 doc/src/sgml/config.sgml                   |   3 +
 src/backend/optimizer/path/indxpath.c      |  82 +++++-
 src/backend/optimizer/util/predtest.c      |  37 +++
 src/backend/optimizer/util/restrictinfo.c  |  13 +
 src/include/optimizer/optimizer.h          |   3 +
 src/include/optimizer/restrictinfo.h       |   1 +
 src/test/regress/expected/create_index.out |  24 +-
 src/test/regress/expected/select.out       | 280 +++++++++++++++++++++
 src/test/regress/sql/select.sql            |  82 ++++++
 9 files changed, 508 insertions(+), 17 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index f384edde05..5772574634 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5486,6 +5486,9 @@ ANY <replaceable class="parameter">num_sync</replaceable> ( <replaceable class="
         The grouping technique of this transformation is based on the equivalence of variable sides.
         One side of such an expression must be a constant clause, and the other must contain a variable clause.
         The default is <literal>on</literal>.
+        Also, during BitmapScan paths generation it enables analysis of elements
+        of IN or ANY constant arrays to cover such clause with BitmapOr set of
+        partial index scans.
         </para>
       </listitem>
      </varlistentry>
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 32c6a8bbdc..f78dae25ff 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -32,6 +32,7 @@
 #include "optimizer/paths.h"
 #include "optimizer/prep.h"
 #include "optimizer/restrictinfo.h"
+#include "utils/array.h"
 #include "utils/lsyscache.h"
 #include "utils/selfuncs.h"
 
@@ -1220,11 +1221,73 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
 	return result;
 }
 
+/*
+ * Expand SAOP node to use it in bitmapscan path building routine.
+ *
+ * If RestrictInfo is an OR bool expression, extract each SAOP from the list of
+ * arguments, if possible.
+ * Working jointly with the TransformOrExprToANY routine, it provides a user
+ * with some sort of independence of the query plan from the approach to writing
+ * alternatives for the same entity in the WHERE section.
+ */
+static List *
+extract_saop_ors(PlannerInfo *root, RestrictInfo *rinfo)
+{
+	List		   *orlist = NIL;
+	List		   *result = NIL;
+	ListCell	   *lc;
+
+	Assert(IsA(rinfo, RestrictInfo));
+
+	if (restriction_is_or_clause(rinfo))
+		orlist = ((BoolExpr *) rinfo->orclause)->args;
+
+	/*
+	 * Don't spend cycles here if the transformation is disabled.
+	 * We don't behave symmetrically here with the OR -> ANY transformation, see
+	 * the process_duplicate_ors routine, because origin list of ORs and
+	 * resulting SAOP args list lengths can differ significantly. Moreover,
+	 * Here we already limited by the MAX_SAOP_ARRAY_SIZE value.
+	 */
+	if (or_transformation_limit < 0)
+		return orlist;
+
+	if (restriction_is_saop_clause(rinfo))
+	{
+		result = transform_saop_to_ors(root, rinfo);
+		return result;
+	}
+
+	foreach(lc, orlist)
+	{
+		Expr *expr = (Expr *) lfirst(lc);
+
+		if (IsA(expr, RestrictInfo) && restriction_is_saop_clause((RestrictInfo *) expr))
+		{
+			List *sublist;
+
+			sublist = extract_saop_ors(root, (RestrictInfo *) lfirst(lc));
+			if (sublist != NIL)
+			{
+				result = list_concat(result, sublist);
+				continue;
+			}
+
+			/* Need to return expr to the result list */
+		}
+
+		result = lappend(result, expr);
+	}
+
+	return result;
+}
+
 /*
  * generate_bitmap_or_paths
- *		Look through the list of clauses to find OR clauses, and generate
- *		a BitmapOrPath for each one we can handle that way.  Return a list
- *		of the generated BitmapOrPaths.
+ *		Look through the list of clauses to find OR and SAOP clauses, and
+ *		Each saop clause are splitted to be covered by partial indexes.
+ *		generate a BitmapOrPath for each one we can handle that way.
+ *		Return a list of the generated BitmapOrPaths.
  *
  * other_clauses is a list of additional clauses that can be assumed true
  * for the purpose of generating indexquals, but are not to be searched for
@@ -1247,20 +1310,25 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 	foreach(lc, clauses)
 	{
 		RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
-		List	   *pathlist;
+		List	   *pathlist = NIL;
 		Path	   *bitmapqual;
 		ListCell   *j;
+		List	   *orlist = NIL;
 
-		/* Ignore RestrictInfos that aren't ORs */
-		if (!restriction_is_or_clause(rinfo))
+		orlist = extract_saop_ors(root, rinfo);
+		if (orlist == NIL)
+			/* Ignore RestrictInfo that doesn't provide proper OR list */
 			continue;
 
+		/* SAOP have splitted, remove already redundant clause */
+		all_clauses = list_delete(all_clauses, rinfo);
+
 		/*
 		 * We must be able to match at least one index to each of the arms of
 		 * the OR, else we can't use it.
 		 */
 		pathlist = NIL;
-		foreach(j, ((BoolExpr *) rinfo->orclause)->args)
+		foreach(j, orlist)
 		{
 			Node	   *orarg = (Node *) lfirst(j);
 			List	   *indlist;
diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c
index 6e3b376f3d..fe8862b0a0 100644
--- a/src/backend/optimizer/util/predtest.c
+++ b/src/backend/optimizer/util/predtest.c
@@ -111,6 +111,43 @@ static bool operator_same_subexprs_lookup(Oid pred_op, Oid clause_op,
 static Oid	get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it);
 static void InvalidateOprProofCacheCallBack(Datum arg, int cacheid, uint32 hashvalue);
 
+/*
+ * Expand a SAOP operation into the list of OR expressions
+ */
+List *
+transform_saop_to_ors(PlannerInfo *root, RestrictInfo *rinfo)
+{
+	PredIterInfoData	clause_info;
+	List			   *orlist = NIL;
+	Node			   *saop = (Node *) rinfo->clause;
+
+	Assert(IsA(saop, ScalarArrayOpExpr));
+
+	if (predicate_classify(saop, &clause_info) != CLASS_OR)
+		return NIL;
+
+	iterate_begin(pitem, saop, clause_info)
+	{
+		RestrictInfo   *rinfo1;
+
+		/* Predicate is found. Add the elem to the saop clause */
+		Assert(IsA(pitem, OpExpr));
+
+		/* Extract constant from the expression */
+		rinfo1 = make_restrictinfo(root, (Expr *) copyObject(pitem),
+								   rinfo->is_pushed_down,
+								   rinfo->has_clone, rinfo->is_clone,
+								   rinfo->pseudoconstant,
+								   rinfo->security_level,
+								   rinfo->required_relids,
+								   rinfo->incompatible_relids,
+								   rinfo->outer_relids);
+		orlist = lappend(orlist, rinfo1);
+	}
+	iterate_end(clause_info);
+
+	return orlist;
+}
 
 /*
  * predicate_implied_by
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index 0b406e9334..1dad1dc654 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -421,6 +421,19 @@ restriction_is_or_clause(RestrictInfo *restrictinfo)
 		return false;
 }
 
+bool
+restriction_is_saop_clause(RestrictInfo *restrictinfo)
+{
+	if (restrictinfo->clause && IsA(restrictinfo->clause, ScalarArrayOpExpr))
+	{
+		ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) restrictinfo->clause;
+
+		if (saop->useOr)
+			return true;
+	}
+	return false;
+}
+
 /*
  * restriction_is_securely_promotable
  *
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index 4c613401d6..4ca26f65d1 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -23,6 +23,7 @@
 #define OPTIMIZER_H
 
 #include "nodes/parsenodes.h"
+#include "optimizer/restrictinfo.h"
 
 /*
  * We don't want to include nodes/pathnodes.h here, because non-planner
@@ -161,6 +162,8 @@ extern List *expand_function_arguments(List *args, bool include_out_arguments,
 
 /* in util/predtest.c: */
 
+
+extern List *transform_saop_to_ors(PlannerInfo *root, RestrictInfo *rinfo);
 extern bool predicate_implied_by(List *predicate_list, List *clause_list,
 								 bool weak);
 extern bool predicate_refuted_by(List *predicate_list, List *clause_list,
diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h
index 1b42c832c5..2cd5fbf943 100644
--- a/src/include/optimizer/restrictinfo.h
+++ b/src/include/optimizer/restrictinfo.h
@@ -34,6 +34,7 @@ extern RestrictInfo *make_restrictinfo(PlannerInfo *root,
 									   Relids outer_relids);
 extern RestrictInfo *commute_restrictinfo(RestrictInfo *rinfo, Oid comm_op);
 extern bool restriction_is_or_clause(RestrictInfo *restrictinfo);
+extern bool restriction_is_saop_clause(RestrictInfo *restrictinfo);
 extern bool restriction_is_securely_promotable(RestrictInfo *restrictinfo,
 											   RelOptInfo *rel);
 extern List *get_actual_clauses(List *restrictinfo_list);
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index e9fb82b64c..0d9c9334f9 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1980,23 +1980,25 @@ SELECT count(*) FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
-                                                         QUERY PLAN                                                          
------------------------------------------------------------------------------------------------------------------------------
+                                                       QUERY PLAN                                                       
+------------------------------------------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: (((hundred = 42) AND ((thousand = ANY ('{42,99}'::integer[])) OR (tenthous < 2))) OR (thousand = 41))
+         Recheck Cond: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
          ->  BitmapOr
                ->  BitmapAnd
                      ->  Bitmap Index Scan on tenk1_hundred
                            Index Cond: (hundred = 42)
                      ->  BitmapOr
                            ->  Bitmap Index Scan on tenk1_thous_tenthous
-                                 Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+                                 Index Cond: (thousand = 42)
+                           ->  Bitmap Index Scan on tenk1_thous_tenthous
+                                 Index Cond: (thousand = 99)
                            ->  Bitmap Index Scan on tenk1_thous_tenthous
                                  Index Cond: (tenthous < 2)
                ->  Bitmap Index Scan on tenk1_thous_tenthous
                      Index Cond: (thousand = 41)
-(14 rows)
+(16 rows)
 
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
@@ -2008,20 +2010,22 @@ SELECT count(*) FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
-                                                          QUERY PLAN                                                          
-------------------------------------------------------------------------------------------------------------------------------
+                                                       QUERY PLAN                                                        
+-------------------------------------------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: ((hundred = 42) AND ((thousand = ANY ('{42,41}'::integer[])) OR ((thousand = 99) AND (tenthous = 2))))
+         Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2))))
          ->  BitmapAnd
                ->  Bitmap Index Scan on tenk1_hundred
                      Index Cond: (hundred = 42)
                ->  BitmapOr
                      ->  Bitmap Index Scan on tenk1_thous_tenthous
-                           Index Cond: (thousand = ANY ('{42,41}'::integer[]))
+                           Index Cond: (thousand = 42)
+                     ->  Bitmap Index Scan on tenk1_thous_tenthous
+                           Index Cond: (thousand = 41)
                      ->  Bitmap Index Scan on tenk1_thous_tenthous
                            Index Cond: ((thousand = 99) AND (tenthous = 2))
-(11 rows)
+(13 rows)
 
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
diff --git a/src/test/regress/expected/select.out b/src/test/regress/expected/select.out
index 33a6dceb0e..b5fdde47ac 100644
--- a/src/test/regress/expected/select.out
+++ b/src/test/regress/expected/select.out
@@ -907,6 +907,286 @@ select unique1, unique2 from onek2
        0 |     998
 (2 rows)
 
+SET enable_seqscan TO off;
+SET enable_indexscan TO off; -- Only BitmapScan is a subject matter here
+SET or_transformation_limit = -1;
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 = 'A' OR stringu1 = 'J';
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 < 'B'::name) OR (stringu1 = 'J'::name))
+         Filter: ((stringu1 = 'A'::name) OR (stringu1 = 'J'::name))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_u2_prtl
+               ->  Bitmap Index Scan on onek2_stu1_prtl
+                     Index Cond: (stringu1 = 'J'::name)
+(8 rows)
+
+-- Without the transformation only seqscan possible here
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique2 < 1 AND stringu1 IN ('A','J') AND stringu1 < 'Z';
+                                         QUERY PLAN                                          
+---------------------------------------------------------------------------------------------
+ Seq Scan on onek2
+   Filter: ((unique2 < 1) AND (stringu1 = ANY ('{A,J}'::name[])) AND (stringu1 < 'Z'::name))
+(2 rows)
+
+-- Use partial indexes
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2
+WHERE stringu1 IN ('B','J') AND (stringu1 = 'A' OR unique1 = 1);
+                                             QUERY PLAN                                             
+----------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 < 'B'::name) OR (unique1 = 1))
+         Filter: ((stringu1 = ANY ('{B,J}'::name[])) AND ((stringu1 = 'A'::name) OR (unique1 = 1)))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_u2_prtl
+               ->  Bitmap Index Scan on onek2_u1_prtl
+                     Index Cond: (unique1 = 1)
+(8 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 < 1 OR (stringu1 = 'A' OR stringu1 = 'J');
+                                     QUERY PLAN                                      
+-------------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: ((unique1 < 1) OR (stringu1 < 'B'::name) OR (stringu1 = 'J'::name))
+   Filter: ((unique1 < 1) OR (stringu1 = 'A'::name) OR (stringu1 = 'J'::name))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 < 1)
+         ->  Bitmap Index Scan on onek2_u2_prtl
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: (stringu1 = 'J'::name)
+(9 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 = 1 OR unique2 = PI()::integer;
+                 QUERY PLAN                 
+--------------------------------------------
+ Seq Scan on onek2
+   Filter: ((unique1 = 1) OR (unique2 = 3))
+(2 rows)
+
+RESET or_transformation_limit;
+-- OR <-> ANY transformation must find a path with partial indexes scan
+-- regardless the clause representation.
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 = 'A' OR stringu1 = 'J';
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 < 'B'::name) OR (stringu1 = 'J'::name))
+         Filter: (stringu1 = ANY ('{A,J}'::name[]))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_u2_prtl
+               ->  Bitmap Index Scan on onek2_stu1_prtl
+                     Index Cond: (stringu1 = 'J'::name)
+(8 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A','J');
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 < 'B'::name) OR (stringu1 = 'J'::name))
+         Filter: (stringu1 = ANY ('{A,J}'::name[]))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_u2_prtl
+               ->  Bitmap Index Scan on onek2_stu1_prtl
+                     Index Cond: (stringu1 = 'J'::name)
+(8 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 = ANY ('{A,J}');
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 < 'B'::name) OR (stringu1 = 'J'::name))
+         Filter: (stringu1 = ANY ('{A,J}'::name[]))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_u2_prtl
+               ->  Bitmap Index Scan on onek2_stu1_prtl
+                     Index Cond: (stringu1 = 'J'::name)
+(8 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A') OR stringu1 IN ('J');
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 < 'B'::name) OR (stringu1 = 'J'::name))
+         Filter: (stringu1 = ANY ('{A,J}'::name[]))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_u2_prtl
+               ->  Bitmap Index Scan on onek2_stu1_prtl
+                     Index Cond: (stringu1 = 'J'::name)
+(8 rows)
+
+-- Don't scan partial indexes because of extra value.
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A', 'J', 'C');
+                      QUERY PLAN                      
+------------------------------------------------------
+ Aggregate
+   ->  Seq Scan on onek2
+         Filter: (stringu1 = ANY ('{A,J,C}'::name[]))
+(3 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT unique2 FROM onek2
+WHERE stringu1 IN ('A', 'A') AND (stringu1 = 'A' OR stringu1 = 'A');
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: (stringu1 < 'B'::name)
+   Filter: ((stringu1 = ANY ('{A,A}'::name[])) AND (stringu1 = 'A'::name))
+   ->  Bitmap Index Scan on onek2_u2_prtl
+(4 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique2 < 1 AND stringu1 IN ('A','J') AND stringu1 < 'Z';
+                                                     QUERY PLAN                                                      
+---------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: (((unique2 < 1) AND (stringu1 < 'B'::name)) OR ((stringu1 = 'J'::name) AND (stringu1 < 'Z'::name)))
+   Filter: ((unique2 < 1) AND (stringu1 = ANY ('{A,J}'::name[])))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_u2_prtl
+               Index Cond: (unique2 < 1)
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: ((stringu1 = 'J'::name) AND (stringu1 < 'Z'::name))
+(8 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 = 1 OR unique1 = PI()::integer;
+                        QUERY PLAN                        
+----------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: (unique1 = ANY ('{1,3}'::integer[]))
+   ->  Bitmap Index Scan on onek2_u1_prtl
+         Index Cond: (unique1 = ANY ('{1,3}'::integer[]))
+(4 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 IN (1, PI()::integer);
+                        QUERY PLAN                        
+----------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: (unique1 = ANY ('{1,3}'::integer[]))
+   ->  Bitmap Index Scan on onek2_u1_prtl
+         Index Cond: (unique1 = ANY ('{1,3}'::integer[]))
+(4 rows)
+
+-- Don't apply the optimization to clauses, containing volatile functions
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE unique1 = (random()*2)::integer OR unique1 = (random()*3)::integer;
+                                                             QUERY PLAN                                                             
+------------------------------------------------------------------------------------------------------------------------------------
+ Seq Scan on onek2
+   Filter: ((unique1 = ((random() * '2'::double precision))::integer) OR (unique1 = ((random() * '3'::double precision))::integer))
+(2 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE unique1 IN ((random()*2)::integer, (random()*3)::integer);
+                                                           QUERY PLAN                                                            
+---------------------------------------------------------------------------------------------------------------------------------
+ Seq Scan on onek2
+   Filter: (unique1 = ANY (ARRAY[((random() * '2'::double precision))::integer, ((random() * '3'::double precision))::integer]))
+(2 rows)
+
+-- Combine different saops. Some of them doesnt' fit a set of partial indexes,
+-- but other fits.
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE
+  unique1 IN (1,2,21) AND
+  (stringu1 IN ('A','J') OR unique1 IN (3,4) OR stringu1 = 'J');
+                                                                           QUERY PLAN                                                                           
+----------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: ((stringu1 < 'B'::name) OR (stringu1 = 'J'::name) OR (unique1 = 3) OR (unique1 = 4) OR (stringu1 = 'J'::name))
+   Filter: ((unique1 = ANY ('{1,2,21}'::integer[])) AND ((stringu1 = ANY ('{A,J}'::name[])) OR (unique1 = ANY ('{3,4}'::integer[])) OR (stringu1 = 'J'::name)))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_u2_prtl
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: (stringu1 = 'J'::name)
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 = 3)
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 = 4)
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: (stringu1 = 'J'::name)
+(13 rows)
+
+-- Check recursive combination of OR and SAOP expressions
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 < 1 OR (stringu1 = 'A' OR stringu1 = 'J');
+                                     QUERY PLAN                                      
+-------------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: ((unique1 < 1) OR (stringu1 < 'B'::name) OR (stringu1 = 'J'::name))
+   Filter: ((unique1 < 1) OR (stringu1 = ANY ('{A,J}'::name[])))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 < 1)
+         ->  Bitmap Index Scan on onek2_u2_prtl
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: (stringu1 = 'J'::name)
+(9 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE (unique1 < 1 OR stringu1 IN ('A','J'));
+                                     QUERY PLAN                                      
+-------------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: ((unique1 < 1) OR (stringu1 < 'B'::name) OR (stringu1 = 'J'::name))
+   Filter: ((unique1 < 1) OR (stringu1 = ANY ('{A,J}'::name[])))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 < 1)
+         ->  Bitmap Index Scan on onek2_u2_prtl
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: (stringu1 = 'J'::name)
+(9 rows)
+
+-- Although SAOP doesn't fit partial indexes fully, we can use anded OR clause
+-- to scan another couple of partial indexes.
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2
+WHERE stringu1 IN ('B','J') AND (stringu1 = 'A' OR unique1 = 1);
+                                             QUERY PLAN                                             
+----------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 < 'B'::name) OR (unique1 = 1))
+         Filter: ((stringu1 = ANY ('{B,J}'::name[])) AND ((stringu1 = 'A'::name) OR (unique1 = 1)))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_u2_prtl
+               ->  Bitmap Index Scan on onek2_u1_prtl
+                     Index Cond: (unique1 = 1)
+(8 rows)
+
+RESET enable_indexscan;
+RESET enable_seqscan;
 --
 -- Test some corner cases that have been known to confuse the planner
 --
diff --git a/src/test/regress/sql/select.sql b/src/test/regress/sql/select.sql
index 019f1e7673..10ed6f0a9c 100644
--- a/src/test/regress/sql/select.sql
+++ b/src/test/regress/sql/select.sql
@@ -234,6 +234,88 @@ select unique1, unique2 from onek2
 select unique1, unique2 from onek2
   where (unique2 = 11 and stringu1 < 'B') or unique1 = 0;
 
+SET enable_seqscan TO off;
+SET enable_indexscan TO off; -- Only BitmapScan is a subject matter here
+SET or_transformation_limit = -1;
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 = 'A' OR stringu1 = 'J';
+-- Without the transformation only seqscan possible here
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique2 < 1 AND stringu1 IN ('A','J') AND stringu1 < 'Z';
+-- Use partial indexes
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2
+WHERE stringu1 IN ('B','J') AND (stringu1 = 'A' OR unique1 = 1);
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 < 1 OR (stringu1 = 'A' OR stringu1 = 'J');
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 = 1 OR unique2 = PI()::integer;
+RESET or_transformation_limit;
+
+-- OR <-> ANY transformation must find a path with partial indexes scan
+-- regardless the clause representation.
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 = 'A' OR stringu1 = 'J';
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A','J');
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 = ANY ('{A,J}');
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A') OR stringu1 IN ('J');
+
+-- Don't scan partial indexes because of extra value.
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A', 'J', 'C');
+EXPLAIN (COSTS OFF)
+SELECT unique2 FROM onek2
+WHERE stringu1 IN ('A', 'A') AND (stringu1 = 'A' OR stringu1 = 'A');
+
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique2 < 1 AND stringu1 IN ('A','J') AND stringu1 < 'Z';
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 = 1 OR unique1 = PI()::integer;
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 IN (1, PI()::integer);
+
+-- Don't apply the optimization to clauses, containing volatile functions
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE unique1 = (random()*2)::integer OR unique1 = (random()*3)::integer;
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE unique1 IN ((random()*2)::integer, (random()*3)::integer);
+
+-- Combine different saops. Some of them doesnt' fit a set of partial indexes,
+-- but other fits.
+
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE
+  unique1 IN (1,2,21) AND
+  (stringu1 IN ('A','J') OR unique1 IN (3,4) OR stringu1 = 'J');
+
+-- Check recursive combination of OR and SAOP expressions
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 < 1 OR (stringu1 = 'A' OR stringu1 = 'J');
+EXPLAIN (COSTS OFF)
+SELECT unique2, stringu1 FROM onek2
+WHERE (unique1 < 1 OR stringu1 IN ('A','J'));
+-- Although SAOP doesn't fit partial indexes fully, we can use anded OR clause
+-- to scan another couple of partial indexes.
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM onek2
+WHERE stringu1 IN ('B','J') AND (stringu1 = 'A' OR unique1 = 1);
+
+RESET enable_indexscan;
+RESET enable_seqscan;
+
 --
 -- Test some corner cases that have been known to confuse the planner
 --
-- 
2.44.0