# Parallel posting-tree build (4.3.1)

Status: implemented in `src/am/ambuild.c`. This note records why it is shaped
the way it is.

## Before

```
participants (leader + W workers): scan -> extract -> worker-role sort  (parallel)
leader:  merge W+1 runs -> for each trigram: posting tree    (serial)
leader:  upper tree, SuRF                                     (serial, small)
```

At large scale the serial middle step dominates. Reading the merged stream
and encoding and writing every posting runs on one core, while the workers
sit idle.

## After

The 64-bit trigram hash space is cut into `R` equal ranges, with `R` = 4 x the
number of planned participants. Each participant feeds `R` worker-role sorts,
one per range, instead of one. Range `r` of every participant lands in
shared sort `r`.

```
participants:  scan -> extract -> route by hash range -> R worker-role sorts
barrier:       every participant has performsort'ed all R sorts
participants:  claim ranges (atomic counter), for each claimed range r:
                 leader-role merge of sort r -> posting trees for range r
                 -> append (hash, root|inline) and SuRF keys to a range file
leader:        wait for all ranges; read range files 0..R-1 in order
               -> upper tree (global hash order = range order), SuRF
```

- **Ordering.** Ranges are contiguous and ascending in hash, so concatenating
  range results 0..R-1 gives exactly the serial `accums[]` order. The upper
  tree and SuRF are identical in content. Only the block numbers of posting
  pages differ, because ranges write interleaved.
- **Leader-role merges.** A tuplesort leader-role merge needs only the shared
  fileset and `nParticipants`, and any backend attached to the DSM can run
  one. `leader_takeover_tapes` checks that all worker runs are finished; the
  barrier guarantees that.
- **Writing pages from workers.** Workers write index pages through
  `pg_tre_extend` (`ExtendBufferedRel`; relation extension locks still
  conflict within a lock group, so extension serialises safely) and
  GenericXLog. Parallel vacuum workers already WAL-log index pages, and
  `RestorePendingSyncs` gives workers the same `RelationNeedsWAL` answer
  under `wal_level=minimal`.
- **Results back to the leader.** BufFiles in a SharedFileSet, one per range,
  as in `sharedtuplestore.c`. Records are
  `(hash u64, root u32, inline_bytes u32, inline bytes…)`, followed by SuRF
  keys.
- **Memory.** Each participant's sort memory (`maintenance_work_mem / P`) is
  split across its `R` sorts. Each range merge runs with
  `maintenance_work_mem / P`.
- **Load balance.** TID volume per trigram is Zipf-skewed, and the hash's
  high bits are not uniform. With one range per participant, the largest
  range ran 50 s past the others on the 2 GB corpus (posting phase 81 s). With
  4 ranges per participant, claimed dynamically, it took 53 s.
  `PG_TRE_RANGES_PER_PARTICIPANT`. Ranges are counted from planned
  participants, so a worker that never launches just leaves its share to the
  others.
- **Serial builds** (no workers, or `pg_tre.enable_parallel_build = off`)
  are unchanged: one sort, leader readout, through the same per-range
  function with a single range.

Not done: sizing ranges from a hash sample. Add it if skew at scale outgrows
the fixed 4x.