Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1qapYN-00AUSw-H9 for pgsql-hackers@arkaria.postgresql.org; Tue, 29 Aug 2023 03:38:08 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1qapYM-002Bd6-2f for pgsql-hackers@arkaria.postgresql.org; Tue, 29 Aug 2023 03:38:05 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1qapYL-002Ap9-Hb for pgsql-hackers@lists.postgresql.org; Tue, 29 Aug 2023 03:38:05 +0000 Received: from mail.postgrespro.ru ([93.174.131.139]) by magus.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1qapYB-001etB-8h for pgsql-hackers@postgresql.org; Tue, 29 Aug 2023 03:38:01 +0000 Received: from [192.168.43.178] (unknown [176.59.172.122]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) (Authenticated sender: a.rybakina@postgrespro.ru) by mail.postgrespro.ru (Postfix/587) with ESMTPSA id 60E48E20E97; Tue, 29 Aug 2023 06:37:53 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mx2023; t=1693280273; bh=uLDbdzJmBjsYrZXhDyyu098wzFqUS1mDBGy7tUNOY9g=; h=Message-ID:Date:User-Agent:From:Subject:To:Cc:References: In-Reply-To:From; b=p0oG5im/8Ssk3H0qragyWQRKUQfhx9zL0ISjdAICi1XBjchwhZglHpUxUuaHGSXp2 jHqsc9z+erzopV4M+v/e4hAXfrQkqICUBUmLpzexyAshiTMqjZ4ZH3S1OsQ0IcuUPS +SF91FX7UukwfZ9laldIG3eRqJ3qF19YiJLmpM2yjLTLHW5B9xdayUpYe+kh4emEXw cg/DEKuIgTYMwEM9lTYzCfG12zsGT1PQ1CCfJJHBldLClpF9gE6YjLeUF5D5Rg5NDX XWK87xIJ9aD7XMubN0JhCO3u8qrFjT5QA1EVST+yt5Lqz3mDfONqi5N9Ykb9S6ftN7 CxUQEhtyuJ2Lw== Content-Type: multipart/alternative; boundary="------------3RJsWfX3B6DlmJJvXVpUYUp3" Message-ID: Date: Tue, 29 Aug 2023 06:37:51 +0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.13.0 From: "a.rybakina" Subject: Re: POC, WIP: OR-clause support for indexes To: Peter Geoghegan Cc: "Finnerty, Jim" , Marcos Pegoraro , Andrey Lepikhov , pgsql-hackers@postgresql.org, teodor@sigaev.ru, Ranier Vilela , Tomas Vondra References: <567ED6CA.2040504@sigaev.ru> <7829312a-eb6b-b9ba-9719-71c9bc410884@yandex.ru> <9ea35f18-419d-efb7-b7c8-2e641a61f020@yandex.ru> <08f5ff34-1497-2123-8701-461a299035c9@yandex.ru> <8d714510-af73-a908-99c8-fc14536f2669@yandex.ru> <4bac271d-1700-db24-74ac-8414f2baf9fd@postgrespro.ru> Content-Language: en-US In-Reply-To: List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk This is a multi-part message in MIME format. --------------3RJsWfX3B6DlmJJvXVpUYUp3 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit 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. --------------3RJsWfX3B6DlmJJvXVpUYUp3 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 7bit

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.

--------------3RJsWfX3B6DlmJJvXVpUYUp3--