Format numbers

Every number written to disk or checked on upgrade, and who claims it. A new feature takes the next free number here before one in the code; two released features never share a number or a flag. The features of one release that no earlier release shipped share that release’s minor (4.3: 44), since a library before it refuses all of them the same way.

1. Extension script

version script from
3.0 sql/pg_sift--3.0.sql sql/pg_sift--1.2--3.0.sql
3.1 sql/pg_sift--3.1.sql sql/pg_sift--3.0--3.1.sql (3.0.x, every patch release, update to 3.1 with ALTER EXTENSION pg_sift UPDATE)
3.2 sql/pg_sift--3.2.sql sql/pg_sift--3.1--3.2.sql
3.3 sql/pg_sift--3.3.sql sql/pg_sift--3.2--3.3.sql
3.4 sql/pg_sift--3.4.sql sql/pg_sift--3.3--3.4.sql
3.5 sql/pg_sift--3.5.sql sql/pg_sift--3.4--3.5.sql

sql/pg_sift--3.5.sql is the complete script and sql/pg_sift--3.4--3.5.sql adds the same objects to a 3.4 install (test/t/extension_lifecycle.sh compares them). Released scripts never change, so an in-place update equals a fresh install: later objects go into the next version’s two scripts, and scripts/ci.sh --selftest checks released ones against scripts/released-sql.sha256. The on-disk formats below do not depend on the script: the library reads whatever the files hold.

2. Metapage (SiftMetaPageData, src/core/sift.h)

Format major 1. The minor is what a build must read to understand an index or table; a build refuses a larger one with a REINDEX hint (check_meta). A metapage starts at SIFT_FORMAT_MINOR_BASE (2); only the first segment that needs more raises it and nothing lowers it, so an index without newer structures stays readable by 3.0.

minor meaning raised by
1.1 term blobs may end with a position stream BM25 index with positions
1.2 segment format 2 BM25 index
1.3 BM25: segments of segment format 3. sift_table: a column group with unfrozen rows (SIFT_SEG_VERS) the first such segment
1.4 BM25: segments of segment format 4 (the position stream in blocks). A sift_table stays at 1.3 the first such segment
1.5 BM25: segments of segment format 5 (the values of the INCLUDE columns). A sift_table stays at 1.3 the first such segment, of an index that names INCLUDE columns
1.6 BM25: a write buffer of buffer format 6 (SIFT_WBUF_FORMAT_WIDE, below). A sift_table stays at 1.3 the first such buffer: the next insert into a BM25 index after the upgrade opens one

sift_col indexes are never raised: their segment formats are the column engine’s (section 4).

Metapage flags: SIFT_COL_META_FLAG 0x00010000 (a sift_col index), SIFT_TBL_META_FLAG 0x00020000 (a sift_table); the low byte is the failure count (SIFT_META_FAILURES_MASK).

3. BM25 segments (SiftSegEntry.format, access method sift)

The write buffer of a BM25 index is a lane chain whose directory entry has a format of its own (not a segment format): 0, pages with the 256-bit bloom of term hashes in the header (SiftWbufPageHeaderData), which a page of 900 terms and more fills, so that a term in no document of the buffer still reads every page; 6 (SIFT_WBUF_FORMAT_WIDE, 4.2), the same header followed by a bloom of 8,192 bits (SiftWbufWideHeaderData, 2 probes: bits 0..12 and 13..25 of the term hash; 4% false positives at 900 terms). A buffer keeps the format it was opened with, and a library of 4.2 reads both, so an upgrade has no manual step: the buffer open at the upgrade is read as it is and the one opened after it is format 6. The first buffer of format 6 raises the metapage to 1.6, which a library of 4.1 or older refuses (check_meta: it reads formats 1.0 to 1.5, REINDEX or install the release that wrote the index); nothing lowers it.

format name written by
1 SIFT_SEGFMT_RANKBITS: one liveness bit per doc in rank order SQLite and MariaDB hosts
2 SIFT_SEGFMT_LIVEROWS: liveness rows per superblock, dead-posting table 3.0
3 SIFT_SEGFMT_PACKED: dictionary blocks, narrower docmap rows, packed containers (perf/BM25-SIZE.md section 5) 3.1 PostgreSQL
4 SIFT_SEGFMT_POSBLK: the position stream of a term in blocks of 32 postings, bit-packed (bm25/posblk.c, perf/BM25-SIZE.md section 5.4); a dictionary block says so with SIFT_DICT_POS2 3.7 PostgreSQL
5 SIFT_SEGFMT_ATTR: format 4 with the values of the INCLUDE columns: per column and SB one record (a 24-byte SiftAttrColHdr of the smallest value, the code of an unknown value, the width and the flags (1: no rows; 2: no document of the SB is unknown, so the smallest value and the code give its exact range and a test that no value of it passes drops the SB), then the row of each present page, width bits a slot: 0 is NULL, v - base + 1 a value, the unknown code a document whose heap tuple was gone) after the docmap records, and a docmap trailer SiftAttrRef[nsb][ncols], u64 recs_end, u32 ncols, u32 nsb (bm25/segment.h, bm25/segment_int.h) 4.0 PostgreSQL

A 4.0 build reads 1 to 5 side by side, and writes format 5 only for an index with INCLUDE columns (the others stay at 4: a 3.7 library still reads them); a merge writes the current format. 3.0 refuses a segment of format 3, 3.6 and older one of format 4, and 3.7 and older one of format 5, through the metapage minor (section 2); REINDEX with the older library rewrites it.

4. Column segments (SiftSegEntry.format of access methods sift_col and sift_table)

format meaning written by
3 3.0 layout (dictionaries as codec string lists) 3.0, and 3.1 with sift.col_format_minor = 3 (a sift_table group without a version section)
4 3.1: type tags (SIFT_COLC_TAGS) and kinds (SIFT_COLC_KINDS) of overflowing values, element rollups (COLP directory v2), optional version section 3.1 default
5 3.2: a schema with wide leaves; written only for such an index 3.2
6 3.2: complete JSON kinds for path leaves, including element leaves; only when every input preserves them 3.2 default for declared JSON paths
7 3.3: min and max per group of the cube’s integer measures; only an index with cube_minmax (the default) 3.3 default (setting 7 or more), for an index with the option
8 3.3: the cube holds, for every date, timestamp and timestamptz column, the groups of its calendar cells as a dim, at the finest grain that fits (days, months or years; the directory leaf is grain * SIFT_PAGG_CAL plus the column); only a segment of a schema without JSON path leaves 3.3 default of sift_table and of sift_col (calendar_columns, default all)
9 3.3: a unit also holds the rollup of its rows by the scalar columns of rollup_columns (the element-rollup blob, leaf ncols); only an index with the option 3.3 default (sift.col_format_minor 9 or more), for an index with the option
10 3.3: the exact keys or bloom filter of the leaves of key_columns in a unit; only for an index with the option under sift.col_format_minor 10 or more 3.3 default (setting 10 or more), for an index with the option
11 3.3: the write buffer of a sift_table that holds a row on tail pages (table/table.h); a build that does not know it cannot write the table 3.3
12 3.3: the sidecar also holds, per group of units, the merged leaf sums and cube (a superunit summary); only for an index with superunit (the default is 16) 3.3 default (setting 12), for an index with the option
13 3.3: the sorted run of the leaves of order_columns in a unit; only for an index with the option 3.3 default (setting 13), for an index with the option
14 3.3: a string dictionary of 1,024 strings or more is stored in blocks of 64 strings that are read in place where that adds at most 3% to the segment, and with the codes in byte order too (form 2) for the columns of key_columns, point_columns and return_columns, with dict_lookup = on for every column, and in a sift_table with sift.table_dict_lookup = on; also the point directory of the leaves of point_columns at the end of the DICT section, only for an index with the option 3.3 default (setting 14), for a dictionary of that size that is stored in blocks or asks for the order, or an index with the option
15 3.3: the key list or bitmap of the leaves of key_columns in a unit; written by default for the int2, int4 and date foreign key columns and *_id columns that fit 3.3 default (setting 15)
16 3.3: the point directory of the leaves of point_tid_columns lists the heap addresses of the rows, not their numbers in the segment; only for an index with the option 3.3 default (setting 15), only for an index with the option (the option stamps it; the setting stays 15)
17 3.4: the units of the segment are cut by the range of the declared key (key_cut), not by superblock, and each lists its heap addresses; only for an index with the option 3.4 default (setting 15), only for an index with the option (the option stamps it; the setting stays 15)
18 3.4: the sorted runs of the segment also hold their heads, the first and last n / 128 (at most 32) keys of a leaf with no NULL or overflow value with the heap address of each row; not for a key-cut segment 3.4 default (setting 15), for an index with order_columns (the option stamps it; the setting stays 15)
19 3.4: a unit also holds the cube and the element rollups of its few rows where one NULL-heavy integer leaf is not NULL (the exceptions), so that a filter leaf IS NULL is answered from the pre-aggregates (COL-PREAGG.md section 11) 3.4 default (setting 15), for a sift_col index with a leaf NULL in 99% of the rows of a unit (the data stamps it; the setting stays 15)
20 3.4: the HyperLogLog sketch of the leaves of hll_columns in a unit; only for an index with the option 3.4 default (setting 15), only for an index with the option (the option stamps it; the setting stays 15)
21 3.4: the global order of the keys of a leaf in a segment; only for an index with order_array_columns 3.4 default (setting 15), only for an index with the option (the option stamps it; the setting stays 15)
22 3.5: the key table of a leaf of key_columns in a segment: its distinct keys with the rows, sums, minima and maxima of each; all key tables together take at most 3% of the segment bytes 3.5 default (setting 15, the largest), for an index with key_columns leaves and key_table on (the default; the option stamps it; a setting below 15 writes none), and for a sift_table with foreign key or *_id columns under sift.table_key_table on (the default)
23 3.5: a key list of some leaf in some unit is stored as runs of consecutive keys; only for an index with key_columns whose keys come in bursts 3.4 refuses it
24 3.5: the dictionary of a text leaf read in place also holds the rows of each string in byte order, in blocks of 64 places with the counts bit-packed; for a leaf of 1,024 strings or more with no inline string, unless count_columns is off 3.5 default (setting 15 or more; count_columns = 'off' or a smaller setting leaves it out)
25 3.6: the lookup dictionary (form 2 or 4, or the blocks of form 3 that no leaf asked to search) also holds a hash of its strings to their codes: an equality or IN test reads one slot and one block of strings in each segment, and an absent string decompresses nothing; for a dictionary of 1,024 strings or more written in the lookup form 3.6 default (setting 15 or more; a smaller setting leaves it out)
26 3.6: the leaf list of a range, inet or cidr column has the lanes of its containment operators after the image; written for every index with such a column, whatever the setting 3.5 and older refuse the index (“does not match its column layout”, REINDEX)
33 3.7: the tables of the point directories have ceil(keys * 4 / 3) slots, not a power of two, and a key starts at the slot its hash scales to; written under sift.col_format_minor 15 or more 3.6 and older refuse the segment (“Use a newer pg_sift, or REINDEX”); SET sift.col_format_minor = 14 and REINDEX write the power of two (sift.upgrade_check('3.6') says so)
41 4.0: the global order of a leaf in a segment may be a compact block (version 4 of the block of col/gorder.h): the heap address of every row and, for each entry, the bucket of its key (mini-blocks of 32 differences, bit-packed, col/gquant.h); the exact key is read from the table row. Written by order_layout auto (a chunk where it is at least a fifth smaller and has no run of 8 equal keys) or compact (bit 2 of the pad word marks a compact chunk with such a run), for a segment of more than 32,768 values; the first and last 8,192 entries and the NULL rows of the block stay whole. The block of the second order by group (order_array_group, version 2) may have compact chunks too, and is then version 6: the keys of each group start one bucket after the one before it, and the first key of every group after the first in the chunk is kept exact after the addresses (positions, then keys; the count is in bits 16 to 23 of the pad word, at most 255, else the chunk stays whole) 3.7 and older refuse the segment (“Use a newer pg_sift”)
42 4.0: the global order of a text leaf names the strings of its ranks by their dictionary codes (version 5 of the block of col/gorder.h: bits bits a rank in the section that ends the block) and keeps no copy of them, for a leaf whose dictionaries, added up over the segments of the index, take three quarters of the cache of parsed dictionaries or less and whose codes save a fifth of the bytes (the others keep the strings of version 3 or 4); the dictionary of the leaf is written in blocks when it has 1,024 strings or more, to be read in place by code 3.7 and older refuse the segment (“Use a newer pg_sift”)
43 4.0: the index has a tombstone log, a directory entry of kind SIFT_SEG_TOMB (a lane chain of the 32-byte entries of core/tomb.h: the heap address of an entry of the index that stopped being live, the transaction and command that said so), and the rows of its write buffer carry the transaction that inserted them; written only for an index with the reloption track_changes 3.7 and older refuse the index (“Use a newer pg_sift”)
44 4.3, the one minor of its new features, which a segment or directory entry is stamped with when it holds any of them (the lowest minor that describes what it holds: an index with none stays at 43 and 4.2 reads it): (1) the tombstone log of the index holds the key journal of a connected parent index: its header page has the journal record (lineage and trim, 16 bytes) and the log may hold records of kind KEYCHG (the key of an entry that an UPDATE, DELETE or key change ended, and the transaction), the format of the directory entry of the log, written when the first child index is connected; (2) the index of a connected child carries values of its parent tables as leaves after its own (flag SIFT_COLD_CARRIED: per connection a boolean leaf <fk>#found and the leaves <fk>.<column> the connect reloption names, filled from the parent index under a stamp), written only for an index with the reloption connect (docs/COL-CONNECT.md describes both); (3) the directory entry of a write buffer that holds records that are references to heap tuples (SIFT_COLR_REF, setting sift.col_wbuf_ref; the values are in the shared arena of the server and in the heap, docs/USAGE.md): the entry is marked before the first reference is written, and stays so until the buffer is promoted; the buffer is not a segment, so sift.col_segments has no format for it; (4) a chunk of a global order may be seekable (SIFT_CGORD_SEEK, bit 3 of the pad word of its directory entry in col/gorder.h: a fence key every 32 entries, so that a seek or a cursor decodes 32 entries and not 512), and the segment is stamped 44 when one is. Two more bits of the same words are read under this minor and are not minors of their own: SIFT_CGORD_POS (bit 4 of the pad word, a positional chunk of a grouped block: its entries are positions in the plain block of the leaf) and SIFT_CGORD_GRP_PACKED (bit 16 of word 7 of a grouped block: its table of groups is packed to the bits of a group’s distance from the first and of the start of its entries, for 1,024 groups or more and no NULL key); a chunk or block without them reads as before 4.2 and older refuse the index or the segment (“Use a newer pg_sift”, or the format error that names 1.44)

SIFT_COL_FORMAT_MIN_READ is 3. 3.0 reads only 3 and refuses 4 with a REINDEX hint; 3.2 reads 3 through 6, 3.3 3 through 16, 3.4 3 through 21, 3.5 3 through 24, 3.6 3 through 32, 3.7 3 through 39, 4.0 to 4.2 3 through 43, 4.3 3 through 44 (SIFT_COL_FORMAT_MAX_READ). A 3.1 library refuses minors 5 and 6, a 3.2 library minors 7 to 23, and a 3.4 library minors 22 and 23, with a format error and a REINDEX hint. Old segments remain readable; predicates needing unavailable kinds use the normal plan. REINDEX and a table VACUUM FULL rebuild from the original documents and restore complete kinds.

sift.col_format_minor accepts 3 to 15 (default 15; options with a newer layout stamp their own minor; 3.2 defaulted to 6); 5 is selected only by a wide schema. A lower setting limits what is written: 7 or less writes a sift_table without the month dims, 8 or less ignores rollup_columns, 9 or less the summaries of key_columns, 11 or less superunit, 12 or less order_columns, 13 or less the stored form of the dictionaries, 14 or less the key lists and bitmaps of key_columns, all of which are still read. Schemas without JSON paths stay at 4 (or 5 for wide leaves). Minor 6 guarantees complete JSON kinds, including element leaves; its chunk bytes are the minor-4 layout, and the new number distinguishes them from a minor-4 merge that lost the kinds of older inputs. New column write buffers carry format 6 in their directory entry; an older unmarked buffer is decoded with uncertainty for untagged NULL/astext slots, and promotion never labels those slots complete.

The default (15) allows every section, and a segment is stamped with the lowest minor that describes what it holds. A sift_col index created with cube_minmax = false, superunit = 0 and calendar_columns = 'off' stays at 4 or 6 and a 3.2 library reads it. With the defaults a 3.3-built index is no longer readable by a 3.2 library (it carries minors 7 and 12 at least), nor is a sift_table with a date, timestamp or timestamptz column (8), an index with rollup_columns, key_columns or order_columns, or an index with a dictionary of 1,024 strings or more that is stored for a lookup (14, not the default). The 3.2 library refuses it with the REINDEX hint unless sift.col_format_minor was lowered to 6 before it was written. UPGRADING.md section 4 lists the setting that keeps each minor and the sequence that takes a 3.3 database back to a 3.2 library.

A sift_table follows sift.col_format_minor too, except that a group with a version section (unfrozen rows) is at least SIFT_COL_FORMAT_VERS (4). Minors 0 to 2 were never released. A sift_col index goes back to 3.0.x by REINDEX there; a sift_table, which cannot be reindexed, stays readable by 3.0.x (a standby on 3.0.x included) when sift.col_format_minor = 3 (superuser) is set before its first write or before an ALTER TABLE ... SET ACCESS METHOD rewrite. pg_upgrade copies the files as they are. The chunk flags are SIFT_COLC_NULLS 0x1, SIFT_COLC_OVF 0x2, SIFT_COLC_TAGS 0x4, SIFT_COLC_KINDS 0x8 (src/col/enc.h).

5. Segment entry flags (SiftSegEntry.flags)

flag value meaning
SIFT_SEG_DIRTY 0x0001 some liveness bit cleared
SIFT_SEG_POSITIONS 0x0002 written with word positions
SIFT_TBL_SEG_WBUF 0x0100 sift_table write buffer
SIFT_TBL_SEG_TOMB 0x0200 sift_table tombstone segment
SIFT_SEG_ROOTS 0x0004 column segment whose documents were shredded with a string root stored as the overflow of every column below it (below)
SIFT_SEG_VERS 0x0400 column segment with unfrozen rows (reserved is the smallest xid); cleared when the rows are frozen
SIFT_SEG_NET 0x2000 column segment with the pre-aggregates of its dirty units net of their dead rows, in whole pages at the end of the stream (below)
  • SiftSegEntry.sum_dl of a sift_col write buffer is the mask of leaves holding a JSON null; 3.2 only.
  • SiftSegEntry.reserved is the owner’s tag for an immutable sift_col segment and the smallest xid when SIFT_SEG_VERS is set.
  • SIFT_SEG_ROOTS (4.2) needs no column format minor either (a segment entry flag, as SIFT_SEG_NET and SIFT_SEG_LSTATS). The segment’s documents were shredded with a document that is a JSON string stored as the overflow of every column declared below it (shape, JSON type none), as a document that is an array always was; before, such a document left every column absent, which is what a missing key leaves, so no read could tell '"k"'::jsonb ? 'k' from '{}'::jsonb ? 'k'. The bytes are the same, so a build that does not know the flag reads the segment as before (a string document is a missing key, the overflow stays a value its reads give as NULL), and a merge or rewrite by it drops the flag. A merge keeps the flag only when every segment it reads has it; a write buffer (lane) carries it from the first row. The segments written before have no flag: a read that needs it (doc ? 'k') reads all their NULL slots from the heap, and VACUUM sets the flag on every unflagged segment when it finds no version of any row, dead or alive, whose document in a jsonb column of the index is a string (src/col/maint/roots.c; the entries are the only thing it writes).
  • SIFT_SEG_NET (4.0) needs no column format minor, as the leaf statistics (SIFT_SEG_LSTATS) needed none: a build that does not know the flag lists the pages in the header’s extents like any others and never looks in them, so it reads the segment as written and a rewrite or merge by it drops the sidecar with the segment. The sidecar starts at a page boundary after the segment’s own stream (and its leaf statistics); the last 16 bytes of the stream are {magic 0x5445474e, offset of the sidecar}. The sidecar is NetHeader, NetUnit[nsb] (the dead rows the unit had when it was made, the lengths of its cube and rollup blobs), NetAgg[ncols][nsb] (the zone and exact sums of each leaf over the live rows) and the blobs, the bytes sift_cpagg_cube writes for the live rows with the dims, rollups and measures of the unit’s own blobs (src/col/seg/net.c). VACUUM writes it (src/col/maint/net.c): the segment keeps its generation and its header page is written again, as a relocation does, with the extents of the stream and those of the new sidecar; the old header page and the old sidecar are released together with the directory switch. A reader uses the unit’s net blobs when the unit has exactly the number of dead rows they were made for (liveness bits are only cleared), else it reads the unit as before.
  • The mirror (4.3) needs no column format minor and no flag: the header page of a segment holds, after its extents, a copy of the small ranges of the stream that a plan and the first read of the segment open (the schema, the unit directory, the point directories, the first bytes of each order block, the zone directory, the headers of the pre-aggregates and of the sets, and, when they all fit, the zone arrays of the leaves), so that they cost no pages of their own. The block is {magic 0x3152524d, nranges, len, sum}, nranges of {stream offset, length, offset in the block} and the bytes, at most SEG_MIRROR_BYTES (6144) of the page. It is a function of the stream bytes alone: the writer takes the ranges as it writes them, and sift.col_verify compares the sum and every range with the stream. A reader that does not know it never looks past the extents and reads the stream; a header page without the magic (a segment written before, a block that did not fit, a trailer a relocation moved) is read from the stream as before, and a rewrite or merge by a build that does not know it writes a segment without it. A reader refuses a block whose sum, length or ranges are damaged when the segment is opened or first read from it (corruption error), and a stream that differs from its mirror at sift.col_verify.
  • A group written by 3.0.1 under pressure with a tag but no version section is read as a constant version vector.

Zone flags: SIFT_COLZ_NOSUM 0x1, SIFT_COLZ_NAN 0x2, SIFT_COLZ_CONST 0x4, SIFT_COLZ_OVERFLOW 0x8, SIFT_COLZ_INLINE 0x10, SIFT_COLZ_JNULL 0x20 (3.2, segment format 6: a NULL slot of the leaf is a JSON null; informational, a segment written before the flag does not have it and is read as one that may).

6. Upgrade tests

what test
BM25 files of 2.x and 3.0 read and maintained by 3.1 test/t/compat_2x_fixture.sh, test/t/compat_30_fixture.sh
every 3.1 object after CREATE EXTENSION and after ALTER EXTENSION .. UPDATE from 3.0; a sift_col index and a sift_table written by 3.0 (column minor 3) read across the update test/t/extension_lifecycle.sh
an older library refuses what it cannot read, with the REINDEX or VACUUM FULL hint test/t/old_lib_refusal.sh
real 3.0/3.1 write buffers, promotion, minor-6 REINDEX and 3.1 refusal test/t/compat_31_column.sh
the releases 3.0.2, 3.1.0 and 3.2.0 write, this tree takes over (update, verify, REINDEX, writes), and the release reads what this tree writes at the lowest minor, its newest and 4, and with the default options off, and refuses every minor above (7 to 15, and an index at the defaults) and the calendar sift_table; 3.2.0 gets the downgrade of UPGRADING.md section 4 end to end test/t/compat_matrix.sh
the stored unit, chunk (flags, tags, kinds) and leaf list (wide lanes, type tags) of a segment cut and damaged byte by byte are refused with a corruption error or still sound; the cube with min and max (minor 7) test/sql/col_damage.sql, test/sql/col_preagg_minmax.sql
a kill before and after each directory update of a build, promotion, merge, VACUUM, table sealing and the promotion worker, with minor 7 and generic WAL page checks test/t/col_crash_matrix.sh
mixed minors ¾/5/6, partition parents, table rewrite and JSON kinds test/sql/agg_jsonpath_kinds.sql
a 3.2 index with wide leaves (minor 5) beside the older minors, merges and REINDEX test/sql/col_format5.sql
scripts/upgrade-check.sh reports the formats of every index and table, and what a given release could not read (--to) test/t/upgrade_check.sh
standby and crash recovery of the new structures test/t/col_index_replica.sh, col_index_crash.sh, store_replica.sh, store_crash.sh, 014_tbl_writepath.pl