[PG19] btree_gin misses rows for a timestamptz bound in the repeated DST hour

Started by shihao zhongabout 1 month ago4 messageshackers
Jump to latest
#1shihao zhong
zhong950419@gmail.com

Hi hackers,

This is Medium 4 from my list in [1]/messages/by-id/CAGRkXqSFdjqZP_kwRz7dv6LHX-CSrkDnynNXgntRsCEnQTKxmg@mail.gmail.com.

Since fc896821c44, a btree_gin index on a timestamp column can be
used to compare with a timestamptz value. When that value is in the
first pass of the repeated hour at the end of DST, the index scan
misses rows.

create extension btree_gin;
set timezone = 'America/New_York';
create table t (ts timestamp);
insert into t values ('2026-11-01 01:10'), ('2026-11-01 01:40');
create index on t using gin (ts);
set enable_seqscan = off;
select * from t where ts >= '2026-11-01 01:30-04'::timestamptz;

master returns only 01:40. 18 returns both rows, and so does master
with a seq scan.

0001 converts the start key back to timestamptz. If the result is
after the bound, it moves the key earlier by the difference. Here the
key becomes 00:30. The scan already rechecks each entry with the real
operator, so nothing extra is returned. 0002 adds a test. The patches
apply to master and REL_19_STABLE.

A date column goes through the same kind of conversion. I could not
make it fail, also not in the Cuba time zone where midnight repeats.
A bound in the spring gap can give wrong rows too, but a plain btree
index does the same there, so I left it alone.

The commit came from [2]/messages/by-id/262624.1738460652@sss.pgh.pa.us.

[1]: /messages/by-id/CAGRkXqSFdjqZP_kwRz7dv6LHX-CSrkDnynNXgntRsCEnQTKxmg@mail.gmail.com
/messages/by-id/CAGRkXqSFdjqZP_kwRz7dv6LHX-CSrkDnynNXgntRsCEnQTKxmg@mail.gmail.com
[2]: /messages/by-id/262624.1738460652@sss.pgh.pa.us

Thanks,
Shihao

Attachments:

t254170_1
v1-0002-btree_gin-Test-timestamptz-bound-in-repeated-DST-.patchapplication/octet-stream; name=v1-0002-btree_gin-Test-timestamptz-bound-in-repeated-DST-.patchDownload+41-1
v1-0001-btree_gin-Fix-timestamptz-lower-bound-in-repeated.patchapplication/octet-stream; name=v1-0001-btree_gin-Fix-timestamptz-lower-bound-in-repeated.patchDownload+15-1
#2Tom Lane
tgl@sss.pgh.pa.us
In reply to: shihao zhong (#1)
Re: [PG19] btree_gin misses rows for a timestamptz bound in the repeated DST hour

shihao zhong <zhong950419@gmail.com> writes:

Since fc896821c44, a btree_gin index on a timestamp column can be
used to compare with a timestamptz value. When that value is in the
first pass of the repeated hour at the end of DST, the index scan
misses rows.

Hm, good catch. The comparisons themselves are done correctly, but we
are failing to obtain a starting point that is guaranteed <= the first
matching index row.

0001 converts the start key back to timestamptz. If the result is
after the bound, it moves the key earlier by the difference. Here the
key becomes 00:30.

I think that's assuming way too much about the behavior of the
timezone code. I'd be inclined to use logic more along the line
of "compare to the original value using the relevant comparison
function; if greater, subtract an hour and try again".

Also, doesn't cvt_timestamptz_date have the same issue? I think
it'd only be at risk in a zone where midnight is part of the
repeatable hour, but there are some like that.

regards, tom lane

#3shihao zhong
zhong950419@gmail.com
In reply to: shihao zhong (#1)
Re: [PG19] btree_gin misses rows for a timestamptz bound in the repeated DST hour

Hi Tom,

I think that's assuming way too much about the behavior of the

timezone code. I'd be inclined to use logic more along the line
of "compare to the original value using the relevant comparison
function; if greater, subtract an hour and try again".

Done in v2. cvt_timestamptz_timestamp now moves the key back an hour
while timestamp_cmp_timestamptz_internal() says it is later than the
bound.

Also, doesn't cvt_timestamptz_date have the same issue?

I could not make it fail in a test over every backward clock change
in tzdata, and the code agrees. The key is the local date of the
bound. An earlier date can only compare as later than the bound if
the clock goes back by more than a whole day. The biggest step back
in tzdata is exactly 24 hours, Alaska in 1867. If you'd rather not
rely on that, the same loop with result-- works there and I can add
it.

Thanks,
Shihao

Attachments:

t254170_2
v2-0001-btree_gin-Fix-timestamptz-lower-bound-in-repeated.patchapplication/octet-stream; name=v2-0001-btree_gin-Fix-timestamptz-lower-bound-in-repeated.patchDownload+9-1
v2-0002-btree_gin-Test-timestamptz-bound-in-repeated-DST-.patchapplication/octet-stream; name=v2-0002-btree_gin-Test-timestamptz-bound-in-repeated-DST-.patchDownload+41-1
#4Tom Lane
tgl@sss.pgh.pa.us
In reply to: shihao zhong (#3)
Re: [PG19] btree_gin misses rows for a timestamptz bound in the repeated DST hour

shihao zhong <zhong950419@gmail.com> writes:

Done in v2. cvt_timestamptz_timestamp now moves the key back an hour
while timestamp_cmp_timestamptz_internal() says it is later than the
bound.

OK. It occurred to me that another source of a converted timestamp
appearing larger than the given value is if we produce timestamp
infinity from a value close to the maximum finite timestamptz.
I'm not quite convinced whether that can lead to problems, but
at the least it complicates reasoning about the behavior because
we again lose the property that result compares <= val. So just
ignoring the case as your patch does seems risky. I made it
look like this instead:

if (TIMESTAMP_IS_NOEND(result))
result = END_TIMESTAMP;
while (timestamp_cmp_timestamptz_internal(result, val) > 0)
result -= USECS_PER_HOUR;

Also, doesn't cvt_timestamptz_date have the same issue?

I could not make it fail in a test over every backward clock change
in tzdata, and the code agrees. The key is the local date of the
bound. An earlier date can only compare as later than the bound if
the clock goes back by more than a whole day. The biggest step back
in tzdata is exactly 24 hours, Alaska in 1867. If you'd rather not
rely on that, the same loop with result-- works there and I can add
it.

Hm. I feel a little itchy about that, but as long as we can't point
to a failure case I'm okay with leaving cvt_timestamptz_date alone.

Pushed with that correction and some cosmetic foolery.

regards, tom lane