MIME-Version: 1.0
References: <567ED6CA.2040504@sigaev.ru> <CAB-JLwb7NQHUdrc9_coV+kKGYF7hBb+XktY6TkYj4aejCqF9DQ@mail.gmail.com>
 <eddaa746-d02c-35a6-561b-e9f371920b91@yandex.ru> <CAH2-WzmD5u5kCZG0qMtVySz8VB1_drOiX=j0buDufK-EJc3YkQ@mail.gmail.com>
 <7829312a-eb6b-b9ba-9719-71c9bc410884@yandex.ru> <CAH2-WzkzzDK7FPEv7M5GL_jo0E81DDG41t7wHU9SOAwnqwX=eQ@mail.gmail.com>
 <9ea35f18-419d-efb7-b7c8-2e641a61f020@yandex.ru> <CAH2-Wzm-W7KYtMQ_3F1zU3Fg0zhRd-kASuOzNewXEWjR5kZrtg@mail.gmail.com>
 <08f5ff34-1497-2123-8701-461a299035c9@yandex.ru> <CAH2-WznHNTXQ=bX4Kc9hHebyXvR0a0CxH9OnirkP0ahgQAX7Aw@mail.gmail.com>
 <8d714510-af73-a908-99c8-fc14536f2669@yandex.ru> <CAH2-WzkNaPbBJ_yWDXzk5ESJZH62vi=+brHHQ2SrDrPXka1xYA@mail.gmail.com>
 <b301dce1-09fd-72b1-834a-527ca428db5e@yandex.ru> <CAH2-WzmG-+vvN6YEh4J_j3-Q1Yn=HRrjDrz2HDhttPcLVqN0rw@mail.gmail.com>
 <bf504287-c3ac-e492-c6ea-31be60b2c92f@yandex.ru> <CAH2-WzkmLg0JPXkZ75b+ha_wJGoJk3QyZ6aUjA0Ba11rdPwdgw@mail.gmail.com>
 <fa5f57e1-4051-93d8-5f54-f1e2f4587cc2@yandex.ru> <4bac271d-1700-db24-74ac-8414f2baf9fd@postgrespro.ru>
In-Reply-To: <4bac271d-1700-db24-74ac-8414f2baf9fd@postgrespro.ru>
From: Peter Geoghegan <pg@bowt.ie>
Date: Sun, 20 Aug 2023 15:11:24 -0700
Message-ID: <CAH2-Wzkp1RYWC4Lsh==ALNeOR=gQEtCMVbcFRLa-faMQe6YRPA@mail.gmail.com>
Subject: Re: POC, WIP: OR-clause support for indexes
To: "a.rybakina" <a.rybakina@postgrespro.ru>
Cc: "Finnerty, Jim" <jfinnert@amazon.com>, Marcos Pegoraro <marcos@f10.com.br>, 
	Andrey Lepikhov <a.lepikhov@postgrespro.ru>, pgsql-hackers@postgresql.org, teodor@sigaev.ru, 
	Ranier Vilela <ranier.vf@gmail.com>, Tomas Vondra <tomas.vondra@enterprisedb.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://www.postgresql.org/message-id/CAH2-Wzkp1RYWC4Lsh%3D%3DALNeOR%3DgQEtCMVbcFRLa-faMQe6YRPA%40mail.gmail.com>
Precedence: bulk

On Thu, Aug 17, 2023 at 3:08=E2=80=AFAM a.rybakina <a.rybakina@postgrespro.=
ru> wrote:
> This is an interesting feature. I didn't notice this function before, I s=
tudied 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 di=
dn't solve my problem with calculating selectivity. I'll reconsider it agai=
n, maybe I can find something I missed.

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.

--=20
Peter Geoghegan