Index plan returns different results to sequential scan

On 3/21/24 18:25, John Burns wrote:

Hi…

...

Although the postcode package is probably not especially significant
in the scheme of things , the behaviour of indexed versus non-indexed
queries is worrisome.

Seems like a thinko in the indexing, but that's just a guess.

I’ve had to make a couple of minor changes to the postcode package
as the Postgres versions have changed, i.e. define TRUE and FALSE in
the c header files and change the location of the include files when
Postgres 16 arrived, but nothing else.

Can you share a patch with the tweaks?

I’ve attached a sample data file to populate a table that exhibits
the behaviour, and the tweaked version of the Postcode package.

I don't see any attachments :-(

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 3/21/24 21:08, John Burns wrote:

On 21 Mar 2024, at 20:27, Tomas Vondra <tomas.vondra@enterprisedb.com> wrote:

Sorry about that … the patched version of the package, plus a sample data set is in the attached zip file,

-John

Thanks, I can reproduce the issue. I don't know why is it happening, but
the behavior I see is that the (postcode % 'NW10') query somehow misses
rows with postcodes 'NW10 0AA' - 'NW10 3NL' when executed using index.

I don't see anything obviously wrong in the extension / index pages.

You suggested it used to work OK and then broke. Do you perhaps know at
which version it broke? Or did you use 9.x until now, upgrades to 16 and
realized it's broken?

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 3/22/24 00:58, Tomas Vondra wrote:

On 3/21/24 21:08, John Burns wrote:

On 21 Mar 2024, at 20:27, Tomas Vondra <tomas.vondra@enterprisedb.com> wrote:

Sorry about that … the patched version of the package, plus a sample data set is in the attached zip file,

-John

Thanks, I can reproduce the issue. I don't know why is it happening, but
the behavior I see is that the (postcode % 'NW10') query somehow misses
rows with postcodes 'NW10 0AA' - 'NW10 3NL' when executed using index.

I don't see anything obviously wrong in the extension / index pages.

You suggested it used to work OK and then broke. Do you perhaps know at
which version it broke? Or did you use 9.x until now, upgrades to 16 and
realized it's broken?

After some bisecting, this seems to be broken since this PG12 commit:

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=dd299df8189bd00fbe54b72c64f43b6af2ffeccd

==========================================================================
commit dd299df8189bd00fbe54b72c64f43b6af2ffeccd
tree 931ef720687d61cf5e75464fa0b1c1d75fb3f9d3 tree
parent e5adcb789d80ba565ccacb1ed4341a7c29085238 commit | diff
Make heap TID a tiebreaker nbtree index column.

Make nbtree treat all index tuples as having a heap TID attribute.
Index searches can distinguish duplicates by heap TID, since heap TID is
always guaranteed to be unique. This general approach has numerous
benefits for performance, and is prerequisite to teaching VACUUM to
perform "retail index tuple deletion".

...
==========================================================================

I don't know what the problem is, or whether it's a big in PG or in the
postcode extension (I agree the extension is fairly straightforward).

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thu, Mar 21, 2024 at 9:22 PM Tomas Vondra
<tomas.vondra@enterprisedb.com> wrote:

I don't know what the problem is, or whether it's a big in PG or in the
postcode extension (I agree the extension is fairly straightforward).

Could you try running amcheck's bt_index_check function against the index?

--
Peter Geoghegan

I’m sorry, but I can’t really say when it broke — we suspect when we went from version 14 to 16 — we use this functionality a lot, and we would have noticed long ago if it was wrong.

As additional information, I created a new operator that used another function — wrapping the function postcode_cmp_partial(...) = 0 — and it exhibited the same behaviour.
Not surprised since the postcode_eq_partial is a trivially simple function.

— John Burns

On 3/22/24 02:40, Peter Geoghegan wrote:

On Thu, Mar 21, 2024 at 9:22 PM Tomas Vondra
<tomas.vondra@enterprisedb.com> wrote:

I don't know what the problem is, or whether it's a big in PG or in the
postcode extension (I agree the extension is fairly straightforward).

Could you try running amcheck's bt_index_check function against the index?

I tried (on master). It doesn't report anything:

test=# select bt_index_check('xxx_postcode_idx', 't');
bt_index_check
----------------

(1 row)

I also tried looking at the index using bt_page_items from pageinspect,
and I did not notice anything obviously wrong. But I don't have much
experience with btree at such low level ...

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 3/22/24 08:43, Tomas Vondra wrote:

On 3/22/24 02:40, Peter Geoghegan wrote:

On Thu, Mar 21, 2024 at 9:22 PM Tomas Vondra
<tomas.vondra@enterprisedb.com> wrote:

I don't know what the problem is, or whether it's a big in PG or in the
postcode extension (I agree the extension is fairly straightforward).

Could you try running amcheck's bt_index_check function against the index?

I tried (on master). It doesn't report anything:

test=# select bt_index_check('xxx_postcode_idx', 't');
bt_index_check
----------------

(1 row)

I also tried looking at the index using bt_page_items from pageinspect,
and I did not notice anything obviously wrong. But I don't have much
experience with btree at such low level ...

I realized I can create an index on e5adcb789, apply dd299df81 and
create another index, and then compare what bt_page_items says for those.

FWIW xxx_postcode_idx (created before e5adcb789) keeps returning the
correct data even after dd299df81 gets applied.

I'll only show 5 rows - the only difference is in the first item (which
I guess is hikey?), all other items are exactly the same.

For the index created on e5adcb789 (that returns the correct results
even with the new build), I get this:

test=# select * from bt_page_items(get_Raw_page('xxx_postcode_idx', 1))
limit 5;
itemoffset | ctid | itemlen | nulls | vars | data
------------+--------+---------+-------+------+-------------------------
1 | (2,15) | 16 | f | f | ce 51 20 50 00 00 00 00
2 | (0,1) | 16 | f | f | 27 48 20 01 00 00 00 00
3 | (0,2) | 16 | f | f | 30 48 20 01 00 00 00 00
4 | (0,3) | 16 | f | f | 41 48 20 01 00 00 00 00
5 | (0,4) | 16 | f | f | 41 48 20 01 00 00 00 00
(5 rows)

test=# select * from bt_page_items(get_Raw_page('xxx_postcode_idx', 2))
limit 5;
itemoffset | ctid | itemlen | nulls | vars | data
------------+--------+---------+-------+------+-------------------------
1 | (4,5) | 16 | f | f | 25 60 20 50 00 00 00 00
2 | (2,15) | 16 | f | f | ce 51 20 50 00 00 00 00
3 | (2,16) | 16 | f | f | d3 51 20 50 00 00 00 00
4 | (2,17) | 16 | f | f | d3 51 20 50 00 00 00 00
5 | (2,18) | 16 | f | f | d3 51 20 50 00 00 00 00
(5 rows)

test=# select * from bt_page_items(get_Raw_page('xxx_postcode_idx', 3))
limit 5;
itemoffset | ctid | itemlen | nulls | vars | data
------------+--------+---------+-------+------+-------------------------
1 | (1,0) | 8 | f | f |
2 | (2,15) | 16 | f | f | ce 51 20 50 00 00 00 00
3 | (4,5) | 16 | f | f | 25 60 20 50 00 00 00 00
(3 rows)

test=# select * from bt_page_items(get_Raw_page('xxx_postcode_idx', 4))
limit 5;
itemoffset | ctid | itemlen | nulls | vars | data
------------+-------+---------+-------+------+-------------------------
1 | (4,5) | 16 | f | f | 25 60 20 50 00 00 00 00
2 | (4,6) | 16 | f | f | 25 60 20 50 00 00 00 00
3 | (4,7) | 16 | f | f | 25 60 20 50 00 00 00 00
4 | (4,8) | 16 | f | f | 25 60 20 50 00 00 00 00
5 | (4,9) | 16 | f | f | 30 60 20 50 00 00 00 00
(5 rows)

while for the index created with dd299df81 (and returning incomplete
results) I get this:

test=# select * from bt_page_items(get_Raw_page('xxx2_postcode_idx', 1))
limit 5;
itemoffset | ctid | itemlen | nulls | vars | data
------------+-------+---------+-------+------+-------------------------
1 | (2,1) | 16 | f | f | ce 51 20 50 00 00 00 00
2 | (0,1) | 16 | f | f | 27 48 20 01 00 00 00 00
3 | (0,2) | 16 | f | f | 30 48 20 01 00 00 00 00
4 | (0,3) | 16 | f | f | 41 48 20 01 00 00 00 00
5 | (0,4) | 16 | f | f | 41 48 20 01 00 00 00 00
(5 rows)

test=# select * from bt_page_items(get_Raw_page('xxx2_postcode_idx', 2))
limit 5;
itemoffset | ctid | itemlen | nulls | vars |
data
------------+----------+---------+-------+------+-------------------------------------------------
1 | (4,4097) | 24 | f | f | 25 60 20 50 00 00 00
00 00 00 00 00 04 00 04 00
2 | (2,15) | 16 | f | f | ce 51 20 50 00 00 00 00
3 | (2,16) | 16 | f | f | d3 51 20 50 00 00 00 00
4 | (2,17) | 16 | f | f | d3 51 20 50 00 00 00 00
5 | (2,18) | 16 | f | f | d3 51 20 50 00 00 00 00
(5 rows)

test=# select * from bt_page_items(get_Raw_page('xxx2_postcode_idx', 3))
limit 5;
itemoffset | ctid | itemlen | nulls | vars |
data
------------+----------+---------+-------+------+-------------------------------------------------
1 | (1,0) | 8 | f | f |
2 | (2,1) | 16 | f | f | ce 51 20 50 00 00 00 00
3 | (4,4097) | 24 | f | f | 25 60 20 50 00 00 00
00 00 00 00 00 04 00 04 00
(3 rows)

test=# select * from bt_page_items(get_Raw_page('xxx2_postcode_idx', 4))
limit 5;
itemoffset | ctid | itemlen | nulls | vars | data
------------+-------+---------+-------+------+-------------------------
1 | (4,5) | 16 | f | f | 25 60 20 50 00 00 00 00
2 | (4,6) | 16 | f | f | 25 60 20 50 00 00 00 00
3 | (4,7) | 16 | f | f | 25 60 20 50 00 00 00 00
4 | (4,8) | 16 | f | f | 25 60 20 50 00 00 00 00
5 | (4,9) | 16 | f | f | 30 60 20 50 00 00 00 00
(5 rows)

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thu, Mar 21, 2024 at 2:03 PM John Burns <john@impactdatametrics.com> wrote:

The query is SELECT * FROM XXX where postcode % ’NW10’
To create a sample table — create table XXX ( udprn bigint, postcode postcode )
To Index it CREATE INDEX on XXX(postcode)

The opfamily's % operator uses the B-Tree equality strategy. This
means that it works the same way as = works in most other opfamilies.

I don't see how equality can work reliably here. A query with a
predicate "WHERE my_indexed_postcode_column % ‘NW10’" seems to work by
masking the value stored in the index, throwing away some amount of
suffix bytes in the process. But the values from the index are still
stored in their original order -- the temporarily masked suffix bytes
aren't masked in the index, of course (they're only masked
temporarily, by the cross-type equality operator %).

Wouldn't you need something closer to "WHERE
my_indexed_postcode_column >= ‘NW10’ and my_indexed_postcode_column <
‘NW11’" for this to work reliably?

The relevant rules for btree operator families are described here:

https://www.postgresql.org/docs/devel/btree-behavior.html

Offhand, I suspect that you don't see problems pre-12 B-Tree because
the B-Tree code happened to have been more forgiving of opfamilies
that were broken in this way. Earlier versions treated < and <= as the
same thing in certain contexts.

--
Peter Geoghegan

On 3/23/24 03:24, Peter Geoghegan wrote:

On Thu, Mar 21, 2024 at 2:03 PM John Burns <john@impactdatametrics.com> wrote:

The query is SELECT * FROM XXX where postcode % ’NW10’
To create a sample table — create table XXX ( udprn bigint, postcode postcode )
To Index it CREATE INDEX on XXX(postcode)

The opfamily's % operator uses the B-Tree equality strategy. This
means that it works the same way as = works in most other opfamilies.

I don't see how equality can work reliably here. A query with a
predicate "WHERE my_indexed_postcode_column % ‘NW10’" seems to work by
masking the value stored in the index, throwing away some amount of
suffix bytes in the process. But the values from the index are still
stored in their original order -- the temporarily masked suffix bytes
aren't masked in the index, of course (they're only masked
temporarily, by the cross-type equality operator %).

Wouldn't you need something closer to "WHERE
my_indexed_postcode_column >= ‘NW10’ and my_indexed_postcode_column <
‘NW11’" for this to work reliably?

Yeah, I was not sure how come this could be processed using equality
operator, but I got distracted by bisecting this to a particular commit.
I didn't realize the commit might have changed how much we rely on the
opfamily to do things correctly.

I do think the '%' operator is pretty close to what we do for LIKE with
prefix patterns for text:

explain select * from t where a like 'aa%';
QUERY PLAN
-----------------------------------------------------------------------
Index Only Scan using t_a_idx on t (cost=0.29..4.31 rows=1 width=33)
Index Cond: ((a ~>=~ 'aa'::text) AND (a ~<~ 'ab'::text))
Filter: (a ~~ 'aa%'::text)
(3 rows)

So I guess postcode would need to do something similar - treat the '%'
operator as separate from opclass equality, and define a new support
procedure akin to text_support, translating the '%' into the range quals
that can match the index.

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company