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", with a hint that the server is a
  standby. It failed with an internal error (XX000), "cannot assign
  TransactionIds during recovery": pgrx's writable SPI calls assign a
  transaction id before the write, which a standby refuses. That covers
  create_graph, refresh, promote, compact, the drop_* functions,
  access and quota changes, contract, persisted vector writes and the
  library functions, which persist their result. Reads, and compute with
  persist := false, work on a standby and answer as on the primary
  (DESIGN.md §5.1, Standbys; found by test/replicas.py). A read-only
  transaction on a primary now gets the same refusal before it assigns a
  transaction id.

• refresh with a NULL name or promote, and prewarm with a NULL
  name, are refused with null_value_not_allowed (22004), "… must not
  be NULL". They failed with an internal error, "argument 0 must not be
  null" (XX000). Found by the SQL fuzzer.

• eigen with vectors_prefix and a k larger than the graph, and
  distance(..., 'subspace') with a k larger than the vectors stored,
  no longer crash the server. Each made a name for every one of the k
  vectors before anything else, and with k near 2^31 that allocation
  failed and aborted the backend (signal 6), which restarted every
  backend. With vectors_prefix, eigen now admits the eigenproblem
  before it makes or checks a name for each eigenvector: a k past the
  dimension is refused with invalid_parameter_value (22023), "cannot
  compute k eigenpairs of a matrix of dimension n", and a working set
  that cannot fit with 53400, which now comes before a refusal to replace
  another role's eigenvectors (42501). subspace makes each name as it reads it,
  failing at the first missing vector with undefined_object (42704).
  Found by the SQL fuzzer.

• An array of node ids whose last element is NULL no longer fails with
  an internal error ("assertion failed: array.is_within_bounds", XX000)
  in debug builds: a bfs or reachable_set start, a node_filter, a
  step's filter (warren.s). The NULL is skipped, as a NULL elsewhere
  in the array always was. Found by the SQL fuzzer
  (test/sql_fuzz.py). The ids are read while the array is alive,
  including an array read from a table column, which a function gets
  detoasted into a copy (tested with short, compressed and out-of-line
  text[] and uuid[] arrays).

• A persisted vector written to a version that retention or
  drop_version deleted meanwhile fails with undefined_object (42704),
  "version … no longer exists: vector … was not written to it". It
  failed with a raw foreign-key violation on warren.vectors (23503).
  Every persisted write (spmv, pagerank, vector_const and the rest)
  now locks the graph's and the version's rows before it writes, waiting
  for a deletion in progress (harness tests vector_retention_race and
  test/concurrent_refresh.py). Under REPEATABLE READ or SERIALIZABLE
  such a write fails with serialization_failure (40001) instead: retry
  it.

• A read of a shared version that another backend was evicting at that
  moment could fail with an internal error, "cannot pin a segment that
  is already pinned" (XX000): the evicting backend unpinned the version's
  segment after releasing the shared cache's lock, so a reader could
  revive the version first. It now unpins under the lock a segment that
  another backend still maps, which frees nothing; one nobody maps, which
  unpinning frees, is still unpinned after the lock is released, so no
  lookup waits for it (found by test/concurrent_refresh.py, preloaded).

• compact could fail with data_corrupted (XX001), "vector has 0
  bytes", when a vector bound to the version it compacts was dropped
  while it ran. It now locks each vector before moving it and skips one
  dropped since it listed them (found by test/concurrent_refresh.py). A
  vector that reassign_owned gave to another role while compact ran
  is moved under that role (harness test compact_reassign_race). Under
  REPEATABLE READ or SERIALIZABLE either change fails the compaction with
  serialization_failure (40001) instead: retry it.

• DISCARD ALL frees the backend's transient vectors, of every role,
  and forgets last_stats(). It left both, so behind a session pooler
  (PgBouncer's server_reset_query), the next client on a server backend
  could read the transient vectors and the stats the last client left,
  and the vectors stayed until the backend exited (found by
  test/pooler_soak.py; regression test test/sql/discard_all.sql).

• A persisted vector dropped by another backend no longer stays in the
  cache of the backend that wrote it. That backend pruned dead vectors
  only when it next loaded one privately; with the shared cache serving
  its reads it never did, so behind a transaction pooler, where a vector
  is often written on one server backend and dropped on another, each
  backend kept the vectors it wrote until warren.max_cache_memory (4 GB
  by default) evicted them: 8 MB a minute per backend in the pooler
  soak. A write now prunes as a load does (found by test/pooler_soak.py).

• An ERROR raised while pg_warren read a query through a cursor that
  had a parallel plan running no longer crashes the server (SIGSEGV,
  which restarts every backend). Closing the cursor as the ERROR unwound
  detached the parallel query's shared memory before the
  (sub)transaction's abort ended the parallel query, which then read the
  unmapped segment. The cursors pg_warren reads (the node and edge
  queries, gather's messages, the other queries a function is given,
  and segment chunks) are now left open on an ERROR, for the abort to
  close in Postgres's own order (DESIGN.md §6.9;
  found by the SQL fuzzer: a statement_timeout during
  label_propagation_majority under debug_parallel_query).

Performance

• A relation whose edges start from at most about a sixth of the nodes
  (an eighth above 2³² nodes) stores its rows' ids and an offset per row
  (12 bytes a row, 16 above 2³²) instead of 8 bytes per node, in each
  direction on its own; the merged CSR is unchanged (DESIGN.md §5.3).
  FB15k-237 (237 relations, 14.5K nodes, 310K edges) now takes 8.0 MB
  where it took 60.5 MB, refreshes in about 0.2 s instead of 0.45 s and
  loads cold in 60 ms instead of 113 ms. Reads restricted to relations
  pay a binary search per row looked up: on FB15k-237, a BFS over its 10
  largest relations takes 1.1× as long and an SpMV over them 1.2–1.4×;
  reads over all relations are unchanged.
• Without the merged CSR (store_merged := false), BFS and components
  read the relations' rows in ascending order; on FB15k-237 they are
  1.5–2.2× faster than in 0.6.0, and the version ten times smaller, but
  an all-relations spmv takes 1.6–2× as long (docs/limits.md).
• triangles (and clustering, which counts them) orients each edge
  from its endpoint of lower degree and finds each triangle once, about
  M·√M at worst, where it intersected every neighbour row of every node:
  on SNAP's facebook graph 156 → 7.0 ms and on Hetionet
  4.09 → 0.116 s, and on a skewed (R-MAT) graph of 2M edges 14.6 →
  0.53 s on one thread. It holds 8 bytes per stored edge, half the
  symmetric adjacency it built before. Counts are unchanged.
• contract finds which of a pair's entries count in one sweep of the
  rows, so louvain and leiden on graphs with many relations are not
  slowed by counting a pair once: on FB15k-237 (237 relations) they take
  0.42 s and 1.49 s, against 0.70 s and 1.84 s in 0.6.0 (YAGO3-10 0.80 /
  2.49 s against 1.26 / 3.30 s; Hetionet 1.61 / 3.05 s against 1.77 /
  2.78 s; medians of 5). The partitions differ from 0.6.0's where pairs
  are linked in several relations (under Behaviour changes).
• walk and neighbours hold only the current row's external ids: over
  50,000 IRIs, a cursor on one held 3.7 MB (neighbours, walk ends) or
  17.9 MB (walk paths) after its first row, and now holds 0.09 MB,
  against 0.05 MB over 1,000.

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.