pg_sift 4.1.0: the aggregate scan answers more of what an application runs, with the defaults and the queries it has. A join of a range of events to a large lookup table, `EXISTS`, `NOT EXISTS`, `IN` and `NOT IN` over one, a scalar sub-select used as a constant, a sum times a value of a joined table, an `ORDER BY .. LIMIT n` over a join by a text key, and group-bys whose groups outgrow `work_mem` are planned as probes and passes where they were a join of every row or a scan read again for each share. A minor release of 4.0.3 with no new SQL object and four new settings: install the packages, restart the server, then run `ALTER EXTENSION pg_sift UPDATE` in each database.

## Highlights

The figures are those of `bench/bench cases --rows 300000` on this release (run a8be5fa5be36-20261105T122909Z-aec6; PostgreSQL 18.6, one x86-64 host, the data in memory, one backend, warm medians of 5 runs), as milliseconds, millions of instructions and buffers touched, against PostgreSQL's plan with the index left out. Each has a row in `bench/claims.tsv`.

- **Faster: a join of a range of the scan's keys to a large b-tree table, and `EXISTS`, `NOT EXISTS`, `IN`, `NOT IN` over one** (`sift.agg_probe_rewrite`, `sift.agg_probe_direct`, on by default). The scan takes the keys it meets and the planner probes the b-tree of the large table for each, in batches, from the entries of the index when it holds the columns the join reads (key columns or `INCLUDE`), where the join read every row of the range. Case `lookup_probe_join` (60 parents of 3,000, a links table of 1,500,000 rows): 2.42 ms · 26.4 M instructions · 232 blocks, against 129 ms · 1,466 M · 11,998 (53 times). A 60-key range of 300,000 events against a table of 1,000,000 rows: 344.5 M instructions become 14.9 M for the inner join, 549.8 M become 57.0 M for `NOT IN` and 701 M become 48 M for `EXISTS`. The comma join, `NOT IN` over sub-selects, alias columns, an anti join over several tables and `LATERAL` entries take the same plan, and so do `RIGHT` and `FULL JOIN` to a lookup with an aggregate of the scanned table. The keys of a filtered table joined to a grouped sub-select are looked up before the groups are made (200,000 rows in 20,000 groups, one name: 20.0 M instructions become 2.6 M).
- **Faster: a scalar sub-select is a constant of the scan.** `WHERE amount > (SELECT avg(amount) FROM t)`, `kind_id = (SELECT id FROM kinds WHERE name = 'x')` and `sum(amount + (SELECT max(w) FROM kinds))` kept the whole query out of the scan; the scan now asks the sub-select once when it starts, also in the workers the plan asks for. A sub-select that may give a second row keeps the normal plan. A sum of a numeric column times such a value, or times the value of a table joined by its unique key, adds up the amounts of each key first (`agg_eager_lookup`).
- **Faster: an `ORDER BY .. LIMIT n` over a table joined by a text key** (`JOIN keys ON keys.k = t.title`, `IN (SELECT ..)`, `EXISTS`; an inner join needs a unique index on the key) is answered by the top-N scan, as the joins by an integer or a date key are. 600,000 rows and 200 keys: 6,461 M instructions and 3.6 s become 118 M and 0.14 s. A join of a text column with up to 256 distinct keys tests the keys on the encoded form of each unit, also for a text field of the elements of an array (`jsonb_to_recordset`), and the in-memory dictionary hashes long strings in wide steps.
- **Faster: group-bys whose groups outgrow hash memory.** A scan whose group table is several times hash memory chooses the number of passes from the planner's estimate and reads the table once for each pass, where it read it once to find out, threw that away and read it again for every share (`group_passes_upfront`: 14.3 ms · 107 M · 1,194 blocks, against 94.5 ms · 849 M · 4,105; 6.6 times). Two or more integer keys whose direct arrays do not fit put their groups in the hash table at once (`group_direct_arrays_passes`: 40.1 ms · 392 M · 5,065, against 162 ms · 1,643 M · 4,105; it touches more buffers than the sequential scan, the gain is time and instructions). A spill is cheaper for each group written and merged back (`group_spill_two_keys`, 64 kB of hash memory: 106 ms · 831 M · 303, against 180 ms · 1,970 M · 4,105; 1.7 times). The passes split the groups by another constant than the table of ids hashes by, which had crowded the slots of one share.
- **Faster: the sum of a float column that is not grouped** (`SELECT sum(value_a) FROM t`, `avg`, a filtered sum) keeps the running sum in a register, in the same order, so the bits of the result are the same (`float_sum_ungrouped`: 0.546 ms · 5.21 M · 149 blocks, against 23.2 ms · 140 M · 1,911; 43 times). A float column grouped by the buckets of its values (`floor(x / 5)::int`, `round(x / 10)`) is evaluated for each bucket (`sift.agg_float_step`: 624 M instructions become 107.5 M over 1,000,000 rows).
- **Changed: `key_cut` indexes are built by key ranges** (`sift.col_build_key_ranges`, on by default). The segments of a large `CREATE INDEX` or `REINDEX` no longer each hold rows of every key, so a lookup of a few keys reads one unit; the build takes about a quarter longer (2,650,000 rows: a key in 1.00 units against 7.95; WAL 170 MB against 340 MB for the rewrite). The maintenance rewrite of an index built before 4.1 cuts its overlapping segments by key, paced by `sift.col_auto_merge_pass_mb` (1,024 MB of runs a pass, 0 does all at once) so the first maintenance after the upgrade does not write an index at once.
- **Faster: sorted output and ordered aggregates.** `array_agg(id ORDER BY amount DESC, id)` sorts the values of a group in tuples with the fixed-width columns first (2,740 M instructions against 5,071 M, 205 ms against 282 ms); the scan that gives its groups in the order of the `ORDER BY` or window above it, a `Sort` above the groups with several keys, a group key that is a `COALESCE` of two columns, an aggregate of the groups of a sub-select that sorts, and the radix sort of `CREATE INDEX` take fewer passes and less work for each group.
- **Cheaper planning.** The planner counts the all-visible pages of the visibility map with the CPU's popcount in one pass for each run, computes the share of the keys of a CTE list once for each run and arm, plans a statement with pulled-up lateral sub-selects once after its first run, and prices a lookup table read whole from its heap and the rows a join adds beyond the fact table by what the load and the join take.
- **Fixed:** a `LIMIT`, a merge join or a window above a grouped sub-select took the scan whenever it cost less in total, not for the rows it must give first; `GROUPING SETS`, `ROLLUP` and `CUBE` over keys that are expressions of a sub-select; and `SET ..; EXPLAIN ANALYZE ..` sent in one query string as the first statement of a connection that has not preloaded the library ran the ordinary plan. Each has a test below. Every answer is those of the plan without the extension.

## Who is affected and what to do

- **Update (the steps, in this order):** install the files; **restart the server** (a standby too), because a backend that already loaded the old library keeps it until its connection ends; then run **`ALTER EXTENSION pg_sift UPDATE`** in each database. The update runs `pg_sift--4.0.3--4.1.sql`, which changes nothing in the SQL (the two functions `sift.index_choices` and `sift.help` came with 4.0.3); no column format changes, no `REINDEX`. The new plans are used by the indexes you have; a `REINDEX` of a `key_cut` index builds it by key ranges.
- **Coming from 4.0.0 to 4.0.2:** the update goes through 4.0.3 by itself (`pg_sift--4.0--4.0.3.sql`, then `pg_sift--4.0.3--4.1.sql`). Those releases corrected wrong grouped reads (a table attached as a partition or inheritance child, a primary key dropped and added again, `pg_squeeze`): after the update run `REINDEX INDEX <index>` on the `sift_col` index of such a table, and `SELECT sift.col_verify('<index>', true)` returns no row for a good index. A database from 4.0.3 needs nothing else.
- **A `key_cut` index larger than `sift.vacuum_rewrite_limit` that a build wrote as several segments:** the first maintenance after the update (VACUUM, a read tick or `sift.col_maintain`) starts the rewrite by key range and goes on from where it stopped; each pass writes about 1,024 MB of runs and the index is valid and equal to the heap's between passes. `sift.col_auto_merge_pass_mb = 0` does all of it at once, `sift.col_build_key_ranges = off` builds as 4.0.3 did.
- **Going back to 4.0.3** after `ALTER EXTENSION pg_sift UPDATE`: [docs/UPGRADING.md](https://github.com/brauliobo/pg_sift/blob/v4.1.0/docs/UPGRADING.md), "An older release".
- **Every setting has an off switch:** `sift.agg_probe_rewrite = off` and `sift.agg_probe_direct = off` give the plans of 4.0.3 for joins and lookups, `sift.agg_float_step = off` evaluates each distinct float value, `sift.col_build_key_ranges = off` and `sift.col_auto_merge_pass_mb = 0` as above. [docs/OPTIONS.md](https://github.com/brauliobo/pg_sift/blob/v4.1.0/docs/OPTIONS.md) gives the gain, the cost and the reason of each default.

## Known issues

Not fixed here, each with its reason:

- **A float sum stays out of the eager rewrite** (the sum of the amounts of each key first): float addition depends on the order, so the rewrite would change the bits of the result. A numeric sum takes it.
- **A `key_cut` index takes only integer, date, timestamp, numeric and float keys** (the columns `key_cut` takes); the build by key ranges needs the same, so a text key keeps the runs in the order of the table.
- **Scans of 6 to 18 ms can get slower with workers** (as with literals): a scan this short does not repay starting them, and the planner's price is not exact at that size; `max_parallel_workers_per_gather = 0` for such a statement.
- **The planning of a `NOT EXISTS` that the scan keeps as the plain form grows with `default_statistics_target`:** PostgreSQL's `eqjoinsel` compares the most common values of both join columns ([docs/AGG.md](https://github.com/brauliobo/pg_sift/blob/v4.1.0/docs/AGG.md)); this is the native planner's cost, which the scan does not change.
- **A `key_cut` index is built by one process, also with `max_parallel_maintenance_workers`:** by design, because the segments of parallel participants overlap in the key and the merge that follows rewrites every row, which took longer than one writer; the build by key ranges is serial too.
- **The passes cost about twice the in-memory plan for float sums at a small `work_mem`:** a statement with float sums is read as before (the groups spill to partitions and are merged back), because float sums add in the order of the scan; raise `work_mem` or `hash_mem_multiplier` for such a report.
- **Still as before (from 4.0.0, not fixed here):** `DROP INDEX CONCURRENTLY` of an index with `track_changes` and `pg_repack --only-indexes` fail with `must be first action in transaction` (run `ALTER INDEX <index> SET (track_changes = 'off')` first); after `ENABLE TRIGGER ALL` following a `DISABLE TRIGGER ALL` (what `pg_restore --disable-triggers` does), and after `REINDEX CONCURRENTLY` the reads of the table go to the heap, which is slower and not wrong, until a plain `REINDEX INDEX <index>`. A table attached (`ATTACH PARTITION`, `INHERIT`) before 4.0.2 and written through its parent needs `REINDEX INDEX <index>` at its `DETACH PARTITION` or `NO INHERIT`.

## Tests

`agg_probe_rewrite`, `agg_probe_direct` and `agg_probe_direct_race` (the probe plans and the concurrent probes), `agg_lookup_in_keyed`, `agg_decor_lookup`, `agg_group_key_lookup` (the keys of a filtered table), `agg_scalar_initplan`, `agg_factor_constant` and `agg_eager_lookup` (the sub-select as a constant, the eager sum), `agg_topn_join_text`, `agg_join_filter_text` and `agg_join_filter_elem_text` (the text keys), `agg_plan_passes`, `agg_group_hash_probe`, `agg_group_startup`, `agg_float_step`, `agg_rank_sort`, `agg_vis_counts`, `agg_preserved_leaf_aggs` and `agg_eligibility_survey`, `col_key_cut_ranges`, `col_key_cut_overlap` and `col_key_cut_paced` (the build and the paced rewrite by key range), `col_list_test_once`, `col_point_many_keys`, `agg_key_list_once` and `core_radix_sort`. The update paths 3.7 to 4.1, 4.0 to 4.1 and 4.0.3 to 4.1 and a fresh install are in `extension_lifecycle`; a cluster written by 4.0.3 and by 4.0.0 is upgraded with `pg_upgrade` and updated in `pg_upgrade`, `pg_upgrade_31`, `pg_upgrade_32` and `pg_upgrade_33` (a cluster of 3.x, with an index named after the key of its table); `compat_matrix` and `old_lib_refusal` run on every major.

## Compatibility

- PostgreSQL 17, 18 and 19; the packages below cover all three (other builds from source with `make USE_PGXS=1`). A replacement of 4.0.3, 4.0.2, 4.0.1 and 4.0.0 with one step after the install: extension SQL 4.1 (`pg_sift--4.0.3--4.1.sql`, no change of an object); column format minors 3 to 42 are read and written as in 4.0.0, BM25 metapage minors 1.0 to 1.5. The SQLite and MariaDB extensions: no change since 4.0.0.

## Packages

x86-64 and arm64 packages for PostgreSQL 17, 18 and 19 are attached below (`SHA256SUMS` covers every asset); other versions build from source with `make USE_PGXS=1`.

- Debian 12 and 13, Ubuntu 22.04 and 24.04 (PGDG `postgresql-N`, N = 17, 18 or 19): `sudo apt install ./postgresql-N-pg-sift_4.1.0-1_amd64.deb` (`_arm64.deb` on arm64)
- RHEL, Rocky, Alma 9 and 10 (PGDG `postgresqlN-server`): `sudo dnf install ./pg_sift_N-4.1.0-1.el9.x86_64.rpm` (`.aarch64.rpm` on arm64)
- Amazon Linux 2023 (the distribution's `postgresqlN-server`, N = 17 or 18): `sudo dnf install ./pg_sift_N-4.1.0-1.amzn2023.x86_64.rpm` (`.aarch64.rpm` on arm64)
- Arch Linux: AUR `pg_sift`.

Every change: [CHANGELOG.md](https://github.com/brauliobo/pg_sift/blob/v4.1.0/CHANGELOG.md).

## SQLite extension

pg_sift for SQLite 4.1.0 (`sift`, a loadable extension; a separate component from the PostgreSQL extension above). Rebuilt with the PostgreSQL 4.1.0 release: no change to the SQL interface or the shared format.

- **No change:** the changes of this release are in the PostgreSQL column index, which is not in this extension. No speed-up or slow-down is claimed.
- Needs SQLite 3.38 or newer; Linux x86-64, glibc 2.34 or newer. Built on Debian 12, loaded into the SQLite of Debian 12, Ubuntu 24.04 and AlmaLinux 10 before release.
- Storage format 2: tables of 3.4.0 to 3.7.0 open as they are, nothing to rebuild.

Download `sift-sqlite-4.1.0-linux-x86_64.tar.gz` (below, covered by `SHA256SUMS` with the packages), unpack it and `.load ./sift` from the `sqlite3`
shell (`sha256sum --ignore-missing -c SHA256SUMS`). Documentation: [sqlite/README.md](https://github.com/brauliobo/pg_sift/blob/v4.1.0/sqlite/README.md).
Every change: [sqlite/CHANGELOG.md](https://github.com/brauliobo/pg_sift/blob/v4.1.0/sqlite/CHANGELOG.md).

## MariaDB extension

pg_sift for MariaDB 4.1.0 (`sift`, a UDF library and two SQL files; a separate component from the extensions above). Rebuilt with the PostgreSQL 4.1.0 release: no change to the SQL files.

- **No change:** the changes of this release are in the PostgreSQL column index, which is not in this extension. No speed-up or slow-down is claimed.
- One library per MariaDB series, because it calls the server's own symbols and refuses to load into another series: 10.11, 11.4, 11.8, 12.1 and 13.0; Linux x86-64. Each was built in the stock `mariadb:<series>` image against that server's headers and loaded into a server of the same image before release. `BUILD-INFO` in the tarball lists the server version and the glibc each library needs.
- Index format 2: an index of 3.4.0 to 3.7.0 opens as it is, nothing to rebuild.

Download `sift-mariadb-4.1.0-linux-x86_64.tar.gz` (below, covered by `SHA256SUMS` with the packages), unpack it, copy `lib/<series>/libsift_udf.so` of your server's series
(`SELECT VERSION()`) into its `plugin_dir`, then `SOURCE sql/functions.sql` once per server and `sql/sift.sql` once per database (`sha256sum --ignore-missing -c SHA256SUMS`).
Documentation: [mariadb/README.md](https://github.com/brauliobo/pg_sift/blob/v4.1.0/mariadb/README.md).
Every change: [mariadb/CHANGELOG.md](https://github.com/brauliobo/pg_sift/blob/v4.1.0/mariadb/CHANGELOG.md).