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 1sUAS6-000xpl-N4 for pgsql-hackers@arkaria.postgresql.org; Wed, 17 Jul 2024 19:36:38 +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 1sUAS4-004ese-0C for pgsql-hackers@arkaria.postgresql.org; Wed, 17 Jul 2024 19:36:36 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1sUAS3-004esV-Dj for pgsql-hackers@lists.postgresql.org; Wed, 17 Jul 2024 19:36:36 +0000 Received: from mail-yb1-xb30.google.com ([2607:f8b0:4864:20::b30]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1sUAS0-0004Vf-DH for pgsql-hackers@postgresql.org; Wed, 17 Jul 2024 19:36:34 +0000 Received: by mail-yb1-xb30.google.com with SMTP id 3f1490d57ef6-e0365588ab8so69282276.1 for ; Wed, 17 Jul 2024 12:36:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1721244991; x=1721849791; darn=postgresql.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=ZsDBFHOtPr+8HFndTlJvk9qPbzCVPZbINgEKT8+txks=; b=kPPH8JREqoAFzzxuK/0scXGToBCc781toxu7izYMmBIC6WjzRraCdu+KOWKYhK3Xdn RFQQRNENmxjLYEFiM9mXwk1mjvpReOLeyiZGIj9x9nLowqrwqZyPWE0zvrsdIhGyDGWj 48qzG7r2xmpPOXbn75FafnpSyHmn8hDJ4zM/lDWJRVCncEb4zlYZG6R4Vi4/OBgY3IGz yoMDzJ/ZucXbbtzrybfffDwWwlsViefBQYWYewTEilfvnsaf+Suubx+ayC24SAXcNyEn Mwv4gmtwxTQht/iQekttHlpMr86lN7N/Hzr6gzpotetvrozC799BYLSF8pc6F5nYxyTx Wptw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721244991; x=1721849791; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=ZsDBFHOtPr+8HFndTlJvk9qPbzCVPZbINgEKT8+txks=; b=rxgJxJlAeCp+NW9b97r56HuBkupWIvLRKVlPPbFJP1ly4/eh3EcbAIaYXWKD/RYryB pdj6AHmFzc3RLpSf4HOXsonRphTyO/5JBRG5PGYRAc+y9hk6H9FMq3SP8gf/oRyde0Ge GvGyH/bYa7eGTDz1Rd7xml9nJFr/nyg1gspudBElKZV/q8Uyxv2u85KUI+zstHmzLvSf iGcd9JihzCV48oTZdi31tOuH81pEyGXKFVaHP9cw6zXThG/wxyjdzT4p70ZDFgqePGLL AVc8a9TojUtRkSPpKNKlPVbYsgDSN6+9+v4MonYb27j9G2MV0RYxxUqBSFUXLTd+DL6V CiHA== X-Forwarded-Encrypted: i=1; AJvYcCVbEkHbSiv0ICiWWN39DlamL3fm/DTWMb67z1CLO3W2I9COEhXDXGshexwVUbw1YdSCPFTvh1IfD/cNiaqz7mjegCSq3edHU8J2zJrQ X-Gm-Message-State: AOJu0YxTiloY5kZHk1yTjDfWWLpCmLZNZnelcfcu5D3ZlGiHcsNk6xGP xgZDvUaD9do/hQV5LHQlE9fOYAnKYUawERKsgMYM5t9acrbtAytEFnWt1BN7HQtdMEaWnKyZvTE KqNWj8FBC8LrVkSKD8RGBOn8OVOk= X-Google-Smtp-Source: AGHT+IE6xzRKAl33SQZA3inVmj+5fGJXEuPynJJsvfjiKOnWmX/15vqCpZtHLnmcmo3Dqgg89bhL0RvVAEQ1+e1jMTo= X-Received: by 2002:a05:6902:1690:b0:e02:b580:d0e with SMTP id 3f1490d57ef6-e05ed7bd062mr3545698276.52.1721244991009; Wed, 17 Jul 2024 12:36:31 -0700 (PDT) MIME-Version: 1.0 References: <567ED6CA.2040504@sigaev.ru> <196b44d5-f4e5-41a0-9a8f-9fbf26a13760@postgrespro.ru> <9736220.CDJkKcVGEf@thinkpad-pgpro> <2193851.QkHrqEjB74@thinkpad-pgpro> <3b9bb831-da52-4779-8f3e-f8b6b83ba41f@postgrespro.ru> In-Reply-To: From: Alexander Korotkov Date: Wed, 17 Jul 2024 22:36:19 +0300 Message-ID: Subject: Re: POC, WIP: OR-clause support for indexes To: Alena Rybakina Cc: Nikolay Shaplov , pgsql-hackers@lists.postgresql.org, Andrei Lepikhov , jian he , Robert Haas , pgsql-hackers@postgresql.org, Peter Geoghegan , "Finnerty, Jim" , Marcos Pegoraro , teodor@sigaev.ru, Tomas Vondra , Peter Eisentraut , Ranier Vilela Content-Type: multipart/alternative; boundary="00000000000042bb60061d76943a" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --00000000000042bb60061d76943a Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi, Alena! On Wed, Jul 17, 2024 at 3:53=E2=80=AFPM Alena Rybakina wrote: > On 17.07.2024 03:03, Alexander Korotkov wrote: > > Hi, Alena! > > > > On Thu, Jul 11, 2024 at 7:17=E2=80=AFPM Alena Rybakina > > wrote: > >> I have finished patch and processed almost your suggestions (from [0], > [1], [2]). It remains only to add tests where the conversion should work, > but I will add this in the next version. > >> > >> [0] > https://www.postgresql.org/message-id/3381819.e9J7NaK4W3%40thinkpad-pgpro > >> > >> [1] > https://www.postgresql.org/message-id/9736220.CDJkKcVGEf%40thinkpad-pgpro > >> > >> [2] > https://www.postgresql.org/message-id/2193851.QkHrqEjB74%40thinkpad-pgpro > > I dare making another revision of this patch. In this version I moved > > the transformation to match_clause_to_indexcol(). Therefore, this > > allows to successfully construct index scans with SAOP, but has no > > degradation in generation of bitmap scans which I observed in [1] and > > [2]. BTW, I found that my description in [2] lacks of t_b_c_idx index > > definition. Sorry for that. > > > > Given that now we're doing OR-to-ANY transformation solely to match an > > index we don't need complex analysis of OR-list, which potentially > > could take quadratic time. Instead, we're trying to match every OR > > element to an index and quit immediately on failure. > > Yes I see that. I will look at this in detail, but so far I have not > found any unpleasant side effects indicating that the patch should be > moved to another place and this is very good) > > The only thing that worries me so far is that most likely we will need > to analyze the changes in rinfo and distribute them to others places > where links about them are used. > But I need to look at this in more detail separately before discussing it= . > I'm not sure if would need to distribute changes of RestrictInfo's, because we're modifying anything in-place. Instead we create a new RestrictInfo for IndexOptInfo. I think this is what Robert proposed at [1]. The side effect of this I yet see is redundancy of clauses in [2] test case. QUERY PLAN ---------------------------------------------------------------------------= ------------------------------------------------------------- Bitmap Heap Scan on t (cost=3D19.70..26.93 rows=3D5001 width=3D12) Recheck Cond: (((b =3D 1) AND (b =3D ANY ('{1,2}'::integer[])) AND (c = =3D 2)) OR ((a =3D 1) AND (b =3D 2) AND (b =3D ANY ('{1,2}'::integer[])))) Filter: ((a =3D 1) AND (c =3D 2)) -> BitmapOr (cost=3D19.70..19.70 rows=3D2 width=3D0) -> Bitmap Index Scan on t_b_c_idx (cost=3D0.00..8.60 rows=3D1 width=3D0) Index Cond: ((b =3D 1) AND (b =3D ANY ('{1,2}'::integer[])) = AND (c =3D 2)) -> Bitmap Index Scan on t_a_b_idx (cost=3D0.00..8.60 rows=3D1 width=3D0) Index Cond: ((a =3D 1) AND (b =3D 2) AND (b =3D ANY ('{1,2}'::integer[]))) (8 rows) You can see that index conds and recheck conds contain both SAOP clauses and equality clauses. I this this happens because bitmap scan planning code doesn't understands equivalency of original and transformed RestrictInfo's. I'm not yet sure what to do about this. We probably need to teach bitmap scan planning code to understand this equivalency. Or, otherwise, just allow this redundancy given that this is quite rare case I believe. > Yes, I am ready to agree that there was no degradation in tests [1] and > [2]. But just in case, I will do a review to rule out any other problems. > > I'd like to head a feedback on the new place to apply the > > transformation. It looks like significant simplification for me and > > the way to go. > > > > Also, I have addressed some of notes by Robert Haas [3]. In v27 we > > don't use expression evaluation, but directly construct an array > > constant when possible. Also we don't transform operator id to string > > and back, but directly construct SAOP instead. > > > > Links. > > 1. > https://www.postgresql.org/message-id/CAPpHfduJtO0s9E%3DSHUTzrCD88BH0eik0= UNog1_q3XBF2wLmH6g%40mail.gmail.com > > 2. > https://www.postgresql.org/message-id/CAPpHfdtSXxhdv3mLOLjEewGeXJ%2BFtfhj= qodn1WWuq5JLsKx48g%40mail.gmail.com > > 3. > https://www.postgresql.org/message-id/CA%2BTgmobu0DUFCTF28DuAi975mEc4xYqX= 3xyt8RA0WbnyrYg%2BFw%40mail.gmail.com > > Thanks for your effort and any help is welcome) > > Yesterday I finished a big project in my work and now I'm ready to > continue working on this thread. I'll write the results one of these days= . > Great, thank you. I would appreciate your further work on this patch. Apart from general feedback on approach, the last patch requires comments, code beautification etc. Links. 1. https://www.postgresql.org/message-id/CA%2BTgmoarYLO6PL%2BFEnXJ6A-57KsVsotp= vHnB771M-wXQOGNy9w%40mail.gmail.com 2. https://www.postgresql.org/message-id/CAPpHfdtSXxhdv3mLOLjEewGeXJ%2BFtfhjqo= dn1WWuq5JLsKx48g%40mail.gmail.com ------ Regards, Alexander Korotkov Supabase --00000000000042bb60061d76943a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi, Alena!

On Wed, Jul 17, 2024 at 3:53=E2=80= =AFPM Alena Rybakina <a.ryb= akina@postgrespro.ru> wrote:
On 17.07.2024 03:03, Alexander Korotkov wrote:
> Hi, Alena!
>
> On Thu, Jul 11, 2024 at 7:17=E2=80=AFPM Alena Rybakina
> <a.r= ybakina@postgrespro.ru> wrote:
>> I have finished patch and processed almost your suggestions (from = [0], [1], [2]). It remains only to add tests where the conversion should wo= rk, but I will add this in the next version.
>>
>> [0] https://www.po= stgresql.org/message-id/3381819.e9J7NaK4W3%40thinkpad-pgpro
>>
>> [1] https://www.po= stgresql.org/message-id/9736220.CDJkKcVGEf%40thinkpad-pgpro
>>
>> [2] https://www.po= stgresql.org/message-id/2193851.QkHrqEjB74%40thinkpad-pgpro
> I dare making another revision of this patch.=C2=A0 In this version I = moved
> the transformation to match_clause_to_indexcol().=C2=A0 Therefore, thi= s
> allows to successfully construct index scans with SAOP, but has no
> degradation in generation of bitmap scans which I observed in [1] and<= br> > [2].=C2=A0 BTW, I found that my description in [2] lacks of t_b_c_idx = index
> definition. Sorry for that.
>
> Given that now we're doing OR-to-ANY transformation solely to matc= h an
> index we don't need complex analysis of OR-list, which potentially=
> could take quadratic time.=C2=A0 Instead, we're trying to match ev= ery OR
> element to an index and quit immediately on failure.

Yes I see that. I will look at this in detail, but so far I have not
found any unpleasant side effects indicating that the patch should be
moved to another place and this is very good)

The only thing that worries me so far is that most likely we will need
to analyze the changes in rinfo and distribute them to others places
where links about them are used.
But I need to look at this in more detail separately before discussing it.<= br>

I'm not sure if would need to distr= ibute changes of=C2=A0RestrictInfo's, because we're modifying anyth= ing in-place.=C2=A0 Instead we create a new RestrictInfo for=C2=A0IndexOptI= nfo.=C2=A0 I think this is what Robert proposed at [1].=C2=A0 The side effe= ct of this I yet see is redundancy of clauses in [2] test case.
<= span style=3D"font-family:monospace">
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0QUERY PLAN=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0=C2=A0
----------------------------------------------------------------------= ------------------------------------------------------------------
=C2= =A0Bitmap Heap Scan on t =C2=A0(cost=3D19.70..26.93 rows=3D5001 width=3D12)=
=C2=A0 =C2=A0Recheck Cond: (((b =3D 1) AND (b =3D ANY ('{1,2}':= :integer[])) AND (c =3D 2)) OR ((a =3D 1) AND (b =3D 2) AND (b =3D ANY (= 9;{1,2}'::integer[]))))
=C2=A0 =C2=A0Filter: ((a =3D 1) AND (c =3D 2= ))
=C2=A0 =C2=A0-> =C2=A0BitmapOr =C2=A0(cost=3D19.70..19.70 rows=3D2= width=3D0)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-> =C2=A0Bitmap Index S= can on t_b_c_idx =C2=A0(cost=3D0.00..8.60 rows=3D1 width=3D0)
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Index Cond: ((b =3D 1) AND (b = =3D ANY ('{1,2}'::integer[])) AND (c =3D 2))
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0-> =C2=A0Bitmap Index Scan on t_a_b_idx =C2=A0(cost=3D0= .00..8.60 rows=3D1 width=3D0)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0Index Cond: ((a =3D 1) AND (b =3D 2) AND (b =3D ANY ('{1,2= }'::integer[])))
(8 rows)

You ca= n see that index conds and recheck conds contain both SAOP clauses and equa= lity clauses.=C2=A0 I this this happens because bitmap scan planning code d= oesn't understands equivalency of original and transformed RestrictInfo= 's.=C2=A0 I'm not yet sure what to do about this.=C2=A0 We probably= need to teach bitmap scan planning code to understand this equivalency.=C2= =A0 Or, otherwise, just allow this redundancy given that this is quite rare= case I believe.
=C2=A0
Yes, I am ready to agree that there was no degradation in tests [1] and [2]. But just in case, I will do a review to rule out any other problems. > I'd like to head a feedback on the new place to apply the
> transformation.=C2=A0 It looks like significant simplification for me = and
> the way to go.
>
> Also, I have addressed some of notes by Robert Haas [3].=C2=A0 In v27 = we
> don't use expression evaluation, but directly construct an array > constant when possible.=C2=A0 Also we don't transform operator id = to string
> and back, but directly construct SAOP instead.
>
> Links.
> 1. https://www.postgresql.org/message-id/CAPpHfduJtO0s9E%3DSHU= TzrCD88BH0eik0UNog1_q3XBF2wLmH6g%40mail.gmail.com
> 2. https://www.postgresql.org/message-id/CAPpHfdtSXxhdv3mLOLjE= ewGeXJ%2BFtfhjqodn1WWuq5JLsKx48g%40mail.gmail.com
> 3. https://www.postgresql.org/message-id/CA%2BTgmobu0DUFCTF2= 8DuAi975mEc4xYqX3xyt8RA0WbnyrYg%2BFw%40mail.gmail.com

Thanks for your effort and any help is welcome)

Yesterday I finished a big project in my work and now I'm ready to
continue working on this thread. I'll write the results one of these da= ys.

Great, thank you. I would appreciat= e your further work on this patch.=C2=A0 Apart from general feedback on app= roach, the last patch requires comments, code beautification etc.

Links.

------<= br>Regards,
Alexander Korotkov
Supabase
--00000000000042bb60061d76943a--