Warning

This is not authoritative documentation. It describes a plan of work that is not yet implemented and will change as it lands.

Task 6: secondary indexes, unique and non-unique

Repo: https://opendev.org/drizzle/drizzle. Depends on task 5 (index maintenance must be transactional from the first commit).

Layout, from the spec — two shapes, selected by uniqueness, because the selection is a concurrency-control decision rather than a space one:

  • Non-unique: key = 0x01 || table-id || index-id || encoded-index-cols || encoded-pk, value = empty. The PK suffix is what keeps equal-valued rows distinct.

  • Unique, no NULL in the index columns: key = 0x01 || table-id || index-id || encoded-index-cols — no PK suffix — value = encoded-pk.

  • Unique, any NULL part: the non-unique shape. SQL permits many NULLs in a UNIQUE index; distinct physical keys are how that permission is expressed.

The encoded PK is consumed as verbatim bytes for the primary point-read — no decode — taken from the value in the unique case and from the key suffix in the other two. Key structure is parseable without decoding values (nullability prefix bytes, fixed widths, the 0x00 0x00 string terminator from task 2), which is what lets a reader find the suffix boundary and lets the encoder test a key for NULL parts.

Why the unique shape drops the PK suffix. Per the spec’s “What the conflict detector actually sees”: under IsolationLevel::Snapshot SlateDB tracks only the write set, so a probe that finds nothing confers no protection whatsoever. With a PK suffix, two sessions inserting the same unique value with different primary keys write two different physical keys — both probe-miss, both commit, and the UNIQUE constraint is silently violated. That is WiredTiger Tier 0.3 reappearing in a new engine, which is the exact outcome this task exists to prevent. Without the suffix they write the same physical key and SlateDB’s write-write check rejects one of them. NULL-bearing entries keep the suffix precisely because they must not collide.

Write-side maintenance

All inside the statement transaction, so index and row are atomic:

  • doInsertRecord: after the PK dup probe, for each UNIQUE secondary whose index columns are all non-NULL, a point ``get`` on the exact unique key — no bounded scan any more, the key is exact — hit → HA_ERR_FOUND_DUPP_KEY with the correct key number (WiredTiger Tier 0.3’s silent non-enforcement is the anti-pattern); then put all index entries. A unique index with a NULL part is not probed at all: by definition it cannot collide.

  • The probe is an optimization, not the enforcement. Enforcement is the shared physical key at commit time. Two concurrent inserters of the same unique value therefore both probe-miss and the loser gets CONFLICT → HA_ERR_LOCK_DEADLOCK instead of HA_ERR_FOUND_DUPP_KEY; the spec accepts that as correct and retryable, and the concurrency tests below assert it rather than treating it as a flake to be quieted.

  • doUpdateRecord / doDeleteRecord: compute old entries from the old row image, new from the new; delete/insert the differences; unique probes on changed unique keys. A unique key that changes between NULL-bearing and non-NULL-bearing changes the entry’s shape, so such an update is always delete-old + insert-new and never an in-place value rewrite; the codec exposes the NULL-part predicate and the update path calls it rather than open-coding the test. NULL semantics: multiple NULLs are permitted in UNIQUE indexes (SQL standard and server expectation — assert against a MyISAM/innobase baseline test).

Read side

doStartIndexScan(idx>0) scans the index prefix; each hit yields an encoded PK — read from the entry’s value for a non-NULL unique entry, sliced from the key suffix otherwise — and point-reads the primary entry inside the same transaction and decodes it. The find-flag state machine from task 4 is reused unchanged — it operates on encoded prefixes and does not care which index id follows the table id. Updates and deletes during a secondary-driven scan write via primary keys taken from the index entries, never via the scan (Tier 0.5 remains structurally excluded).

records_in_range extends to secondary indexes with the same capped probe.

Covering-index reads stay refused (HA_KEYREAD_ONLY unset) — keys are strnxfrm-encoded and never decoded, per the spec.

Commit boundary

Three commits: index maintenance on the write path (+ tests proving atomicity under rollback); index read path (+ find-flag tests against a secondary, including a descending composite key with NULLs); unique enforcement (+ dup tests, NULL-multiplicity tests, IODKU-via-unique tests with distinct insert/update values, and the two-session concurrency tests below — they are the reason the layout has two shapes, so they land with the enforcement, not after it).

Verification

  • drizzle-test green including: UPDATE that changes indexed columns mid-secondary-scan (the Halloween-shaped case), DELETE via secondary-index plan, unique violations reporting the right key name, ROLLBACK removing index entries, and an UPDATE that moves a unique key between the NULL-bearing and non-NULL shapes in both directions.

  • Two-session unique concurrency test (named deliverable, because it is the test the layout exists to pass): sessions A and B each BEGIN and each INSERT a row carrying the same unique secondary value with different primary keys, then both COMMIT. Assert exactly one commit succeeds; the loser returns the deadlock-mapped error and its row is absent. Retry the loser and assert it now reports HA_ERR_FOUND_DUPP_KEY — the uncontended path — and that the table still holds exactly one row. Sanity requirement on the test itself: it must fail against a deliberately PK-suffixed unique layout. If it passes there, the test is wrong and gets fixed before the code is trusted.

  • Multiple-NULL concurrency test: two sessions concurrently insert rows whose unique index columns are NULL, with different primary keys. Assert both commit and both rows are present — NULL entries must never share a physical key. Plus the single-session form: N rows with NULL unique columns all insert, and an index scan returns all N ordered by PK within the NULL group.

  • Composite unique index with one NULL part: the same contended and uncontended pair, since this is the case an “all columns NULL” shortcut gets wrong.

  • Primary-key duplicate under concurrency: two sessions insert the same PK; exactly one commits, the loser sees the deadlock mapping, and a retry sees HA_ERR_FOUND_DUPP_KEY. Asserted as documented behavior per the spec, not filed as a bug.

  • storage_engine_api_tester re-run.

  • Perf suite: point lookup via secondary vs primary, measured and recorded in metrics.json (two object-store-logical reads vs one is the expected shape; the block cache should collapse most of it — verify, don’t assume). Record unique and non-unique separately: the unique path is now a point get plus a point get, the non-unique path a range scan plus a point get per hit.