Thread: Re: Index AM API cleanup

I want to call out one particular aspect that is central to this patch
series that needs more broader discussion and agreement.

The problem is that btree indexes (and to a lesser extent hash
indexes) are hard-coded in various places.  This includes various
places in the optimizer (see patch v17-0018) that might be harder to
understand, but also more easy-to-understand places such as:

- Only hash and btree are supported for replica identity.  (see patch 
v17-0015)

- Only btree is supported for speculative insertion.  (see patch v17-0016)

- Only btree is supported for foreign keys.  (see patch v17-0017)

- Only btree can participate in merge join.  (see patch v17-0020)

The problem in cases such as these, and some of them actually contain
code comments about this, is that we somehow need to know what the
equality operator (and in some cases ordering operator) for a type is.
And the way this is currently done is that the btree and hash strategy
numbers are hardcoded, and other index AMs are just not supported
because there is no way to find that out from those.

We faced a similar issue for the temporal primary keys feature.  One
thing this feature had to overcome is that

- Only btree is supported for primary keys.

For that feature, we wanted to add support for gist indexes, and we
had to again find a way to get the equals operator (and also the
overlaps operator).

The solution we ended up with there is to add a support function to
gist that translates the strategy numbers used by the operator class
to "well-known" strategy numbers that we can understand (commit
7406ab623fe).  It later turned out that this problem actually might be
a subset of the general problem being discussed here, so we can also
change that solution if we find a more general solution here.

So the question is, how do we communicate these fundamental semantics
of operators?

The solution we discussed for temporal primary keys is that we just
mandate that certain strategy numbers have fixed meanings.  This is
how btree and hash work anyway, but this was never required for gist.
And there are many gist opclass implementations already out there that
don't use compatible strategy numbers, so that solution would not have
worked (at least without some upgrading pain).  Hence the idea of
mapping the actual strategy numbers to a fixed set of well-known ones.

For the general case across all index AMs, we could similarly decree
that all index AMs use certain strategy numbers for fixed purposes.
But again, this already wouldn't work for gist and perhaps others
already out there.  So here again we need some kind of mapping to
numbers with a fixed purpose.  Or perhaps new index AMs can start out
with the "correct" numbers and only some existing ones would need the
mapping.

And then what do you map them to?

One idea would be to map them to the existing btree numbers.  This
could work, but I always found it kind of confusing that you'd then
have multiple sets of strategy numbers in play, one native to the
index AM or opclass, and one sort of global one.

Another idea is to map them to another thing altogether, a new enum.
This is what this patch series does, essentially.  But it turns out
(so argues the patch series), that this enum already exists, namely

typedef enum RowCompareType
{
     /* Values of this enum are chosen to match btree strategy numbers */
     ROWCOMPARE_LT = 1,          /* BTLessStrategyNumber */
     ROWCOMPARE_LE = 2,          /* BTLessEqualStrategyNumber */
     ROWCOMPARE_EQ = 3,          /* BTEqualStrategyNumber */
     ROWCOMPARE_GE = 4,          /* BTGreaterEqualStrategyNumber */
     ROWCOMPARE_GT = 5,          /* BTGreaterStrategyNumber */
     ROWCOMPARE_NE = 6,          /* no such btree strategy */
} RowCompareType;

which in spite of the name, yes, sounds like exactly that kind of
thing.  And it's also used in many places for this kind of thing
already.

The patch series adds index AM callbacks

     amtranslatestrategy
     amtranslaterctype

to convert between strategy number and RowCompareType, and also adds

     ROWCOMPARE_NONE
     ROWCOMPARE_INVALID

to handle cases where there is no mapping.  I suppose for the temporal
PK use, we would need to add something like ROWCOMPARE_OVERLAPS.

So this is the idea.  To take a step back, I can see the following
options:

1. Require all index AMs to use btree-compatible strategy numbers.
    (Previously rejected, too much upgrading mess.)

2. Provide mapping between index AM strategy numbers and btree strategy
    numbers.  (This doesn't have a space for non-btree operations like
    overlaps.)

3. Provide mapping between index AM strategy numbers and the existing
    RT*StrategyNumber numbers.  (We can expand the set as we want.)
    (This is what the existing mapping function for gist does.)

4. Provide mapping between index AM strategy numbers and some
    completely new set of numbers/symbols.

5. Provide mapping between index AM strategy numbers and
    RowCompareType (with some small extensions).  This is what this
    patch does.

Other ideas?  Thoughts?

> On Oct 30, 2024, at 12:54 PM, Peter Eisentraut <peter@eisentraut.org> wrote:
>
> So this is the idea.  To take a step back, I can see the following
> options:
>
> 1. Require all index AMs to use btree-compatible strategy numbers.
>   (Previously rejected, too much upgrading mess.)
>
> 2. Provide mapping between index AM strategy numbers and btree strategy
>   numbers.  (This doesn't have a space for non-btree operations like
>   overlaps.)

I agree that neither of these options are good, for the reasons you mention.

> 3. Provide mapping between index AM strategy numbers and the existing
>   RT*StrategyNumber numbers.  (We can expand the set as we want.)
>   (This is what the existing mapping function for gist does.)

The point of such a mapping is that core code outside any index AM can know what an AM is claiming it can do when it
advertisesthat it implements one of these strategy numbers.  We don't need any new entries in that mapping until some
corefeature depends on the semantics of the new entry.  Right now, all six of the btree comparators (including
not-equal)have semantics that are used outside AMs by functions like match_clause_to_ordering_op().  If any index AM
authorcomes along and creates an index AM which purports to provide these six semantics but actually does something
semanticallyinconsistent with what the backend thinks these mean, that index AM is totally at fault when, for example,
ORDERBY returns the wrong results. 

On the other hand, if we add RTOverlapStrategyNumber to the common framework of strategy numbers, without anything
outsidean index AM depending on that, how is an index AM author to know exactly how an "overlaps" operator is supposed
tobehave?  No doubt, brin, gist, spgist, and friends all have their own understanding of what RTOverlapStrategyNumber
means,but how is a new index AM supposed to know if it has analogized that concept correctly to its own operator?  And
ifseveral major versions later, you come along to create some feature, let's say a logical replication feature
dependingon "overlaps" semantics, how are you to know whether all the index AMs in the wild which advertise they
providean "overlaps" operator will work correctly with your new feature?  When logical replication breaks, who is at
fault? Perversely, knowing that RTOverlapStrategyNumber is already in the list, you would likely implement the new
logicalreplication feature on some new strategy number, perhaps naming it RTLogicalOverlapStrategyNumber, to avoid such
conflicts.

The RT*StrategyNumber list is much too long, containing many such problematic entries.  We should not, in my opinion,
addthese to the list prior to some new feature which depends on them, such as a planner or executor optimization. 

> 4. Provide mapping between index AM strategy numbers and some
>   completely new set of numbers/symbols.

This is fine, if the new set is sufficiently restricted.  However, as mentioned below, the set of sufficiently
restrictedvalues is identical to what we currently define as a RowCompareType.  It creates needless code churn to throw
thataway and replace it with a new name. 

> 5. Provide mapping between index AM strategy numbers and
>   RowCompareType (with some small extensions).  This is what this
>   patch does.

As the patch author, obviously this is the one I chose.  The "small extensions" are just to handle "no such value" type
cases.


—
Mark Dilger
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company