pg.ddx.io pgsql-bugs@postgresql.org mailing list archive
help / color / mirror / Atom feedBUG #17975: Nested Loop Index Scan returning wrong result
18+ messages / 5 participants
[nested] [flat]
* BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-14 15:17 PG Bug reporting form <noreply@postgresql.org>
0 siblings, 1 reply; 18+ messages in thread
From: PG Bug reporting form @ 2023-06-14 15:17 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: tel@jklm.no
The following bug has been logged on the website:
Bug reference: 17975
Logged by: Tor Erik Linnerud
Email address: tel@jklm.no
PostgreSQL version: 15.3
Operating system: MacOS 13.4, Linux 5.16
Description:
Hi, first let me say thanks for all the hard work that goes into Postgres.
I ran into a very specific query + index + data combination that appears to
return the wrong result. After much trial and error I’ve been able to
construct a dump to reproduce the problem, when running ANALYZE after the
import.
1. Grab the DB dump (13 MB)
curl -L "https://www.dropbox.com/s/k1ai0765gc2k98f/bug5.sql?dl=1"; -o
bug5.sql
2. Create an empty database, import the dump and analyze:
createdb bug5 && psql -d bug5 -f bug5.sql && psql -d bug5 -c "ANALYZE"
3. Run queries:
psql -d bug5 -c "set enable_indexscan = 'off'; SELECT a.id FROM a JOIN b ON
b.a_id = a.id JOIN c ON c.id = b.c_id WHERE c.tag = '13880'"
1 row expected, get 1
psql -d bug5 -c "set enable_indexscan = 'on'; SELECT a.id FROM a JOIN b ON
b.a_id = a.id JOIN c ON c.id = b.c_id WHERE c.tag = '13880'"
1 row expected, get 0
Thanks,
Tor Erik
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-14 20:36 Andres Freund <andres@anarazel.de>
parent: PG Bug reporting form <noreply@postgresql.org>
0 siblings, 2 replies; 18+ messages in thread
From: Andres Freund @ 2023-06-14 20:36 UTC (permalink / raw)
To: tel@jklm.no; pgsql-bugs@lists.postgresql.org
Hi,
On 2023-06-14 15:17:31 +0000, PG Bug reporting form wrote:
> The following bug has been logged on the website:
>
> Bug reference: 17975
> Logged by: Tor Erik Linnerud
> Email address: tel@jklm.no
> PostgreSQL version: 15.3
> Operating system: MacOS 13.4, Linux 5.16
> Description:
>
> Hi, first let me say thanks for all the hard work that goes into Postgres.
>
>
> I ran into a very specific query + index + data combination that appears to
> return the wrong result. After much trial and error I’ve been able to
> construct a dump to reproduce the problem, when running ANALYZE after the
> import.
>
> 1. Grab the DB dump (13 MB)
>
> curl -L "https://www.dropbox.com/s/k1ai0765gc2k98f/bug5.sql?dl=1"; -o
> bug5.sql
>
> 2. Create an empty database, import the dump and analyze:
>
> createdb bug5 && psql -d bug5 -f bug5.sql && psql -d bug5 -c "ANALYZE"
>
> 3. Run queries:
>
> psql -d bug5 -c "set enable_indexscan = 'off'; SELECT a.id FROM a JOIN b ON
> b.a_id = a.id JOIN c ON c.id = b.c_id WHERE c.tag = '13880'"
>
> 1 row expected, get 1
>
> psql -d bug5 -c "set enable_indexscan = 'on'; SELECT a.id FROM a JOIN b ON
> b.a_id = a.id JOIN c ON c.id = b.c_id WHERE c.tag = '13880'"
>
> 1 row expected, get 0
Uh, huh. I can reproduce that. And it's not just 15, reproduces in old
versions too.
The plan doesn't look obviously wrong:
┌────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ QUERY PLAN │
├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Nested Loop (cost=1.26..17.46 rows=1 width=8) (actual time=0.063..0.065 rows=0 loops=1) │
│ Output: a.id │
│ Inner Unique: true │
│ -> Nested Loop (cost=0.84..16.88 rows=1 width=8) (actual time=0.056..0.059 rows=1 loops=1) │
│ Output: b.a_id │
│ Inner Unique: true │
│ -> Index Scan using c_tag_idx on public.c (cost=0.42..8.44 rows=1 width=8) (actual time=0.034..0.036 rows=1 loops=1) │
│ Output: c.id, c.tag │
│ Index Cond: ((c.tag)::text = '13880'::text) │
│ -> Index Scan using index_b_c_id on public.b (cost=0.42..8.44 rows=1 width=16) (actual time=0.015..0.016 rows=1 loops=1) │
│ Output: b.id, b.c_id, b.a_id │
│ Index Cond: (b.c_id = c.id) │
│ -> Index Only Scan using a_pkey on public.a (cost=0.42..0.59 rows=1 width=8) (actual time=0.002..0.003 rows=0 loops=1) │
│ Output: a.id │
│ Index Cond: (a.id = b.a_id) │
│ Heap Fetches: 0 │
│ Planning Time: 0.998 ms │
│ Execution Time: 0.148 ms │
└────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
(18 rows)
It's not an IOS issue, it happens without IOS as well.
Something seems to be off with the relevant param - it's NULL. Haven't dug
deeper.
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-14 21:10 Peter Geoghegan <pg@bowt.ie>
parent: Andres Freund <andres@anarazel.de>
1 sibling, 1 reply; 18+ messages in thread
From: Peter Geoghegan @ 2023-06-14 21:10 UTC (permalink / raw)
To: Andres Freund <andres@anarazel.de>; +Cc: tel@jklm.no; pgsql-bugs@lists.postgresql.org
On Wed, Jun 14, 2023 at 1:37 PM Andres Freund <andres@anarazel.de> wrote:
> Something seems to be off with the relevant param - it's NULL. Haven't dug
> deeper.
I see that the bad plan has _bt_first() return false early during a
btgettuple() call for one of the a_pkey index scans. That is,
_bt_first() returns false early in the "Quit now if
_bt_preprocess_keys() discovered that the scan keys can never be
satisfied (eg, x == 1 AND x > 2)" path.
It's possible that this is a red herring -- this is not the only
difference between the "bad" index scan heavy plan and the "good" plan
that uses bitmap scans. But right now my suspicion falls on
_bt_preprocess_keys().
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-14 21:12 Andres Freund <andres@anarazel.de>
parent: Andres Freund <andres@anarazel.de>
1 sibling, 1 reply; 18+ messages in thread
From: Andres Freund @ 2023-06-14 21:12 UTC (permalink / raw)
To: tel@jklm.no; pgsql-bugs@lists.postgresql.org
Hi,
On 2023-06-14 13:36:51 -0700, Andres Freund wrote:
> On 2023-06-14 15:17:31 +0000, PG Bug reporting form wrote:
> > The following bug has been logged on the website:
> >
> > Bug reference: 17975
> > Logged by: Tor Erik Linnerud
> > Email address: tel@jklm.no
> > PostgreSQL version: 15.3
> > Operating system: MacOS 13.4, Linux 5.16
> > Description:
> >
> > Hi, first let me say thanks for all the hard work that goes into Postgres.
> >
> >
> > I ran into a very specific query + index + data combination that appears to
> > return the wrong result. After much trial and error I’ve been able to
> > construct a dump to reproduce the problem, when running ANALYZE after the
> > import.
> >
> > 1. Grab the DB dump (13 MB)
> >
> > curl -L "https://www.dropbox.com/s/k1ai0765gc2k98f/bug5.sql?dl=1"; -o
> > bug5.sql
> >
> > 2. Create an empty database, import the dump and analyze:
> >
> > createdb bug5 && psql -d bug5 -f bug5.sql && psql -d bug5 -c "ANALYZE"
> >
> > 3. Run queries:
> >
> > psql -d bug5 -c "set enable_indexscan = 'off'; SELECT a.id FROM a JOIN b ON
> > b.a_id = a.id JOIN c ON c.id = b.c_id WHERE c.tag = '13880'"
> >
> > 1 row expected, get 1
> >
> > psql -d bug5 -c "set enable_indexscan = 'on'; SELECT a.id FROM a JOIN b ON
> > b.a_id = a.id JOIN c ON c.id = b.c_id WHERE c.tag = '13880'"
> >
> > 1 row expected, get 0
>
> Uh, huh. I can reproduce that. And it's not just 15, reproduces in old
> versions too.
>
> The plan doesn't look obviously wrong:
> ┌────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
> │ QUERY PLAN │
> ├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
> │ Nested Loop (cost=1.26..17.46 rows=1 width=8) (actual time=0.063..0.065 rows=0 loops=1) │
> │ Output: a.id │
> │ Inner Unique: true │
> │ -> Nested Loop (cost=0.84..16.88 rows=1 width=8) (actual time=0.056..0.059 rows=1 loops=1) │
> │ Output: b.a_id │
> │ Inner Unique: true │
> │ -> Index Scan using c_tag_idx on public.c (cost=0.42..8.44 rows=1 width=8) (actual time=0.034..0.036 rows=1 loops=1) │
> │ Output: c.id, c.tag │
> │ Index Cond: ((c.tag)::text = '13880'::text) │
> │ -> Index Scan using index_b_c_id on public.b (cost=0.42..8.44 rows=1 width=16) (actual time=0.015..0.016 rows=1 loops=1) │
> │ Output: b.id, b.c_id, b.a_id │
> │ Index Cond: (b.c_id = c.id) │
> │ -> Index Only Scan using a_pkey on public.a (cost=0.42..0.59 rows=1 width=8) (actual time=0.002..0.003 rows=0 loops=1) │
> │ Output: a.id │
> │ Index Cond: (a.id = b.a_id) │
> │ Heap Fetches: 0 │
> │ Planning Time: 0.998 ms │
> │ Execution Time: 0.148 ms │
> └────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
> (18 rows)
>
> It's not an IOS issue, it happens without IOS as well.
>
>
> Something seems to be off with the relevant param - it's NULL. Haven't dug
> deeper.
I think it's a problem with the uniqueness determination / missing a
qual / index selection.
There are two rows in b with b.c_id = 13880, except that one of them has a
NULL a_id:
=> SELECT * FROM b WHERE c_id = 13880;
┌────────┬───────┬────────┐
│ id │ c_id │ a_id │
├────────┼───────┼────────┤
│ 326048 │ 13880 │ (null) │
│ 572151 │ 13880 │ 955968 │
└────────┴───────┴────────┘
(2 rows)
. The uniqueness information comes from:
"index_a_cannot_share_c" UNIQUE, btree (c_id) WHERE a_id IS NOT NULL
But note that we aren't using that index, we use
"index_b_c_id" btree (c_id)
which of course also contains the a_id = NULL row.
We either need to force the index that we got the uniqueness information to be
used when it is partial, or add the quals from the partial unique index to all
other index scans.
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-14 21:21 Andres Freund <andres@anarazel.de>
parent: Peter Geoghegan <pg@bowt.ie>
0 siblings, 1 reply; 18+ messages in thread
From: Andres Freund @ 2023-06-14 21:21 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: tel@jklm.no; pgsql-bugs@lists.postgresql.org
Hi,
On 2023-06-14 14:10:02 -0700, Peter Geoghegan wrote:
> On Wed, Jun 14, 2023 at 1:37 PM Andres Freund <andres@anarazel.de> wrote:
> > Something seems to be off with the relevant param - it's NULL. Haven't dug
> > deeper.
>
> I see that the bad plan has _bt_first() return false early during a
> btgettuple() call for one of the a_pkey index scans. That is,
> _bt_first() returns false early in the "Quit now if
> _bt_preprocess_keys() discovered that the scan keys can never be
> satisfied (eg, x == 1 AND x > 2)" path.
I think that's a consequence of the planner bug (see subsequent email) - the
bad plan wrongly uses an index that first returns a null a_id, which then
quite legitimately makes _bt_preprocess_keys() exit early. That bit of
smartness did confuse me for a moment, I was expecting the index scan to
actually scan the index at first :).
I haven't figured out where we're dropping the implied index qual on the floor
yet...
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-14 21:38 Peter Geoghegan <pg@bowt.ie>
parent: Andres Freund <andres@anarazel.de>
0 siblings, 0 replies; 18+ messages in thread
From: Peter Geoghegan @ 2023-06-14 21:38 UTC (permalink / raw)
To: Andres Freund <andres@anarazel.de>; +Cc: tel@jklm.no; pgsql-bugs@lists.postgresql.org
On Wed, Jun 14, 2023 at 2:21 PM Andres Freund <andres@anarazel.de> wrote:
> I think that's a consequence of the planner bug (see subsequent email) - the
> bad plan wrongly uses an index that first returns a null a_id, which then
> quite legitimately makes _bt_preprocess_keys() exit early. That bit of
> smartness did confuse me for a moment, I was expecting the index scan to
> actually scan the index at first :).
It certainly looks that way now.
On further examination the only substantive difference is that the
indexes themselves differ in one leaf of the plan. The good plan and
the bad plan match everywhere else (except that the good plan uses
bitmap index scans rather than index scans everywhere).
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-14 22:49 Andres Freund <andres@anarazel.de>
parent: Andres Freund <andres@anarazel.de>
0 siblings, 1 reply; 18+ messages in thread
From: Andres Freund @ 2023-06-14 22:49 UTC (permalink / raw)
To: tel@jklm.no, pgsql-bugs@lists.postgresql.org, Tom Lane <tgl@sss.pgh.pa.us>; David Rowley <dgrowleyml@gmail.com>; +Cc: Peter Geoghegan <pg@bowt.ie>
Hi,
On 2023-06-14 14:12:31 -0700, Andres Freund wrote:
> I think it's a problem with the uniqueness determination / missing a
> qual / index selection.
>
> There are two rows in b with b.c_id = 13880, except that one of them has a
> NULL a_id:
>
> => SELECT * FROM b WHERE c_id = 13880;
> ┌────────┬───────┬────────┐
> │ id │ c_id │ a_id │
> ├────────┼───────┼────────┤
> │ 326048 │ 13880 │ (null) │
> │ 572151 │ 13880 │ 955968 │
> └────────┴───────┴────────┘
> (2 rows)
>
> . The uniqueness information comes from:
> "index_a_cannot_share_c" UNIQUE, btree (c_id) WHERE a_id IS NOT NULL
>
> But note that we aren't using that index, we use
> "index_b_c_id" btree (c_id)
>
> which of course also contains the a_id = NULL row.
>
>
> We either need to force the index that we got the uniqueness information to be
> used when it is partial, or add the quals from the partial unique index to all
> other index scans.
I suspect this is an issue going back to 9c7f5229. Indeed, 9.6 doesn't
reproduce the issue (9c7f5229 was in 10). I haven't bisected it down to that,
but it seems pretty likely - and if it's not that commit, it's a closely
related one.
It's not immediately obvious to me how to nicely fix this in a backpatchable
way. An easy fix would be to not allow predicate indexes at all anymore in
relation_has_unique_index_for(), but that's a pretty big cannon - fixes the
issue though.
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-14 23:02 Tom Lane <tgl@sss.pgh.pa.us>
parent: Andres Freund <andres@anarazel.de>
0 siblings, 1 reply; 18+ messages in thread
From: Tom Lane @ 2023-06-14 23:02 UTC (permalink / raw)
To: Andres Freund <andres@anarazel.de>; +Cc: tel@jklm.no, pgsql-bugs@lists.postgresql.org, David Rowley <dgrowleyml@gmail.com>; Peter Geoghegan <pg@bowt.ie>
Andres Freund <andres@anarazel.de> writes:
> On 2023-06-14 14:12:31 -0700, Andres Freund wrote:
>> We either need to force the index that we got the uniqueness information to be
>> used when it is partial, or add the quals from the partial unique index to all
>> other index scans.
I did not study this example yet, but generally we ignore predicate
indexes unless their predicates can be proven from base restrictions
of their table (that's what predOK means). If the base restrictions
are enforced at scan level, which they should be, then uniqueness
should hold at any join level regardless of whether we actually
scanned with that index or some other way. Maybe we broke that
chain of reasoning somehow?
> It's not immediately obvious to me how to nicely fix this in a backpatchable
> way. An easy fix would be to not allow predicate indexes at all anymore in
> relation_has_unique_index_for(), but that's a pretty big cannon - fixes the
> issue though.
Yeah, that would be the easy way out if we don't find a better answer.
But right at the moment I don't understand why this is failing.
regards, tom lane
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-14 23:57 Andres Freund <andres@anarazel.de>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 18+ messages in thread
From: Andres Freund @ 2023-06-14 23:57 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: tel@jklm.no, pgsql-bugs@lists.postgresql.org, David Rowley <dgrowleyml@gmail.com>; Peter Geoghegan <pg@bowt.ie>
Hi,
On 2023-06-14 19:02:48 -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> writes:
> > On 2023-06-14 14:12:31 -0700, Andres Freund wrote:
> >> We either need to force the index that we got the uniqueness information to be
> >> used when it is partial, or add the quals from the partial unique index to all
> >> other index scans.
>
> I did not study this example yet, but generally we ignore predicate
> indexes unless their predicates can be proven from base restrictions
> of their table (that's what predOK means). If the base restrictions
> are enforced at scan level, which they should be, then uniqueness
> should hold at any join level regardless of whether we actually
> scanned with that index or some other way. Maybe we broke that
> chain of reasoning somehow?
It doesn't really hold at lower join levels with partial unique indexes, at
least as far as inner_unique goes. In this case we have one partial unique
index on b(c_id) WHERE a_id IS NOT NULL, and we have a plain index on b(c_id).
inner_unique is set to true based on the partial index - but then we decide
use the non-partial index for the index scan. That ends up returning a row
which with a_is = NULL, which won't find a match in the upper join levels. But
because the join is inner_unique, it'll not try to find another row on the
inner side.
> > It's not immediately obvious to me how to nicely fix this in a backpatchable
> > way. An easy fix would be to not allow predicate indexes at all anymore in
> > relation_has_unique_index_for(), but that's a pretty big cannon - fixes the
> > issue though.
>
> Yeah, that would be the easy way out if we don't find a better answer.
> But right at the moment I don't understand why this is failing.
Hope the above made it a bit clearer?
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-14 23:59 Tom Lane <tgl@sss.pgh.pa.us>
parent: Andres Freund <andres@anarazel.de>
0 siblings, 2 replies; 18+ messages in thread
From: Tom Lane @ 2023-06-14 23:59 UTC (permalink / raw)
To: Andres Freund <andres@anarazel.de>; +Cc: tel@jklm.no, pgsql-bugs@lists.postgresql.org, David Rowley <dgrowleyml@gmail.com>; Peter Geoghegan <pg@bowt.ie>
Andres Freund <andres@anarazel.de> writes:
> On 2023-06-14 19:02:48 -0400, Tom Lane wrote:
>> I did not study this example yet, but generally we ignore predicate
>> indexes unless their predicates can be proven from base restrictions
>> of their table (that's what predOK means).
> It doesn't really hold at lower join levels with partial unique indexes, at
> least as far as inner_unique goes. In this case we have one partial unique
> index on b(c_id) WHERE a_id IS NOT NULL, and we have a plain index on b(c_id).
> inner_unique is set to true based on the partial index - but then we decide
> use the non-partial index for the index scan. That ends up returning a row
> which with a_is = NULL, which won't find a match in the upper join
> levels.
But how did it decide that the partial index is predOK, if there's not
a qual forcing a_id to not be null?
regards, tom lane
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-15 00:09 Andres Freund <andres@anarazel.de>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 0 replies; 18+ messages in thread
From: Andres Freund @ 2023-06-15 00:09 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: tel@jklm.no, pgsql-bugs@lists.postgresql.org, David Rowley <dgrowleyml@gmail.com>; Peter Geoghegan <pg@bowt.ie>
Hi,
On 2023-06-14 19:59:26 -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> writes:
> > On 2023-06-14 19:02:48 -0400, Tom Lane wrote:
> >> I did not study this example yet, but generally we ignore predicate
> >> indexes unless their predicates can be proven from base restrictions
> >> of their table (that's what predOK means).
>
> > It doesn't really hold at lower join levels with partial unique indexes, at
> > least as far as inner_unique goes. In this case we have one partial unique
> > index on b(c_id) WHERE a_id IS NOT NULL, and we have a plain index on b(c_id).
> > inner_unique is set to true based on the partial index - but then we decide
> > use the non-partial index for the index scan. That ends up returning a row
> > which with a_is = NULL, which won't find a match in the upper join
> > levels.
>
> But how did it decide that the partial index is predOK, if there's not
> a qual forcing a_id to not be null?
There is - but it's at a higher join level. That would prevent us from
returning a wrongly matching row, but in the inner_unique case we don't even
get to that point.
We obviously could make it correct by injecting the relevant check into the
index scan on the inner side, but it doesn't look trivial to do so.
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-15 00:16 David Rowley <dgrowleyml@gmail.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 2 replies; 18+ messages in thread
From: David Rowley @ 2023-06-15 00:16 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Andres Freund <andres@anarazel.de>; tel@jklm.no, pgsql-bugs@lists.postgresql.org, Peter Geoghegan <pg@bowt.ie>
On Thu, 15 Jun 2023 at 11:59, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> Andres Freund <andres@anarazel.de> writes:
> > It doesn't really hold at lower join levels with partial unique indexes, at
> > least as far as inner_unique goes. In this case we have one partial unique
> > index on b(c_id) WHERE a_id IS NOT NULL, and we have a plain index on b(c_id).
> > inner_unique is set to true based on the partial index - but then we decide
> > use the non-partial index for the index scan. That ends up returning a row
> > which with a_is = NULL, which won't find a match in the upper join
> > levels.
>
> But how did it decide that the partial index is predOK, if there's not
> a qual forcing a_id to not be null?
In check_index_predicates(), we seem to use the results of
generate_join_implied_equalities() as index predicate proofs. That
seems fishy because surely those are only valid to use in cases after
the join for the particular predicate is evaluated.
In this case a.id = b.a_id AND c.id = b.c_id are used as proofs. I
didn't debug all the way, but I assume we deduce that the NOT NULL
index is ok due to the strict join quals.
David
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-15 00:23 David Rowley <dgrowleyml@gmail.com>
parent: David Rowley <dgrowleyml@gmail.com>
1 sibling, 0 replies; 18+ messages in thread
From: David Rowley @ 2023-06-15 00:23 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Andres Freund <andres@anarazel.de>; tel@jklm.no, pgsql-bugs@lists.postgresql.org, Peter Geoghegan <pg@bowt.ie>
On Thu, 15 Jun 2023 at 12:16, David Rowley <dgrowleyml@gmail.com> wrote:
>
> On Thu, 15 Jun 2023 at 11:59, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> > But how did it decide that the partial index is predOK, if there's not
> > a qual forcing a_id to not be null?
>
> In check_index_predicates(), we seem to use the results of
> generate_join_implied_equalities() as index predicate proofs. That
> seems fishy because surely those are only valid to use in cases after
> the join for the particular predicate is evaluated.
>
> In this case a.id = b.a_id AND c.id = b.c_id are used as proofs. I
> didn't debug all the way, but I assume we deduce that the NOT NULL
> index is ok due to the strict join quals.
Isn't it just a wrong assumption to use predOK for unique proofs for
all cases here. predOK seems ok to set to true for when it comes to
using that index for the query as by the time we finish evaluating all
the joins we'd have filtered out all rows that the partial index won't
contain... The problem just lies with the assumption that it's ok to
use the unique partial index as proofs before evaluation of all quals
that were used to determine predOK is true.
Perhaps we need another predOK field that just uses baserestrictinfos...
David
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-15 00:28 Tom Lane <tgl@sss.pgh.pa.us>
parent: David Rowley <dgrowleyml@gmail.com>
1 sibling, 1 reply; 18+ messages in thread
From: Tom Lane @ 2023-06-15 00:28 UTC (permalink / raw)
To: David Rowley <dgrowleyml@gmail.com>; +Cc: Andres Freund <andres@anarazel.de>; tel@jklm.no, pgsql-bugs@lists.postgresql.org, Peter Geoghegan <pg@bowt.ie>
David Rowley <dgrowleyml@gmail.com> writes:
> On Thu, 15 Jun 2023 at 11:59, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> But how did it decide that the partial index is predOK, if there's not
>> a qual forcing a_id to not be null?
> In this case a.id = b.a_id AND c.id = b.c_id are used as proofs. I
> didn't debug all the way, but I assume we deduce that the NOT NULL
> index is ok due to the strict join quals.
Ah. So the index is okay to use as far as the final result is
concerned, but it's not okay for the purpose to which it's being put.
I concur that we'd better just not use partial indexes in
relation_has_unique_index_for.
regards, tom lane
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-15 00:38 David Rowley <dgrowleyml@gmail.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 18+ messages in thread
From: David Rowley @ 2023-06-15 00:38 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Andres Freund <andres@anarazel.de>; tel@jklm.no, pgsql-bugs@lists.postgresql.org, Peter Geoghegan <pg@bowt.ie>
On Thu, 15 Jun 2023 at 12:28, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I concur that we'd better just not use partial indexes in
> relation_has_unique_index_for.
I wonder if that's ok for a backpatch. This affects both left join
removals and unique joins. Seems like suddenly making a left join
removal not work might cause someone some pain.
Is it worth trying to jam in a new boolean field into IndexOptInfo
into some spare padding to that we run predicate_implied_by() just
using baserestrictinfo and use those in
relation_has_unique_index_for()?
One problem might be that I don't see anywhere we could jam another
boolean into IndexOptInfo on 32-bit builds. Maybe we could put it at
the end given that we should only be making these structs in core?
David
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-15 00:50 Tom Lane <tgl@sss.pgh.pa.us>
parent: David Rowley <dgrowleyml@gmail.com>
0 siblings, 1 reply; 18+ messages in thread
From: Tom Lane @ 2023-06-15 00:50 UTC (permalink / raw)
To: David Rowley <dgrowleyml@gmail.com>; +Cc: Andres Freund <andres@anarazel.de>; tel@jklm.no, pgsql-bugs@lists.postgresql.org, Peter Geoghegan <pg@bowt.ie>
David Rowley <dgrowleyml@gmail.com> writes:
> On Thu, 15 Jun 2023 at 12:28, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I concur that we'd better just not use partial indexes in
>> relation_has_unique_index_for.
> I wonder if that's ok for a backpatch. This affects both left join
> removals and unique joins. Seems like suddenly making a left join
> removal not work might cause someone some pain.
I kind of doubt that this will affect any large number of users.
If it did, we'd have had reports sooner.
> Is it worth trying to jam in a new boolean field into IndexOptInfo
> into some spare padding to that we run predicate_implied_by() just
> using baserestrictinfo and use those in
> relation_has_unique_index_for()?
How will that work with the caching in innerrel_is_unique?
I also seriously doubt that we can make such a thing work
without adding parameters to any externally-visible functions.
regards, tom lane
^ permalink raw reply [nested|flat] 18+ messages in thread
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-15 04:33 David Rowley <dgrowleyml@gmail.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 18+ messages in thread
From: David Rowley @ 2023-06-15 04:33 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Andres Freund <andres@anarazel.de>; tel@jklm.no, pgsql-bugs@lists.postgresql.org, Peter Geoghegan <pg@bowt.ie>
On Thu, 15 Jun 2023 at 12:50, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> David Rowley <dgrowleyml@gmail.com> writes:
> > On Thu, 15 Jun 2023 at 12:28, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >> I concur that we'd better just not use partial indexes in
> >> relation_has_unique_index_for.
>
> > I wonder if that's ok for a backpatch. This affects both left join
> > removals and unique joins. Seems like suddenly making a left join
> > removal not work might cause someone some pain.
>
> I kind of doubt that this will affect any large number of users.
> If it did, we'd have had reports sooner.
OK, I've attached a patch for just not using partial indexes as
uniqueness proofs.
> > Is it worth trying to jam in a new boolean field into IndexOptInfo
> > into some spare padding to that we run predicate_implied_by() just
> > using baserestrictinfo and use those in
> > relation_has_unique_index_for()?
>
> How will that work with the caching in innerrel_is_unique?
> I also seriously doubt that we can make such a thing work
> without adding parameters to any externally-visible functions.
relation_has_unique_index_for() would just check this new field that
gets set only from baserestrictinfo quals. We'd just completely
ignore join quals for the new boolean field that'll be used in
relation_has_unique_index_for().
You're probably thinking that we could use join quals up to the level
that we've already joined to for unique joins. That's probably true,
but seems more complex than it might be worth to do that. I imagined
the majority of predOK are set to true based on baserestrictinfo
quals. I've no data to back that up, however. I was just trying to
think of ways to lessen the cases we regress from fixing this bug.
David
Attachments:
v1-0001-Don-t-use-partial-unique-indexes-for-unique-proof.patch (application/octet-stream, 5.6K)
download | inline diff:
From 2deda1edcc717a531b79231ce83da67c9ad92db2 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Thu, 15 Jun 2023 15:20:15 +1200
Subject: [PATCH v1] Don't use partial unique indexes for unique proofs in the
planner
Here we adjust relation_has_unique_index_for() so that it no longer makes
use of partial unique indexes as uniqueness proofs. It is incorrect to
use these as the predicates used by check_index_predicates() to set
predOK makes use of not only baserestrictinfo quals as proofs, but also
qual from join conditions. For relation_has_unique_index_for()'s case, we
need to know the relation is unique for a given set of columns before any
joins are evaluated, so if predOK was only set to true due to some join
qual, then it's unsafe to use such indexes in
relation_has_unique_index_for() as the final plan may not even make
use of that index, which could result in reading tuples that break the
uniqueness proofs that the index was supposedly enforcing.
We could maybe work a bit harder and add another field to IndexOptInfo
to record if the predicate is ok by just using the given baserestrictinfos
as proofs that the partial index can be used and make use of that field
instead in relation_has_unique_index_for(). However, uniqueness proofs
from such indexes are probably fairly rare.
Bug: #17975
Reported-by: Tor Erik Linnerud
Backpatch-through: 11, all supported versions
Discussion: https://postgr.es/m/17975-98a90c156f25c952%40postgresql.org
---
src/backend/optimizer/path/indxpath.c | 8 +++++---
src/backend/optimizer/plan/analyzejoins.c | 9 ++++-----
src/test/regress/expected/join.out | 17 +++++++++++++++++
src/test/regress/sql/join.sql | 9 +++++++++
4 files changed, 35 insertions(+), 8 deletions(-)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 1436dbc2f2..a1dcc63b37 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3549,10 +3549,12 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
/*
* If the index is not unique, or not immediately enforced, or if it's
- * a partial index that doesn't match the query, it's useless here.
+ * a partial index, it's useless here. We're unable to make use of predOK
+ * partial unique indexes due to the fact that check_index_predicates() also
+ * makes use of join predicates to determine if the partial index is usable.
+ * Here we need proofs that hold true before any joins are evaluated.
*/
- if (!ind->unique || !ind->immediate ||
- (ind->indpred != NIL && !ind->predOK))
+ if (!ind->unique || !ind->immediate || ind->indpred != NIL)
continue;
/*
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 6476e55e56..cd16bba63e 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -733,9 +733,9 @@ rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
/*
* For a plain relation, we only know how to prove uniqueness by
* reference to unique indexes. Make sure there's at least one
- * suitable unique index. It must be immediately enforced, and if
- * it's a partial index, it must match the query. (Keep these
- * conditions in sync with relation_has_unique_index_for!)
+ * suitable unique index. It must be immediately enforced, and not a
+ * partial index. (Keep these conditions in sync with
+ * relation_has_unique_index_for!)
*/
ListCell *lc;
@@ -743,8 +743,7 @@ rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
{
IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
- if (ind->unique && ind->immediate &&
- (ind->indpred == NIL || ind->predOK))
+ if (ind->unique && ind->immediate && ind->indpred == NIL)
return true;
}
}
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 98b2667821..b4d2ede4e8 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -7601,6 +7601,23 @@ left join j2 on j1.id1 = j2.id1 where j1.id2 = 1;
Output: j2.id1, j2.id2
(8 rows)
+create unique index j1_id2_idx on j1(id2) where id2 is not null;
+-- ensure we don't use a partial unique index as unique proofs
+explain (verbose, costs off)
+select * from j1
+inner join j2 on j1.id2 = j2.id2;
+ QUERY PLAN
+------------------------------------------
+ Nested Loop
+ Output: j1.id1, j1.id2, j2.id1, j2.id2
+ Join Filter: (j2.id2 = j1.id2)
+ -> Seq Scan on public.j2
+ Output: j2.id1, j2.id2
+ -> Seq Scan on public.j1
+ Output: j1.id1, j1.id2
+(7 rows)
+
+drop index j1_id2_idx;
-- validate logic in merge joins which skips mark and restore.
-- it should only do this if all quals which were used to detect the unique
-- are present as join quals, and not plain quals.
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 7daa390b1d..6191c05a92 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -2734,6 +2734,15 @@ explain (verbose, costs off)
select * from j1
left join j2 on j1.id1 = j2.id1 where j1.id2 = 1;
+create unique index j1_id2_idx on j1(id2) where id2 is not null;
+
+-- ensure we don't use a partial unique index as unique proofs
+explain (verbose, costs off)
+select * from j1
+inner join j2 on j1.id2 = j2.id2;
+
+drop index j1_id2_idx;
+
-- validate logic in merge joins which skips mark and restore.
-- it should only do this if all quals which were used to detect the unique
-- are present as join quals, and not plain quals.
--
2.39.2
* Re: BUG #17975: Nested Loop Index Scan returning wrong result
@ 2023-06-20 23:01 David Rowley <dgrowleyml@gmail.com>
parent: David Rowley <dgrowleyml@gmail.com>
0 siblings, 0 replies; 18+ messages in thread
From: David Rowley @ 2023-06-20 23:01 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Andres Freund <andres@anarazel.de>; tel@jklm.no, pgsql-bugs@lists.postgresql.org, Peter Geoghegan <pg@bowt.ie>
On Thu, 15 Jun 2023 at 16:33, David Rowley <dgrowleyml@gmail.com> wrote:
> OK, I've attached a patch for just not using partial indexes as
> uniqueness proofs.
I still have concerns about not doing anything for partial unique
indexes that are predOK as far as the baserestrictinfos are concerned.
I did push the patch to disable the unique join optimisation for all
partial unique indexes for now as we do need to at least fix the bug.
I've attached another patch which adds predOKBase and uses just
baserestrictinfo quals to set that field. If we were to backpatch
something like this, we'd need to figure out how to represent this new
field in IndexOptInfo. Changing the predOK bool to a uint8 and having
3 values might be an ok method.
David
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 0065c8992b..0a83db409b 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3294,7 +3294,8 @@ match_clause_to_ordering_op(IndexOptInfo *index,
void
check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
{
- List *clauselist;
+ List *basequals;
+ List *allquals;
bool have_partial;
bool is_target_rel;
Relids otherrels;
@@ -3320,6 +3321,8 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
if (!have_partial)
return;
+ basequals = rel->baserestrictinfo;
+
/*
* Construct a list of clauses that we can assume true for the purpose of
* proving the index(es) usable. Restriction clauses for the rel are
@@ -3327,7 +3330,7 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
* rel. Also, we can consider any EC-derivable join clauses (which must
* be "movable to" this rel, by definition).
*/
- clauselist = list_copy(rel->baserestrictinfo);
+ allquals = list_copy(rel->baserestrictinfo);
/* Scan the rel's join clauses */
foreach(lc, rel->joininfo)
@@ -3338,7 +3341,7 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
if (!join_clause_is_movable_to(rinfo, rel))
continue;
- clauselist = lappend(clauselist, rinfo);
+ allquals = lappend(allquals, rinfo);
}
/*
@@ -3357,8 +3360,8 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
otherrels = bms_del_members(otherrels, rel->nulling_relids);
if (!bms_is_empty(otherrels))
- clauselist =
- list_concat(clauselist,
+ allquals =
+ list_concat(allquals,
generate_join_implied_equalities(root,
bms_union(rel->relids,
otherrels),
@@ -3396,8 +3399,16 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
if (index->indpred == NIL)
continue; /* ignore non-partial indexes here */
+ if (!index->predOKBase)
+ index->predOKBase = predicate_implied_by(index->indpred,
+ basequals, false);
+
+ /* if the index satisfies the basequals, don't check allquals */
+ if (index->predOKBase)
+ index->predOK = true;
+
if (!index->predOK) /* don't repeat work if already proven OK */
- index->predOK = predicate_implied_by(index->indpred, clauselist,
+ index->predOK = predicate_implied_by(index->indpred, allquals,
false);
/* If rel is an update target, leave indrestrictinfo as set above */
@@ -3549,13 +3560,11 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
/*
* If the index is not unique, or not immediately enforced, or if it's
- * a partial index, it's useless here. We're unable to make use of
- * predOK partial unique indexes due to the fact that
- * check_index_predicates() also makes use of join predicates to
- * determine if the partial index is usable. Here we need proofs that
- * hold true before any joins are evaluated.
+ * a partial index that doesn't match the rel's baserestrictinfo, it's
+ * useless here.
*/
- if (!ind->unique || !ind->immediate || ind->indpred != NIL)
+ if (!ind->unique || !ind->immediate ||
+ (ind->indpred != NIL && !ind->predOKBase))
continue;
/*
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 5f3cce873a..6322a70070 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -801,9 +801,9 @@ rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
/*
* For a plain relation, we only know how to prove uniqueness by
* reference to unique indexes. Make sure there's at least one
- * suitable unique index. It must be immediately enforced, and not a
- * partial index. (Keep these conditions in sync with
- * relation_has_unique_index_for!)
+ * suitable unique index. It must be immediately enforced, and if
+ * it's a partial index, it must match the rel's baserestrictinfo.
+ * (Keep these conditions in sync with relation_has_unique_index_for!)
*/
ListCell *lc;
@@ -811,7 +811,8 @@ rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
{
IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
- if (ind->unique && ind->immediate && ind->indpred == NIL)
+ if (ind->unique && ind->immediate &&
+ (ind->indpred == NIL || ind->predOKBase))
return true;
}
}
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 39932d3c2d..e18c4890de 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -427,6 +427,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
info->indrestrictinfo = NIL; /* set later, in indxpath.c */
info->predOK = false; /* set later, in indxpath.c */
+ info->predOKBase = false; /* set later, in indxpath.c */
info->unique = index->indisunique;
info->immediate = index->indimmediate;
info->hypothetical = false;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index c17b53f7ad..84d61ef32a 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1159,8 +1159,10 @@ struct IndexOptInfo
*/
List *indrestrictinfo;
- /* true if index predicate matches query */
+ /* true if index predicate matches query (including join quals) */
bool predOK;
+ /* true if index predicate matches rel's baserestrictinfo */
+ bool predOKBase;
/* true if a unique index */
bool unique;
/* is uniqueness enforced immediately? */
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 6917faec14..44e53d0e6b 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -7692,7 +7692,8 @@ left join j2 on j1.id1 = j2.id1 where j1.id2 = 1;
(8 rows)
create unique index j1_id2_idx on j1(id2) where id2 is not null;
--- ensure we don't use a partial unique index as unique proofs
+-- ensure we don't use partial unique indexes that were marked predOK as
+-- unique proofs for unique joins.
explain (verbose, costs off)
select * from j1
inner join j2 on j1.id2 = j2.id2;
@@ -7707,6 +7708,24 @@ inner join j2 on j1.id2 = j2.id2;
Output: j1.id1, j1.id2
(7 rows)
+-- we can use the unique index if it's marked as predOKBase
+explain (verbose, costs off)
+select * from j1
+inner join j2 on j1.id2 = j2.id2
+where j1.id2 is not null;
+ QUERY PLAN
+------------------------------------------
+ Nested Loop
+ Output: j1.id1, j1.id2, j2.id1, j2.id2
+ Inner Unique: true
+ Join Filter: (j2.id2 = j1.id2)
+ -> Seq Scan on public.j2
+ Output: j2.id1, j2.id2
+ -> Seq Scan on public.j1
+ Output: j1.id1, j1.id2
+ Filter: (j1.id2 IS NOT NULL)
+(9 rows)
+
drop index j1_id2_idx;
-- validate logic in merge joins which skips mark and restore.
-- it should only do this if all quals which were used to detect the unique
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 55080bec9a..104c0b7d15 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -2781,11 +2781,18 @@ left join j2 on j1.id1 = j2.id1 where j1.id2 = 1;
create unique index j1_id2_idx on j1(id2) where id2 is not null;
--- ensure we don't use a partial unique index as unique proofs
+-- ensure we don't use partial unique indexes that were marked predOK as
+-- unique proofs for unique joins.
explain (verbose, costs off)
select * from j1
inner join j2 on j1.id2 = j2.id2;
+-- we can use the unique index if it's marked as predOKBase
+explain (verbose, costs off)
+select * from j1
+inner join j2 on j1.id2 = j2.id2
+where j1.id2 is not null;
+
drop index j1_id2_idx;
-- validate logic in merge joins which skips mark and restore.
Attachments:
predOKBase.patch (text/plain, 7.7K)
download | inline diff:
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 0065c8992b..0a83db409b 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3294,7 +3294,8 @@ match_clause_to_ordering_op(IndexOptInfo *index,
void
check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
{
- List *clauselist;
+ List *basequals;
+ List *allquals;
bool have_partial;
bool is_target_rel;
Relids otherrels;
@@ -3320,6 +3321,8 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
if (!have_partial)
return;
+ basequals = rel->baserestrictinfo;
+
/*
* Construct a list of clauses that we can assume true for the purpose of
* proving the index(es) usable. Restriction clauses for the rel are
@@ -3327,7 +3330,7 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
* rel. Also, we can consider any EC-derivable join clauses (which must
* be "movable to" this rel, by definition).
*/
- clauselist = list_copy(rel->baserestrictinfo);
+ allquals = list_copy(rel->baserestrictinfo);
/* Scan the rel's join clauses */
foreach(lc, rel->joininfo)
@@ -3338,7 +3341,7 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
if (!join_clause_is_movable_to(rinfo, rel))
continue;
- clauselist = lappend(clauselist, rinfo);
+ allquals = lappend(allquals, rinfo);
}
/*
@@ -3357,8 +3360,8 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
otherrels = bms_del_members(otherrels, rel->nulling_relids);
if (!bms_is_empty(otherrels))
- clauselist =
- list_concat(clauselist,
+ allquals =
+ list_concat(allquals,
generate_join_implied_equalities(root,
bms_union(rel->relids,
otherrels),
@@ -3396,8 +3399,16 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
if (index->indpred == NIL)
continue; /* ignore non-partial indexes here */
+ if (!index->predOKBase)
+ index->predOKBase = predicate_implied_by(index->indpred,
+ basequals, false);
+
+ /* if the index satisfies the basequals, don't check allquals */
+ if (index->predOKBase)
+ index->predOK = true;
+
if (!index->predOK) /* don't repeat work if already proven OK */
- index->predOK = predicate_implied_by(index->indpred, clauselist,
+ index->predOK = predicate_implied_by(index->indpred, allquals,
false);
/* If rel is an update target, leave indrestrictinfo as set above */
@@ -3549,13 +3560,11 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
/*
* If the index is not unique, or not immediately enforced, or if it's
- * a partial index, it's useless here. We're unable to make use of
- * predOK partial unique indexes due to the fact that
- * check_index_predicates() also makes use of join predicates to
- * determine if the partial index is usable. Here we need proofs that
- * hold true before any joins are evaluated.
+ * a partial index that doesn't match the rel's baserestrictinfo, it's
+ * useless here.
*/
- if (!ind->unique || !ind->immediate || ind->indpred != NIL)
+ if (!ind->unique || !ind->immediate ||
+ (ind->indpred != NIL && !ind->predOKBase))
continue;
/*
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 5f3cce873a..6322a70070 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -801,9 +801,9 @@ rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
/*
* For a plain relation, we only know how to prove uniqueness by
* reference to unique indexes. Make sure there's at least one
- * suitable unique index. It must be immediately enforced, and not a
- * partial index. (Keep these conditions in sync with
- * relation_has_unique_index_for!)
+ * suitable unique index. It must be immediately enforced, and if
+ * it's a partial index, it must match the rel's baserestrictinfo.
+ * (Keep these conditions in sync with relation_has_unique_index_for!)
*/
ListCell *lc;
@@ -811,7 +811,8 @@ rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
{
IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
- if (ind->unique && ind->immediate && ind->indpred == NIL)
+ if (ind->unique && ind->immediate &&
+ (ind->indpred == NIL || ind->predOKBase))
return true;
}
}
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 39932d3c2d..e18c4890de 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -427,6 +427,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
info->indrestrictinfo = NIL; /* set later, in indxpath.c */
info->predOK = false; /* set later, in indxpath.c */
+ info->predOKBase = false; /* set later, in indxpath.c */
info->unique = index->indisunique;
info->immediate = index->indimmediate;
info->hypothetical = false;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index c17b53f7ad..84d61ef32a 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1159,8 +1159,10 @@ struct IndexOptInfo
*/
List *indrestrictinfo;
- /* true if index predicate matches query */
+ /* true if index predicate matches query (including join quals) */
bool predOK;
+ /* true if index predicate matches rel's baserestrictinfo */
+ bool predOKBase;
/* true if a unique index */
bool unique;
/* is uniqueness enforced immediately? */
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 6917faec14..44e53d0e6b 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -7692,7 +7692,8 @@ left join j2 on j1.id1 = j2.id1 where j1.id2 = 1;
(8 rows)
create unique index j1_id2_idx on j1(id2) where id2 is not null;
--- ensure we don't use a partial unique index as unique proofs
+-- ensure we don't use partial unique indexes that were marked predOK as
+-- unique proofs for unique joins.
explain (verbose, costs off)
select * from j1
inner join j2 on j1.id2 = j2.id2;
@@ -7707,6 +7708,24 @@ inner join j2 on j1.id2 = j2.id2;
Output: j1.id1, j1.id2
(7 rows)
+-- we can use the unique index if it's marked as predOKBase
+explain (verbose, costs off)
+select * from j1
+inner join j2 on j1.id2 = j2.id2
+where j1.id2 is not null;
+ QUERY PLAN
+------------------------------------------
+ Nested Loop
+ Output: j1.id1, j1.id2, j2.id1, j2.id2
+ Inner Unique: true
+ Join Filter: (j2.id2 = j1.id2)
+ -> Seq Scan on public.j2
+ Output: j2.id1, j2.id2
+ -> Seq Scan on public.j1
+ Output: j1.id1, j1.id2
+ Filter: (j1.id2 IS NOT NULL)
+(9 rows)
+
drop index j1_id2_idx;
-- validate logic in merge joins which skips mark and restore.
-- it should only do this if all quals which were used to detect the unique
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 55080bec9a..104c0b7d15 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -2781,11 +2781,18 @@ left join j2 on j1.id1 = j2.id1 where j1.id2 = 1;
create unique index j1_id2_idx on j1(id2) where id2 is not null;
--- ensure we don't use a partial unique index as unique proofs
+-- ensure we don't use partial unique indexes that were marked predOK as
+-- unique proofs for unique joins.
explain (verbose, costs off)
select * from j1
inner join j2 on j1.id2 = j2.id2;
+-- we can use the unique index if it's marked as predOKBase
+explain (verbose, costs off)
+select * from j1
+inner join j2 on j1.id2 = j2.id2
+where j1.id2 is not null;
+
drop index j1_id2_idx;
-- validate logic in merge joins which skips mark and restore.
end of thread, other threads:[~2023-06-20 23:01 UTC | newest]
Thread overview: 18+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2023-06-14 15:17 BUG #17975: Nested Loop Index Scan returning wrong result PG Bug reporting form <noreply@postgresql.org>
2023-06-14 20:36 ` Andres Freund <andres@anarazel.de>
2023-06-14 21:10 ` Peter Geoghegan <pg@bowt.ie>
2023-06-14 21:21 ` Andres Freund <andres@anarazel.de>
2023-06-14 21:38 ` Peter Geoghegan <pg@bowt.ie>
2023-06-14 21:12 ` Andres Freund <andres@anarazel.de>
2023-06-14 22:49 ` Andres Freund <andres@anarazel.de>
2023-06-14 23:02 ` Tom Lane <tgl@sss.pgh.pa.us>
2023-06-14 23:57 ` Andres Freund <andres@anarazel.de>
2023-06-14 23:59 ` Tom Lane <tgl@sss.pgh.pa.us>
2023-06-15 00:09 ` Andres Freund <andres@anarazel.de>
2023-06-15 00:16 ` David Rowley <dgrowleyml@gmail.com>
2023-06-15 00:23 ` David Rowley <dgrowleyml@gmail.com>
2023-06-15 00:28 ` Tom Lane <tgl@sss.pgh.pa.us>
2023-06-15 00:38 ` David Rowley <dgrowleyml@gmail.com>
2023-06-15 00:50 ` Tom Lane <tgl@sss.pgh.pa.us>
2023-06-15 04:33 ` David Rowley <dgrowleyml@gmail.com>
2023-06-20 23:01 ` David Rowley <dgrowleyml@gmail.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox