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

Hi,

I now have a local reference version of the index type (patch 2), on top of
0001.

On real data, NYC taxi trips (119M rows, 18 GB), against the fastest plain
GROUP BY with a warm cache, in ms:

plain grain
hourly30d 859.467 1.196
daily30d 896.286 0.134
total365d 2732.230 0.512

With a cold cache grain is 83x to 193x faster. Every answer matched the
plain query, including after late writes, and the summary table is under 2%
of the table's size. I haven't measured the write cost yet.

What patch 2 looks like depends on two questions: is an index the right
object, and may an index own a summary table and a marker table? I can post
it as 0002 if anyone wants to read the code.

cheers,
JB

On Fri, Oct 30, 2026 at 8:53 AM Jan Bjørge Løvland <janbjorge(at)gmail(dot)com>
wrote:

> Hi,
>
> v2 attached, rebased on master. The isolation specs failed on macOS in CI:
> under debug_parallel_query=regress a parallel worker loads dummy_index_am
> again and prints its reloption notices. The specs now turn the parallel
> query off. No code changes.
>
> --
> BR,
> Jan Bjørge (JB)
> Norway
>
> On Thu, Oct 22, 2026 at 1:19 PM Jan Bjørge Løvland <janbjorge(at)gmail(dot)com>
> wrote:
>
>> Hi,
>>
>> Attached is v1 of the amnotifydelete callback, patch 1 from the plan
>> above. Besides DELETE and UPDATE it covers MERGE, ON CONFLICT, logical
>> replication apply and REPACK (CONCURRENTLY). The limits are documented in
>> indexam.sgml, and dummy_index_am has tests.
>>
>> --
>> BR,
>> Jan Bjørge (JB)
>> Norway
>>
>> On Tue, Oct 20, 2026 at 12:54 PM Jan Bjørge Løvland <janbjorge(at)gmail(dot)com>
>> wrote:
>>
>>> 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
>>>
>>>