Subject: Table AM Interface Enhancements

From: Alexander Korotkov <[email-masked]>
Date: Thu, 23 Nov 2023 14:42:49 +0200

Hello PostgreSQL Hackers,

I am pleased to submit a series of patches related to the Table Access
Method (AM) interface, which I initially announced during my talk at
PGCon 2023 [1]. These patches are primarily designed to support the
OrioleDB engine, but I believe they could be beneficial for other
table AM implementations as well.

The focus of these patches is to introduce more flexibility and
capabilities into the Table AM interface. This is particularly
relevant for advanced use cases like index-organized tables,
alternative MVCC implementations, etc.

Here's a brief overview of the patches included in this set:

0001-Allow-locking-updated-tuples-in-tuple_update-and--v1.patch

Optimizes the process of locking concurrently updated tuples during
update and delete operations. Helpful for table AMs where refinding
existing tuples is expensive.

0002-Add-EvalPlanQual-delete-returning-isolation-test-v1.patch

The new isolation test is related to the previous patch.  These two
patches were previously discussed in [2].

0003-Allow-table-AM-to-store-complex-data-structures-i-v1.patch

Allows table AM to store complex data structure in rd_amcache rather
than a single chunk of memory.

0004-Add-table-AM-tuple_is_current-method-v1.patch

This allows us to abstract how/whether table AM uses transaction identifiers.

0005-Generalize-relation-analyze-in-table-AM-interface-v1.patch

Provides a more flexible API for sampling tuples, beneficial for
non-standard table types like index-organized tables.

0006-Generalize-table-AM-API-for-INSERT-.-ON-CONFLICT-v1.patch

Provides a new table AM API method to encapsulate the whole INSERT ...
ON CONFLICT ... algorithm rather than just implementation of
speculative tokens.

0007-Allow-table-AM-tuple_insert-method-to-return-the--v1.patch

This allows table AM to return a native tuple slot, which is aware of
table AM-specific system attributes.

0008-Let-table-AM-insertion-methods-control-index-inse-v1.patch

Allows table AM to skip index insertions in the executor and handle
those insertions itself.

0009-Custom-reloptions-for-table-AM-v1.patch

Enables table AMs to define and override reloptions for tables and indexes.

0010-Notify-table-AM-about-index-creation-v1.patch

Allows table AMs to prepare or update specific meta-information during
index creation.

011-Introduce-RowRefType-which-describes-the-table-ro-v1.patch

Separates the row identifier type from the lock mode in RowMarkType,
providing clearer semantics and more flexibility.

0012-Introduce-RowID-bytea-tuple-identifier-v1.patch

`This patch introduces 'RowID', a new bytea tuple identifier, to
overcome the limitations of the current 32-bit block number and 16-bit
offset-based tuple identifier. This is particularly useful for
index-organized tables and other advanced use cases.

Each commit message contains a detailed explanation of the changes and
their rationale. I believe these enhancements will significantly
improve the flexibility and capabilities of the PostgreSQL Table AM
interface.

I am looking forward to your feedback and suggestions on these patches.

Links

1. https://www.pgcon.org/events/pgcon_2023/schedule/session/470-future-of-table-access-methods/
2. https://www.postgresql.org/message-id/CAPpHfdua-YFw3XTprfutzGp28xXLigFtzNbuFY8yPhqeq6X5kg%40mail.gmail.com

------
Regards,
Alexander Korotkov

---

From: Matthias van de Meent <[email-masked]>
Date: Fri, 24 Nov 2023 00:07:12 +0100

Hi,

> Here's a brief overview of the patches included in this set:

Note: no significant review of the patches, just a first response on
the cover letters and oddities I noticed:

Overall, this patchset adds significant API area to TableAmRoutine,
without adding the relevant documentation on how it's expected to be
used. With the overall size of the patchset also being very
significant, I don't think this patch is reviewable as is; the goal
isn't clear enough, the APIs aren't well explained, and the
interactions with the index API are left up in the air.

> existing tuples is expensive.

Is this essentially an optimized implementation of the "DELETE FROM
... RETURNING *" per-tuple primitive?

> than a single chunk of memory.

I don't think we should allow arbitrarily large and arbitrarily many
chunks of data in the relcache or table caches. Why isn't one chunk
enough?

> This allows us to abstract how/whether table AM uses transaction identifiers.

I'm not a fan of the indirection here. Also, assuming that table slots
don't outlive transactions, wouldn't this be a more appropriate fit
with the table tuple slot API?

> ON CONFLICT ... algorithm rather than just implementation of

Does this not still require speculative inserts, with speculative
tokens, for secondary indexes? Why make AMs implement that all over
again?

> table AM-specific system attributes.

This seems reasonable.

> Allows table AM to skip index insertions in the executor and handle

Who handles index tuple removal then? I don't see a patch that
describes index AM changes for this...

> Allows table AMs to prepare or update specific meta-information during

I don't think the described use case of this API is OK - a table AM
cannot know about the internals of index AMs, and is definitely not
allowed to overwrite the information of that index.
If I ask for an index that uses the "btree" index, then that needs to
be the AM actually used, or an error needs to be raised if it is
somehow incompatible with the table AM used. It can't be that we
silently update information and create an index that is explicitly not
what the user asked to create.

I also don't see updates in documentation, which I think is quite a
shame as I have trouble understanding some parts.

> index-organized tables and other advanced use cases.

We don't have any index methods that can handle anything but
block+offset TIDs, and I don't see any changes to the IndexAM APIs to
support these RowID tuples, so what's the plan here? I don't see any
of that in the commit message, nor in the rest of this patchset.

> improve the flexibility and capabilities of the PostgreSQL Table AM

I've noticed there is not a lot of rationale for several of the
changes as to why PostgreSQL needs these changes implemented like
this, amongst which the index-related tableAM changes.

I understand that index-organized tables can be quite useful, but I
don't see design solutions to the more complex questions that would
still be required before we could host such table AMs like OreoleDB's
as a first-party citizen: For index-organized tables, you also need
index AM APIs that support TIDS with more than 48 bits of data
(assuming we actually want primary keys with >48 bits of usable
space), and for undo-based logging you would probably need index APIs
for retail index tuple deletion. Neither is supplied here, nor is
described why these APIs were omitted.

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)

---

From: Alexander Korotkov <[email-masked]>
Date: Sun, 3 Mar 2024 13:48:07 +0200

Hi, Matthias!

On Fri, Nov 24, 2023 at 1:07 AM Matthias van de Meent
<[email-masked]> wrote:
> used.

I have to note that, unlike documentation for index access methods,
our documentation for table access methods doesn't have an explanation
of API functions.  Instead, it just refers to tableam.h for details.
The patches touching tableam.h also revise relevant comments.  These
comments are for sure a target for improvements.

> With the overall size of the patchset also being very
> significant

I wouldn't say that volume is very significant.  It's just 2K lines,
not the great size of a patchset.  But it for sure represents changes
of great importance.

> I don't think this patch is reviewable as is; the goal
> isn't clear enough,

The goal is to revise table AM API so that new full-featured
implementations could exist.  AFAICS, the current API was designed
keeping zheap in mind, but even zheap was always shipped with the core
patch.  All other implementations of table AM, which I've seen, are
very limited.  Basically, there is still no real alternative and
functional OLTP table AM.  I believe API limitation is one of the
reasons for that.

> the APIs aren't well explained, and

As I mentioned before, the table AM API is documented by the comments
in tableam.h.  The comments in the patchset aren't perfect for sure,
but a subject for the incremental improvements.

> the interactions with the index API are left up in the air.

Right.  These patches bring more control on interactions with indexes
to table AMs without touching the index API.  In my PGCon 2016 talk I
proposed that table AM could have its own implementation of index AM.

As you mentioned before, this patchset isn't very small already.
Considering it all together with a patchset for index AM redesign
would make it a mess.  I propose we can consider here the patches,
which are usable by themselves even without index AM changes.  And the
patches tightly coupled with index AM API changes could be considered
later together with those changes.

> ... RETURNING *" per-tuple primitive?

Not really.  The test for "DELETE FROM ... RETURNING *" was used just
to reproduce one of the bugs stopped in [2].  The general idea is to
avoid repeated calls for tuple lock.

> chunks of data in the relcache or table caches.

Hmm.. It seems to be far out of control of API what and how large
PostgreSQL extensions could actually cache.

> Why isn't one chunk

It's generally possible to fit everything into one chunk, but that's
extremely unhandy when your cache contains something at least as
complex as tuple slots and descriptors.  I think the reason that we
still have one chunk restriction is that we don't have a full-featured
implementation fitting API yet.  If we had it, I can't imagine there
would be one chunk for a cache.

> with the table tuple slot API?

This is a good idea.  I will update the patch accordingly.

> tokens, for secondary indexes? Why make AMs implement that all over

The idea here is to generalize upsert and leave speculative tokens as
details of one particular implementation.  Imagine an index-organized
table and upsert on primary key.  For that you need to just locate the
relevant page in a tree and do insert or update.  Speculative tokens
would rather be an unreasonable complication for this case.

> Who handles index tuple removal then?

Table AM implementation decides what actions to perform on tuple
update/delete.  The reason why it can't really care about updating
indexes is that the executor already does it.
The situation is different with deletes, because the executor doesn't
do something immediately about the corresponding index tuples.  They
are deleted later by vacuum, which is also controlled by table AM
implementation.

> I don't see a patch that describes index AM changes for this...

Yes, index AM should be revised for that.  See my comment about that earlier.

> what the user asked to create.

I agree that this currently looks more like workarounds rather than
proper API changes.  I propose these two should be considered later
together with relevant index API changes.

> shame as I have trouble understanding some parts.

Sorry for this.  I hope I gave some answers in this message and I'll
update the patchset comments and commit messages accordingly.  And I'm
open to answer any further questions.

> described why these APIs were omitted.

As I mentioned before, I agree that index AM changes haven't been
presented yet.  And yes, for bytea rowID there is currently no way to
use the current index API.  However, I think this exact patch could be
useful even without index AM implements.  This allows table AMs to
identify rows by custom bytea, even though these tables couldn't be
indexed yet.  So, if we allow a custom table AM to implement an
index-organized table, that would have use cases even if secondary
indexes are not supported yet.

Links
1. https://pgconf.ru/media/2016/02/19/06_Korotkov%20Extendability.pdf

------
Regards,
Alexander Korotkov

---

From: Mats Kindahl <[email-masked]>
Date: Fri, 24 May 2024 08:36:32 +0200

> alternative MVCC implementations, etc.

Hi Alexander and great to see some action around in the table access method
interface.

Sorry for being late to the game, but wondering a few things about the
patches, but I'll start with the first one that caught my eye.

> table AM-specific system attributes.

This patch seems straightforward enough, but from reading the surrounding
code and trying to understand the context I am wondering a few things.
Reading the thread, I am unsure if this will go in or not, but just wanted
to point out a concern I had. My apologies if I am raising an issue that is
already resolved.

AFAICT, the general contract for working with table tuple slots is creating
them for a particular purpose, filling it in, and then passing around a
pointer to it. Since the slot is created using a "source" implementation,
the "source" is responsible for memory allocation and also other updates to
the state. Please correct me if I have misunderstood how this is intended
to work, but this seems like a good API since it avoids
unnecessary allocation and, in particular, unbounded creation of new slots
affecting memory usage while a query is executing. For a plan you want to
execute, you just make sure that you have slots of the right kind in each
plan node and there is no need to dynamically allocate more slots. If you
want one for the table access method, just make sure to fetch the slot
callbacks from the table access method use those correctly. As a result,
the number of slots used during execution is bounded

Assuming that I've understood it correct, if a TTS is then created and
passed to tuple_insert, and it needs to return a different slot, this
raises two questions:

   - As Andres pointed out: who is responsible for taking care of and
   dealing with the cleanup of the returned slot here? Note that this is not
   just a matter of releasing memory, there are other stateful things that
   they might need to deal with that the TAM have created for in the slot. For
   this, some sort of callback is needed and the tuple_insert implementation
   needs to call that correctly.
   - The dual is the cleanup of the "original" slot passed in: a slot of a
   particular kind is passed in and you need to deal with this correctly to
   release the resources allocated by the original slot, using some sort of
   callback.

For both these cases, the question is what cleanup function to call.

In most cases, the slot comes from a subplan and is not dynamically
allocated, i.e., it cannot just use release() since it is reused later. For
example, for ExecScanFetch the slot ss_ScanTupleSlot is returned, which is
then used with tuple_insert (unless I've misread the code), which is
typically cleared, not released.

If clear() is used instead, and you clear this slot as part of inserting a
tuple, you can instead clear a premature intermediate result
(ss_ScanTupleSlot, in the example above), which can cause strange issues if
this result is needed later.

So, given that the dynamic allocation of new slots is unbounded within a
query and it is complicated to make sure that slots are
cleared/reset/released correctly depending on context, this seems to be
hard to get to work correctly and not risk introducing bugs. IMHO, it would
be preferable to have a very simple contract where you init, set, clear,
and release the slot to avoid bugs creeping into the code, which is what
the PostgreSQL code mostly has now.

So, the question here is why changing the slot implementation is needed. I
do not know the details of OrioleDB, but this slot is immediately used
with ExecInsertIndexTuples() after the call in nodeModifyTable. If the need
is to pass information from the TAM to the IAM then it might be better to
store this information in the execution state. Is there a case where the
correct slot is not created, then fixing that location might be better.
(I've noticed that the copyFrom code has a somewhat naïve assumption of
what slot implementation should be used, but that is a separate discussion.)

Best wishes,
Mats Kindahl