Обсуждение: Sequence Access Methods, round two

Hi all,

Back in 2016, a patch set has been proposed to add support for
sequence access methods:
https://www.postgresql.org/message-id/flat/CA%2BU5nMLV3ccdzbqCvcedd-HfrE4dUmoFmTBPL_uJ9YjsQbR7iQ%40mail.gmail.com

This included quite a few concepts, somewhat adapted to the point
where this feature was proposed:
- Addition of USING clause for CREATE/ALTER SEQUENCE.
- Addition of WITH clause for sequences, with custom reloptions.
- All sequences rely on heap
- The user-case focused on was the possibility to have cluster-wide
sequences, with sequence storage always linked to heap.
- Dump/restore logic depended on that, with a set of get/set functions
to be able to retrieve and force a set of properties to sequences.

A bunch of the implementation and design choices back then come down
to the fact that *all* the sequence properties were located in a
single heap file, including start, restart, cycle, increment, etc.
Postgres 10 has split this data with the introduction of the catalog
pg_sequence, that has moved all the sequence properties within it.
As a result, the sequence "heap" metadata got reduced to its
last_value, is_called and log_cnt (to count if a metadata tuple should
be WAL-logged).  Honestly, I think we can do simpler than the original
proposal, while satisfying more cases than what the original thread
wanted to address.  One thing is that a sequence AM may want storage,
but it should be able to plug in to a table AM of its choice.

Please find attached a patch set that aims at implementing sequence
access methods, with callbacks following a model close to table and
index AMs, with a few cases in mind:
- Global sequences (including range-allocation, local caching).
- Local custom computations (a-la-snowflake).

The patch set has been reduced to what I consider the minimum
acceptable for an implementation, with some properties like:
- Implementation of USING in CREATE SEQUENCE only, no need for WITH
and reloptions (could be added later).
- Implementation of dump/restore, with a GUC to force a default
sequence AM, and a way to dump/restore without a sequence AM set (like
table AMs, this relies on SET and a --no-sequence-access-method).
- Sequence AMs can use a custom table AM to store its meta-data, which
could be heap, or something else.  A sequence AM is free to choose if
it should store data or not, and can plug into a custom RMGR to log
data.
- Ensure compatibility with the existing in-core method, called
"local" in this patch set.  This uses a heap table, and a local
sequence AM registers the same pg_class entry as past releases.
Perhaps this should have a less generic name, like "seqlocal",
"sequence_local", but I have a bad tracking history when it comes to
name things.  I've just inherited the name from the patch of 2016.
- pg_sequence is used to provide hints (or advices) to the sequence
AM about the way to compute values.  A nice side effect of that is
that cross-property check for sequences are the same for all sequence
AMs.  This gives a clean split between pg_sequence and the metadata
managed by sequence AMs.

On HEAD, sequence.c holds three different concepts, and decided that
this stuff should actually split them for table AMs:
1) pg_sequence and general sequence properties.
2) Local sequence cache, for lastval(), depending on the last sequence
value fetched.
3) In-core sequence metadata, used to grab or set values for all
the flavors of setval(), nextval(), etc.

With a focus on compatibility, the key design choices here are that 1)
and 2) have the same rules shared across all AMs, and 3) is something
that sequence AMs are free to play with as they want.  Using this
concept, the contents of 3) in sequence.c are now local into the
"local" sequence AM:
- RMGR for sequences, as of xl_seq_rec and RM_SEQ_ID (renamed to use
"local" as well).
- FormData_pg_sequence_data for the local sequence metadata, including
its attributes, SEQ_COL_*, the internal routines managing rewrites of
its heap, etc.
- In sequence.c, log_cnt is not a counter, just a way to decide if a
sequence metadata should be reset or not (note that init_params() only
resets it to 0 if sequence properties are changed).
As a result, 30% of sequence.c is trimmed of its in-core AM concepts,
all moved to local.c.

While working on this patch, I've finished by keeping a focus on
dump/restore permeability and focus on being able to use nextval(),
setval(), lastval() and even pg_sequence_last_value() across all AMs
so as it makes integration with things like SERIAL or GENERATED
columns natural.  Hence, the callbacks are shaped so as these
functions are transparent across all sequence AMs.  See sequenceam.h
for the details about them, and local.c for the "local" sequence AM.

The attached patch set covers all the ground I wanted to cover with
this stuff, including dump/restore, tests, docs, compatibility, etc,
etc.  I've done a first split of things to make the review more
edible, as there are a few independent pieces I've bumped into while
implementing the callbacks.

Here are some independent refactoring pieces:
- 0001 is something to make dump/restore transparent across all
sequence AMs.  Currently, pg_dump queries sequence heap tables, but a
sequence AM may not have any storage locally, or could grab its values
from elsewhere.  pg_sequence_last_value(), a non-documented function
used for pg_sequence, is extended so as it returns a row made of
(last_value, is_called), so as it can be used for dump data, across
all AMs.
- 0002 introduces sequence_open() and sequence_close().  Like tables
and indexes, this is coupled with a relkind check, and used as the
sole way to open sequences in sequence.c.
- 0003 groups the sequence cache updates of sequence.c closer to each
other.  This stuff was hidden in the middle of unrelated computations.
- 0004 removes all traces of FormData_pg_sequence_data from
init_params(), which is used to guess the start value and is_called
for a sequence depending on its properties in the catalog pg_sequence.
- 0005 is an interesting one.  I've noticed that I wanted to attach
custom attributes to the pg_class entry of a sequence, or just not
store any attributes at *all* within it.  One approach I have
considered first is to list for the attributes to send to
DefineRelation() within each AM, but this requires an early lookup at
the sequence AM routines, which was gross.  Instead, I've chosen the
method similar to views, where attributes are added after the relation
is defined, using AlterTableInternal().  This simplifies the set of
callbacks so as initialization is in charge of creating the sequence
attributes (if necessary) and add the first batch of metadata tuple
for a sequence (again, if necessary).  The changes that reflect to
event triggers and the commands collected is also something I've
wanted, as it becomes possible to track what gets internally created
for a sequence depending on its AM (see test_ddl_deparse).

Then comes the core of the changes, with a split depending on code
paths:
- 0006 includes the backend changes, that caches a set of callback
routines for each sequence Relation, with an optional rd_tableam.
Callbacks are documented in sequenceam.h.  Perhaps the sequence RMGR
renames should be split into a patch of its own, or just let as-is as
as it could be shared across more than one AM, but I did not see a
huge argument one way or another.  The diffs are not that bad
considering that the original patch at +1200 lines for src/backend/,
with less documentation for the internal callbacks:
 45 files changed, 1414 insertions(+), 718 deletions(-)
- 0007 adds some documentation.
- 0008 adds support for dump/restore, where I have also incorporated
tests and docs.  The implementation finishes by being really
straight-forward, relying on a new option switch to control if
SET queries for sequence AMs should be dumped and/or restored,
depending ona GUC called default_sequence_access_method.
- 0009 is a short example of sequence AM, which is a kind of in-memory
sequence reset each time a new connection is made, without any
physical storage.  I am not clear yet if that's useful as local.c can
be used as a point of reference, but I was planning to include that in
one of my own repos on github like my blackhole_am.

I am adding that to the next CF.  Thoughts and comments are welcome.
--
Michael

On Fri, Dec 01, 2023 at 02:00:54PM +0900, Michael Paquier wrote:
> - 0006 includes the backend changes, that caches a set of callback
> routines for each sequence Relation, with an optional rd_tableam.
> Callbacks are documented in sequenceam.h.  Perhaps the sequence RMGR
> renames should be split into a patch of its own, or just let as-is as
> as it could be shared across more than one AM, but I did not see a
> huge argument one way or another.  The diffs are not that bad
> considering that the original patch at +1200 lines for src/backend/,
> with less documentation for the internal callbacks:
>  45 files changed, 1414 insertions(+), 718 deletions(-)

While looking at the patch set, I have noticed that the previous patch
0006 for the backend changes could be split into two patches to make
the review much easier, as of
- A first patch moving the code related to the in-core sequence AM
from commands/sequence.c to access/sequence/local.c, reshaping the
sequence RMGR:
 12 files changed, 793 insertions(+), 611 deletions(-)
- A second patch to introduce the callbacks, the relcache and the
backend pieces, renaming the contents moved to local.c by the first
patch switching it to the handler:
 38 files changed, 661 insertions(+), 155 deletions(-)

So please find attached a v2 set, with some typos fixed on top of this
extra split.

While on it, I have been doing some performance tests to see the
effect of the extra function pointers from the handler, required for
the computation of nextval(), using:
- Postgres on a tmpfs, running on scissors.
- An unlogged sequence.
- "SELECT count(nextval('popo')) FROM generate_series(1,N);" where N >
0.
At N=5M, one of my perf machines takes 3230ms in average to run the
query on HEAD (646ns per value, 20 runs), and 3315ms with the patch
(663ns, 20 runs), which is..  Err, not noticeable.  But perhaps
somebody has a better idea of tests, say more micro-benchmarking
around nextval_internal()?
--
Michael

On 01.12.23 06:00, Michael Paquier wrote:
> Please find attached a patch set that aims at implementing sequence
> access methods, with callbacks following a model close to table and
> index AMs, with a few cases in mind:
> - Global sequences (including range-allocation, local caching).
> - Local custom computations (a-la-snowflake).

That's a lot of code, but the use cases are summarized in two lines?!?

I would like to see a lot more elaboration what these uses cases are (I 
recognize the words, but do we have the same interpretation of them?) 
and how they would be addressed by what you are proposing, and better 
yet an actual implementation of something useful, rather than just a 
dummy test module.

On Thu, 18 Jan 2024, 16:06 Peter Eisentraut, <peter@eisentraut.org> wrote:
>
> On 01.12.23 06:00, Michael Paquier wrote:
> > Please find attached a patch set that aims at implementing sequence
> > access methods, with callbacks following a model close to table and
> > index AMs, with a few cases in mind:
> > - Global sequences (including range-allocation, local caching).
> > - Local custom computations (a-la-snowflake).
>
> That's a lot of code, but the use cases are summarized in two lines?!?
>
> I would like to see a lot more elaboration what these uses cases are (I
> recognize the words, but do we have the same interpretation of them?)
> and how they would be addressed by what you are proposing, and better
> yet an actual implementation of something useful, rather than just a
> dummy test module.

At $prevjob we had a use case for PRNG to generate small,
non-sequential "random" numbers without the birthday problem occurring
in sqrt(option space) because that'd increase the printed length of
the numbers beyond a set limit. The sequence API proposed here
would've been a great alternative to the solution we found, as it
would allow a sequence to be backed by an Linear Congruential
Generator directly, rather than the implementation of our own
transactional random_sequence table.

Kind regards,

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

On Thu, Jan 18, 2024 at 04:54:06PM +0100, Matthias van de Meent wrote:
> On Thu, 18 Jan 2024, 16:06 Peter Eisentraut, <peter@eisentraut.org> wrote:
>> On 01.12.23 06:00, Michael Paquier wrote:
>>> Please find attached a patch set that aims at implementing sequence
>>> access methods, with callbacks following a model close to table and
>>> index AMs, with a few cases in mind:
>>> - Global sequences (including range-allocation, local caching).
>>> - Local custom computations (a-la-snowflake).
>>
>> That's a lot of code, but the use cases are summarized in two lines?!?
>>
>> I would like to see a lot more elaboration what these uses cases are (I
>> recognize the words, but do we have the same interpretation of them?)
>> and how they would be addressed by what you are proposing, and better
>> yet an actual implementation of something useful, rather than just a
>> dummy test module.
>
> At $prevjob we had a use case for PRNG to generate small,
> non-sequential "random" numbers without the birthday problem occurring
> in sqrt(option space) because that'd increase the printed length of
> the numbers beyond a set limit. The sequence API proposed here
> would've been a great alternative to the solution we found, as it
> would allow a sequence to be backed by an Linear Congruential
> Generator directly, rather than the implementation of our own
> transactional random_sequence table.

Interesting.

Yes, one of the advantages of this API layer is that all the
computation is hidden behind a sequence object at the PostgreSQL
level, hence applications just need to set a GUC to select a given
computation method *while* still using the same DDLs from their
application, or just append USING to their CREATE SEQUENCE but I've
heard that applications would just do the former and forget about it.

The reason why this stuff has bumped into my desk is that we have no
good solution in-core for globally-distributed transactions for
active-active deployments.  First, anything we have needs to be
plugged into default expressions of attributes like with [1] or [2],
or a tweak is to use sequence values that are computed with different
increments to avoid value overlaps across nodes.  Both of these
require application changes, which is meh for a bunch of users.  The
second approach with integer-based values can be become particularly a
pain if one has to fix value conflicts across nodes as they'd usually
require extra tweaks with the sequence definitions, especially if it
blocks applications in the middle of the night.  Sequence AMs offer
more control on that.  For example, snowflake IDs can rely on a GUC to
set a specific machine ID to force some of the bits of a 64-bit
integer to be the same for a single node in an active-active
deployment, ensuring that any value computed across *all* the nodes of
a cluster are always unique, while being maintained behind a sequence
object in-core.  (I can post a module to demonstrate that based on the
sequence AM APIs, just wait a min..  Having more than a test module
and/or a contrib is a separate discussion.)

By the way, patches 0001 to 0004 are just refactoring pieces.
Particularly, 0001 redesigns pg_sequence_last_value() to work across
the board for upgrades and dumps, while avoiding a scan of the
sequence "heap" relation in pg_dump.  These are improvements for the
core code in any case.

[1]: https://github.com/pgEdge/snowflake
[2]:
https://www.postgresql.org/message-id/TY3PR01MB988983D23E4F1DA10567BC5BF5B9A%40TY3PR01MB9889.jpnprd01.prod.outlook.com
--
Michael

2024-01 Commitfest.

Hi, This patch has a CF status of "Needs Review" [1], but it seems
there were CFbot test failures last time it was run [2]. Please have a
look and post an updated version if necessary.

======
[1] https://commitfest.postgresql.org/46/4677/
[2] https://cirrus-ci.com/task/5576959615303680

Kind Regards,
Peter Smith.

On Mon, Jan 22, 2024 at 05:03:16PM +1100, Peter Smith wrote:
> Hi, This patch has a CF status of "Needs Review" [1], but it seems
> there were CFbot test failures last time it was run [2]. Please have a
> look and post an updated version if necessary.

Indeed.  This is conflicting with the new gist_stratnum_identity on
OID 8047, so switched to 8048.  There was a second one in
src/test/modules/meson.build.  Attached is a rebased patch set.
--
Michael

On 18.01.24 16:54, Matthias van de Meent wrote:
> At $prevjob we had a use case for PRNG to generate small,
> non-sequential "random" numbers without the birthday problem occurring
> in sqrt(option space) because that'd increase the printed length of
> the numbers beyond a set limit. The sequence API proposed here
> would've been a great alternative to the solution we found, as it
> would allow a sequence to be backed by an Linear Congruential
> Generator directly, rather than the implementation of our own
> transactional random_sequence table.

This is an interesting use case.  I think what you'd need for that is 
just the specification of a different "nextval" function and some 
additional parameters (modulus, multiplier, and increment).

The proposed sequence AM patch would support a different nextval 
function, but does it support additional parameters?  I haven't found that.

Another use case I have wished for from time to time is creating 
sequences using different data types, for example uuids.  You'd just 
need to provide a data-type-specific "next" function.  However, in this 
patch, all the values and state are hardcoded to int64.

While distributed systems can certainly use global int64 identifiers, 
I'd expect that there would also be demand for uuids, so designing this 
more flexibly would be useful.

I think the proposed patch covers too broad a range of abstraction 
levels.  The use cases described above are very high level and are just 
concerned with how you get the next value.  The current internal 
sequence state would be stored in whatever way it is stored now.  But 
this patch also includes callbacks for very low-level-seeming concepts 
like table AMs and persistence.  Those seem like different things.  And 
the two levels should be combinable.  Maybe I want a local sequence of 
uuids or a global sequence of uuids, or a local sequence of integers or 
a global sequence of integers.  I mean, I haven't thought this through, 
but I get the feeling that there should be more than one level of API 
around this.

On Tue, Jan 23, 2024 at 10:58:50AM +0100, Peter Eisentraut wrote:
> On 18.01.24 16:54, Matthias van de Meent wrote:
> The proposed sequence AM patch would support a different nextval function,
> but does it support additional parameters?  I haven't found that.

Yes and no.  Yes as in "the patch set can support it" and no as in
"the patch does not implement that yet".  You could do two things
here:
- Add support for reloptions for sequences.  The patch does not
include that on purpose because it already covers a lot of ground, and
that did not look like a strict requirement to me as a first shot.  It
can be implemented on top of the patch set.  That's not technically
complicated, actually, but there are some shenanigans to discuss with
the heap relation used under the hood by a sequence for the in-core
method or any other sequence AM that would need a sequence.
- Control that with GUCs defined in the AM, which may be weird, still
enough at relation level.  And enough with the current patch set.

reloptions would make the most sense to me here, I assume, to ease we
handle use nextval().

> Another use case I have wished for from time to time is creating sequences
> using different data types, for example uuids.  You'd just need to provide a
> data-type-specific "next" function.  However, in this patch, all the values
> and state are hardcoded to int64.

Yeah, because all the cases I've seen would be happy with being able
to map a result to 8 bytes with a controlled computation method.  The
size of the output generated, the set of data types that can be
supported by a table AM and the OID/name of the SQL function in charge
of retrieving the value could be controlled in the callbacks
themselves, and this would require a design of the callbacks.  The
thing is that you *will* need callbacks and an AM layer to be able to
achieve that.  I agree this can be useful.  Now this is a separate
clause in the SEQUENCE DDLs, so it sounds to me like an entirely
different feature.

FWIW, MSSQL has a concept of custom data types for one, though these
need to map to integers (see user-defined_integer_type).

Another thing is the SQL specification.  You or Vik will very likely
correct me here, but the spec mentions that sequences need to work on
integer values.  A USING clause means that we already diverge from it,
perhaps it is OK to diverge more.  How about DDL properties like
Min/Max or increment, then?

> I think the proposed patch covers too broad a range of abstraction levels.
> The use cases described above are very high level and are just concerned
> with how you get the next value.  The current internal sequence state would
> be stored in whatever way it is stored now.  But this patch also includes
> callbacks for very low-level-seeming concepts like table AMs and
> persistence.  Those seem like different things.  And the two levels should
> be combinable.  Maybe I want a local sequence of uuids or a global sequence
> of uuids, or a local sequence of integers or a global sequence of integers.
> I mean, I haven't thought this through, but I get the feeling that there
> should be more than one level of API around this.

That's a tricky question, and I don't really know how far this needs
to go.  FWIW, like table AMs I don't want the callbacks to be set in
stone across major releases.  Now I am worrying a bit about designing
callbacks that are generic, still impact performance because they
require more catalog lookups and/or function point manipulations for
the default cases.  Separating the computation and the in-core SQL
functions in a cleaner way is a step that helps in any case, IMO,
though I agree that the design of the callbacks influences how much is
exposed to users and AM developers.  Having only a USING clause that
gives support to integer-based results while providing a way to force
the computation is useful.  Custom data types that can be plugged into
the callbacks are also useful, still they are doing to require an AM
callback layer so as an AM can decide what it needs to do with the
data type given by the user in input of CREATE SEQUENCE.
--
Michael

On 19.01.24 00:27, Michael Paquier wrote:
> The reason why this stuff has bumped into my desk is that we have no
> good solution in-core for globally-distributed transactions for
> active-active deployments.  First, anything we have needs to be
> plugged into default expressions of attributes like with [1] or [2],
> or a tweak is to use sequence values that are computed with different
> increments to avoid value overlaps across nodes.  Both of these
> require application changes, which is meh for a bunch of users.

I don't follow how these require "application changes".  I guess it 
depends on where you define the boundary of the "application".  The 
cited solutions require that you specify a different default expression 
for "id" columns.  Is that part of the application side?  How would your 
solution work on that level?  AFAICT, you'd still need to specify the 
sequence AM when you create the sequence or identity column.  So you'd 
need to modify the DDL code in any case.

On Thu, Feb 08, 2024 at 04:06:36PM +0100, Peter Eisentraut wrote:
> On 19.01.24 00:27, Michael Paquier wrote:
>> The reason why this stuff has bumped into my desk is that we have no
>> good solution in-core for globally-distributed transactions for
>> active-active deployments.  First, anything we have needs to be
>> plugged into default expressions of attributes like with [1] or [2],
>> or a tweak is to use sequence values that are computed with different
>> increments to avoid value overlaps across nodes.  Both of these
>> require application changes, which is meh for a bunch of users.
>
> I don't follow how these require "application changes".  I guess it depends
> on where you define the boundary of the "application".

Yep.  There's a dependency to that.

> The cited solutions
> require that you specify a different default expression for "id" columns.
> Is that part of the application side?  How would your solution work on that
> level?  AFAICT, you'd still need to specify the sequence AM when you create
> the sequence or identity column.  So you'd need to modify the DDL code in
> any case.

One idea is to rely on a GUC to control what is the default sequence
AM when taking the DefineRelation() path, so as the sequence AM
attached to a sequence is known for any DDL operation that may create
one internally, including generated columns.  The patch set does that
with default_sequence_access_method, including support for
pg_dump[all] and pg_restore to give the possibility to one to force a
new default or just dump data without a specific AM (this uses SET
commands in-between the CREATE/ALTER commands).
--
Michael

Hi Michael,

I took a quick look at this patch series, mostly to understand how it
works and how it might interact with the logical decoding patches
discussed in a nearby thread.

First, some general review comments:

0001
------

I think this bit in pg_proc.dat is not quite right:

  proallargtypes => '{regclass,bool,int8}', proargmodes => '{i,o,o}',
  proargnames => '{seqname,is_called,last_value}',

the first argument should not be "seqname" but rather "seqid".


0002, 0003
------------
seems fine, cosmetic changes


0004
------

I don't understand this bit in AlterSequence:

    last_value = newdataform->last_value;
    is_called = newdataform->is_called;

    UnlockReleaseBuffer(buf);

    /* Check and set new values */
    init_params(pstate, stmt->options, stmt->for_identity, false,
                seqform, &last_value, &reset_state, &is_called,
                &need_seq_rewrite, &owned_by);

Why set the values only to pass them to init_params(), which will just
overwrite them anyway? Or do I get this wrong?

Also, isn't "reset_state" just a different name for (original) log_cnt?


0005
------

I don't quite understand what "elt" stands for :-(

    stmt->tableElts = NIL;

Do we need AT_AddColumnToSequence? It seems to work exactly like
AT_AddColumn. OTOH we do have AT_AddColumnToView too ...

Thinking about this code:

    case T_CreateSeqStmt:
        EventTriggerAlterTableStart(parsetree);
        address = DefineSequence(pstate, (CreateSeqStmt *) parsetree);
        /* stashed internally */
        commandCollected = true;
        EventTriggerAlterTableEnd();
        break;

Does this actually make sense? I mean, are sequences really relations?
Or was that just a side effect of storing the state in a heap table
(which is more of an implementation detail)?


0006
------
no comment, just moving code


0007
------
I wonder why heap_create_with_catalog needs to do this (check that it's
a sequence):

if ((RELKIND_HAS_TABLE_AM(relkind) && relkind != RELKIND_TOASTVALUE) ||
    relkind == RELKIND_SEQUENCE)

Presumably this is to handle sequences that use heap to store the state?
Maybe the comment should explain that. Also, will the other table AMs
need to do something similar, just in case some sequence happens to use
that table AM (which seems out of control of the table AM)?

I don't understand why DefineSequence need to copy the string:

    stmt->accessMethod = seq->accessMethod ? pstrdup(seq->accessMethod)
: NULL;

RelationInitTableAccessMethod now does not need to handle sequences, or
rather should not be asked to handle sequences. Is there a risk we'd
pass a sequence to the function anyway? Maybe an assert / error would be
appropriate?

This bit in RelationBuildLocalRelation looks a bit weird ...

    if (RELKIND_HAS_TABLE_AM(relkind))
        RelationInitTableAccessMethod(rel);
    else if (relkind == RELKIND_SEQUENCE)
        RelationInitSequenceAccessMethod(rel);

It's not a fault of this patch, but shouldn't we now have something like
RELKIND_HAS_SEQUENCE_AM()?


0008-0010
-----------
no comment


logical decoding / replication
--------------------------------
Now, regarding the logical decoding / replication, would introducing the
sequence AM interfere with that in some way? Either in general, or with
respect to the nearby patch.

That is, what would it take to support logical replication of sequences
with some custom sequence AM? I believe that requires (a) synchronizing
the initial value, and (b) decoding the sequence WAL and (c) apply the
decoded changes. I don't think the sequence AM breaks any of this, as
long as it allows selecting "current value", decoding the values from
WAL, sending them to the subscriber, etc.

I guess the decoding would be up to the RMGR, and this patch maintains
the 1:1 mapping of sequences to relfilenodes, right? (That is, CREATE
and ALTER SEQUENCE would still create a new relfilenode, which is rather
important to decide if a sequence change is transactional.)

It seems to me this does not change the non-transactional behavior of
sequences, right?


alternative sequence AMs
--------------------------
I understand one of the reasons for adding sequence AMs is to allow
stuff like global/distributed sequences, etc. But will people actually
use that?

For example, I believe Simon originally proposed this in 2016 because
the plan was to implement distributed sequences in BDR on top of it. But
I believe BDR ultimately went with a very different approach, not with
custom sequence AMs. So I'm a bit skeptical this being suitable for
other active-active systems ...

Especially when the general consensus seems to be that for active-active
systems it's much better to use e.g. UUID, because that does not require
any coordination between the nodes, etc.

I'm not claiming there are no use cases for sequence AMs, of course. For
example the PRNG-based sequences mentioned by Mattias seems interesting.
I don't know how widely useful that is, though, and if it's worth it
(considering they managed to implement it in a different way).

But I think it might be a good idea to implement a PoC of such sequence
AM, if only to verify it can be implemented using the proposed code.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thu, Feb 22, 2024 at 05:36:00PM +0100, Tomas Vondra wrote:
> 0002, 0003
> ------------
> seems fine, cosmetic changes

Thanks, I've applied these two for now.  I'll reply to the rest
tomorrow or so.

By the way, I am really wondering if the update of elm->increment in
nextval_internal() should be treated as a bug?  In the "fetch" cache
if a sequence does not use cycle, we may fail when reaching the upper
or lower bound for respectively an ascending or descending sequence,
while still keeping what could be an incorrect value if values are
cached on a follow-up nextval_internal call?
--
Michael

On Mon, 26 Feb 2024 at 09:11, Michael Paquier <michael@paquier.xyz> wrote:
>
> On Thu, Feb 22, 2024 at 05:36:00PM +0100, Tomas Vondra wrote:
> > 0002, 0003
> > ------------
> > seems fine, cosmetic changes
>
> Thanks, I've applied these two for now.  I'll reply to the rest
> tomorrow or so.

Huh, that's surprising to me. I'd expected this to get at least a
final set of patches before they'd get committed. After a quick check
6e951bf seems fine, but I do have some nits on 449e798c:

> +/* ----------------
> + *        validate_relation_kind - check the relation's kind
> + *
> + *        Make sure relkind is from an index

Shouldn't this be "... from a sequence"?

> + * ----------------
> + */
> +static inline void
> +validate_relation_kind(Relation r)

Shouldn't this be a bit more descriptive than just
"validate_relation_kind"? I notice this is no different from how this
is handled in index.c and table.c, but I'm not a huge fan of shadowing
names, even with static inlines functions.

> -ERROR:  "serialtest1" is not a sequence
> +ERROR:  cannot open relation "serialtest1"
> +DETAIL:  This operation is not supported for tables.

We seem to lose some details here: We can most definitely open tables.
We just can't open them while treating them as sequences, which is not
mentioned in the error message.

Kind regards,

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

On Mon, Feb 26, 2024 at 09:38:06AM +0100, Matthias van de Meent wrote:
> On Mon, 26 Feb 2024 at 09:11, Michael Paquier <michael@paquier.xyz> wrote:
>> Thanks, I've applied these two for now.  I'll reply to the rest
>> tomorrow or so.
>
> Huh, that's surprising to me. I'd expected this to get at least a
> final set of patches before they'd get committed.

FWIW, these refactoring pieces just make sense taken independently,
IMHO.  I don't think that the rest of the patch set is going to make
it into v17, because there's no agreement about the layer we want,
which depend on the use cases we want to solve.  Perhaps 0001 or 0004
could be salvaged.  0005~ had no real design discussion, so it's good
for 18~ as far as I am concerned.  That's something that would be fit
for an unconference session at the next pgconf in Vancouver, in
combination with what we should do to support sequences across logical
replication setups.

> After a quick check
> 6e951bf seems fine, but I do have some nits on 449e798c:

Thanks.

>> +/* ----------------
>> + *        validate_relation_kind - check the relation's kind
>> + *
>> + *        Make sure relkind is from an index
>
> Shouldn't this be "... from a sequence"?

Right, will fix.

>> + * ----------------
>> + */
>> +static inline void
>> +validate_relation_kind(Relation r)
>
> Shouldn't this be a bit more descriptive than just
> "validate_relation_kind"? I notice this is no different from how this
> is handled in index.c and table.c, but I'm not a huge fan of shadowing
> names, even with static inlines functions.

Not sure that it matters much, TBH.  This is local to sequence.c.

>> -ERROR:  "serialtest1" is not a sequence
>> +ERROR:  cannot open relation "serialtest1"
>> +DETAIL:  This operation is not supported for tables.
>
> We seem to lose some details here: We can most definitely open tables.
> We just can't open them while treating them as sequences, which is not
> mentioned in the error message.

I am not sure to agree with that.  The user already knows that he
should be dealing with a sequence based on the DDL used, and we gain
information about the relkind getting manipulated here.
--
Michael

On Thu, Feb 22, 2024 at 05:36:00PM +0100, Tomas Vondra wrote:
> I took a quick look at this patch series, mostly to understand how it
> works and how it might interact with the logical decoding patches
> discussed in a nearby thread.

Thanks.  Both discussions are linked.

> 0001
> ------
>
> I think this bit in pg_proc.dat is not quite right:
>
>   proallargtypes => '{regclass,bool,int8}', proargmodes => '{i,o,o}',
>   proargnames => '{seqname,is_called,last_value}',
>
> the first argument should not be "seqname" but rather "seqid".

Ah, right.  There are not many system functions that use regclass as
arguments, but the existing ones refer more to IDs, not names.

> 0002, 0003
> ------------
> seems fine, cosmetic changes

Applied these ones as 449e798c77ed and 6e951bf98e2e.

> 0004
> ------
>
> I don't understand this bit in AlterSequence:
>
>     last_value = newdataform->last_value;
>     is_called = newdataform->is_called;
>
>     UnlockReleaseBuffer(buf);
>
>     /* Check and set new values */
>     init_params(pstate, stmt->options, stmt->for_identity, false,
>                 seqform, &last_value, &reset_state, &is_called,
>                 &need_seq_rewrite, &owned_by);
>
> Why set the values only to pass them to init_params(), which will just
> overwrite them anyway? Or do I get this wrong?

The values of "last_value" and is_called may not get updated depending
on the options given in the ALTER SEQUENCE query, and they need to use
as initial state what's been returned from their last heap lookup.

> Also, isn't "reset_state" just a different name for (original) log_cnt?

Yep.  That's quite the point.  That's an implementation detail
depending on the interface a sequence AM should use, but the main
argument behind this change is that log_cnt is a counter to decide
when to WAL-log the changes of a relation, but I have noticed that all
the paths of init_params() don't care about log_cnt as being a counter
at all: we just want to know if the state of a sequence should be
reset.  Form_pg_sequence_data is a piece that only the in-core "local"
sequence AM cares about in this proposal.

> 0005
> ------
>
> I don't quite understand what "elt" stands for :-(
>
>     stmt->tableElts = NIL;
>
> Do we need AT_AddColumnToSequence? It seems to work exactly like
> AT_AddColumn. OTOH we do have AT_AddColumnToView too ...

Yeah, that's just cleaner to use a separate one, to be able to detect
the attributes in the DDL deparsing pieces when gathering these pieces
with event triggers.  At least that's my take once you extract the
piece that a sequence AM may need a table AM to store its data with
its own set of attributes (a sequence AM may as well not need a local
table for its data).

> Thinking about this code:
>
>     case T_CreateSeqStmt:
>         EventTriggerAlterTableStart(parsetree);
>         address = DefineSequence(pstate, (CreateSeqStmt *) parsetree);
>         /* stashed internally */
>         commandCollected = true;
>         EventTriggerAlterTableEnd();
>         break;
>
> Does this actually make sense? I mean, are sequences really relations?
> Or was that just a side effect of storing the state in a heap table
> (which is more of an implementation detail)?

This was becoming handy when creating custom attributes for the
underlying table used by a sequence.

Sequences are already relations (views are also relations), we store
them in pg_class.  Now sequences can also use tables internally to
store their data, like the in-core "local" sequence AM defined in the
patch.  At least that's the split done in this patch set.

> 0007
> ------
> I wonder why heap_create_with_catalog needs to do this (check that it's
> a sequence):
>
> if ((RELKIND_HAS_TABLE_AM(relkind) && relkind != RELKIND_TOASTVALUE) ||
>     relkind == RELKIND_SEQUENCE)
>
> Presumably this is to handle sequences that use heap to store the state?
> Maybe the comment should explain that. Also, will the other table AMs
> need to do something similar, just in case some sequence happens to use
> that table AM (which seems out of control of the table AM)?

Okay, I can see why this part can be confusing with the state of
things in v2.  In DefineRelation(), heap_create_with_catalog() passes
down the OID of the sequence access method when creating a sequence,
not the OID of the table AM it may rely on.  There's coverage for that
in the regression tests if you remove the check, see the "Try to drop
and fail on dependency" in create_am.sql.

You have a good point here: there could be a dependency between a
table AM and a sequence AM that may depend on it.  The best way to
tackle that would be to add a DEPENDENCY_NORMAL on the amhandler of
the table AM when dealing with a sequence amtype in
CreateAccessMethod() in this design.  Does that make sense?

(This may or may not make sense depending on how the design problem
related to the relationship between a sequence AM and its optional
table AM is tackled, of course, but at least it makes sense to me in
the scope of the design of this patch set.)

> I don't understand why DefineSequence need to copy the string:
>
>     stmt->accessMethod = seq->accessMethod ? pstrdup(seq->accessMethod)
> : NULL;

That's required to pass down the correct sequence AM for
DefineRelation() when creating the pg_class entry of a sequence.

> RelationInitTableAccessMethod now does not need to handle sequences, or
> rather should not be asked to handle sequences. Is there a risk we'd
> pass a sequence to the function anyway? Maybe an assert / error would be
> appropriate?

Hmm.  The risk sounds legit.  This is something where an assertion
based on RELKIND_HAS_TABLE_AM()  would be useful.  Same argument for
RelationInitSequenceAccessMethod() with RELKIND_HAS_SEQUENCE_AM()
suggested below.  I've added these, for now.

> This bit in RelationBuildLocalRelation looks a bit weird ...
>
>     if (RELKIND_HAS_TABLE_AM(relkind))
>         RelationInitTableAccessMethod(rel);
>     else if (relkind == RELKIND_SEQUENCE)
>         RelationInitSequenceAccessMethod(rel);
>
> It's not a fault of this patch, but shouldn't we now have something like
> RELKIND_HAS_SEQUENCE_AM()?

Perhaps, I was not sure.  This would just be a check on
RELKIND_SEQUENCE, but perhaps that's worth having at the end, and this
makes the code more symmetric in the relcache, for one.  The comment
at the top of RELKIND_HAS_TABLE_AM is wrong with 0007 in place anyway.

> logical decoding / replication
> --------------------------------
> Now, regarding the logical decoding / replication, would introducing the
> sequence AM interfere with that in some way? Either in general, or with
> respect to the nearby patch.

I think it does not.  The semantics of the existing in-core "local"
sequence AM are not changed.  So what's here is just a large
refactoring shaped around the current semantics of the existing
computation method.  Perhaps it should be smarter about some aspects,
but that's not something we'll know about until folks start
implementing their own custom methods.  On my side, being able to plug
in a custom callback into nextval_internal() is the main taker.

> That is, what would it take to support logical replication of sequences
> with some custom sequence AM? I believe that requires (a) synchronizing
> the initial value, and (b) decoding the sequence WAL and (c) apply the
> decoded changes. I don't think the sequence AM breaks any of this, as
> long as it allows selecting "current value", decoding the values from
> WAL, sending them to the subscriber, etc.

Sure, that may make sense to support, particularly if one uses a
sequence AM that uses a computation method that may not be unique
across nodes, and where you may want to copy them.  I don't think that
this is problem for something like the proposal of this thread or
what the other thread does, they can tackle separate areas (the
logirep patch has a lot of value for rolling upgrades where one uses
logical replication to create the new node and somebody does not want
to bother with a custom computation).

> I guess the decoding would be up to the RMGR, and this patch maintains
> the 1:1 mapping of sequences to relfilenodes, right? (That is, CREATE
> and ALTER SEQUENCE would still create a new relfilenode, which is rather
> important to decide if a sequence change is transactional.)

Yeah, one "local" sequence would have one relfilenode.  A sequence AM
may want something different, like not using shared buffers, or just
not use a relfilenode at all.

> It seems to me this does not change the non-transactional behavior of
> sequences, right?

This patch set does nothing about the non-transactional behavior of
sequences.  That seems out of scope to me from the start of what I
have sent here.

> alternative sequence AMs
> --------------------------
> I understand one of the reasons for adding sequence AMs is to allow
> stuff like global/distributed sequences, etc. But will people actually
> use that?

Good question.  I have users who would be happy with that, hiding
behind sequences custom computations rather than plug in a bunch of
default expressions to various attributes.  You can do that today, but
this has this limitations depending on how much control one has over
their applications (for example this cannot be easily achieved with
generated columns in a schema).

> For example, I believe Simon originally proposed this in 2016 because
> the plan was to implement distributed sequences in BDR on top of it. But
> I believe BDR ultimately went with a very different approach, not with
> custom sequence AMs. So I'm a bit skeptical this being suitable for
> other active-active systems ...

Snowflake IDs are popular AFAIK, thanks to the unicity of the values
across nodes.

> Especially when the general consensus seems to be that for active-active
> systems it's much better to use e.g. UUID, because that does not require
> any coordination between the nodes, etc.

That means being able to support something larger than 64b values as
these are 128b.

> I'm not claiming there are no use cases for sequence AMs, of course. For
> example the PRNG-based sequences mentioned by Mattias seems interesting.
> I don't know how widely useful that is, though, and if it's worth it
> (considering they managed to implement it in a different way).

Right.  I bet that they just plugged a default expression to the
attributes involved.  When it comes to users at a large scale, a
sequence AM makes the change more transparent, especially if DDL
queries are replication across multiple logical nodes.

> But I think it might be a good idea to implement a PoC of such sequence
> AM, if only to verify it can be implemented using the proposed code.

You mean the PRNG idea or something else?  I have a half-baked
implementation for snowflake, actually.  Would that be enough?  I
still need to spend more hours on it to polish it.  One part I found
more difficult than necessary with the patch set of this thread is the
APIs used in commands/sequence.c for the buffer manipulations,
requiring more duplications.  Not impossible to do outside core, but
I've wanted more refactoring of the routines used by the "local"
sequence AM of this patch.

Plugging in a custom data type on top of the existing sequence objects
is something entirely different, where we will need a callback
separation anyway at the end, IMHO.  This seems like a separate topic
to me at the end, as custom computations with 64b to store them is
enough based on what I've heard even for hundreds of nodes.  I may be
wrong and may not think big enough, of course.

Attaching a v3 set, fixing one conflict, while on it.
--
Michael

On Tue, Feb 27, 2024 at 10:27:13AM +0900, Michael Paquier wrote:
> On Thu, Feb 22, 2024 at 05:36:00PM +0100, Tomas Vondra wrote:
>> 0001
>> ------
>>
>> I think this bit in pg_proc.dat is not quite right:
>>
>>   proallargtypes => '{regclass,bool,int8}', proargmodes => '{i,o,o}',
>>   proargnames => '{seqname,is_called,last_value}',
>>
>> the first argument should not be "seqname" but rather "seqid".
>
> Ah, right.  There are not many system functions that use regclass as
> arguments, but the existing ones refer more to IDs, not names.

This patch set is not going to be merged for this release, so I am
going to move it to the next commit fest to continue the discussion in
v18~.

Anyway, there is one piece of this patch set that I think has a lot of
value outside of the discussion with access methods, which is to
redesign pg_sequence_last_value so as it returns a (last_value,
is_called) tuple rather than a (last_value).  This has the benefit of
switching pg_dump to use this function rather than relying on a scan
of the heap table used by a sequence to retrieve the state of a
sequence dumped.  This is the main diff:
-    appendPQExpBuffer(query,
-                      "SELECT last_value, is_called FROM %s",
-                      fmtQualifiedDumpable(tbinfo));
+    /*
+     * In versions 17 and up, pg_sequence_last_value() has been switched to
+     * return a tuple with last_value and is_called.
+     */
+    if (fout->remoteVersion >= 170000)
+        appendPQExpBuffer(query,
+                          "SELECT last_value, is_called "
+                          "FROM pg_sequence_last_value('%s')",
+                          fmtQualifiedDumpable(tbinfo));
+    else
+        appendPQExpBuffer(query,
+                          "SELECT last_value, is_called FROM %s",
+                          fmtQualifiedDumpable(tbinfo));

Are there any objections to that?  pg_sequence_last_value() is
something that we've only been relying on internally for the catalog
pg_sequences.
--
Michael

On 12.03.24 00:44, Michael Paquier wrote:
> Anyway, there is one piece of this patch set that I think has a lot of
> value outside of the discussion with access methods, which is to
> redesign pg_sequence_last_value so as it returns a (last_value,
> is_called) tuple rather than a (last_value).  This has the benefit of
> switching pg_dump to use this function rather than relying on a scan
> of the heap table used by a sequence to retrieve the state of a
> sequence dumped.  This is the main diff:
> -    appendPQExpBuffer(query,
> -                      "SELECT last_value, is_called FROM %s",
> -                      fmtQualifiedDumpable(tbinfo));
> +    /*
> +     * In versions 17 and up, pg_sequence_last_value() has been switched to
> +     * return a tuple with last_value and is_called.
> +     */
> +    if (fout->remoteVersion >= 170000)
> +        appendPQExpBuffer(query,
> +                          "SELECT last_value, is_called "
> +                          "FROM pg_sequence_last_value('%s')",
> +                          fmtQualifiedDumpable(tbinfo));
> +    else
> +        appendPQExpBuffer(query,
> +                          "SELECT last_value, is_called FROM %s",
> +                          fmtQualifiedDumpable(tbinfo));
> 
> Are there any objections to that?  pg_sequence_last_value() is
> something that we've only been relying on internally for the catalog
> pg_sequences.

I don't understand what the overall benefit of this change is supposed 
to be.

If this route were to be pursued, it should be a different function 
name.  We shouldn't change the signature of an existing function.

On Wed, Mar 13, 2024 at 07:00:37AM +0100, Peter Eisentraut wrote:
> I don't understand what the overall benefit of this change is supposed to
> be.

In the context of this thread, this removes the dependency of sequence
value lookup to heap.

> If this route were to be pursued, it should be a different function name.
> We shouldn't change the signature of an existing function.

I'm not so sure about that.  The existing pg_sequence_last_value is
undocumented and only used in a system view.
--
Michael

On Thu, Mar 14, 2024 at 09:40:29AM +0900, Michael Paquier wrote:
> In the context of this thread, this removes the dependency of sequence
> value lookup to heap.

I am not sure where this is leading in combination with the sequence
stuff for logical decoding, so for now I am moving this patch to the
next commit fest to discuss things in 18~.
--
Michael

On Tue, Mar 19, 2024 at 10:54:41AM +0900, Michael Paquier wrote:
> I am not sure where this is leading in combination with the sequence
> stuff for logical decoding, so for now I am moving this patch to the
> next commit fest to discuss things in 18~.

I have plans to rework this patch set for the next commit fest,
and this includes some investigation about custom data types that
could be plugged into these AMs.  For now, please find a rebase as
there were a couple of conflicts.
--
Michael

On Fri, Apr 19, 2024 at 04:00:28PM +0900, Michael Paquier wrote:
> I have plans to rework this patch set for the next commit fest,
> and this includes some investigation about custom data types that
> could be plugged into these AMs.

So, I have worked more on this patch set, and finished by reorganizing
it more, with more things:
- The in-core sequence access method is split into more files:
-- One for its callbacks, called seqlocalam.c.
-- The WAL replay routines are moved into their own file.
- As asked, Implementation of a contrib module that introduces a
sequence access method for snowflake IDs, to demonstrate what can be
done using the APIs of the patch.  The data of such sequences is
stored in an unlogged table, based on the assumption that the
timestamps and the machine IDs ensure the unicity of the IDs for the
sequences.  The advantage of what's presented here is that support for
lastval(), nextval() and currval() is straight-forward.  Identity
columns are able to feed on that.  cache is handled by sequence.c, not
the AM.  WAL-logging is needed for the init fork, it goes through the
generic WAL APIs like bloom to log full pages.  Some docs are
included.  This is still a rough WIP, though, and the buffer handling
is not optimal, and could be made transactional this time (assuming
autovacuum is able to process them at some point, or perhaps the
sequence AMs should offer a way for autovacuum to know if such
sequences should be cleaned up or not).

After having done that, I've also found about a module developed by
pgEdge, that copies a bunch of the code from sequence.c, though it is
not able to handle the sequence cache:
https://github.com/pgEdge/snowflake

The approach this module uses is quite similar to what I have here,
but it is smarter regarding clock ticking, where the internal sequence
counter is bumped only when we fetch the same timestamp as a previous
attempt.  The module presented could be switched to do something
similar by storing into the heap table used by the sequence a bit more
data than just the sequence counter.  Well, the point I want to make
at this stage is what can be done with sequence AMs, so let's discuss
about that later.

Finally, custom types, where I have come up with a list of open
questions:
- Catalog representation.  pg_sequence and pg_sequences switch to
something else than int64.
- The existing functions are also interesting to consider here.
nextval() & co would not be usable as they are for sequence AMs that
use more than int64.  Note that the current design taken in the patch
has a strong dependency on int64 (see sequenceam.h).  So the types
would need to reflect.  With identity columns, the change would not be
that hard as the executor has NextValueExpr.  Perhaps each sequence AM
should just have callback equivalents for currval(), nextval() and
lastval().  This hits with the fact that this makes sequence AMs less
transparent to applications because custom data types means different
functions than the native ones.
- Option representation.
- I have polled Twitter and Fosstodon with four choices:
-- No need for that, 64b representation is enough.
-- Possibility to have integer-like types (MSSQL does something like
that).
-- Support for 128b or larger (UUIDs, etc, with text-like
representation or varlenas).
-- Support for binary representation, which comes down to the
possibility of having sequence values even larger than 128b.

Based on the first estimations, 50%-ish of people mentioned than 64b
is more than enough, while Jelte mentioned that Citus has tackled this
problem with an equivalent of 128b (64b for the sequence values, some
more for machine states).  Then there's a trend of 25%-ish in favor of
128b and 25%-ish for more than that.  The results are far from being
final, but that's something.

My own take after pondering about it is that 64b is still more than
enough for the clustering cases I've seen in the past 15 years or so,
while offering room for implementations even if it comes to thousands
of nodes.  So there's some margin depending on the number of bits
reserved for the "machine" part of the sequence IDs when used in
clusters.

The next plan is to hopefully be able to trigger a discussion at the
next pgconf.dev at the end of May, but let's see how it goes.

Thanks,
--
Michael