The full-text index that survives updates

The text index model

UpdatableDiskValues reads and rewrites the complete ID list of every key it touches. For a text index that is one key per node and the lists are short unless the value is frequent.

Why it breaks for full-text

Every node has many tokens, and the common ones have lists proportional to the database. A single edit would cost the sum of those lists.

What every engine does instead

Immutable segments, deletion marks and merging: Lucene and everything built on it, SQLite FTS5, InnoDB, Oracle Text. BaseX already had the machinery, because FTBuilder writes partial indexes when memory runs out and merges them at the end.

One key decides everything

FTXSEGS present means numbered segments, node IDs mapped through data.pre(id), an updatable index and storage version 13.0. Absent means the 12.0 layout, PRE values, OLDSTORAGE, and the first update invalidates the index as before.

No legacy read path

A 12.0 database opened with UPDINDEX simply carries a non-updatable index until the next OPTIMIZE rebuilds it segmented. Databases without UPDINDEX stay byte-identical (pinned by IndexFormatTest).

Supersede sets stay sparse

File s lists the units this segment re-indexed or excluded. Deleted units need no mark: IdPreMap.pre returns −1 for them.

The rule

A reference for unit i in segment s is live iff pre(i) ≠ −1 and no segment newer than s, the buffer included, supersedes i.

The derived union

FTSegment.newer is the union of the supersede sets of all newer segments and of the buffer. It is recomputed from the files at open and after every merge; a put adds its ID to the union of every existing segment.

Consequences

• A unit's references never straddle two segments, so exactly one holder is live.
• Sets hold one int per unit changed since the last full merge: sparse by construction.
• Deleted references are purged lazily, when their segment is merged.

One operation

put(id, tokens, positions) bumps the ID's generation, appends the triples under it, and writes a log record. An empty token list records an exclusion (a rename out of the included names).

Why no removal

An editor saving the same document repeatedly, or many changes below one included element, re-puts the same units. Filtering by generation at query time and at segment write costs nothing; a forward map and deletion would.

Bounded by the threshold

The count of references appended since the last segment write is checked after every unit. Past 1 million (SPLITSIZE × 1 000 000), the buffer becomes segment n, the log is deleted, and the count restarts. This bounds memory, the log and its replay.

What the hooks record

Failure handling

If the lexer cannot be built or an I/O error hits the log, a segment or a merge, the index is dropped and ftindex cleared. An update never fails because of the full-text index.

Mechanism

FTBuilder.merge(inputs, output, live) is the same k-way merge that joins the builder's partial files, with one predicate per input: pre(id) ≠ −1 and id ∉ newer(input). Tokens whose references all died are skipped; surviving references are sorted by ID and position.

Policy

• After a segment write, if more than 8 segments exist: merge those below 1/8 of the total size. A transaction never rewrites the base.
• OPTIMIZE and db:optimize: write the buffer, merge everything into one segment. 22 s for the 568 MB XMark index.
• AUTOOPTIMIZE: the same, but only when superseded units exceed 10 % of lastid.

Merges run inside finishUpdate under the write lock; a background merger would change the locking model. Inputs are deleted as soon as the output is open.

Unchanged contract

Callers still receive PRE values grouped with their match positions. The 12.0 path with a single unnumbered segment goes through the same code with the ID mapping switched off.

Upper bounds, by design

costs, size and the counts of ft:tokens and INFO INDEX sum the segments' entries. Superseded and deleted references are counted until the next merge; a token present in several segments appears once, because entries is a k-way merge of the per-segment iterators by (length, token).

Measured

On XMark 1 GB with 712 buffered references, ft:search for will took 156 ms warm, the same as before the change; fuzzy 265 ms.

Reused, not rewritten

• FTBuilder gained a range build and a static merge with liveness predicates; its partial-file splitting is the builder route for a 1 GB insert.
• FTSegmentWriter extracts the x/y/z writing that writeIndex and the old merge each had inline.
• ValueIndex hooks were unified beforehand, so Data has no full-text branches.

Two small API changes

ValueIndex.optimize(boolean auto) distinguishes AUTOOPTIMIZE from an explicit optimize; IndexBuilder.splitFactor(type) is public so the threshold shares the builder's constant.

Opening databases

Crash consistency

Equal to the other UPDINDEX structures: segments, log and meta data are written in finishUpdate after the table. Unlisted files are removed at open; an incomplete log record is truncated on replay.

Documented costs

• Under FTMIXED, an update below an included element re-lexes that element. Including a document element means re-indexing the document on every change; include leaf elements instead.
• Counts are upper bounds until the next merge.
• Deletions alone never trigger an automatic merge; the flush policy purges them when small segments are merged.
• A missing external stop-word file at update time drops the index instead of failing the update.

Not measured yet

FTMIXED at the 1 GB scale, and query latency at 4 and 8 segments on a large database. Both are exercised functionally by FTIndexUpdateTest with a lowered threshold.