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

I'm sorry I didn't write for a long time, but I really had a very
difficult month, now I'm fully back to work.

*I was able to implement the patches to the end and moved the
transformation of "OR" expressions to ANY.* I haven't seen a big
difference between them yet, one has a transformation before calculating
selectivity (v7.1-Replace-OR-clause-to-ANY.patch), the other after
(v7.2-Replace-OR-clause-to-ANY.patch). Regression tests are passing, I
don't see any problems with selectivity, nothing has fallen into the
coredump, but I found some incorrect transformations. What is the reason
for these inaccuracies, I have not found, but, to be honest, they look
unusual). Gave the error below.

In the patch, I don't like that I had to drag three libraries from
parsing until I found a way around it.The advantage of this approach
compared to the other ([1]) is that at this stage all possible or
transformations are performed, compared to the patch, where the
transformation was done at the parsing stage. That is, here, for
example, there are such optimizations in the transformation:

I took the common element out of the bracket and the rest is converted
to ANY, while, as noted by Peter Geoghegan, we did not have several
bitmapscans, but only one scan through the array.

postgres=# explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 AND prolang=1 OR prolang = 13 AND prolang = 2 OR
prolang = 13 AND prolang = 3;
                                              QUERY PLAN
-------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..151.66 rows=1 width=68) (actual
time=1.167..1.168 rows=0 loops=1)
   Filter: ((prolang = '13'::oid) AND (prolang = ANY (ARRAY['1'::oid,
'2'::oid, '3'::oid])))
   Rows Removed by Filter: 3302
 Planning Time: 0.146 ms
 Execution Time: 1.191 ms
(5 rows)

*While I was testing, I found some transformations that don't work,
although in my opinion, they should:**
**
**1. First case:*
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 AND prolang=1 OR prolang = 2 AND prolang = 2 OR
prolang = 13 AND prolang = 13;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..180.55 rows=2 width=68) (actual
time=2.959..3.335 rows=89 loops=1)
   Filter: (((prolang = '13'::oid) AND (prolang = '1'::oid)) OR
((prolang = '2'::oid) AND (prolang = '2'::oid)) OR ((prolang =
'13'::oid) AND (prolang = '13'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 1.278 ms
 Execution Time: 3.486 ms
(5 rows)

Should have left only prolang = '13'::oid:

                                              QUERY PLAN
-------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..139.28 rows=1 width=68) (actual
time=2.034..2.034 rows=0 loops=1)
   Filter: ((prolang = '13'::oid ))
   Rows Removed by Filter: 3302
 Planning Time: 0.181 ms
 Execution Time: 2.079 ms
(5 rows)

*2. Also does not work:*
postgres=# explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.422..2.686 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR ((prolang = '2'::oid) AND (prolang
= '2'::oid)) OR (prolang = '13'::oid))
   Rows Removed by Filter: 3213
 Planning Time: 1.370 ms
 Execution Time: 2.799 ms
(5 rows)

Should have left:
Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))

*3. Or another:*

explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.350..2.566 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR ((prolang
= '2'::oid) AND (prolang = '2'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 0.215 ms
 Execution Time: 2.624 ms
(5 rows)

Should have left:
Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))

*Falls into coredump at me:*
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;

explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.350..2.566 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR ((prolang
= '2'::oid) AND (prolang = '2'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 0.215 ms
 Execution Time: 2.624 ms

(5 rows)

I remind that initially the task was to find an opportunity to optimize
the case of processing a large number of "or" expressions to optimize
memory consumption. The FlameGraph for executing 50,000 "or"
expressionshas grown 1.4Gb and remains in this state until exiting the
psql session (flamegraph1.png) and it sagged a lot in execution time. If
this case is converted to ANY, the query is executed much faster and
memory is optimized (flamegraph2.png). It may be necessary to use this
approach if there is no support for the framework to process ANY, IN
expressions.

Peter Geoghegan also noticed some development of this patch in terms of
preparing some transformations to optimize the query at the stage of its
execution [0].

[0]
https://www.postgresql.org/message-id/CAH2-Wz%3D9N_4%2BEyhtyFqYQRx4OgVbP%2B1aoYU2JQPVogCir61ZEQ%40mail.gmail.com

[1]
https://www.postgresql.org/message-id/attachment/149105/v7-Replace-OR-clause-to-ANY-expressions.patch