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 1rGc8l-00GBRS-GP for pgsql-hackers@arkaria.postgresql.org; Fri, 22 Dec 2023 09:48:23 +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 1rGc8k-004mgX-6O for pgsql-hackers@arkaria.postgresql.org; Fri, 22 Dec 2023 09:48:22 +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 1rGc8j-004md7-RZ for pgsql-hackers@lists.postgresql.org; Fri, 22 Dec 2023 09:48:21 +0000 Received: from mail-yw1-x1133.google.com ([2607:f8b0:4864:20::1133]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1rGc8h-00DKZR-Uj for pgsql-hackers@lists.postgresql.org; Fri, 22 Dec 2023 09:48:21 +0000 Received: by mail-yw1-x1133.google.com with SMTP id 00721157ae682-5e7415df4d6so22557637b3.0 for ; Fri, 22 Dec 2023 01:48:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1703238498; x=1703843298; darn=lists.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=Ea+fBA98lwbATd152nFH58QjqZXHSdsozDSetKIi/LM=; b=PRRdUdcd6mKcvJ58n2KM80nv4MFgG/55ocgAI1nyu343cu4nxYXZ4JAX2ybIrHxmSR chDRJHC6XeSkf1SGpqQqc/m4nDhw2w24TWh7ZMH2EgWdxI3RQL9aaIb9t+JItODdHILb MX4xQKr6SBnfbzktTzDFfmIkpCSVXctcSmOjhR/5xckVmyhkcZ2Qv7X1Fu1B+F4Uxtid 66o0C1eM243S3bKkOHz3HWiWGEO3yL7nnDklgVgcepREgAy4iV8Z51ollUFNy9SiK9W8 R4TjRsxsdgUqEPPpJ5dHLis13FKmULg+1U7difdQsTS3AfIMw30HmeD+cuzCqZQRHwLd CXfA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1703238498; x=1703843298; 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=Ea+fBA98lwbATd152nFH58QjqZXHSdsozDSetKIi/LM=; b=j6Hkq+gtbycDaY2X5GBW1FjB+rW6j2QgzkDLIn4h8d2oxLjRDQvbYRUzlYw1nKgoNG JaLsfe8gHH5Dn9AB5FBCid5GSwJhQddiQoSChhVujVPvkuPaBChZurQExtg5xIX22nof dwIBiFeKLcU6gScakmuYbIa8c5fjmSuMC2a30WdWP5nEuxEd4rRx7b+a4ulebL9WVHbT /C8KEUHFZb96wUN6CJsCxvMGPLBI5pTB0cRM9xnjpVey+5nL31S7jSpvpTkTN1zzWD70 kMIVHGSpaDOvtDTWZPuRJ7K93IGzv9CmI2dDPPLfiMYwRZ1djOaOZVPi4cFaX3kiWYzK WVRw== X-Gm-Message-State: AOJu0YwyDdX5rfOQF0RcaSA6udvFY6py1t0e+f1Hj+JFfBOteViLazwP LEePMl8NDbzjUKkNELYLAOO/kNgN+vm4kEH748+jUN7BM2A= X-Google-Smtp-Source: AGHT+IGrOcUso9EyOLiwanPRDGSkiJ8lzIhdZ4qDQUYkng1kuWw8huGDyEK+waKFf+tAt88dl/XajyOfR51ZqFcAtyc= X-Received: by 2002:a25:73ca:0:b0:dbd:688b:f1e8 with SMTP id o193-20020a2573ca000000b00dbd688bf1e8mr1575451ybc.11.1703238498160; Fri, 22 Dec 2023 01:48:18 -0800 (PST) MIME-Version: 1.0 References: <10a1586e-f96e-41b1-abe9-6f93667bf6bc@postgrespro.ru> In-Reply-To: <10a1586e-f96e-41b1-abe9-6f93667bf6bc@postgrespro.ru> From: Alexander Korotkov Date: Fri, 22 Dec 2023 11:48:06 +0200 Message-ID: Subject: Re: Optimization outcome depends on the index order To: Andrei Lepikhov Cc: PostgreSQL Hackers Content-Type: multipart/alternative; boundary="000000000000a694dc060d161d9a" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --000000000000a694dc060d161d9a Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Fri, Dec 22, 2023 at 8:53=E2=80=AFAM Andrei Lepikhov wrote: > On 21/12/2023 12:10, Alexander Korotkov wrote: > > I took a closer look at the patch in [9]. I should drop my argument > > about breaking the model, because add_path() already considers other > > aspects than just costs. But I have two more note about that patch: > > > > 1) It seems that you're determining the fact that the index path > > should return strictly one row by checking path->rows <=3D 1.0 and > > indexinfo->unique. Is it really guaranteed that in this case quals > > are matching unique constraint? path->rows <=3D 1.0 could be just an > > estimation error. Or one row could be correctly estimated, but it's > > going to be selected by some quals matching unique constraint and > > other quals in recheck. So, it seems there is a risk to select > > suboptimal index due to this condition. > > Operating inside the optimizer, we consider all estimations to be the > sooth. This patch modifies only one place: having two equal assumptions, > we just choose one that generally looks more stable. > Filtered tuples should be calculated and included in the cost of the > path. The decision on the equality of paths has been made in view of the > estimation of these filtered tuples. Even if estimates are accurate the conditions in the patch doesn't guarantee there is actually a unique condition. # create table t as select i/1000 a, i % 1000 b, i % 1000 c from generate_series(1,1000000) i; # create unique index t_unique_idx on t(a,b); # create index t_another_idx on t(a,c); # \d t Table "public.t" Column | Type | Collation | Nullable | Default --------+---------+-----------+----------+--------- a | integer | | | b | integer | | | c | integer | | | Indexes: "t_another_idx" btree (a, c) "t_unique_idx" UNIQUE, btree (a, b) # set enable_bitmapscan =3D off; explain select * from t where a =3D 1 and = c =3D 1; SET Time: 0.459 ms QUERY PLAN -------------------------------------------------------------------------- Index Scan using t_unique_idx on t (cost=3D0.42..1635.16 rows=3D1 width= =3D12) Index Cond: (a =3D 1) Filter: (c =3D 1) (3 rows) > > 2) Even for non-unique indexes this patch is putting new logic on top > > of the subsequent code. How we can prove it's going to be a win? > > That could lead, for instance, to dropping parallel-safe paths in > > cases we didn't do so before. > Because we must trust all predictions made by the planner, we just > choose the most trustworthy path. According to the planner logic, it is > a path with a smaller selectivity. We can make mistakes anyway just > because of the nature of estimation. Even if we need to take selectivity into account here, it's still not clear why this should be on top of other logic later in add_path(). > > Anyway, please start a separate thread if you're willing to put more > > work into this. > > Done Thanks. ------ Regards, Alexander Korotkov --000000000000a694dc060d161d9a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Fri, Dec 22, 2023 at 8:53=E2=80=AFAM Andrei Lepikhov &l= t;a.lepikhov@postgrespro.ru> wrote:
> On 21/12/2023 12:10, Alexander Korotkov wrote:
>= =C2=A0> I took a closer look at the patch in [9].=C2=A0 I should drop m= y argument
> =C2=A0> about breaking the model, because add_path() = already considers other
> =C2=A0> aspects than just costs.=C2=A0 B= ut I have two more note about that patch:
> =C2=A0>
> =C2=A0= > 1) It seems that you're determining the fact that the index path> =C2=A0> should return strictly one row by checking path->rows = <=3D 1.0 and
> =C2=A0> indexinfo->unique.=C2=A0 Is it really= guaranteed that in this case quals
> =C2=A0> are matching unique = constraint? =C2=A0path->rows <=3D 1.0 could be just an
> =C2=A0= > estimation error.=C2=A0 Or one row could be correctly estimated, but i= t's
> =C2=A0> going to be selected by some quals matching uniq= ue constraint and
> =C2=A0> other quals in recheck.=C2=A0 So, it s= eems there is a risk to select
> =C2=A0> suboptimal index due to t= his condition.
>
> Operating inside the optimizer, we consider = all estimations to be the
> sooth. This patch modifies only one place= : having two equal assumptions,
> we just choose one that generally l= ooks more stable.
> Filtered tuples should be calculated and included= in the cost of the
> path. The decision on the equality of paths has= been made in view of the
> estimation of these filtered tuples.
<= br>Even if estimates are accurate the conditions in the patch doesn't g= uarantee there is actually a unique condition.

# create table t as select i/1000 a, i % 1000 b, i % 1000 c from genera= te_series(1,1000000) i;
# create unique index t_unique_idx on t(a,b);# create index t_another_idx on t(a,c);
# \d t
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Table "public.t"
=C2= =A0Column | =C2=A0Type =C2=A0 | Collation | Nullable | Default
--------+= ---------+-----------+----------+---------
=C2=A0a =C2=A0 =C2=A0 =C2=A0|= integer | =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 | =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0|
=C2=A0b =C2=A0 =C2=A0 =C2=A0| integer | =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 | =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0|
=C2=A0c =C2=A0 =C2= =A0 =C2=A0| integer | =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 | =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0|
Indexes:
=C2=A0 =C2=A0 "t_another_idx"= ; btree (a, c)
=C2=A0 =C2=A0 "t_unique_idx" UNIQUE, btree (a, = b)
# set enable_bitmapscan =3D off; explain select * from t where a =3D = 1 and c =3D 1;
SET
Time: 0.459 ms
=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=A0Index Scan using t_unique_idx on t =C2=A0(cos= t=3D0.42..1635.16 rows=3D1 width=3D12)
=C2=A0 =C2=A0Index Cond: (a =3D 1= )
=C2=A0 =C2=A0Filter: (c =3D 1)
(3 rows)

=C2=A0
>= ; =C2=A0> 2) Even for non-unique indexes this patch is putting new logic= on top
> =C2=A0> of the subsequent code.=C2=A0 How we can prove i= t's going to be a win?
> =C2=A0> That could lead, for instance= , to dropping parallel-safe paths in
> =C2=A0> cases we didn't= do so before.
> Because we must trust all predictions made by the pl= anner, we just
> choose the most trustworthy path. According to the p= lanner logic, it is
> a path with a smaller selectivity. We can make = mistakes anyway just
> because of the nature of estimation.

Even if we need to take selectivity into account here, it's still no= t clear why this should be on top of other logic later in add_path().
=

> =C2=A0> Anyway, please start a separate thread = if you're willing to put more
> =C2=A0> work into this.
>= ;
> Done

Thanks.

------
Regards,
Alexander Korotkov
--000000000000a694dc060d161d9a--