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 1rkhRl-00EgVA-99 for pgsql-hackers@arkaria.postgresql.org; Thu, 14 Mar 2024 09:32:21 +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 1rkhRj-00GCzG-NC for pgsql-hackers@arkaria.postgresql.org; Thu, 14 Mar 2024 09:32:20 +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 1rkhRj-00GCz8-7F for pgsql-hackers@lists.postgresql.org; Thu, 14 Mar 2024 09:32:19 +0000 Received: from mail-yw1-x1134.google.com ([2607:f8b0:4864:20::1134]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1rkhRb-004RB7-87 for pgsql-hackers@postgresql.org; Thu, 14 Mar 2024 09:32:18 +0000 Received: by mail-yw1-x1134.google.com with SMTP id 00721157ae682-609eb3e5a56so8573047b3.1 for ; Thu, 14 Mar 2024 02:32:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710408731; x=1711013531; 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=PqKWfVE9J7NgjMYejA6gaUzEALZfFbB4nO+wi8chzvs=; b=jzFW+y+eR5pXt5ayotUfZMyXnS1ooSL5OE2+6NFMYDc10ldkJ3ryYeeU7SFAQvn2uK QzFXyCdZY8bV/cokj+rcPLr1JjpeRlfnSVHo1vXIRCNLegdmy4mOY3RDq6F90KzP3fWu 0Rmz9keysU4xIaDdL6tY/ivd+CKhRC3bLpy5XbblQS08MU33xhh84S6XmVloUGLAcP3b ydo/4cFOLwm/x3xV6Dw3suE6wJly89Abp7k33VdrsshaOcrPx1keuQh9cV9KJp93hOzC NObafZUrUY6ea/O/Q13P8n+BZGBbcLy0XTrSs44EMwKEMUsjV2/WN8/w8MMCIHiE3IlY 6NdA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710408731; x=1711013531; 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=PqKWfVE9J7NgjMYejA6gaUzEALZfFbB4nO+wi8chzvs=; b=Ya20jhvNmJJTMVQLhxITkoRMOihjjhIRbiFB9TrMtN+GZOq1aTC27YlibWIAqhaHvO k5qjvVaP7AMJeDW5GicAahGoFdwajTmXC3Q1ZlOllxkQnannZhYGZY1yG8e+b1mWvHYK IFKLnvM4IDRB6RRnTIIr2aBE9g/1qAwwr3Dacx6ZB2YTX4Ipm+NfmIFjccYKAzXxeoTf x6x7FpmaEDWJHFpSWLA7I6riEGQsV8Gfyt1C+UoP2IT1BClf9urzY8+sP95FQSNWO4RU quCItHOFO6EhcMcedSvgdpAaOSfeY8/1rabi7zQqDbfXpWhYjOHCK58+/313sjaVpySJ M6Rw== X-Forwarded-Encrypted: i=1; AJvYcCVI769Bd2MtpCiWx77/QVH6wBcfgPQHkSUrwjlNZ+kaHgAS7RPkzr/cQyvNKDlNF2moMKDXJQcZ53wG5Tqwr3UNTasUWQY8lya4Yk+g X-Gm-Message-State: AOJu0Yxc05hGcYZyyl1TcGycyp6t5Cug6tO5EVQwZOhj4PvzHXxVSz2a JCVF0mVXgnvnw6l9aLY7fHpltOQaoGeibFjQEv7xTsOyN8IBu0hIdxauL5ZERBocc1VeeWlyDW2 i72R6qMZcHmFioG4uhhykaIVUokE= X-Google-Smtp-Source: AGHT+IG0my6SpnZ/q2pPVFs/1RPLnGWLgxVtAGbqa5OEPGtPs/HnN8TFDlaZh7+DiVqqi5aUVwMQqr+AsPokgS0ctmI= X-Received: by 2002:a25:ab2e:0:b0:db5:3b32:b1c3 with SMTP id u43-20020a25ab2e000000b00db53b32b1c3mr1231536ybi.21.1710408731273; Thu, 14 Mar 2024 02:32:11 -0700 (PDT) MIME-Version: 1.0 References: <567ED6CA.2040504@sigaev.ru> <11ee9c04-281f-43c8-a0ff-d481c1e01c09@postgrespro.ru> <54009ba5-4aea-4344-a30d-e3558a59e2a9@postgrespro.ru> <380e5683-cdfd-4220-ab9b-7cccb9d3e480@postgrespro.ru> <7389d0dd-05d5-41b7-a12d-2e73f939f851@postgrespro.ru> <74e3c8bc-dccd-45e5-ad2d-6a6e96fc5864@postgrespro.ru> In-Reply-To: From: Alexander Korotkov Date: Thu, 14 Mar 2024 11:31:58 +0200 Message-ID: Subject: Re: POC, WIP: OR-clause support for indexes To: Andrei Lepikhov Cc: jian he , Alena Rybakina , 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="000000000000d9357406139b905d" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --000000000000d9357406139b905d Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Wed, Mar 13, 2024 at 2:16=E2=80=AFPM Andrei Lepikhov wrote: > On 13/3/2024 18:05, Alexander Korotkov wrote: > > On Wed, Mar 13, 2024 at 7:52=E2=80=AFAM Andrei Lepikhov > > Given all of the above, I think moving transformation to the > > canonicalize_qual() would be the right way to go. > Ok, I will try to move the code. > I have no idea about the timings so far. I recall the last time I got > bogged down in tons of duplicated code. I hope with an almost-ready > sketch, it will be easier. Thank you! I'll be looking forward to the updated patch. I also have notes about the bitmap patch. /* * Building index paths over SAOP clause differs from the logic of OR clauses. * Here we iterate across all the array elements and split them to SAOPs, * corresponding to different indexes. We must match each element to an index. */ This covers the case I posted before. But in order to fix all possible cases we probably need to handle the SAOP clause in the same way as OR clauses. Check also this case. Setup create table t (a int not null, b int not null, c int not null); insert into t (select 1, 1, i from generate_series(1,10000) i); insert into t (select i, 2, 2 from generate_series(1,10000) i); create index t_a_b_idx on t (a, b); create statistics t_a_b_stat (mcv) on a, b from t; create statistics t_b_c_stat (mcv) on b, c from t; vacuum analyze t; Plan with enable_or_transformation =3D on: # explain select * from t where a =3D 1 and (b =3D 1 or b =3D 2) and c =3D = 2; QUERY PLAN ---------------------------------------------------------------------------= --- Bitmap Heap Scan on t (cost=3D156.55..440.56 rows=3D5001 width=3D12) Recheck Cond: (a =3D 1) Filter: ((b =3D ANY ('{1,2}'::integer[])) AND (c =3D 2)) -> Bitmap Index Scan on t_a_b_idx (cost=3D0.00..155.29 rows=3D10001 width=3D0) Index Cond: (a =3D 1) (5 rows) Plan with enable_or_transformation =3D off: # explain select * from t where a =3D 1 and (b =3D 1 or b =3D 2) and c =3D = 2; QUERY PLAN ---------------------------------------------------------------------------= --- Bitmap Heap Scan on t (cost=3D11.10..18.32 rows=3D5001 width=3D12) Recheck Cond: (((b =3D 1) AND (c =3D 2)) OR ((a =3D 1) AND (b =3D 2))) Filter: ((a =3D 1) AND (c =3D 2)) -> BitmapOr (cost=3D11.10..11.10 rows=3D2 width=3D0) -> Bitmap Index Scan on t_b_c_idx (cost=3D0.00..4.30 rows=3D1 width=3D0) Index Cond: ((b =3D 1) AND (c =3D 2)) -> Bitmap Index Scan on t_a_b_idx (cost=3D0.00..4.30 rows=3D1 width=3D0) Index Cond: ((a =3D 1) AND (b =3D 2)) (8 rows) As you can see this case is not related to partial indexes. Just no index selective for the whole query. However, splitting scan by the OR qual lets use a combination of two selective indexes. ------ Regards, Alexander Korotkov --000000000000d9357406139b905d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Wed, Mar 13, 2024 at 2:16=E2=80=AFPM Andrei Lepikhov &l= t;a.lepikhov@postgrespro.ru> wrote:
> On 13/3/2024 18:05, Alexander Korotkov wrote:
> = > On Wed, Mar 13, 2024 at 7:52=E2=80=AFAM Andrei Lepikhov
> > G= iven all of the above, I think moving transformation to the
> > ca= nonicalize_qual() would be the right way to go.
> Ok, I will try to m= ove the code.
> I have no idea about the timings so far. I recall the= last time I got
> bogged down in tons of duplicated code. I hope wit= h an almost-ready
> sketch, it will be easier.

Thank you!=C2= =A0 I'll be looking forward to the updated patch.

I also have no= tes about the bitmap patch.

/*
=C2=A0* B= uilding index paths over SAOP clause differs from the logic of OR clauses.<= br>=C2=A0* Here we iterate across all the array elements and split them to = SAOPs,
=C2=A0* corresponding to different indexes. We must match each el= ement to an index.
=C2=A0*/

This covers the case I posted = before.=C2=A0 But in order to fix all possible cases we probably need to ha= ndle the SAOP=C2=A0clause=C2=A0in the same way as OR clauses.=C2=A0 Check a= lso this case.

Setup
= create table t (a int not null, b int not null, c int not null);
insert into t (select 1, 1, i from generate= _series(1,10000) i);
insert into t (select i, 2, 2 from generate_series(= 1,10000) i);
create index t_a_b_idx on t (a, b);
create statistics t_a_b_stat (mcv) on a, b from t;
cr= eate statistics t_b_c_stat (mcv) on b, c from t;
vacuum analyze t;

Plan with=C2= =A0enable_or_transformation =3D on:
# ex= plain select * from t where a =3D 1 and (b =3D 1 or b =3D 2) and c =3D 2;=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 QUERY PLAN
---------------= ---------------------------------------------------------------
=C2=A0Bi= tmap Heap Scan on t =C2=A0(cost=3D156.55..440.56 rows=3D5001 width=3D12)=C2=A0 =C2=A0Recheck Cond: (a =3D 1)
=C2=A0 =C2=A0Filter: ((b =3D ANY (= '{1,2}'::integer[])) AND (c =3D 2))
=C2=A0 =C2=A0-> =C2=A0Bit= map Index Scan on t_a_b_idx =C2=A0(cost=3D0.00..155.29 rows=3D10001 width= =3D0)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Index Cond: (a =3D 1)
(5 rows= )

Plan with=C2=A0enable_or_transformation =3D off:
=
# explain select * from t where a =3D 1 and (= b =3D 1 or b =3D 2) and c =3D 2;
=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 QUERY PLAN
-----= -------------------------------------------------------------------------=C2=A0Bitmap Heap Scan on t =C2=A0(cost=3D11.10..18.32 rows=3D5001 width= =3D12)
=C2=A0 =C2=A0Recheck Cond: (((b =3D 1) AND (c =3D 2)) OR ((a =3D = 1) AND (b =3D 2)))
=C2=A0 =C2=A0Filter: ((a =3D 1) AND (c =3D 2))
=C2= =A0 =C2=A0-> =C2=A0BitmapOr =C2=A0(cost=3D11.10..11.10 rows=3D2 width=3D= 0)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-> =C2=A0Bitmap Index Scan on t_= b_c_idx =C2=A0(cost=3D0.00..4.30 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 (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..4.30 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))
= (8 rows)

As you can see this case is not related to partial i= ndexes.=C2=A0 Just no index selective for the whole query.=C2=A0 However, s= plitting scan by the OR qual lets use a combination of two selective indexe= s.

------
Regards,
Alexander Korotkov
--000000000000d9357406139b905d--