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

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)