Design proposal: grain, exact per-time-bucket aggregates from a summarizing index

Hi!

Thanks for taking the time. I used agents to help write this: I'm highly
dyslexic, and without help I feel that my proposal doesn't come across.

I'd like design feedback on a new index type that keeps exact count, sum,
min and max per time bucket, and on a new index access method callback it
needs. I have working code for the callback, with tests and benchmarks, but
I haven't posted it. I'd like some blessing on the callback before going
further. The index type itself isn't written yet.

Problem

SELECT date_bin('1 day', created_at, '2000-01-01 00:00+00'),
count(*), sum(amount_cents)
FROM orders
WHERE status = 'paid' AND created_at >= now() - interval '365 days'
GROUP BY 1 ORDER BY 1;

In our runs, the time of this query grew with the number of rows in the
window, with no index, a btree, a covering btree and BRIN alike.
Materialized views go stale. Triggers that keep a rollup table are tricky
to get right: the incremental view maintenance patches [1], built on
triggers, lock the view on DELETE and UPDATE and raise errors under
REPEATABLE READ. TimescaleDB works, but for one rollup on one table it
feels like shooting sparrows with a cannon, as we say in Norway.

Proposal

CREATE INDEX ON orders USING grain (created_at) INCLUDE (amount_cents)
WITH (buckets = '1 minute, 1 hour, 1 day') WHERE status = 'paid';

The first version has a timestamptz time key and integer INCLUDE columns.
Bucket widths are fixed, finest first, and each width divides the next.
Partial indexes work. The index is never scanned. Reads go through
pg_grain_buckets(index, from, to) first, later through a planner path for
GROUP BY date_bin(...).

The index keeps three things:
- W, a timestamp in the index's metapage: buckets before W are summarized,
rows after W are read from the table. W only moves forward.
- A hidden summary table with one row per summarized bucket at each level,
holding count, sum, min and max as plain values.
- A hidden marker table listing buckets that changed after they were
summarized.
Both tables are ordinary tables owned by the index, the way a TOAST table
is owned by its table, so they are transactional, crash safe and replicated
like any other table.

A write whose row's time key is before W inserts a marker in the same
transaction. Rows stamped "now" cost one comparison. Inserts go through
aminsert, and deletes and the old version of an update go through the new
callback.

The sealer advances W, then calls WaitForLockers(heap, ShareLock) as CREATE
INDEX CONCURRENTLY does. Then, under one snapshot, it recomputes new and
marked buckets, rolls them up into the coarser levels, and deletes the
markers it handled.

A reader uses a bucket's summary row when the row is visible, no marker is
visible, and the bucket is wholly inside the window. Otherwise it
range-scans the bucket's rows.

Why we think it is exact: a write that a summary row misses comes from a
transaction the sealer didn't wait for. The sealer waits for everyone
already holding a write lock when it moves W, so that writer locked the
table after W moved. It therefore saw the new W and wrote a marker in the
same transaction. A reader sees both the write and the marker, or neither,
and a marker makes it scan the bucket instead. This relies only on locks
and MVCC visibility, not on the visibility map, VACUUM or clocks.

The callback
void amnotifydelete(Relation index, Datum *values, bool *isnull,
ItemPointer heap_tid, Relation heap,
IndexInfo *indexInfo);

It is NULL for every existing index type. The executor computes the old row
version's index values and calls it from ExecDeleteEpilogue,
ExecUpdateEpilogue (not on TU_None) and the logical replication apply
paths. The relcache tracks whether any index on a table opted in, and the
executor does nothing extra when none did.

The closest earlier proposals are amtargetdelete() [2], which was driven by
VACUUM, and amupdate() [3]. The executor passing old values to the index
follows Robert's suggestion in the WARM thread [4].

Numbers

Callback, on a 1 million row table, master against the patch, both -O2
without asserts. Medians, in ms:

master patch
one-row DELETE + INSERT 0.106 0.105
one-row UPDATE of an indexed column 0.072 0.070
UPDATE of every row, rolled back 4808.265 4572.124
DELETE of every row, fresh table 463.349 469.150

With an index that asks for the callback (dummy_index_am), the DELETE of
every row took 555.168 ms on the patch. The DELETE rows are rounds 4 to 7;
master's first three rounds took 845.669, 1015.431 and 880.740 ms.

Read path, simulated in SQL since the index type isn't written yet: 100
million rows, warm cache, one client, against the fastest plain GROUP BY
(no index, btree, covering btree, BRIN). Answers were identical, including
after late writes.

daily, 30 days: 1196.245 ms -> 0.375 ms
total, 365 days: 909.363 ms -> 0.590 ms

Open questions

1. Is an index the right object, or does this want its own DDL?
2. A delete callback, or a broader amupdate()?
3. Hidden heaps: which namespace, and how should pg_dump and pg_upgrade
handle them?
4. Is a CREATE INDEX CONCURRENTLY style wait acceptable for a job that runs
every minute?
5. Generic WAL for the metapage, or its own resource manager?

Plan: patch 1 the callback, patch 2 the index type with docs and tests,
patch 3 the planner path. Target is master.

[1] https://commitfest.postgresql.org/patch/4337/
[2]
https://www.postgresql.org/message-id/flat/11d32604-c0b9-7c05-edee-76582374404c%40postgrespro.ru
[3]
https://www.postgresql.org/message-id/CAH2-WzmL%2Bp-F1JOb7b6gJRhV-qiO_%3DaNETG43%2BV%2B7EPKxSKP5g%40mail.gmail.com
[4]
https://www.postgresql.org/message-id/CA%2BTgmob4RAhFm_is%3DszyvXWGvtV%3D5-9gbr9Ni391NFWpce6tOg%40mail.gmail.com

--
BR,
Jan Bjørge (JB)
Norway