pg_warren 0.8.0

Upgrading

• Run ALTER EXTENSION pg_warren UPDATE; in every database that has
  the extension, after installing the new build. The update replaces
  the PL/pgSQL definitions of warren.pagerank and warren.leiden with
  native ones (under Performance), keeping their privileges; it changes
  no table. Until the update, 0.7.0's definitions still run with the new
  library, as they did.

Behaviour changes

• warren.pagerank refuses a NULL out or damping before it runs, as
  out must not be NULL and damping must not be NULL (SQLSTATE 22004,
  as before; 0.7.0 ran first and then named y, or value). An empty
  or unwritable out is refused before the run, too. Its intermediates
  (_warren_pagerank_*) no longer exist, even during a run, and it no
  longer carries SET search_path: the access guard pins it for the call
  (DESIGN.md §7). Everything else is kept: its signature, ranks to the
  bit, iteration counts, SQLSTATEs, progress, parallel label and
  privileges, including a NULL tol never stopping it early and a NULL
  max_iter running no iteration.
• leiden checks that the caller may write out before it runs, not
  after. The error is the same (42501). The function no longer sets its
  own search_path; like every other warren.* function, it pins it for
  the call.
• On graphs with fractional weights, leiden sums a level's edge weights
  in a different order from 0.7.0's contract. A weight may differ in its
  last bit, and a tie between moves that it decides may then go the other
  way. On unweighted and integer-weighted graphs the partitions, kept
  levels and modularity are 0.7.0's, to the bit.

Fixes

• gather over char(n) messages no longer truncates them to one
  character for collect and first: their query was cast to
  character, which is character(1); it is now cast to bpchar, as
  array_agg keeps them.
• gather's collect, first and count over text, varchar or
  char messages no longer depend on client_encoding: a message it
  could not represent failed with 22P05 ("has no equivalent in
  encoding"), since each message passed through textsend.

Performance

• warren.pagerank is a native kernel, not a PL/pgSQL loop over the
  compute primitives (DESIGN.md §6.7). The loop made eleven calls an
  iteration, about 1.5 ms of overhead an iteration however small the
  graph; the kernel makes two parallel passes and one product an
  iteration, and holds four vectors of the id space (five with a seed)
  where the loop held eleven: 0.32 GB of scratch at 10M nodes instead of
  0.88 GB.
  Twenty iterations, in a first single before-and-after run on a loaded
  machine (median warm times, warren.threads = 4): lesmis 34.7 → 1.6 ms, facebook 47.3 → 6.3 ms,
  email-enron 74.9 → 22.6 ms, cit-hepth 65.7 → 18.6 ms and DBLP
  318 → 113 ms. The later three-round run timed lesmis at 3.1 ms.
  Against igraph on the 12 head-to-head datasets (three
  interleaved rounds, bench/results/corpus/head_to_head/README.md,
  "PageRank in 0.8.0"): faster on 7 (roadNet-TX 0.22 s against 0.81 s,
  DBLP 105 ms against 251 ms) and slower on 5 (WN18RR, cit-hepth and
  YAGO3-10 by 1.2–1.8×, polblogs by 3.1×, and lesmis, 3.1 ms against
  29 µs, by a call's fixed cost).
• leiden is native (DESIGN.md §6.7, "Leiden's levels"). Each level's
  graph is contracted from the level below, not from the whole graph, and
  is held in memory, charged to warren.max_compute_memory. Only out
  and the levels levels_prefix asks for are written. No level graph,
  segment or WAL is written for a level, and the disk a run needed grew
  with its levels before.
  • It finds the same partitions as before. A pg_test runs the frozen
    0.7.0 function beside it.
  • On the head-to-head's real graphs it is 1.3–21× faster:
    fb15k-237 1.44 → 0.21 s, yago3-10 2.26 → 0.73 s, roadnet-tx
    7.9 → 3.8 s, lesmis 25 → 1.2 ms.
  • It takes 0.76–1.6× igraph's time on the medium tier, where it was
    1.9–180×, and is faster than igraph on ss-gleich-usroads-48, dblp,
    yago3-10 and roadnet-tx (bench/results/corpus/head_to_head/,
    "Leiden in 0.8.0").
• gather over text, varchar, char and bytea messages keeps
  them as their bytes, as concat did, instead of each going through its
  type's send and receive functions, and lays a collected array out
  straight from them: at 10M nodes and 11.5M messages, a collect of
  cheap text messages takes 14.5 s rather than 16.7 s (13.5 s as
  bigint). Appendix A.3's first superstep goes from 30.8 s to 29.5 s;
  most of it is its message query (DESIGN.md §13, "After 0.7.0").
• distance('edit') across two graphs (graph2) no longer rebuilds
  the second graph in the first's dense ids: it maps each edge as it
  reads it and looks it up in the first graph's row (DESIGN.md §8). It
  charges only the id mapping, 8 bytes a node of the second graph, where
  it charged 96 bytes an edge for the rebuild, so Appendix A.2 at 10M
  asks for 88 MB instead of 10.9 GB and runs under the 4GB default rather
  than failing with 53400. At 2.2M nodes and 22M stored edges the call's
  peak memory falls from 290 MB to 9 MB and its time from 1.33 s to
  0.39 s. Results are unchanged.
• A short kernel step no longer waits to be woken. The calling thread
  spins for up to 50 µs before it parks while the compute pool runs a job,
  so a job over a small graph returns in 2–4 µs instead of the 20–40 µs
  the operating system took to wake the caller (DESIGN.md §6.9).
  PageRank runs three jobs an iteration: on lesmis a call takes
  1.3–1.4 ms instead of 3.5–3.7 ms (on a 3-node graph 1.0–1.2 ms instead
  of 2.8–3.0 ms), and larger graphs are unchanged or slightly faster.
• Measured: a traversal call's fixed cost is 25–70 µs, not 0.2–2 ms.
  Warm, with the round trip, bfs, shortest_path and walk take
  0.07–0.11 ms against 0.04 ms for SELECT 1, on PG 16 and 18. Half of
  the server's share is the one catalog read that resolves the graph
  (DESIGN.md §13, "After 0.7.0"). Nothing in traversal changed.

The apt repository's signing key has the fingerprint A7FFD766EE915EE8E97085F8DF33D7645F721A34;
check the key you fetched with gpg --show-keys /etc/apt/keyrings/pg_warren.asc.