Collection metadata pages grow with every save and are never reclaimed: int/long auto-increment inserts slow down linearly #195

Version: main at cb8a521, .NET 10, macOS arm64. The code path is platform-independent.

What happens

Every SaveCollectionMetadata call grows the chain of collection metadata pages (page 1 and its overflow pages), and nothing ever shrinks it. Every metadata read or write walks the whole chain from page 1, so each such operation gets linearly slower over the life of the database.

The most frequent writer is StorageEngine.GetNextSequence: one read and one save of the collection's metadata for every insert into an int/long-keyed collection whose id is left at 0 (DocumentCollection.cs ~L2152-2160). Time-series pruning, index creation and drops, root page changes and so on also save metadata, but much less often.

Measurements

Fresh database with 8 collections, GetNextSequence on one of them, page size 16 KB:

The file grew from 3 MB to 6 MB over the same run, all of it metadata pages.

Typed inserts into TestDbContext.Products (int id, left at 0, so one metadata save per insert):

The total cost is quadratic in the number of inserts. Neither a reopen nor VacuumAsync(new VacuumOptions { RebuildIndexes = true }) reclaims anything: after 20,000 saves, a vacuum and a reopen, the chain still has 46 pages with 1 live record and 20,001 deleted slots.

Cause

StorageEngine.SaveCollectionMetadata (StorageEngine.Collections.cs):

• It marks the old slot Deleted and writes the new record into the first page whose AvailableFreeSpace is large enough, or into a new page appended to the chain.
• The bytes and slot entries of deleted records are never reused, because FreeSpaceEnd only moves down. So every save permanently consumes one record's worth of space plus one slot entry, and about every 430 saves add a page.
• GetCollectionMetadata, SaveCollectionMetadata, DeleteCollectionMetadata and GetAllCollectionsMetadata all walk the entire chain, deleted slots included.

Possible fixes

1. Rewrite in place when the new record is no larger than the stored one. A sequence update only changes the fixed-size Int64 SequenceValue, so its record has the same length every time. This alone removes the growth for the insert path.
2. Compact a page before giving up on it. When a page lacks room, move its live records together and drop the deleted slots before moving on to the next page or appending one. The slotted-page layout allows this, and records are located by name, not by slot index.
3. Let VACUUM compact the metadata chain and free the pages that become empty, to repair databases that have already grown.

(1) plus (2) would keep the chain at about one page per page-full of live records. Separately, GetNextSequence could reserve ids in blocks so it saves less often, but that changes what happens to the counter after a crash, so it is a separate decision.

Noticed while measuring the save path for #194.