public inbox for [email protected]
help / color / mirror / Atom feedFrom: a.rybakina <[email protected]>
To: Peter Geoghegan <[email protected]>
Cc: Finnerty, Jim <[email protected]>
Cc: Marcos Pegoraro <[email protected]>
Cc: Andrey Lepikhov <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: Ranier Vilela <[email protected]>
Cc: Tomas Vondra <[email protected]>
Subject: Re: POC, WIP: OR-clause support for indexes
Date: Tue, 29 Aug 2023 06:37:51 +0300
Message-ID: <[email protected]> (raw)
In-Reply-To: <CAH2-Wz=rJOP_1niMTSN_=pzKXUu5tAGRYMGj6uC6Xx=XzkgdPg@mail.gmail.com>
References: <[email protected]>
<[email protected]>
<CAH2-WzkzzDK7FPEv7M5GL_jo0E81DDG41t7wHU9SOAwnqwX=eQ@mail.gmail.com>
<[email protected]>
<CAH2-Wzm-W7KYtMQ_3F1zU3Fg0zhRd-kASuOzNewXEWjR5kZrtg@mail.gmail.com>
<[email protected]>
<CAH2-WznHNTXQ=bX4Kc9hHebyXvR0a0CxH9OnirkP0ahgQAX7Aw@mail.gmail.com>
<[email protected]>
<CAH2-WzkNaPbBJ_yWDXzk5ESJZH62vi=+brHHQ2SrDrPXka1xYA@mail.gmail.com>
<[email protected]>
<CAH2-WzmG-+vvN6YEh4J_j3-Q1Yn=HRrjDrz2HDhttPcLVqN0rw@mail.gmail.com>
<[email protected]>
<CAH2-WzkmLg0JPXkZ75b+ha_wJGoJk3QyZ6aUjA0Ba11rdPwdgw@mail.gmail.com>
<[email protected]>
<[email protected]>
<CAH2-Wzkp1RYWC4Lsh==ALNeOR=gQEtCMVbcFRLa-faMQe6YRPA@mail.gmail.com>
<CAH2-Wz=rJOP_1niMTSN_=pzKXUu5tAGRYMGj6uC6Xx=XzkgdPg@mail.gmail.com>
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.
On 21.08.2023 01:26, Peter Geoghegan wrote:
> 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.
view thread (33+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: POC, WIP: OR-clause support for indexes
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox