Subject: Re: POC, WIP: OR-clause support for indexes

From: Alena Rybakina <[email-masked]>
Date: Mon, 22 Jul 2024 01:53:51 +0300

Hi! Thank you for your contribution to this thread!

To be honest,I saw a larger problem. Look at the query bellow:

master:

alena@postgres=# create table t (a int not null, b int not null, c int 
not null);
insert into t (select 1, 1, i from generate_series(1,10000) i);
insert into t (select i, 2, 2 from generate_series(1,10000) i);
create index t_a_b_idx on t (a, b);
create statistics t_a_b_stat (mcv) on a, b from t;
create statistics t_b_c_stat (mcv) on b, c from t;
vacuum analyze t;
CREATE TABLE
INSERT 0 10000
INSERT 0 10000
CREATE INDEX
CREATE STATISTICS
CREATE STATISTICS
VACUUM
alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 
2) and c = 2;
                                   QUERY PLAN
------------------------------------------------------------------------------
  Bitmap Heap Scan on t  (cost=156.55..465.57 rows=5001 width=12)
    Recheck Cond: (a = 1)
    Filter: ((c = 2) AND ((b = 1) OR (b = 2)))
    ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..155.29 rows=10001 
width=0)
          Index Cond: (a = 1)
(5 rows)

The query plan if v26[0] and v27[1] versions are equal and wrong in my 
opinion -where is c=2 expression?

v27 [1]
alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 
2) and c = 2;
                                   QUERY PLAN
------------------------------------------------------------------------------
  Bitmap Heap Scan on t  (cost=165.85..474.87 rows=5001 width=12)
    Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
    Filter: (c = 2)
    ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..164.59 rows=10001 
width=0)
          Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
(5 rows)
v26 [0]
alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 
2) and c = 2;
                                   QUERY PLAN
------------------------------------------------------------------------------
  Bitmap Heap Scan on t  (cost=165.85..449.86 rows=5001 width=12)
    Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
    Filter: (c = 2)
    ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..164.59 rows=10001 
width=0)
          Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
(5 rows)

In addition, I noticed that the ANY expression will be formed only for 
first group and ignore for others, like in the sample bellow:

v26 version [0]:

alena@postgres=# explain select * from t where (b = 1 or b = 2) and (a = 
2 or a=3);
                                     QUERY PLAN
-----------------------------------------------------------------------------------
  Index Scan using t_a_b_idx on t  (cost=0.29..24.75 rows=2 width=12)
    Index Cond: ((a = ANY ('{2,3}'::integer[])) AND (b = ANY 
('{1,2}'::integer[])))
(2 rows)

v27 version [1]:

alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 
or a=3);
                        QUERY PLAN
--------------------------------------------------------
  Seq Scan on t  (cost=0.00..509.00 rows=14999 width=12)
    Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
(2 rows)

alena@postgres=# create index a_idx on t(a);
CREATE INDEX
alena@postgres=# create index b_idx on t(b);
CREATE INDEX
alena@postgres=# analyze;
ANALYZE

v26:

alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 
or a=3);
                                      QUERY PLAN
------------------------------------------------------------------------------------
  Bitmap Heap Scan on t  (cost=17.18..30.94 rows=4 width=12)
    Recheck Cond: ((a = ANY ('{2,3}'::integer[])) OR (a = ANY 
('{2,3}'::integer[])))
    ->  BitmapOr  (cost=17.18..17.18 rows=4 width=0)
          ->  Bitmap Index Scan on a_idx  (cost=0.00..8.59 rows=2 width=0)
                Index Cond: (a = ANY ('{2,3}'::integer[]))
          ->  Bitmap Index Scan on a_idx  (cost=0.00..8.59 rows=2 width=0)
                Index Cond: (a = ANY ('{2,3}'::integer[]))
(7 rows)

v27:

alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 
or a=3);
                        QUERY PLAN
--------------------------------------------------------
  Seq Scan on t  (cost=0.00..509.00 rows=14999 width=12)
    Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
(2 rows)

The behavior in version 26 is incorrect, but in version 27, it does not 
select anything other than seqscan

Since Thursday I have been trying to add the code forming groups of 
identical "OR" expressions, as in version 26. I'm currently debugging 
errors.

On 21.07.2024 11:17, Nikolay Shaplov wrote:
> В письме от среда, 17 июля 2024 г. 22:36:19 MSK пользователь Alexander
> Korotkov написал:
>
> Hi All!
>
> I am continue reading the patch, now it's newer version
>
> First main question:
>
> As far a I can get, the entry point for OR->ANY convertation have been moved
> to match_clause_to_indexcol funtion, that checks if some restriction can use
> index for performance.
>
> The thing I do not understand what match_clause_to_indexcol actually received
> as arguments. Should this be set of expressions  with OR in between grouped by
> one of the expression argument?
>
> If not I do not understand how this ever should work.
  The point is that we do the transformation for those columns that have 
an index, since this transformation is most useful in these cases. we 
pass the parameters index relation and column number to find out 
information about it.
>
> The rest is about code readability
>
>> +	if (bms_is_member(index->rel->relid, rinfo->right_relids))
>> +		return NULL;
To be honest, I'm not sure that I understand your question. Could you 
explain me?
> This check it totally not obvious for person who is not deep into postgres
> code. There should go comment explaining what are we checking for, and why it
> does not suit our purposes
>
>
>> +	foreach(lc, orclause->args)
>> +	{
I'll add it, thank you.
> Being no great expert in postgres code, I am confused what are we iterating on
> here? Two arguments of OR statement? (a>1) OR (b>2) those in brackets? Or
> what? Comment explaining that would be a great help here.
>
>
>> +if (sub_rinfo->is_pushed_down != rinfo->is_pushed_down ||
>> +	sub_rinfo->is_clone != rinfo->is_clone ||
>> +	sub_rinfo->security_level != rinfo->security_level ||
>> +	!bms_equal(sub_rinfo->required_relids, rinfo->required_relids) ||
>> +	!bms_equal(sub_rinfo->incompatible_relids, rinfo-
> incompatible_relids) ||
>> +	!bms_equal(sub_rinfo->outer_relids, rinfo->outer_relids))
>> +	{
I'll add it.
> This check it totally mind-blowing... What in the name of existence is going
> on here?
>
> I would suggest  to split these checks into parts (compiler optimizer should
> take care about overhead)  and give each part a sane explanation.

Alexander suggested moving the transformation to another place and it is 
correct in my opinion. All previous problems are now gone.
But he also cut the code - he made a transformation for one group of 
"OR" expressions. I agree, some parts don't yet
provide enough explanation of what's going on. I'm correcting this now.

Speaking of the changes according to your suggestions, I made them in 
version 26 [0] and just part of that code will end up in the current 
version of the patch to process all groups of "OR" expressions.

I'll try to do this as best I can, but it took me a while to figure out 
how to properly organize RestrictInfo in the index.

[0] 
https://www.postgresql.org/message-id/3b9bb831-da52-4779-8f3e-f8b6b83ba41f%40postgrespro.ru

[1] 
https://www.postgresql.org/message-id/CAPpHfdvhWE5pArZhgJeLViLx3-A3rxEREZvfkTj3E%3Dh7q-Bx9w%40mail.gmail.com 

-- 
Regards,
Alena Rybakina
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 22 Jul 2024 03:52:43 +0300

Hi, Alena!

Let me answer to some of your findings.

On Mon, Jul 22, 2024 at 12:53 AM Alena Rybakina
<[email-masked]> wrote:
> alena@postgres=# create table t (a int not null, b int not null, c int not null);

Just a side note.  As I mention in [1], there is missing statement
create index t_a_b_idx on t (a, b);
to get same plan as in [2].

> alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
>                                   QUERY PLAN
>    ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..155.29 rows=10001 width=0)
>          Index Cond: (a = 1)
> (5 rows)
>
>
> The query plan if v26[0] and v27[1] versions are equal and wrong in my opinion -where is c=2 expression?
>
> v27 [1]
> alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
>                                   QUERY PLAN
>    ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..164.59 rows=10001 width=0)
> alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
>                                   QUERY PLAN
>    ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..164.59 rows=10001 width=0)

I think both v26 and v27 are correct here.  The c = 2 condition is in
the Filter.

> In addition, I noticed that the ANY expression will be formed only for first group and ignore for others, like in the sample bellow:
>
> v26 version [0]:
>
> alena@postgres=# explain select * from t where (b = 1 or b = 2) and (a = 2 or a=3);
>                                     QUERY PLAN
>    Index Cond: ((a = ANY ('{2,3}'::integer[])) AND (b = ANY ('{1,2}'::integer[])))
> (2 rows)
>
> v27 version [1]:
>
> alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
>                        QUERY PLAN

Did you notice you're running different queries on v26 and v27 here?
If you will run ton v27 the same query you run on v26, the plan also
will be the same.

> alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
>                                      QUERY PLAN
>    Recheck Cond: ((a = ANY ('{2,3}'::integer[])) OR (a = ANY ('{2,3}'::integer[])))
> alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
>                        QUERY PLAN
> The behavior in version 26 is incorrect, but in version 27, it does not select anything other than seqscan

Please, check that there is still possibility to the generate BitmapOr plan.

# explain select * from t where (b = 1 or b = 2 or a = 2 or a = 3);
                                     QUERY PLAN
------------------------------------------------------------------------------------
 Bitmap Heap Scan on t  (cost=326.16..835.16 rows=14999 width=12)
   Recheck Cond: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
   ->  BitmapOr  (cost=326.16..326.16 rows=20000 width=0)
         ->  Bitmap Index Scan on t_b_c_idx  (cost=0.00..151.29
rows=10000 width=0)
               Index Cond: (b = 1)
         ->  Bitmap Index Scan on t_b_c_idx  (cost=0.00..151.29
rows=10000 width=0)
               Index Cond: (b = 2)
         ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..4.29 rows=1 width=0)
               Index Cond: (a = 2)
         ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..4.29 rows=1 width=0)
               Index Cond: (a = 3)

It has higher cost than SeqScan plan, but I think it would be selected
on larger tables.  And yes, this is not ideal, because it fails to
generate BitmapOr over two IndexScans on SAOPs.  But it's not worse
than what current master does.  An optimization doesn't have to do
everything it could possible do.  So, I think this could be improved
in a separate patch.

Links
1. https://www.postgresql.org/message-id/CAPpHfdvhWE5pArZhgJeLViLx3-A3rxEREZvfkTj3E%3Dh7q-Bx9w%40mail.gmail.com
2. https://www.postgresql.org/message-id/CAPpHfdtSXxhdv3mLOLjEewGeXJ%2BFtfhjqodn1WWuq5JLsKx48g%40mail.gmail.com

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 22 Jul 2024 03:54:43 +0300

> # explain select * from t where (b = 1 or b = 2 or a = 2 or a = 3);

Forgot to mention that I have to
# set enable_seqscan = off;
to get this plan.

------
Regards,
Alexander Korotkov
Supabase

---

From: Alena Rybakina <[email-masked]>
Date: Thu, 25 Jul 2024 17:04:44 +0300

> I think both v26 and v27 are correct here.  The c = 2 condition is in
Yes, I see it and agree with that.
> Please, check that there is still possibility to the generate BitmapOr plan.
It is fine, I think. The transformation works, but due to the fact that 
index columns are different for two indexes, the transformation hasn't 
been applied.
> 1.https://www.postgresql.org/message-id/CAPpHfdvhWE5pArZhgJeLViLx3-A3rxEREZvfkTj3E%3Dh7q-Bx9w%40mail.gmail.com
> 2.https://www.postgresql.org/message-id/CAPpHfdtSXxhdv3mLOLjEewGeXJ%2BFtfhjqodn1WWuq5JLsKx48g%40mail.gmail.com

Yes, I see and agree with you.

To be honest, I have found a big problem in this patch - we try to 
perform the transformation every time we examime a column:

for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++) { ...

}

I have fixed it and moved the transformation before going through the loop.

I try to make an array expression for "OR" expr, but at the same time I 
form the result as an "AND" expression, consisting of an "Array" 
expression and "OR" expressions, and then I check whether there is an 
index for this column, if so, I save it and write down the 
transformation. I also had to return the previous part of the patch, 
where we formed "ANY" groups, since we could end up with several such 
groups. I hope I made my idea clear, but if not, please tell me.

Unfortunately, I have got the different result one of the query from 
regression tests and I'm not sure if it is correct:

diff -U3 
/home/alena/postgrespro_or3/src/test/regress/expected/create_index.out 
/home/alena/postgrespro_or3/src/test/regress/results/create_index.out 
--- 
/home/alena/postgrespro_or3/src/test/regress/expected/create_index.out 
2024-07-23 18:51:13.077311360 +0300 +++ 
/home/alena/postgrespro_or3/src/test/regress/results/create_index.out 
2024-07-25 16:43:56.895132328 +0300 @@ -1860,13 +1860,14 @@ EXPLAIN 
(COSTS OFF) SELECT * FROM tenk1 WHERE thousand = 42 AND (tenthous = 1 OR 
tenthous = (SELECT 1 + 2) OR tenthous = 42); - QUERY PLAN 
----------------------------------------------------------------------------------------- 
+ QUERY PLAN 
+--------------------------------------------------------------------------------- 
Index Scan using tenk1_thous_tenthous on tenk1 - Index Cond: ((thousand 
= 42) AND (tenthous = ANY (ARRAY[1, (InitPlan 1).col1, 42]))) + Index 
Cond: ((thousand = 42) AND (tenthous = ANY ('{1,-1,42}'::integer[]))) + 
Filter: ((tenthous = 1) OR (tenthous = (InitPlan 1).col1) OR (tenthous = 
42)) InitPlan 1 -> Result -(4 rows) +(5 rows) SELECT * FROM tenk1 WHERE 
thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous 
= 42);

I'm researching what's wrong here now.

-- 
Regards,
Alena Rybakina
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company
From 31f58b8ad85e77534d38d099368168d9f775149f Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email-masked]>
Date: Thu, 25 Jul 2024 17:03:05 +0300
Subject: [PATCH] Transform OR clauses to ANY expression

Replace (expr op C1) OR (expr op C2) ... with expr op ANY(ARRAY[C1, C2, ...])
during matching a clause to index.

Here Cn is a n-th constant or parameters expression, 'expr' is non-constant
expression, 'op' is an operator which returns boolean result and has a commuter
(for the case of reverse order of constant and non-constant parts of the
expression, like 'Cn op expr').

Discussion: https://postgr.es/m/567ED6CA.2040504%40sigaev.ru
Author: Alena Rybakina <[email-masked]>
Author: Andrey Lepikhov <[email-masked]>
Reviewed-by: Peter Geoghegan <[email-masked]>
Reviewed-by: Ranier Vilela <[email-masked]>
Reviewed-by: Alexander Korotkov <[email-masked]>
Reviewed-by: Robert Haas <[email-masked]>
Reviewed-by: Jian He <[email-masked]>
Reviewed-by: Tom Lane <[email-masked]>
Reviewed-by: Nikolay Shaplov <[email-masked]>
---
 src/backend/optimizer/path/indxpath.c      | 396 +++++++++++++++++++++
 src/include/nodes/pathnodes.h              |  31 ++
 src/test/regress/expected/create_index.out | 183 +++++++++-
 src/test/regress/expected/join.out         |  57 ++-
 src/test/regress/sql/create_index.sql      |  42 +++
 src/test/regress/sql/join.sql              |   9 +
 src/tools/pgindent/typedefs.list           |   1 +
 7 files changed, 697 insertions(+), 22 deletions(-)

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index c0fcc7d78df..35bdf00dcb1 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -32,7 +32,9 @@
 #include "optimizer/paths.h"
 #include "optimizer/prep.h"
 #include "optimizer/restrictinfo.h"
+#include "utils/array.h"
 #include "utils/lsyscache.h"
+#include "utils/syscache.h"
 #include "utils/selfuncs.h"

@@ -191,6 +193,10 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *index,
 static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
 									   EquivalenceClass *ec, EquivalenceMember *em,
 									   void *arg);
+static bool
+try_prepare_single_or(RestrictInfo *rinfo, List **appropriate_group);
+static List *
+transform_or_to_any(PlannerInfo *root, RestrictInfo * rinfo);

 /*
@@ -2087,6 +2093,7 @@ match_clause_to_index(PlannerInfo *root,
 					  IndexClauseSet *clauseset)
 {
 	int			indexcol;
+	List *candidates = NIL;
 
 	/*
 	 * Never match pseudoconstants to indexes.  (Normally a match could not
@@ -2104,6 +2111,9 @@ match_clause_to_index(PlannerInfo *root,
 	if (!restriction_is_securely_promotable(rinfo, index->rel))
 		return;
 
+	if (IsA(rinfo->clause, BoolExpr) && is_orclause(rinfo->clause))
+			candidates = transform_or_to_any(root, rinfo);
+
 	/* OK, check each index key column for a match */
 	for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++)
 	{
@@ -2119,6 +2129,71 @@ match_clause_to_index(PlannerInfo *root,
 				return;
 		}
 
+		if (candidates != NIL)
+		{
+			ListCell *lc1;
+			Expr *item = NULL;
+			Node *nconst_expr = NULL;
+			Expr *expr = NULL;
+			List *result = NIL;
+			bool flag = false;
+
+			foreach(lc1, candidates)
+			{
+				item = lfirst(lc1);
+
+				if(item && IsA(item, BoolExpr))
+				{
+					if(is_andclause((Node*) item) && IsA(linitial(((BoolExpr *) item)->args), ScalarArrayOpExpr))
+					{
+
+						expr = linitial(((BoolExpr *) item)->args);
+
+						nconst_expr = get_leftop(expr);
+
+						if (match_index_to_operand(nconst_expr, indexcol, index))
+						{
+							result = lappend(result, (void *) expr);
+							flag = true;
+							continue;
+						}
+						else
+						{
+							expr = lsecond(((BoolExpr *) item)->args);
+						}
+					}
+				}
+
+				if(expr == NULL)
+					result = lappend(result, (void *)item);
+				else
+					result = lappend(result, expr);
+			}
+
+			if (flag)
+			{
+				rinfo = make_restrictinfo(root,
+									   list_length(result) > 1 ?
+											makeBoolExpr(OR_EXPR, result,
+											((BoolExpr *) rinfo->clause)->location) :
+											linitial(result),
+									   rinfo->is_pushed_down,
+									   rinfo->has_clone,
+									   rinfo->is_clone,
+								   	   rinfo->pseudoconstant,
+									   rinfo->security_level,
+									   rinfo->required_relids,
+									   rinfo->incompatible_relids,
+									   rinfo->outer_relids);
+				iclause = makeNode(IndexClause);
+				iclause->rinfo = rinfo;
+				iclause->indexquals = list_make1(iclause->rinfo);
+				iclause->lossy = false;
+				iclause->indexcol = indexcol;
+				iclause->indexcols = NIL;
+			}
+		}
+
 		/* OK, try to match the clause to the index column */
 		iclause = match_clause_to_indexcol(root,
 										   rinfo,
@@ -2771,6 +2846,327 @@ match_rowcompare_to_indexcol(PlannerInfo *root,
 	return NULL;
 }
 
+static bool
+try_prepare_single_or(RestrictInfo *rinfo, List **appropriate_group)
+{
+	OpExpr	   *orqual;
+	Node	   *const_expr;
+	Node	   *nconst_expr;
+	Oid			opno;
+	Oid			consttype;
+	Node	   *leftop,
+			   *rightop;
+	ListCell   *lc2;
+	bool found = false;
+	OrClauseGroup *or_clause_group;
+
+	if (!IsA(rinfo, RestrictInfo) || !IsA(rinfo->clause, OpExpr))
+	{
+		return false;
+	}
+
+	orqual = (OpExpr *) rinfo->clause;
+	opno = orqual->opno;
+	if (get_op_rettype(opno) != BOOLOID)
+	{
+		/* Only operator returning boolean suits OR -> ANY transformation */
+		return false;
+	}
+
+	/*
+		* Detect the constant side of the clause. Recall non-constant
+		* expression can be made not only with Vars, but also with Params,
+		* which is not bonded with any relation. Thus, we detect the const
+		* side - if another side is constant too, the orqual couldn't be an
+		* OpExpr.  Get pointers to constant and expression sides of the qual.
+		*/
+	leftop = get_leftop(orqual);
+	if (IsA(leftop, RelabelType))
+		leftop = (Node *) ((RelabelType *) leftop)->arg;
+
+	rightop = get_rightop(orqual);
+	if (IsA(rightop, RelabelType))
+		rightop = (Node *) ((RelabelType *) rightop)->arg;
+
+	if (IsA(leftop, Const) || IsA(leftop, Param))
+	{
+		opno = get_commutator(opno);
+
+		if (!OidIsValid(opno))
+		{/* commutator doesn't exist, we can't reverse the order */
+			return false;
+		}
+
+		nconst_expr = get_rightop(orqual);
+		const_expr = get_leftop(orqual);
+	}
+	else if (IsA(rightop, Const) || IsA(rightop, Param))
+	{
+		const_expr = get_rightop(orqual);
+		nconst_expr = get_leftop(orqual);
+	}
+	else
+	{
+		return false;
+	}
+
+	/*
+		* Forbid transformation for composite types, records, and volatile
+		* expressions.
+		*/
+	consttype = exprType(const_expr);
+	if (type_is_rowtype(exprType(const_expr)) ||
+		type_is_rowtype(consttype) ||
+		contain_volatile_functions((Node *) nconst_expr))
+	{
+		return false;
+	}
+
+	or_clause_group = makeNode(OrClauseGroup);
+
+	foreach(lc2, *appropriate_group)
+	{
+
+		if (!IsA(lfirst(lc2), OrClauseGroup))
+			Assert(0);
+
+		or_clause_group = (OrClauseGroup *) lfirst(lc2);
+
+		if (or_clause_group->opno == opno &&
+			or_clause_group->consttype == consttype &&
+			or_clause_group->inputcollid == exprCollation(const_expr) &&
+			equal(or_clause_group->expr, nconst_expr))
+		{
+			found = true;
+			break;
+		}
+	}
+
+	if (!found)
+	{
+		or_clause_group->expr = (Expr *) nconst_expr;
+		or_clause_group->exprs = list_make1((void *) orqual);
+		or_clause_group->opno = opno;
+		or_clause_group->inputcollid = exprCollation(const_expr);
+		or_clause_group->consttype = consttype;
+		or_clause_group->consts = list_make1(const_expr);
+		or_clause_group->have_param = IsA(const_expr, Param);
+		Assert(list_length(or_clause_group->exprs) == list_length(or_clause_group->consts));
+		*appropriate_group = lappend(*appropriate_group, or_clause_group);
+		Assert(list_length(or_clause_group->exprs) == list_length(or_clause_group->consts));
+	}
+	else
+	{
+		or_clause_group->consts = lappend(or_clause_group->consts, const_expr);
+		or_clause_group->exprs = lappend(or_clause_group->exprs, (void *) orqual);
+		Assert(list_length(or_clause_group->exprs) == list_length(or_clause_group->consts));
+
+		Assert(list_length(or_clause_group->exprs) == list_length(or_clause_group->consts));
+	}
+
+	return true;
+}
+
+/*
+ * transform_or_to_any -
+ *	  Discover the args of an OR expression and try to group similar OR
+ *	  expressions to SAOP expressions.
+ *
+ * This transformation groups two-sided equality expression.  One side of
+ * such an expression must be a plain constant or constant expression.  The
+ * other side must be a variable expression without volatile functions.
+ * To group quals, opno, inputcollid of variable expression, and type of
+ * constant expression must be equal too.
+ *
+ * The grouping technique is based on the equivalence of variable sides of
+ * the expression: using exprId and equal() routine, it groups constant sides
+ * of similar clauses into an array.  After the grouping procedure, each
+ * couple ('variable expression' and 'constant array') forms a new SAOP
+ * operation, which is added to the args list of the returning expression.
+ */
+static List *
+transform_or_to_any(PlannerInfo *root, RestrictInfo * rinfo)
+{
+	List	   *appropriate_entries = NIL;
+	List	   *or_entries = NIL;
+	int			len_ors = ((BoolExpr *) rinfo->clause)->args ? list_length(((BoolExpr *) rinfo->clause)->args) : 0;
+	OrClauseGroup *restrict_info_entry = NULL;
+	ListCell	   *lc;
+	bool found;
+	List *result = NIL;
+
+	if(len_ors < 2)
+		return NIL;
+
+	foreach(lc, ((BoolExpr *) rinfo->orclause)->args)
+	{
+		RestrictInfo *sub_rinfo;
+		Expr		 *or_qual = (Expr *) lfirst(lc);
+
+		if(!IsA(lfirst(lc), RestrictInfo))
+			or_entries = lappend(or_entries, (void *) or_qual);
+		else
+		{
+			sub_rinfo = (RestrictInfo *) lfirst(lc);
+
+			/*
+			* Add the restrict_info_entry to the list.  It is needed exclusively to manage
+			* the problem with the order of transformed clauses in explain.
+			* Hash value can depend on the platform and version.  Hence,
+			* sequental scan of the hash table would prone to change the
+			* order of clauses in lists and, as a result, break regression
+			* tests accidentially.
+			*/
+			found = try_prepare_single_or(sub_rinfo, &appropriate_entries);
+
+			if (!found)
+			{
+				or_entries = lappend(or_entries, (void *) sub_rinfo->clause);
+			}
+		}
+	}
+
+	if (list_length(or_entries) == len_ors || (appropriate_entries == NIL && list_length(appropriate_entries) < 1))
+		return NIL;
+
+	found = false;
+
+	/* Let's convert each group of clauses to an ANY expression. */
+
+	/*
+	 * Go through the list of groups and convert each, where number of consts
+	 * more than 1. trivial groups move to OR-list again
+	 */
+
+	foreach(lc, appropriate_entries)
+	{
+		Oid			scalar_type;
+		Oid			array_type;
+		Node	   *newa = NULL;
+		HeapTuple	opertup;
+		Form_pg_operator operform;
+		ScalarArrayOpExpr *saopexpr = NULL;
+		Expr *candidate = NULL;
+		Expr *main_ors = NULL;
+
+		if (!IsA(lfirst(lc), OrClauseGroup))
+		{
+			Assert(0);
+		}
+
+		restrict_info_entry = (OrClauseGroup *) lfirst(lc);
+
+		Assert(list_length(restrict_info_entry->exprs) == list_length(restrict_info_entry->consts));
+
+		if (list_length(restrict_info_entry->consts) == 1)
+		{
+			/*
+			 * Only one element returns origin expression into the BoolExpr
+			 * args list unchanged.
+			 */
+			or_entries = list_concat(or_entries, (void *) restrict_info_entry->exprs);
+			continue;
+		}
+
+		scalar_type = restrict_info_entry->consttype;
+		array_type = OidIsValid(scalar_type) ? get_array_type(scalar_type) :
+			InvalidOid;
+
+		if (!OidIsValid(array_type))
+		{
+			or_entries = list_concat(or_entries, (void *) restrict_info_entry->exprs);
+			continue;
+		}
+
+		if (restrict_info_entry->have_param)
+		{
+			/*
+			* We need to construct an ArrayExpr given we have Param's not just
+			* Const's.
+			*/
+			ArrayExpr  *arexpr = makeNode(ArrayExpr);
+
+			/* array_collid will be set by parse_collate.c */
+			arexpr->element_typeid = scalar_type;
+			arexpr->array_typeid = array_type;
+			arexpr->multidims = false;
+			arexpr->elements = restrict_info_entry->consts;
+			arexpr->location = -1;
+
+			newa = (Node *) arexpr;
+		}
+		else
+		{
+			/* We have only Costs's.  Can generate constant array. */
+
+			int16		typlen;
+			bool		typbyval;
+			char		typalign;
+			Datum	   *elems;
+			int			i = 0;
+			ArrayType  *ar;
+			ListCell *lc1;
+
+			get_typlenbyvalalign(scalar_type, &typlen, &typbyval, &typalign);
+
+			elems = (Datum *) palloc(sizeof(Datum) * list_length(restrict_info_entry->consts));
+			foreach(lc1, restrict_info_entry->consts)
+			{
+				Node	   *elem = (Node *) lfirst(lc1);
+
+				elems[i++] = ((Const *) elem)->constvalue;
+			}
+
+			ar = construct_array(elems, i, scalar_type, typlen, typbyval, typalign);
+			newa = (Node *) makeConst(array_type, -1, restrict_info_entry->inputcollid, -1, PointerGetDatum(ar), false, false);
+
+			pfree(elems);
+		}
+
+		opertup = SearchSysCache1(OPEROID,
+								ObjectIdGetDatum(restrict_info_entry->opno));
+		if (!HeapTupleIsValid(opertup))
+			elog(ERROR, "cache lookup failed for operator %u", restrict_info_entry->opno);
+
+		operform = (Form_pg_operator) GETSTRUCT(opertup);
+
+		/* and build the expression node */
+		saopexpr = makeNode(ScalarArrayOpExpr);
+		saopexpr->opno = restrict_info_entry->opno;
+		saopexpr->opfuncid = operform->oprcode;
+		saopexpr->hashfuncid = InvalidOid;
+		saopexpr->negfuncid = InvalidOid;
+		saopexpr->useOr = true;
+		saopexpr->inputcollid = restrict_info_entry->inputcollid;
+		/* inputcollid will be set by parse_collate.c */
+		saopexpr->args = list_make2(restrict_info_entry->expr, newa);
+		saopexpr->location = -1;
+
+		Assert(list_length(restrict_info_entry->exprs) > 1);
+
+		main_ors = makeBoolExpr(OR_EXPR, restrict_info_entry->exprs, -1);
+
+		candidate = makeBoolExpr(AND_EXPR, list_make2(saopexpr, main_ors), -1);
+		//list_free(restrict_info_entry->consts);
+		result = lappend(result,  (void *) candidate);
+		ReleaseSysCache(opertup);
+	}
+	list_free(appropriate_entries);
+
+	/* One more trick: assemble correct clause */
+	if (result == NIL)
+		return NIL;
+	else
+	{
+		if (or_entries != NIL)
+			result = lappend(result, list_length(or_entries) > 1 ?
+											makeBoolExpr(OR_EXPR, or_entries,
+											((BoolExpr *) rinfo->clause)->location) :
+											linitial(or_entries));
+		return result;
+	}
+}
+
 /*
  * expand_indexqual_rowcompare --- expand a single indexqual condition
  *		that is a RowCompareExpr
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 14ccfc1ac1c..23da57b6d55 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -2708,6 +2708,37 @@ typedef struct RestrictInfo
 	Oid			right_hasheqoperator pg_node_attr(equal_ignore);
 } RestrictInfo;
 
+/*
+ * The group of similar operator expressions in transform_or_to_any().
+ */
+typedef struct OrClauseGroup
+{
+	pg_node_attr(nodetag_only)
+
+	NodeTag		type;
+
+	/* The expression of the variable side of operator */
+Expr	   *expr;
+	/* The operator of the operator expression */
+	Oid			opno;
+	/* The collation of the operator expression */
+	Oid			inputcollid;
+	/* The type of constant side of operator */
+	Oid			consttype;
+
+	/* The list of constant sides of operators */
+	List	   *consts;
+
+	/*
+	 * List of source expressions.  We need this for convenience in case we
+	 * will give up on transformation.
+	 */
+	List	   *exprs;
+
+	Node	   *const_expr;
+	bool have_param;
+} OrClauseGroup;
+
 /*
  * This macro embodies the correct way to test whether a RestrictInfo is
  * "pushed down" to a given outer join, that is, should be treated as a filter
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index cf6eac57349..c2b25936c8c 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1844,18 +1844,11 @@ DROP TABLE onek_with_null;
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
-                                                               QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
- Bitmap Heap Scan on tenk1
-   Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand = 42) AND (tenthous = 42)))
-   ->  BitmapOr
-         ->  Bitmap Index Scan on tenk1_thous_tenthous
-               Index Cond: ((thousand = 42) AND (tenthous = 1))
-         ->  Bitmap Index Scan on tenk1_thous_tenthous
-               Index Cond: ((thousand = 42) AND (tenthous = 3))
-         ->  Bitmap Index Scan on tenk1_thous_tenthous
-               Index Cond: ((thousand = 42) AND (tenthous = 42))
-(9 rows)
+                                  QUERY PLAN                                  
+------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+   Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(2 rows)
 
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -1864,14 +1857,166 @@ SELECT * FROM tenk1
       42 |    5530 |   0 |    2 |   2 |      2 |      42 |       42 |          42 |        42 |       42 |  84 |   85 | QBAAAA   | SEIAAA   | OOOOxx
 (1 row)
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+                                       QUERY PLAN                                       
+----------------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+   Index Cond: ((thousand = 42) AND (tenthous = ANY (ARRAY[1, (InitPlan 1).col1, 42])))
+   InitPlan 1
+     ->  Result
+(4 rows)
+
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4 
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+      42 |    5530 |   0 |    2 |   2 |      2 |      42 |       42 |          42 |        42 |       42 |  84 |   85 | QBAAAA   | SEIAAA   | OOOOxx
+(1 row)
+
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
-                                   QUERY PLAN                                    
----------------------------------------------------------------------------------
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 99)))
+         Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
+         ->  BitmapAnd
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 42)
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ count 
+-------
+    10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+                                  QUERY PLAN                                  
+------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+   Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(2 rows)
+
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4 
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+      42 |    5530 |   0 |    2 |   2 |      2 |      42 |       42 |          42 |        42 |       42 |  84 |   85 | QBAAAA   | SEIAAA   | OOOOxx
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
+         ->  BitmapAnd
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 42)
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ count 
+-------
+    10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+                                        QUERY PLAN                                        
+------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         Recheck Cond: ((hundred = 42) AND (thousand < ANY ('{42,99,43,42}'::integer[])))
+         ->  BitmapAnd
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 42)
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand < ANY ('{42,99,43,42}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+ count 
+-------
+    10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+                                               QUERY PLAN                                               
+--------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         Recheck Cond: (((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[]))) OR (thousand = 41))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[])))
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand = 41)
+(8 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+ count 
+-------
+    10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+                                                       QUERY PLAN                                                       
+------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         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 = 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)
+(16 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+ count 
+-------
+    20
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+                                                       QUERY PLAN                                                        
+-------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         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)
@@ -1879,11 +2024,13 @@ SELECT count(*) FROM tenk1
                      ->  Bitmap Index Scan on tenk1_thous_tenthous
                            Index Cond: (thousand = 42)
                      ->  Bitmap Index Scan on tenk1_thous_tenthous
-                           Index Cond: (thousand = 99)
-(11 rows)
+                           Index Cond: (thousand = 41)
+                     ->  Bitmap Index Scan on tenk1_thous_tenthous
+                           Index Cond: ((thousand = 99) AND (tenthous = 2))
+(13 rows)
 
 SELECT count(*) FROM tenk1
-  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
  count 
 -------
     10
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 53f70d72ed6..abe98ff3c53 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4278,15 +4278,64 @@ select * from tenk1 a join tenk1 b on
                      Index Cond: (hundred = 4)
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+               Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+               Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
                ->  BitmapOr
                      ->  Bitmap Index Scan on tenk1_unique1
                            Index Cond: (unique1 = 1)
                      ->  Bitmap Index Scan on tenk1_unique2
-                           Index Cond: (unique2 = 3)
+                           Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(18 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+  (a.unique1 = 1 and b.unique1 = 2) or
+  ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+                                                      QUERY PLAN                                                      
+----------------------------------------------------------------------------------------------------------------------
+ Nested Loop
+   Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
+   ->  Bitmap Heap Scan on tenk1 b
+         Recheck Cond: ((unique1 = 2) OR (hundred = 4))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on tenk1_unique1
+                     Index Cond: (unique1 = 2)
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 4)
+   ->  Materialize
+         ->  Bitmap Heap Scan on tenk1 a
+               Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+               Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+               ->  BitmapOr
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 1)
                      ->  Bitmap Index Scan on tenk1_unique2
-                           Index Cond: (unique2 = 7)
-(19 rows)
+                           Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(18 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+  (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+  ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+                                                                         QUERY PLAN                                                                          
+-------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Nested Loop
+   Join Filter: ((a.unique1 < 20) OR (a.unique1 = 3) OR ((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
+   ->  Seq Scan on tenk1 b
+   ->  Materialize
+         ->  Bitmap Heap Scan on tenk1 a
+               Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+               Filter: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+               ->  BitmapOr
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 < 20)
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 3)
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 1)
+                     ->  Bitmap Index Scan on tenk1_unique2
+                           Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(16 rows)
 
 --
 -- test placement of movable quals in a parameterized join tree
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index e296891cab8..f74ad415fbf 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -726,6 +726,24 @@ DROP TABLE onek_with_null;
 -- Check bitmap index path planning
 --
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -738,6 +756,30 @@ SELECT count(*) FROM tenk1
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
 
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+SELECT count(*) FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+
 --
 -- Check behavior with duplicate index column contents
 --
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index d81ff63be53..4473b8f04d5 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1433,6 +1433,15 @@ select * from tenk1 a join tenk1 b on
   (a.unique1 = 1 and b.unique1 = 2) or
   ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
 
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+  (a.unique1 = 1 and b.unique1 = 2) or
+  ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+  (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+  ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+
 --
 -- test placement of movable quals in a parameterized join tree
 --
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index b4d7f9217ce..992c80f9350 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1717,6 +1717,7 @@ NumericVar
 OM_uint32
 OP
 OSAPerGroupState
+OrClauseGroup
 OSAPerQueryState
 OSInfo
 OSSLCipher
-- 
2.34.1

---

From: Alexander Korotkov <[email-masked]>
Date: Sat, 27 Jul 2024 13:56:40 +0300

On Thu, Jul 25, 2024 at 5:04 PM Alena Rybakina
<[email-masked]> wrote:
> To be honest, I have found a big problem in this patch - we try to perform the transformation every time we examime a column:
>

What makes you think there is a problem?  Do you have a test case
illustrating a slow planning time?

When v27 performs transformation for a particular column, it just
stops facing the first unmatched OR entry.  So,
match_orclause_to_indexcol() examines just the first OR entry for all
the columns excepts at most one.  So, the check
match_orclause_to_indexcol() does is not much slower than other
match_*_to_indexcol() do.

I actually think this could help performance in many cases, not hurt
it.  At least we get rid of O(n^2) complexity over the number of OR
entries, which could be very many.

------
Regards,
Alexander Korotkov
Supabase

---

From: Alena Rybakina <[email-masked]>
Date: Sun, 28 Jul 2024 12:59:32 +0300

On 27.07.2024 13:56, Alexander Korotkov wrote:
> What makes you think there is a problem?

To be honest, I was bothered by the fact that we need to go through 
expressions several times that obviously will not fit under other 
conditions.
Just yesterday I thought that it would be worthwhile to create a list of 
candidates - expressions that did not fit because the column did not 
match the index (!match_index_to_operand(nconst_expr, indexcol, index)).

Another problem that is related to the first one that the boolexpr could 
contain expressions referring to different operands, for example, both x 
and y. that is, we may have the problem that the optimal "ANY" 
expression may not be used, because the expression with x may come 
earlier and the loop may end earlier.

alena@postgres=# create table b (x int, y int);
CREATE TABLE
alena@postgres=# insert into b select id, id from 
generate_series(1,1000) as id;
INSERT 0 1000
alena@postgres=# create index x_idx on b(x);
CREATE INDEX
alena@postgres=# analyze;
ANALYZE
alena@postgres=# explain select * from b where y =3 or x =4 or x=5 or 
x=6 or x = 7 or x=8 or x=9;
                                       QUERY PLAN
---------------------------------------------------------------------------------------
  Seq Scan on b  (cost=0.00..32.50 rows=7 width=8)
    Filter: ((y = 3) OR (x = 4) OR (x = 5) OR (x = 6) OR (x = 7) OR (x = 
8) OR (x = 9))
(2 rows)
alena@postgres=# explain select * from b where x =4 or x=5 or x=6 or x = 
7 or x=8 or x=9 or y=1;
                                       QUERY PLAN
---------------------------------------------------------------------------------------
  Seq Scan on b  (cost=0.00..32.50 rows=7 width=8)
    Filter: ((x = 4) OR (x = 5) OR (x = 6) OR (x = 7) OR (x = 8) OR (x = 
9) OR (y = 1))
(2 rows)
alena@postgres=# explain select * from b where x =4 or x=5 or x=6 or x = 
7 or x=8 or x=9;
                            QUERY PLAN
----------------------------------------------------------------
  Index Scan using x_idx on b  (cost=0.28..12.75 rows=6 width=8)
    Index Cond: (x = ANY ('{4,5,6,7,8,9}'::integer[]))
(2 rows)

Furthermore expressions can be stored in a different order.
For example, first comes "AND" expr, and then group of "OR" expr, which 
we can convert to "ANY" expr, but we won't do this due to the fact that 
we will exit the loop early, according to this condition:

if (!IsA(sub_rinfo->clause, OpExpr))
            return NULL;

or it may occur due to other conditions.

alena@postgres=# create index x_y_idx on b(x,y);
CREATE INDEX
alena@postgres=# analyze;
ANALYZE

alena@postgres=# explain select * from b where (x = 2 and y =3) or x =4 
or x=5 or x=6 or x = 7 or x=8 or x=9;
                                              QUERY PLAN
-----------------------------------------------------------------------------------------------------
  Seq Scan on b  (cost=0.00..35.00 rows=6 width=8)
    Filter: (((x = 2) AND (y = 3)) OR (x = 4) OR (x = 5) OR (x = 6) OR 
(x = 7) OR (x = 8) OR (x = 9))
(2 rows)

Because of these reasons, I tried to save this and that transformation 
together for each column and try to analyze for each expr separately 
which method would be optimal.

> Do you have a test case
No, I didn't have time to measure it and sorry for that. I'll do it.
> entries, which could be very many.

I agree with you that there is an overhead and your patch fixes this 
problem, but optimizer needs to have a good ordering of expressions for 
application.

I think we can try to move the transformation to another place where 
there is already a loop pass, and also save two options "OR" expr and 
"ANY" expr in one place (through BoolExpr) (like find_duplicate_ors 
function) and teach the optimizer to determine which option is better, 
for example, like now in match_orclause_to_indexcol() function.

What do you thing about it?

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 29 Jul 2024 05:36:57 +0300

> match the index (!match_index_to_operand(nconst_expr, indexcol, index)).

I admit that this area probably could use some optimization,
especially for case of many clauses and many indexes.  But in the
scope of this patch, I think this is enough to not make things worse
in this area.

> x=6 or x = 7 or x=8 or x=9;

Yes, with v27 of the patch, optimization wouldn't work in these cases.
However, you are using quite small table.  If you will use larger
table or disable sequential scans, there would be bitmap plans to
handle these queries.  So, v27 doesn't make the situation worse. It
just doesn't optimize all that it could potentially optimize and
that's OK.

I've written a separate 0002 patch to address this.  Now, before
generation of paths for bitmap OR, similar OR entries are grouped
together.  When considering a group of similar entries, they are
considered both together and one-by-one.  Ideally we could consider
more sophisticated grouping, but that seems fine for now.  You can
check how this patch handles the cases of above.

Also, 0002 address issue of duplicated bitmap scan conditions in
different forms. During generate_bitmap_or_paths() we need to exclude
considered condition for other clauses.  It couldn't be as normal
filtered out in the latter stage, because could reach the index in
another form.

> What do you thing about it?

find_duplicate_ors() and similar places were already tried before.
Please, check upthread.  This approach receives severe critics. AFAIU,
the problem is that find_duplicate_ors() during preprocessing, a
cost-blind stage.

This is why I'd like to continue developing ideas of v27, because it
fits the existing framework.

------
Regards,
Alexander Korotkov
Supabase