MIME-Version: 1.0
References: <567ED6CA.2040504@sigaev.ru> <CACJufxFMFoosvbuFYDiFtpam4sKCSGJeh5jYiZSY8PHjCpEHYA@mail.gmail.com>
 <cf0d1615-b594-404d-9a23-3d8ffd9070ec@postgrespro.ru> <CAEudQAq4XTcwhw2OmfW1AJNqvMfbReEWjuzqv6YTz6ZjbpmL0g@mail.gmail.com>
 <21088129-7cd3-424a-bcce-6a3427ba3276@postgrespro.ru> <CAEudQArk002t_C9LGoeJWnw=iGKikt+gSa8Mh==muG00WS=qYA@mail.gmail.com>
 <CACJufxFhQn0awSEcZD7=FHvjx6OLt6PUtuoi0_10pWFVXUEDJw@mail.gmail.com>
 <ded629b2-7885-4be2-b5f5-9426ff47f72c@postgrespro.ru> <11ee9c04-281f-43c8-a0ff-d481c1e01c09@postgrespro.ru>
 <CACJufxGqLA32zTtaJRL2Cacp771k6PJnau7gsax0KRV434Qq7w@mail.gmail.com>
 <54009ba5-4aea-4344-a30d-e3558a59e2a9@postgrespro.ru> <380e5683-cdfd-4220-ab9b-7cccb9d3e480@postgrespro.ru>
 <CACJufxE6eG3ATnTfO9ubs7CjyfgjpCQrSt85oU33EZj00PdcbQ@mail.gmail.com>
 <e394ac5b-7ae2-4f64-a8ff-51fc934bba3e@postgrespro.ru> <d5d3f257-a2d8-4776-9c97-83f98e74636c@postgrespro.ru>
 <CAPpHfdtACtU_XbuNf9mgDBsTH1cN=i+uASXKBX_rvQk6zQ3MdQ@mail.gmail.com> <7389d0dd-05d5-41b7-a12d-2e73f939f851@postgrespro.ru>
In-Reply-To: <7389d0dd-05d5-41b7-a12d-2e73f939f851@postgrespro.ru>
From: Alexander Korotkov <aekorotkov@gmail.com>
Date: Mon, 11 Mar 2024 13:31:12 +0200
Message-ID: <CAPpHfdsAWGF2VvcszNofc32Sa2pefBpgY1nw2aYV=FTG7Q3wyA@mail.gmail.com>
Subject: Re: POC, WIP: OR-clause support for indexes
To: Andrei Lepikhov <a.lepikhov@postgrespro.ru>
Cc: jian he <jian.universality@gmail.com>, Alena Rybakina <a.rybakina@postgrespro.ru>, 
	Robert Haas <robertmhaas@gmail.com>, pgsql-hackers@postgresql.org, 
	Peter Geoghegan <pg@bowt.ie>, "Finnerty, Jim" <jfinnert@amazon.com>, Marcos Pegoraro <marcos@f10.com.br>, teodor@sigaev.ru, 
	Tomas Vondra <tomas.vondra@enterprisedb.com>, Peter Eisentraut <peter@eisentraut.org>, 
	Ranier Vilela <ranier.vf@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://www.postgresql.org/message-id/CAPpHfdsAWGF2VvcszNofc32Sa2pefBpgY1nw2aYV%3DFTG7Q3wyA%40mail.gmail.com>
Precedence: bulk

Hi Andrei,

Thank you for your response.

On Mon, Mar 11, 2024 at 7:13=E2=80=AFAM Andrei Lepikhov
<a.lepikhov@postgrespro.ru> wrote:
> On 7/3/2024 21:51, Alexander Korotkov wrote:
> > Hi!
> >
> > On Tue, Mar 5, 2024 at 9:59=E2=80=AFAM Andrei Lepikhov
> > <a.lepikhov@postgrespro.ru <mailto:a.lepikhov@postgrespro.ru>> wrote:
> >  > On 5/3/2024 12:30, Andrei Lepikhov wrote:
> >  > > On 4/3/2024 09:26, jian he wrote:
> >  > ... and the new version of the patchset is attached.
> >
> > I made some revisions for the patchset.
> Great!
> > 1) Use hash_combine() to combine hash values.
> Looks better
> > 2) Upper limit the number of array elements by MAX_SAOP_ARRAY_SIZE.
>
> I'm not convinced about this limit. The initial reason was to combine
> long lists of ORs into the array because such a transformation made at
> an early stage increases efficiency.
> I understand the necessity of this limit in the array decomposition
> routine but not in the creation one.

The comment near MAX_SAOP_ARRAY_SIZE says that this limit is because
N^2 algorithms could be applied to arrays.  Are you sure that's not
true for our case?

> > 3) Better save the original order of clauses by putting hash entries an=
d
> > untransformable clauses to the same list.  A lot of differences in
> > regression tests output have gone.
> I agree that reducing the number of changes in regression tests looks
> better. But to achieve this, you introduced a hack that increases the
> complexity of the code. Is it worth it? Maybe it would be better to make
> one-time changes in tests instead of getting this burden on board. Or
> have you meant something more introducing the node type?

For me the reason is not just a regression test.  The current code
keeps the original order of quals as much as possible.  The OR
transformation code reorders quals even in cases when it doesn't
eventually apply any optimization.  I don't think that's acceptable.
However, less hackery ways for this is welcome for sure.

> > We don't make array values unique.  That might make query execution
> > performance somewhat worse, and also makes selectivity estimation
> > worse.  I suggest Andrei and/or Alena should implement making array
> > values unique.
> The fix Alena has made looks correct. But I urge you to think twice:
> The optimizer doesn't care about duplicates, so why do we do it?
> What's more, this optimization is intended to speed up queries with long
> OR lists. Using the list_append_unique() comparator on such lists could
> impact performance. I suggest sticking to the common rule and leaving
> the responsibility on the user's shoulders.

I don't see why the optimizer doesn't care about duplicates for OR
lists.  As I showed before in an example, it successfully removes the
duplicate.  So, currently OR transformation clearly introduces a
regression in terms of selectivity estimation.  I think we should
evade that.

> At least, we should do this optimization later, in one pass, with
> sorting elements before building the array. But what if we don't have a
> sort operator for the type?

It was probably discussed before, but can we do our work later?  There
is a canonicalize_qual() which calls find_duplicate_ors().  This is
the place where currently duplicate OR clauses are removed.  Could our
OR-to-ANY transformation be just another call from
canonicalize_qual()?

------
Regards,
Alexander Korotkov