Cross-type index comparison support in contrib/btree_gin

I wrote:

We've had multiple requests for $SUBJECT over the years
([1][2][3][4][5], and I'm sure my archive search missed some).
I finally decided to look into what it'd take to make that happen.

I forgot to mention a couple of questions for review:

... it turns out that the
comparePartial() method is only ever applied to compare the original
query value with an index entry, which means that internally to
comparePartial() we can apply the proper cross-type comparison
operator. Our GIN index documentation about comparePartial() doesn't
quite say that in so many words, but btree_gin was already relying on
it --- in a very confusing and ill-explained way, if you ask me, but
it was relying on it.

Should we adjust the documentation of comparePartial() to promise
explicitly that partial_key is the same datum returned by extractQuery?
By my reading, it kind of implies that, but it's not quite black and
white.

So basically all I had to do was write a bunch of non-error-throwing
conversion routines and set up some boilerplate infrastructure.

In the 0005 patch, I relied on date2timestamp_opt_overflow and
its siblings where available. But some of the conversions such
as timestamptz-to-timestamp don't have one of those, so I was
forced to copy-and-paste some fairly low-level code. Would it
make sense to refactor the related core routines to expose
xxx2yyy_opt_overflow interfaces, extending what 5bc450629 and
52ad1e659 did? I wouldn't think this worth doing just for
btree_gin's benefit, but if btree_gin needs it maybe some other
extensions could use it too.

regards, tom lane

I wrote:

I forgot to mention a couple of questions for review:

Should we adjust the documentation of comparePartial() to promise
explicitly that partial_key is the same datum returned by extractQuery?
By my reading, it kind of implies that, but it's not quite black and
white.

In the 0005 patch, I relied on date2timestamp_opt_overflow and
its siblings where available. But some of the conversions such
as timestamptz-to-timestamp don't have one of those, so I was
forced to copy-and-paste some fairly low-level code. Would it
make sense to refactor the related core routines to expose
xxx2yyy_opt_overflow interfaces, extending what 5bc450629 and
52ad1e659 did?

After further review it seems like both of those things would be
improvements, so here's a v2 that does it like that. This also
adds a PG_USED_FOR_ASSERTS_ONLY marker whose lack was pointed
out by the cfbot; no other meaningful changes.

regards, tom lane

v3 needed to rebase over 55527368b. (I guess "git am" cannot
tolerate any fuzz at all?) No changes of any significance
whatsoever.

regards, tom lane

On Fri, Mar 28, 2025 at 4:22 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

v3 needed to rebase over 55527368b. (I guess "git am" cannot
tolerate any fuzz at all?) No changes of any significance
whatsoever.

regards, tom lane

Hi!

Thank you for working on this.

I tried the patch and it compiles and works as expected. Several minor
things I noticed:

1) btree_gin.c

case BTEqualStrategyNumber:
if (cmp > 0)
res = -1; /* keep scanning */
else if (cmp == 0)
res = 0;
else
res = 1; /* end scan */
break;

I think the code is correct, but do we need to continue scanning here?
I can't think of an example where we have cmp == 0 after cmp > 0.
Maybe we can use cmp != 0 as a stopping condition?

2) btree_gin.c

switch (data->strategy & 7)
{
case BTLessStrategyNumber:

There are two places where we extract btree_start from the input
strategy. Maybe we can store the extracted value in QueryInfo? Or
create macros to avoid code duplication.

3) float4.sql

-- Check endpoint and out-of-range cases

INSERT INTO test_float4 VALUES ('NaN'), ('Inf'), ('-Inf');

It seems that this test data is in the pending list during the test.
Not sure if we want them to be in the entry tree or not? The same with
date.sql and timestamp.sql.

4)
On 02.02.2025 04:44, Tom Lane wrote:

...

* Query value falls between possible values of the index type
(possible in float8->float4 or timestamp->date cases, for example).
We can just use our usual conversion rules, though. The critical
observation here is that it does not matter whether the conversion
rounds to the next lower or next higher possible value. If we are
searching for equality, neither of those values will pass the
cross-type comparison so it doesn't matter. If we are searching for
inequality, for example "indcol <= value", then only index entries
strictly less than the query value can match. Rounding down clearly
doesn't hurt, while rounding up at worst makes the search include
some index entries just larger than the query value, which will be
correctly rejected by the cross-type comparison.

I agree with the statements. It's quite a tricky part as for me,
probably it's better to add tests for this special case as it's done
for 'out of range' cases. FWIW while testing the patch I wrote some
tests for these rounding cases, I'm ready to add it to the patchset.

Thank you!

Best regards,
Arseniy Mukhin

Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes:

I tried the patch and it compiles and works as expected. Several minor
things I noticed:

Thanks for looking at it!

1) btree_gin.c

case BTEqualStrategyNumber:
if (cmp > 0)
res = -1; /* keep scanning */
else if (cmp == 0)
res = 0;
else
res = 1; /* end scan */
break;

I think the code is correct, but do we need to continue scanning here?
I can't think of an example where we have cmp == 0 after cmp > 0.
Maybe we can use cmp != 0 as a stopping condition?

No, I think you're reading the code backward. cmp > 0 means the
current index entry is less than the query's search value, so we
need to keep scanning forward to see if there's any entries that
match. We can stop when we get to larger entries, with cmp < 0.

I found this sign convention confusing too, and considered reversing
the comparison call so that the "cmp" comparisons in this function
would all flip. But I felt that such a change maybe doesn't belong
in this patch. Also I wasn't sure other people would agree that
it'd be an improvement --- the original code author, for one,
presumably finds this natural.

2) btree_gin.c

switch (data->strategy & 7)
{
case BTLessStrategyNumber:

There are two places where we extract btree_start from the input
strategy. Maybe we can store the extracted value in QueryInfo? Or
create macros to avoid code duplication.

Hardly seems worth maintaining an extra field to get rid of a
bit-masking operation. But maybe a macro would improve readability.

3) float4.sql

-- Check endpoint and out-of-range cases

INSERT INTO test_float4 VALUES ('NaN'), ('Inf'), ('-Inf');

It seems that this test data is in the pending list during the test.
Not sure if we want them to be in the entry tree or not? The same with
date.sql and timestamp.sql.

Good point, it probably makes more sense to force the data into
the entry tree. It's not the charter of these tests to verify
that the pending-list works properly.

* Query value falls between possible values of the index type
(possible in float8->float4 or timestamp->date cases, for example).
We can just use our usual conversion rules, though. The critical
observation here is that it does not matter whether the conversion
rounds to the next lower or next higher possible value.

I agree with the statements. It's quite a tricky part as for me,
probably it's better to add tests for this special case as it's done
for 'out of range' cases. FWIW while testing the patch I wrote some
tests for these rounding cases, I'm ready to add it to the patchset.

Makes sense. Do you want to prepare the next patch version, then?

regards, tom lane

On Tue, Jul 1, 2025 at 11:21 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes:

I tried the patch and it compiles and works as expected. Several minor
things I noticed:

Thanks for looking at it!

1) btree_gin.c

case BTEqualStrategyNumber:
if (cmp > 0)
res = -1; /* keep scanning */
else if (cmp == 0)
res = 0;
else
res = 1; /* end scan */
break;

I think the code is correct, but do we need to continue scanning here?
I can't think of an example where we have cmp == 0 after cmp > 0.
Maybe we can use cmp != 0 as a stopping condition?

No, I think you're reading the code backward. cmp > 0 means the
current index entry is less than the query's search value, so we
need to keep scanning forward to see if there's any entries that
match. We can stop when we get to larger entries, with cmp < 0.

Sorry, I think I wasn't clear enough. I agree with this logic, but I
think it implies an impossible scenario for the "equals" case. The
scenario where during a scan we first have keys that are less than
orig_datum, and then a key that is equal to orig_datum. Why I think
such a scenario is impossible: GIN uses partial_key as a lower bound
when positioning the start of a partial match scan. So if there is any
key in the index that is equal to "partial key", it must be the very
first key in the scan. Then if the very first key in the scan is less
than orig_datum, that means partial_key was also less than orig_datum
(because partial_key is a lower bound). And the only reason
partial_key might not be equal to orig_datum is that there is no value
equal to orig_datum in the index type. So we can say that if the very
first key in the scan is less than orig_datum, then there is no key in
the index that could be equal to orig_datum, and we can stop right
there. In fact, we can catch this right after converting from
orig_datum to entry_datum, but it would make the code more complex. I
think it's similar to what you wrote in the comment about out of range
values.

I found this sign convention confusing too, and considered reversing
the comparison call so that the "cmp" comparisons in this function
would all flip. But I felt that such a change maybe doesn't belong
in this patch. Also I wasn't sure other people would agree that
it'd be an improvement --- the original code author, for one,
presumably finds this natural.

Comments helped me a lot with all these cmp branches.

* Query value falls between possible values of the index type
(possible in float8->float4 or timestamp->date cases, for example).
We can just use our usual conversion rules, though. The critical
observation here is that it does not matter whether the conversion
rounds to the next lower or next higher possible value.

I agree with the statements. It's quite a tricky part as for me,
probably it's better to add tests for this special case as it's done
for 'out of range' cases. FWIW while testing the patch I wrote some
tests for these rounding cases, I'm ready to add it to the patchset.

Makes sense. Do you want to prepare the next patch version, then?

regards, tom lane

Yeah, here is a new version with tests for rounding cases.

Best regards,
Arseniy Mukhin

Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes:

Sorry, I think I wasn't clear enough. I agree with this logic, but I
think it implies an impossible scenario for the "equals" case. The
scenario where during a scan we first have keys that are less than
orig_datum, and then a key that is equal to orig_datum. Why I think
such a scenario is impossible: GIN uses partial_key as a lower bound
when positioning the start of a partial match scan. So if there is any
key in the index that is equal to "partial key", it must be the very
first key in the scan. Then if the very first key in the scan is less
than orig_datum, that means partial_key was also less than orig_datum
(because partial_key is a lower bound). And the only reason
partial_key might not be equal to orig_datum is that there is no value
equal to orig_datum in the index type. So we can say that if the very
first key in the scan is less than orig_datum, then there is no key in
the index that could be equal to orig_datum, and we can stop right
there.

OK, I got your point finally. It seems perhaps a little fragile
to write the code like this, but I agree that it should work.

v5 attached incorporates your test additions and responds to your
other review suggestions. Also, I changed the representation of
the opclass strategy numbers to use 4 bits for the btree strategy,
because I realized that we could write the strategy numbers in the
.sql file as hex literals and thereby improve readability --- the
RHS type and the btree strategy are now independent hex digits
in the DDL.

regards, tom lane

On Wed, Jul 2, 2025 at 8:59 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes:

Sorry, I think I wasn't clear enough. I agree with this logic, but I
think it implies an impossible scenario for the "equals" case. The
scenario where during a scan we first have keys that are less than
orig_datum, and then a key that is equal to orig_datum. Why I think
such a scenario is impossible: GIN uses partial_key as a lower bound
when positioning the start of a partial match scan. So if there is any
key in the index that is equal to "partial key", it must be the very
first key in the scan. Then if the very first key in the scan is less
than orig_datum, that means partial_key was also less than orig_datum
(because partial_key is a lower bound). And the only reason
partial_key might not be equal to orig_datum is that there is no value
equal to orig_datum in the index type. So we can say that if the very
first key in the scan is less than orig_datum, then there is no key in
the index that could be equal to orig_datum, and we can stop right
there.

OK, I got your point finally. It seems perhaps a little fragile
to write the code like this, but I agree that it should work.

v5 attached incorporates your test additions and responds to your
other review suggestions. Also, I changed the representation of
the opclass strategy numbers to use 4 bits for the btree strategy,
because I realized that we could write the strategy numbers in the
.sql file as hex literals and thereby improve readability --- the
RHS type and the btree strategy are now independent hex digits
in the DDL.

Thanks!

Sql file is definitely more readable now. I think the patch is ready.
Should I move it to "Ready for Committer" status or do we need more
reviews or something?

Best regards,
Arseniy Mukhin

Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes:

Sql file is definitely more readable now. I think the patch is ready.
Should I move it to "Ready for Committer" status or do we need more
reviews or something?

If you have no further comments, I agree it's ready. Please mark
as RfC, just for pro-forma process.

regards, tom lane

On Thu, Jul 3, 2025 at 10:21 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes:

Sql file is definitely more readable now. I think the patch is ready.
Should I move it to "Ready for Committer" status or do we need more
reviews or something?

If you have no further comments, I agree it's ready. Please mark
as RfC, just for pro-forma process.

Done.

Best regards,
Arseniy Mukhin

Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes:

On Thu, Jul 3, 2025 at 10:21 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

If you have no further comments, I agree it's ready. Please mark
as RfC, just for pro-forma process.

Done.

And pushed. Thanks for reviewing!

regards, tom lane