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

Thank you for your interest in this problem and help, and I'm sorry that I didn't respond to this email for a long time. To be honest, I wanted to investigate the problems in more detail and already answer more clearly, but unfortunately I have not found anything more significant yet.

There was actually support for OR lists in index AMs prior to
ScalarArrayOpExpr. Even though ScalarArrayOpExpr don't really seem all
that related to bitmap scans these days (since at least nbtree knows
how to execute them "natively"), that wasn't always the case.
ScalarArrayOpExpr were invented the same year that bitmap index scans
were first added (2005), and seem more or less related to that work.
See commits bc843d39, 5b051852, 1e9a6ba5, and 290166f9 (all from
2005). Particularly the last one, which has a commit message that
heavily suggests that my interpretation is correct.

Back in 2003, commit 9888192f removed (or at least simplified) what
were then called "CNF/DNF CONVERSION ROUTINES". Prior to that point
the optimizer README had something about leaving clause lists
un-normalized leading to selectivity estimation problems. Bear in mind
that this is a couple of years before ScalarArrayOpExpr was first
invented. Apparently even back then "The OR-of-ANDs format is useful
for indexscan implementation". It's possible that that old work will
offer some hints on what to do now.
In a way it's not surprising that work in this area would have some
impact on selectivies. The surprising part is the extent of the
problem, I suppose.

I see that a lot of the things in this area are just used by BitmapOr
clauses, such as build_paths_for_OR() -- but you're not necessarily
able to use any of that stuff. Also, choose_bitmap_and() has some
stuff about how it compensates to avoid "too-small selectivity that
makes a redundant AND step look like it reduces the total cost". It
also mentions some problems with match_join_clauses_to_index() +
extract_restriction_or_clauses(). Again, this might be a good place to
look for more clues.

I agree with your assumption about looking at the source of the error related to selectivity in these places. But honestly, no matter how many times I looked, until enough sensible thoughts appeared, which could cause a problem. I keep looking, maybe I'll find something.

 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)

I think that we currently over-rely on BitmapOr for OR clauses. It's
useful that they're so general, of course, but ISTM that we shouldn't
even try to use a BitmapOr in simple cases. Things like the "WHERE
thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42)"
tenk1 query that you brought up probably shouldn't even have a
BitmapOr path (which I guess they don't with you patch). Note that I
recently discussed the same query at length with Tomas Vondra on the
ongoing thread for his index filter patch (you probably knew that
already).

I think so too, but it's still quite difficult to find a stable enough optimization to implement this, in my opinion. But I will finish the current optimization with OR->ANY, given that something interesting has appeared.