Re: DRAFT GIST support for ORDER BY

On Mon, 30 Oct 2023 at 14:39, Michał Kłeczek <michal@kleczek.org> wrote:
>> On 30 Oct 2023, at 13:31, Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:
>>
>>> The problem is though that right now handling of ORDER BY column clauses is tightly coupled to BTree.
>>> It would be good to refactor the code so that semantics of ORDER BY column could be more flexible.
>>
>> The existence of a BTREE operator class for the type is the indicator
>> that (and how) the type can be ordered - that is where PostgreSQL gets
>> its methods for ordering most types. Although I agree that it's a
>> quirk, I don't mind it that much as an indicator of how a type is
>> ordered.
>> I do agree, though, that operator classes by themselves should be able
>> to say "hey, we support full ordered retrieval as well". Right now,
>> that seems to be limited to btrees, but indeed a GiST index with
>> btree_gist columns should be able to support the same.
>
> Right now opfamily and strategy are set in PathKey before creating index scan paths.
>
> The patch actually copies existing code from create_indexscan_plan
> that finds an operator OID for (pk_opfamily, pk_strategy).
> The operator is supposed to be binary with specific operand types.
>
> To create a path:
> 1) do the operator OID lookup as above
> 2) look for sortfamily of pg_amop entry for (operator did, index opfamily)
> If the sort family is the same as pk_opfamily we can create a path.
>
> The side effect is that it is possible to “ORDER BY column < ‘constant’” as we have more ordering operators in
pg_amop.
>
> Ideally we could look up _unary_ operator in pg_amop instead - that would make sense we are actually measuring some
“absolutedistance”. 
> But this would require more changes - createplan.c would need to decide when to lookup unary and when - binary
operator.

After researching this a bit more, I'm confused: If I register an opclass

CREATE OPERATOR CLASS gist_mytype_btree
DEFUALT FOR mytype USING gist
AS
    OPERATOR 1 < (mytype, mytype) FOR ORDER BY mytype_ops, -- operator
<(mytype, mytype) returns bool
    ...
    OPERATOR 15 <-> (mytype, mytype) FOR ORDER BY mytype_ops. --
operator <->(mytype, mytype) returns mytype
    ...

Then which order of values does the system expect the index to return
tuples in when either of these operators is applied?
Is that
  ORDER BY (index_column opr constant); but bool isn't the type
supported by the FOR ORDER BY opclass, or
  ORDER BY (index_column); but this makes no sense for distance operators.

After looking at get_relation_info() in optimizer/util/plancat.c, I
guess the difference is the difference between amhandler->amcanorder
vs amhandler->amcanorderbyop? But still it's not quite clear what the
implication for this is. Does it mean an index AM can either provide
natural ordering, or operator ordering, but not both?

>>> ORDER BY a == ORDER BY a <-> MIN_VALUE
>>> and
>>> ORDER BY a DESC == ORDER BY a <-> MAX_VALUE
>>>
>>> This allows implementing GIST ordered scans for btree_gist datatypes.
>>>
>>> This in turn makes using GIST with partitioning feasible (I have described issues with such usage in my previous
e-mails- see below). 
>>
>> Did you take into account that GiST's internal distance function uses
>> floating point, and is thus only an approximation for values that
>> require more than 2^54 significant bits in their distance function?
>> For example, GiST wouldn't be guaranteed to yield correct ordering of
>> int8/bigint when you use `my_column <-> UINT64_MAX` because as far as
>> the floating point math is concerned, 0 is about as far away from
>> INT64_MAX as (say) 20 and -21.
>
> Hmm… Good point but it means ORDER BY <-> is broken for these types then?
> The patch assumes it works correctly and just uses it for ordered scans.

Huh, I didn't know this before, but apparently values are pushed onto
a reorderqueue/pairingheap if the index scan is marked
xs_recheckorderby (i.e. when the tuple order is not exact), which
would be used in this case.

So it seems like this wouldn't be much of an issue for the patch,
apart from the potential issue where this could use the pairingheap
much more than the usual ordered scan operations, which could result
in larger-than-normal memory usage. E.g. float btree ops wouldn't work
effectively at all because every reasonable value is extremely distant
from its max value.

Kind regards,

Matthias van de Meent