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.

pg_warren 0.7.0

Milestone M11 of DESIGN.md §13: proven on real graphs and in real
deployments. pg_warren now runs a suite of 19 real graphs pinned through
keepset (bench/corpus), checked against NetworkX and igraph and timed
head to head with igraph and Neo4j, with and without GDS (README, "How it
compares"), and Appendix A's use cases at 10M nodes. A pair of nodes
linked in several relations is now read one way everywhere: strengths
are summed and an unweighted pair counts once, costs take the pair's
best edge, and per_relation := true reads an edge in each relation; on
graphs with such pairs some results differ from 0.6.0's (under Behaviour
changes). A relation with few edges stores sparse offsets, so every graph
needs a refresh after the upgrade (under Upgrading). Concurrent
refreshes, crash recovery, streaming replicas, a connection pooler and a
SQL fuzzer found the bugs under Fixes, two of them server crashes.
Packages are published from this release on: a signed apt repository for
Debian and Ubuntu, Docker images, a Homebrew tap and tarballs, for amd64
and arm64 (under New).

Upgrading

• If pg_warren is in shared_preload_libraries, restart the server
  after installing the new build: the postmaster keeps the library it
  loaded at start, and every backend inherits it.
• Restart the server if the shared cache is in use. The shared cache's
  registry is now pg_warren.cache.4, so backends of the old and the new
  build never share a version; the old registry's segments are freed by a
  restart.
• Run ALTER EXTENSION pg_warren UPDATE; in every database that has
  the extension, after installing the new build and before using the
  new version. The update drops and creates again the 27 functions that
  gain per_relation (under New), keeping their privileges; it changes
  no table. Until the update, 0.6.0's definitions still work with the new
  library, reading a pair as the new default does, except 0.6.0's
  sssp_vector (PL/pgSQL), which still sums a pair's weights until the
  update.
• The update drops those functions without CASCADE, so it fails if a
  view, or a function with a BEGIN ATOMIC body, calls one of them
  ("cannot drop function ... because other objects depend on it"). Drop
  the dependent objects, run ALTER EXTENSION pg_warren UPDATE, then
  create them again.
• Refresh every graph after installing the new build. A relation's
  CSR can now store sparse offsets, so CSR segments have a new format
  (2). Reading a version built by an earlier release fails with
  object_not_in_prerequisite_state (55000) and a message naming
  warren.refresh; a refresh builds on it as usual, and the version it
  builds reads. Old versions are not converted. Vectors are bound to a
  version, so recreate them on the new one.

Behaviour changes

• An unweighted pair of nodes linked in several relations now counts
  once in modularity, contract, local_moving, leiden_refine,
  louvain and leiden, as it already did in spmv, degree and
  pagerank. They counted it once per relation, so on graphs with such
  pairs their results differ from 0.6.0's. A counting contract counts
  the pair in the first of its relations. Weighted pairs are unchanged:
  their weights are summed across relations.

• Functions that read edge weights as costs now take a weighted pair
  linked in several relations at its best edge, not the sum of its
  relations' weights: sssp_vector, betweenness_centrality,
  closeness_centrality, harmonic_centrality and
  minimum_spanning_forest its lightest relation's weight,
  dag_longest_path its heaviest. Strengths add, costs don't: a road of
  5 km and a railway of 3 km between two towns are a route of 3 km, not
  8. Through 0.6.0 these functions summed the weights, so on weighted
  graphs with such pairs their results differ from 0.6.0's. dijkstra
  already took the cheapest relation through 0.6.0, and still does.
  Functions that read weights as strengths (spmv, spmm, pagerank
  and the other spectral centralities, the community functions,
  contract, eigen, distance) still sum them; spmv with min_plus
  reads the sum too unless given per_relation := true. Unweighted calls
  are unchanged. See docs/semantics.md, "A pair in several relations".

• per_relation := true gives the cost functions the same result as
  the default (dijkstra, sssp_vector, the three shortest-path
  centralities, dag_longest_path, minimum_spanning_forest): as
  parallel edges, a path takes the cheapest (longest paths the heaviest).
  They accept it, and refuse NULL (22004), so that per_relation means
  one thing on every function.

• Undirected weighted centralities refuse a pair whose weight is NaN in
  one direction (22023), as they refuse a NaN anywhere else. They used
  the other direction's weight.

• eigen (and distance('spectral')) returns every copy of the
  eigenvalue each connected component gives: 0 of laplacian and
  normalized_laplacian with which := 'smallest', 1 of random_walk
  with which := 'largest', and each bipartite component's −1 of
  random_walk and 2 of normalized_laplacian with which := 'largest'. Each copy is one component's eigenvector,
  found exactly and without Lanczos steps, components in the order of
  their lowest node, and Lanczos computes the rest of the k orthogonal
  to them. Before, Lanczos found one copy and mistook the next eigenvalues
  for the rest: 30 disjoint 40-cycles' three smallest Laplacian
  eigenvalues came back as 0, 0.025 and 0.098, and on roadNet-TX (424
  components) the call ran past a 10-minute timeout; four paths' random
  walk gave 1, 1, 1, 1, −1, 0.9709, −0.9709 for its 7 largest, against
  four −1s. A call all of whose pairs are the components' no longer warns
  of several components; one with pairs from Lanczos still does. Other
  results change in the last digits; a connected graph's 0 is now exactly
  0.

• A graph's number of relations no longer refuses its build on its own.
  warren.max_build_memory used to be checked against 8 bytes per node
  for every relation's CSR (and the merged CSR), in each direction; it is
  now checked against the merged CSR's offsets and 8 bytes per relation,
  and each relation's offsets count in the build's estimate by its edges.

• bfs expands each depth's nodes in ascending dense id order (the
  graph's internal node order), so within a depth its rows can come in a
  different order than in 0.6.0, and a node reachable from several nodes
  of the previous depth reports as via the one of smallest dense id.
  Nodes and depths are unchanged.

• walk and neighbours make each row's external ids as the row is
  returned, rather than all rows before the first, as components and
  the others have since 0.6.0. Their rows and order are unchanged; walk
  still runs the whole walk in its first call. Such a call keeps the
  version it reads, private or mapped from the shared cache, until its
  last row is read or it ends (under Performance).

New

• per_relation boolean DEFAULT false on modularity, contract,
  local_moving, leiden_refine, louvain, leiden, spmv, spmm,
  pagerank, katz_centrality, eigenvector_centrality, hits,
  sssp_vector, dijkstra, betweenness_centrality,
  closeness_centrality, harmonic_centrality, dag_longest_path,
  minimum_spanning_forest, degree, vector_degree, degree_vector,
  aggregate_neighbours, gather, label_propagation_majority, eigen
  and distance: true reads a pair linked in several relations as an
  edge in each (one per relation, as parallel edges), for when that
  multiplicity is the signal.

• docs/limits.md, "Behind a connection pooler": what transaction
  pooling loses and leaks between clients (settings, transient vectors,
  last_stats(), SQL PREPARE) and what to use instead, checked by
  test/pooler_soak.py, a soak behind PgBouncer in transaction and
  session pooling that watches pooled backends, the shared cache and the
  catalog for growth (CI runs it for 2 minutes on PG 16).

• Packages, published with each release from this one on (README.md,
  "Install"): a signed apt repository of postgresql-NN-pg-warren
  packages for PostgreSQL 15–18 on Debian 12 and 13 and Ubuntu 22.04 and
  24.04, amd64 and arm64, built against PGDG's PostgreSQL; Docker images
  on GHCR (ghcr.io/exadev/pg_warren:pgNN and X.Y.Z-pgNN, PGDG's
  postgres image with the package's files and pg_warren preloaded);
  a Homebrew formula (brew install exadev/tap/pg_warren, for
  postgresql@17 and @18, bottled on Apple silicon); and tarballs for
  other glibc Linux. Each GitHub Release has a signed SHA256SUMS. The
  packages do not edit postgresql.conf: add the preload yourself. macOS
  is not yet a supported platform (its tests run in CI without gating),
  and RPM packages and PGXN are not built yet.

Fixes

• A read of a graph inside a parallel CREATE TABLE AS (or CREATE MATERIALIZED VIEW, REFRESH MATERIALIZED VIEW) no longer fails with
  "cannot start commands during a parallel operation". Such a statement
  has a transaction id before its plan runs, so pgrx ran every catalog
  read non-read-only, with a command counter increment, which Postgres
  refuses in parallel mode once the command has used its command id: in
  the leader as soon as it ran the function, and in a worker. In parallel
  mode the catalog reads now run read-only, as cursors under the active
  snapshot (DESIGN.md §6.9; found running Appendix A.3 at 10M nodes, whose
  sampled oracle builds a table from warren.id_map; tests
  every_read_runs_in_a_parallel_create_table_as,
  a_parallel_create_table_as_runs_a_safe_read_in_its_leader_too).
• **On a physical standby, every function that writes fails with
  read_only_sql_transaction (25006), "cannot change pg_warren's catalog
  in a read-only transaction"...