Horton

Thread

Commits

  1. Add more cross-type comparisons to contrib/btree_gin.

  2. Add cross-type comparisons to contrib/btree_gin.

  3. Break out xxx2yyy_opt_overflow APIs for more datetime conversions.

  1. Cross-type index comparison support in contrib/btree_gin

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-02-02T01:44:12Z

    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.
It's not as bad as I feared, and attached is a draft patch.

The thing that makes this sticky is that GIN itself doesn't support
any such thing as cross-type comparisons: all the Datums that it deals
with directly have to be of the same type as the stored index keys.
However, for the cases that btree_gin deals with, we can make use of
the "partial match" feature because all the entries we need to find
will be consecutive in the index.  And 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.  (The 0001 patch below is mainly concerned with
making that reliance simpler and clearer.)

The other thing that has to be dealt with is that cross-type or not,
we need to somehow create a Datum of the index key type to perform
the initial index descent with.  But I realized that this isn't
that tough after all.  Aside from boring change-of-representation
work, there are these special cases:

* Query value is out of range for the index type.  We can simply
clamp it to the index type's range, so that GIN descends to one
end of the index or the other and then searches normally.  GIN
might falsely think that the endmost entry(s) of the index equal
the search datum, but it doesn't matter too much what GIN thinks
because comparePartial can filter away the false matches by
applying the correct comparison with the original query value.

* 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.

So basically all I had to do was write a bunch of non-error-throwing
conversion routines and set up some boilerplate infrastructure.
Patch series attached --- it's rather long, but a lot of it is
new test cases.

			regards, tom lane

[1] https://www.postgresql.org/message-id/flat/58782480-ab75-4416-a177-ccf91be288a9%40app.fastmail.com
[2] https://www.postgresql.org/message-id/flat/17079-c5edf57c47debc2c%40postgresql.org
[3] https://www.postgresql.org/message-id/flat/20170207150420.1409.58748%40wrigleys.postgresql.org
[4] https://www.postgresql.org/message-id/flat/20160415185902.22924.77993%40wrigleys.postgresql.org
[5] https://www.postgresql.org/message-id/flat/VisenaEmail.42.91df4628bdf7755c.1537e96e852%40tc7-visena

  2. Re: Cross-type index comparison support in contrib/btree_gin

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-02-02T16:47:13Z

    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

  3. Re: Cross-type index comparison support in contrib/btree_gin

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-02-07T22:41:32Z

    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

  4. Re: Cross-type index comparison support in contrib/btree_gin

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-03-28T01:22:19Z

    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

  5. Re: Cross-type index comparison support in contrib/btree_gin

    Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> — 2025-07-01T09:35:29Z

    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

  6. Re: Cross-type index comparison support in contrib/btree_gin

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-07-01T20:21:15Z

    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

  7. Re: Cross-type index comparison support in contrib/btree_gin

    Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> — 2025-07-02T15:43:50Z

    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

  8. Re: Cross-type index comparison support in contrib/btree_gin

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-07-02T17:59:17Z

    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

  9. Re: Cross-type index comparison support in contrib/btree_gin

    Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> — 2025-07-03T19:07:07Z

    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

  10. Re: Cross-type index comparison support in contrib/btree_gin

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-07-03T19:21:55Z

    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

  11. Re: Cross-type index comparison support in contrib/btree_gin

    Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> — 2025-07-03T19:35:59Z

    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

  12. Re: Cross-type index comparison support in contrib/btree_gin

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-07-03T20:31:14Z

    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