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

Sorry, I didn't write correctly enough, about the second second place in
the code where the conversion works well enough is the removal of
duplicate OR expressions.

I attached patch to learn it in more detail.

On 17.08.2023 13:08, a.rybakina wrote:
> Hi, all!
>>> The optimizer will itself do a limited form of "normalizing to CNF".
>>> Are you familiar with extract_restriction_or_clauses(), from
>>> orclauses.c? Comments above the function have an example of how this
>>> can work:
>>>
>>>   * Although a join clause must reference multiple relations overall,
>>>   * an OR of ANDs clause might contain sub-clauses that reference
>>> just one
>>>   * relation and can be used to build a restriction clause for that
>>> rel.
>>>   * For example consider
>>>   *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
>>>   * We can transform this into
>>>   *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
>>>   *          AND (a.x = 42 OR a.x = 44)
>>>   *          AND (b.y = 43 OR b.z = 45);
>>>   * which allows the latter clauses to be applied during the scans
>>> of a and b,
>>>   * perhaps as index qualifications, and in any case reducing the
>>> number of
>>>   * rows arriving at the join.  In essence this is a partial
>>> transformation to
>>>   * CNF (AND of ORs format).  It is not complete, however, because
>>> we do not
>>>   * unravel the original OR --- doing so would usually bloat the
>>> qualification
>>>   * expression to little gain.
>> This is an interesting feature. I didn't notice this function before,
>> I studied many times consider_new_or_cause, which were called there.
>> As far as I know, there is a selectivity calculation going on there,
>> but as far as I remember, I called it earlier after my conversion,
>> and unfortunately it didn't solve my problem with calculating
>> selectivity. I'll reconsider it again, maybe I can find something I
>> missed.
>>> Of course this immediately makes me wonder: shouldn't your patch be
>>> able to perform an additional transformation here? You know, by
>>> transforming "a.x = 42 OR a.x = 44" into "a IN (42, 44)"? Although I
>>> haven't checked for myself, I assume that this doesn't happen right
>>> now, since your patch currently performs all of its transformations
>>> during parsing.
>>>
>>> I also noticed that the same comment block goes on to say something
>>> about "clauselist_selectivity's inability to recognize redundant
>>> conditions". Perhaps that is relevant to the problems you were having
>>> with selectivity estimation, back when the code was in
>>> preprocess_qual_conditions() instead? I have no reason to believe that
>>> there should be any redundancy left behind by your transformation, so
>>> this is just one possibility to consider.
>>> Separately, the commit message of commit 25a9e54d2d says something
>>> about how the planner builds RestrictInfos, which seems
>>> possibly-relevant. That commit enhanced extended statistics for OR
>>> clauses, so the relevant paragraph describes a limitation of extended
>>> statistics with OR clauses specifically. I'm just guessing, but it
>>> still seems like it might be relevant to the problem you ran into with
>>> selectivity estimation. Another possibility to consider.
>>
>> I understood what is said about AND clauses in this comment. It seems
>> to me that AND clauses saved like (BoolExpr *)
>> expr->args->(RestrictInfo *) clauseA->(RestrictInfo *)clauseB lists
>> and OR clauses saved like (BoolExpr *) expr ->
>> orclause->(RestrictInfo *)clause A->(RestrictInfo *)clause B.
>>
>> As I understand it, selectivity is calculated for each expression.
>> But I'll exploring it deeper, because I think this place may contain
>> the answer to the question, what's wrong with selectivity calculation
>> in my patch.
>
> I could move transformation in there (extract_restriction_or_clauses)
> and didn't have any problem with selectivity calculation, besides it
> also works on the redundant or duplicates stage. So, it looks like:
>
> CREATE TABLE tenk1 (unique1 int, unique2 int, ten int, hundred int);
> insert into tenk1 SELECT x,x,x,x FROM generate_series(1,50000) as x;
> CREATE INDEX a_idx1 ON tenk1(unique1); CREATE INDEX a_idx2 ON
> tenk1(unique2); CREATE INDEX a_hundred ON tenk1(hundred);
>
> explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3
> or a.unique2 = 7));
>
> PLAN
> ------------------------------------------------------------------------------------------------------------------------------
> Nested Loop (cost=0.29..2033.62 rows=100000 width=32) (actual
> time=0.090..60.258 rows=100000 loops=1) -> Seq Scan on tenk1 b
> (cost=0.00..771.00 rows=50000 width=16) (actual time=0.016..9.747
> rows=50000 loops=1) -> Materialize (cost=0.29..12.62 rows=2 width=16)
> (actual time=0.000..0.000 rows=2 loops=50000) -> Index Scan using
> a_idx2 on tenk1 a (cost=0.29..12.62 rows=2 width=16) (actual
> time=0.063..0.068 rows=2 loops=1) Index Cond: (unique2 = ANY (ARRAY[3,
> 7])) Planning Time: 8.257 ms Execution Time: 64.453 ms (7 rows)
>
> Overall, this was due to incorrectly defined types of elements in the
> array, and if we had applied the transformation with the definition of
> the tup operator, we could have avoided such problems (I used
> make_scalar_array_op and have not yet found an alternative to this).
>
> When I moved the transformation on the index creation stage, it
> couldn't work properly and as a result I faced the same problem of
> selectivity calculation. I supposed that the selectivity values are
> also used there, and not recalculated all over again. perhaps we can
> solve this by forcibly recalculating the selectivity values, but I
> foresee other problems there.
>
> explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3
> or a.unique2 = 7));
>
> QUERY PLAN
> -----------------------------------------------------------------------------------------------------------------------------------
> Nested Loop (cost=12.58..312942.91 rows=24950000 width=32) (actual
> time=0.040..47.582 rows=100000 loops=1) -> Seq Scan on tenk1 b
> (cost=0.00..771.00 rows=50000 width=16) (actual time=0.009..7.039
> rows=50000 loops=1) -> Materialize (cost=12.58..298.16 rows=499
> width=16) (actual time=0.000..0.000 rows=2 loops=50000) -> Bitmap Heap
> Scan on tenk1 a (cost=12.58..295.66 rows=499 width=16) (actual
> time=0.025..0.028 rows=2 loops=1) Recheck Cond: ((unique2 = 3) OR
> (unique2 = 7)) Heap Blocks: exact=1 -> BitmapOr (cost=12.58..12.58
> rows=500 width=0) (actual time=0.023..0.024 rows=0 loops=1) -> Bitmap
> Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual
> time=0.019..0.019 rows=1 loops=1) Index Cond: (unique2 = 3) -> Bitmap
> Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual
> time=0.003..0.003 rows=1 loops=1) Index Cond: (unique2 = 7) Planning
> Time: 0.401 ms Execution Time: 51.350 ms (13 rows)
>
> I have attached a diff file so far, but it is very raw and did not
> pass all regression tests (I attached regression.diff) and even had
> bad conversion cases (some of the cases did not work at all, in other
> cases there were no non-converted nodes). But now I see an interesting
> transformation, which was the most interesting for me.
>
> 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 (ARRAY[1, 3, 42]))) +(2 rows)
>