Secondary indexes

How a KDBS secondary index stays complete for every value, why it only appends, and how the engine chooses it.

A secondary index in KDBS is an ordered map from one or more non-key columns to the row’s primary key. It covers every row and is updated on every write, so it can answer any value of its key, including an authoritative “no rows”. It is a read accelerator only: it never adds a rule that can make a write fail for a reason of its own, which is why UNIQUE indexes are refused.

The idea

An index is “a Cabin that observed everything”. A Cabin is complete only for the values queries have asked for. An index is complete for every value, because every write maintains it. Both keep a superset of the matching rows and remove the surplus when a query reads them.

CREATE INDEX ix_passenger_name ON passengers(name) COVERING (member);

How it works

What an entry holds

Each entry holds the key columns, any COVERING columns, and the row’s primary key. It holds no page address, so moving a row never invalidates an index.

A string key column stores only a fixed prefix of its value (32 bytes in this release, a proposed value). An equality on a prefix can match extra rows but never miss one. Every read re-checks the predicate against the real row, so the prefix costs precision, never correctness.

Maintenance only appends

Write	What happens to the index
`INSERT`	One entry is appended per index on the table.
`UPDATE` that changes a key or covered column	A new entry is appended. The old entry stays.
`UPDATE` that touches no key or covered column	Nothing.
`DELETE`	Nothing.

Old entries stay because an older snapshot may still need them to find its version of the row. A reader resolves each entry to the row version its snapshot sees, checks visibility, and re-checks the key. An entry that no longer matches is skipped.

If appending an index entry fails, the statement fails. An index that is missing an entry gives wrong answers, not slow ones. On disk, the index record is written to the log before the row record it describes, so a crash can leave an extra entry, which reads skip, but never a row without its entry.

Reading

WHERE name = 'Park Jiho' AND member = 1
        |
   IndexProbe on ix_passenger_name: walk entries for 'Park Jiho'
        |
   member is covered -> test "member = 1" on the entry
        |                     fails -> drop it, no table read (index_filtered)
        |                     passes or cannot tell -> keep
   sort the kept primary keys into primary-key order
        |
   read each row: check visibility, re-check every predicate, emit

Two access kinds. IndexProbe is an equality on a prefix of the key columns. IndexRange is an equality prefix plus a range on the next key column, or a range on the first one.
Rows come back in primary-key order, the same order a scan returns. Creating an index never reorders a query’s reply.
Covering columns save table reads for rows that will be filtered out. A predicate on a covered column is tested on the entry, and a row that fails it is never read from the table. A row that is returned is always read from the table, because visibility is decided only from the row itself. There is no index-only scan, and even COUNT(*) reads the rows.
Joins can use an index. When the leading key column is bound by equality to a column of an earlier step, such as ON t.passenger_id = p.id with passengers AS p read first, the index is probed once per outer row. Both columns must have exactly the same type.

Which structure the engine picks

For a WHERE column = value on a non-key column, the engine uses an index first, then a Cabin, then a filtered scan, in that fixed order. Among indexes it takes the one matching the longest usable prefix of the statement’s equalities, and on a tie the oldest one. The choice depends on the statement and the catalog, never on data statistics. A statement’s plan therefore never changes as the table grows (see Statements and execution plans).

The price is that KDBS cannot skip its own index on a small table. Measured on an earlier engine (the bench/ tree at commit 1769487), a range over 200 rows ran 11% slower with an index than without one, while a selective equality over 10,000 rows ran 9.7 times faster.

Building over existing rows

CREATE INDEX on a populated table walks every row and adds an entry for each distinct key value across the row’s older versions too, so a reader with an older snapshot finds its version. The catalog row is published only after the build ends. An index is therefore complete or absent, never partial.

Example

Run against the sample tables. The sample already has the index ix_tickets_passenger; the example adds a second one:

kdbs> CREATE INDEX ix_passenger_name ON passengers(name) COVERING (member)
CREATED INDEX name=ix_passenger_name on=passengers index_oid=2 root_page=145 key_width=33 entry_width=42 entries=0
kdbs> SHOW INDEXES
indexes=2
index_oid=1 name=ix_tickets_passenger rel=tickets keys=(passenger_id) covering=(flight_id,baggage_kg) root_page=142 key_width=9 entry_width=33 height=1 entries=9
index_oid=2 name=ix_passenger_name rel=passengers keys=(name) covering=(member) root_page=145 key_width=33 entry_width=42 height=1 entries=8
kdbs> ANALYZE SELECT * FROM passengers WHERE name = 'Park Jiho' AND member = 1
analyze rows=0 class=JoinSelect steps=1 examined=0 pages=1 opens=1 pattern_id=0x33bf2b0d86d56353 fetch_id=0xf78f0ea975a4a9ba
class=JoinSelect steps=1 hoisted=0
step 0 IndexProbe passengers
  filter 0:0.1 = 'Park Jiho'
  filter 0:0.2 = 1
project * (4 column(s) of step 0)
step 0 IndexProbe passengers opens=1 examined=0 matched=0 pages=1 index_scanned=1 index_filtered=1

Park Jiho is not a member (member is 0), so the covered member column ruled the row out on the entry (index_filtered=1) and the table was not read (examined=0).

What it guarantees

On the trust ladder, a secondary index is authoritative with full coverage, one rung below the primary-key tree:

Structure	Authoritative for	Maintained on
Primary-key B+ tree	every key	every write
Secondary index	every key value	every write
Cabin	values queries have observed	every write, for observed values
Waystone trail	nothing (advisory)	nothing

An index that finds no entries is an authoritative “no rows” without opening the table. A trail may never replace an index step, because an index returns a set and a trail cannot prove a set is complete.

What it costs

One appended entry per index for every INSERT, and for every UPDATE that changes a key or covered column. COVERING columns widen every entry.
Superseded entries are never reclaimed. Each costs space and a skipped read.
CREATE INDEX and DROP INDEX take an exclusive lock on the table. They wait for open writes and running reads of it, and block new writes until they finish. A wait that reaches the lock fault net (lock_wait_fault_net_ms, default 1 s) is refused with the retryable TXN_CONFLICT. Both are transactional: ROLLBACK undoes them.

How to observe it

SHOW INDEXES: key and covered columns in declared order, plus height and entries walked from the tree (- if the tree cannot be read).
ANALYZE <select>: the step kind (IndexProbe or IndexRange) and per-step counters such as index_scanned, index_resolved and index_filtered. If index_filtered stays at zero, a COVERING clause has bought only its write cost.
SHOW ACCESS: IndexProbe and IndexRange shapes per table and column.

Configuration

Key	Default	Effect
`indexes`	`on`	A read-path switch. `off` makes an index step take the walk it would take without the index. The compiled plan stays the same, so `ANALYZE` still shows `IndexProbe`.

There is no switch for index maintenance, because an unmaintained index gives wrong answers. To remove the write cost, use DROP INDEX.

Limitations

CREATE UNIQUE INDEX is refused (NOT_IMPLEMENTED). Use the primary key or an assertion for uniqueness rules.
At most 4 key columns and 8 covered columns. Over the cap is refused, never truncated.
Key and covered columns cannot be nullable. IS NULL is answered by a scan.
No index on the primary key; the clustered tree already is one.
No expression, partial or descending indexes.
ORDER BY is never served from an index; a sort step stays.
Only BTREE tables can carry an index. Every new table is one.
An index name is unique across the instance.
An index beats a Cabin on the same column. CREATE INDEX does not drop the Cabin; it is no longer probed, and DROP CABIN frees its memory.
Known defect: inserting, rolling back and re-inserting one key about 600 times with the same indexed value and a new covered value can be refused AlreadyExists by a covering index, and TXN_CONFLICT after that.