Subject: Re: Revisiting {CREATE INDEX, REINDEX} CONCURRENTLY improvements

From: Antonin Houska <[email-masked]>
Date: Thu, 27 Nov 2025 17:56:25 +0100

Michail Nikolaev <[email-masked]> wrote:

> I think about revisiting (1) ({CREATE INDEX, REINDEX} CONCURRENTLY
> improvements) in some lighter way.

I haven't read the whole thread yet, but the effort to minimize the impact of
C/RIC on VACUUM seems to prevail. Following is one more proposal. The core
idea is that C/RIC should avoid indexing dead tuples, however snapshot is not
necessary to distinguish dead tuple from a live one. And w/o snapshot, the
backend executing C/RIC does not restrict VACUUM on other tables.

Concurrent (re)build of unique index appears to be another topic of this
thread, but I think this approach should handle the problem too. The workflow
is:

1. Create an empty index.

2. Wait until all transactions are aware of the index, so they take the new
   index into account when deciding on new HOT chains. (This is already
   implemented.)

3. Set the 'indisready' flag so the index is ready for insertions.

4. While other transactions can insert their tuples into the index now,
   process the table one page at a time this way:

   4.1 Acquire (shared) content lock on the buffer.

   4.3 Collect the root tuples of HOT chains - these and only these need to be
       inserted into the index.

   4.4 Unlock the buffer.

5. Once the whole table is processed, insert the collected tuples into the
   index.

   To avoid insertions of tuples that concurrent transactions have just
   inserted, we'd need something like index.c:validate_index() (i.e. insert
   into the index only the tuples that it does not contain yet), but w/o
   snapshot because we already have the heap tuples collected.

   Also it'd make sense to wait for completion of all the transactions that
   currently have the table locked for INSERT/UPDATE: some of these might have
   inserted their tuples into the heap, but not yet into the index. If we
   included some of those tuples into our collection and insert them into the
   index first, the other transactions could end up with ERROR when inserting
   those tuples again.

6. Set the 'indisvalid' flag so that the index can be used by queries.

Note on pruning: As we only deal with the root tuples of HOT chains (4.3),
page pruning triggered by queries (heap_page_prune_opt) should not be
disruptive. Actually C/RIC can do the pruning itself it it appears to be
useful. For example, if whole HOT chain should be considered DEAD by the next
VACUUM, pruning is likely (depending on the OldestXid) to remove it so that we
do not insert TID of the root tuple into the index unnecessarily.

I can even think of letting VACUUM run on the same table that C/RIC is
processing. In that case, interlocking would take place at page level: either
C/RIC or VACUUM can acquire lock for particular page, but not both. This would
be useful in cases C/RIC takes very long time.

In this case, C/RIC *must not* insert TIDs of dead tuples into the index at
all. Otherwise there could be race conditions such that VACUUM removes dead
tuples from the index and marks the corresponding heap items as UNUSED, but
C/RIC then re-inserts the index tuples.

To avoid this problem, C/RIC needs to re-check each TID before it inserts it
into the index and skip the insertion if the tuple (or the whole HOT-chain
starting at this tuple) it points to is DEAD according to the OldestXmin that
the most recent VACUUM used. (VACUUM could perhaps advertise its OldestXmin
for C/RIC via shared memory.)

Also, before this re-checking starts, it must be ensured that VACUUM does not
start again, until the index creation is complete: a new run of VACUUM implies
a new value of OldestXmin, i.e. need for more stringent re-checking of the
heap tuples.

Related question is which OldestXmin to use in the step 4.3. One option is to
use *exactly* the OldestXmin shared VACUUM. However that wouldn't work if
VACUUM starts while C/RIC is already in progress. (Which seems like a
significant restriction.)

Another option is to get the OldestXmin in the same way as VACUUM
does. However, the value can thus be different from the one used by VACUUM:
older if retrieved before VACUUM started and newer if retrieved while VACUUM
was already running. The first case can be handled by the heap tuple
re-checking (see above). The latter implies that, before setting 'indisvalid',
C/RIC has to wait until all snapshots have their xmin >= this (more recent)
OldestXmin. Otherwise some snapshots could miss data they should see.

(An implication of the rule that C/RIC must not insert TIDs of dead tuples
into the index is that VACUUM does not have to call the index AM bulk delete
while C/RIC is running for that index. This would be just an optimization.)

Of course, I could have missed some important point, so please explain why
this concept is broken :-) Or let me know if something needs to be explained
more in detail. Thanks.

-- 
Antonin Houska
Web: https://www.cybertec-postgresql.com

---

From: Mihail Nikalayeu <[email-masked]>
Date: Thu, 27 Nov 2025 18:40:34 +0100

Hello, Antonin!

> C/RIC on VACUUM seems to prevail
Yes, the thread is super long and probably you missed annotations to
most important emails in [0].

> this concept is broken :-) Or let me know if something needs to be explained

Looks like your idea is not broken, but... It is actually an almost
1-1 to idea used in the "full" version of the patch.
Explanations are available in [1] and [2].
In [3] I reduced the patch scope to find a solution compatible with REPACK.

> 1. Create an empty index.
Yes, patch does exactly the same, introducing special lightweight AM -
STIR (Short Term Index Replacement) to collect new tuples.

       inserted into the index.
>   4.4 Unlock the buffer.

Instead of such technique essentially the same is used - it keeps the
snapshot to be used, it just rotates it every few pages for a fresh
one.
It solves some of the issues with selection of alive tuples you
mentioned without any additional logic.

> thread, but I think this approach should handle the problem too.
It is solved with a special commit in the original patchset.

You know, clever people think the same :)
Interesting fact, it is not the first time - at [4] Sergey also
proposed an idea of an "empty" index to collect tuples (which gives
the single scan).

So, it is very good knews the approach feels valid for multiple people
(also Mathias introduced the idea about "fresh snapshot"~"no snapshot"
initially).

One thing I am not happy about - it is not applicable to the REPACK case.

Best regards,
Mikhail.

[0]: https://commitfest.postgresql.org/patch/4971/
[1]: https://www.postgresql.org/message-id/CADzfLwVOcZ9mg8gOG+KXWurt=[email-masked]
[2]: https://www.postgresql.org/message-id/CADzfLwW9QczZW-E=[email-masked]
[3]: https://www.postgresql.org/message-id/CADzfLwVaV15R2rUNZmKqLKweiN3SnUBg=[email-masked]
[4]: https://www.postgresql.org/message-id/flat/CAMAof6_FY0MrNJOuBrqvQqJKiwskFvjRtgpVHf-D7A%3DKvTtYXg%40mail.gmail.com

---

From: Matthias van de Meent <[email-masked]>
Date: Thu, 27 Nov 2025 19:22:46 +0100

> do not insert TID of the root tuple into the index unnecessarily.
[...]
> this concept is broken :-) Or let me know if something needs to be explained

1. When do you select and insert tuples that aren't part of a hot
chain into the index, i.e. tuples that were never updated after they
got inserted into the table? Or is every tuple "part of a hot chain"
even if the tuple wasn't ever updated?

2. HOT chains can be created while the index wasn't yet present, and
thus the indexed attributes of the root tuples can be different from
the most current tuple of a chain. If you only gather root tuples, we
could index incorrect data for that HOT chain. The correct approach
here is to index only the visible tuples, as those won't have been
updated in a non-HOT manner without all indexed attributes being
unchanged.

3. Having the index marked indisready before it contains any data is
going to slow down the indexing process significantly:
a. The main index build now must go through shared memory and buffer
locking, instead of being able to use backend-local memory
b. The tuple-wise insertion path (IndexAmRoutine->aminsert) can have a
significantly higher overhead than the bulk insertion logic in
ambuild(); in metrics of WAL, pages accessed (IO), and CPU cycles
spent.

So, I don't think moving away from ambuild() as basis for initially
building the index this is such a great idea.

(However, I do think that having an _option_ to build the index using
ambuildempty()+aminsert() instead of ambuild() might be useful, if
only to more easily compare "natural grown" indexes vs freshly built
ones, but that's completely orthogonal to CIC snapshotting
improvements.)

Kind regards,

Matthias van de Meent
Databricks (https://www.databricks.com)

---

From: Mihail Nikalayeu <[email-masked]>
Date: Thu, 27 Nov 2025 19:57:23 +0100

Hi, Antonin!

> STIR (Short Term Index Replacement) to collect new tuples.

Initially understood incorrectly - in your solution you propose to use
a single index.
But STIR is used to collect new coming tuples, while the main index is
built using a batched way.

> snapshot because we already have the heap tuples collected.

And later main and STIR are merged.

Best regards,
Mikhail.

---

From: Antonin Houska <[email-masked]>
Date: Fri, 28 Nov 2025 10:05:24 +0100

> even if the tuple wasn't ever updated?

Right, I considered "standalone tuple" a HOT chain of length 1. So it'll be
picked too.

> updated in a non-HOT manner without all indexed attributes being

Good point.

> ones, but that's completely orthogonal to CIC snapshotting

The retail insertions are not something this proposal depends on. I think it'd
be possible to build a separate index locally and then "merge" it with the
regular one. I just tried to propose a solution that does not need snapshots.

---

From: Matthias van de Meent <[email-masked]>
Date: Fri, 28 Nov 2025 10:51:16 +0100

> regular one. I just tried to propose a solution that does not need snapshots.

I'm not sure we can generalize indexes to the point where merging two
built indexes is always both possible and efficient.

For example, the ANN indexes of pgvector (both HNSW and IVF) could
possibly have merge operations between indexes of the same type and
schema, but it would require a lot of effort on the side of the AM to
support merging; there is no trivial merge operation that also retains
the quality of the index without going through the aminsert() path.
Conversely, the current approach to CIC doesn't require additional
work on the index AM's side, and that's a huge enabler for every kind
of index.

Kind regards,

Matthias van de Meent