System Design - How TiDB Transactionally Backfills an Index

Table of contents

The new index has two kinds of rows to catch up

Suppose a customers table already has ten million rows and we run:

ALTER TABLE customers ADD INDEX idx_email (email);

TiDB has two jobs. New inserts and updates must start maintaining the index while the DDL runs. The older rows need index entries too. If TiDB switched query plans to the new index before those older entries existed, a lookup could miss customers.

This post follows one specific route through the TiDB source: the transactional backfill used when fast reorganization is disabled. Fast reorganization has a separate ingest-based implementation, so its sorted-file pipeline is outside this walkthrough. The source links below pin TiDB to commit 41efd866 and TiKV to commit 96033a26 so the code locations remain reproducible.

The state machine makes writes safe before reads

The DDL worker advances the index through schema states. In the code path for adding an index, it moves from DeleteOnly to WriteOnly, then to WriteReorganization, and finally to Public after the reorganization work is complete.

While the index is WriteOnly, TiDB can maintain it for new or changed rows, while query planning waits to rely on it. The table mutation path iterates writable indexes, and its IsIndexWritable helper includes WriteOnly; the lookup helper FindIndexByColName only returns a Public index. In WriteReorganization, the background DDL work fills entries for rows that were already present. Once that work finishes, the index can become public to queries.

                    DDL worker
                       |
                       v
     DeleteOnly -> WriteOnly -> WriteReorganization -> Public
                       |               |
                       |               +-- backfill old rows
                       +-- DML writes maintain the new index

WriteOnly: new writes can populate the index; reads do not depend on it yet.
WriteReorganization: a worker scans older rows and fills missing entries.
Public: the optimizer may use the complete index.

The transitions in worker.addIndex make the ordering visible in code. They separate the user-visible schema change from the slower task of catching up existing data.

Four pieces divide the work

The worker owns the DDL state machine and dispatches the reorganization. writePhysicalTableRecord divides the table’s key ranges into tasks. A txnBackfillExecutor runs a pool of workers, and each addIndexTxnWorker handles one task by reading rows, making index records, and writing a batch in a KV transaction.

TiDB DDL worker
      |
      | index reaches WriteReorganization
      v
writePhysicalTableRecord
      |
      | key-range tasks
      v
txnBackfillExecutor  <---- worker count from DDL metadata
      |
      +---- task channel ----> addIndexTxnWorker
      |                          |
      |                          +-- snapshot scan + row decoder
      |                          +-- unique-key check
      |                          +-- lock keys + create index records
      |                          |
      |                          v
      |                     kv.RunInNewTxn
      |                          |
      |                          v
      +---- results <-------- TiKV transaction path
               next key, row counts, errors

These names correspond to a small part of pkg/ddl. The executor creates workers from the concurrency stored in the DDL job metadata and starts one addIndexTxnWorker for each slot. This transactional executor caps its local pool at 16 workers. It sends tasks through a channel and receives results through another, so the scheduler can track range progress without making one goroutine scan the entire table.

A worker turns a bounded row batch into index keys

For each task, addIndexTxnWorker.BackfillData opens a new KV transaction. baseIndexWorker.fetchRowColVals walks the task’s record-key range at that transaction’s start timestamp. It decodes each row, evaluates the columns needed by the index, and creates an indexRecord containing the indexed values, row handle, and source record key.

If idx_email is unique, the worker checks the generated keys before writing them. An existing unique key that belongs to a different row is a real duplicate and makes the index build fail. If the same row’s entry already exists, the worker can skip it. That can happen because normal DML has already maintained the hidden index while the DDL was catching up.

The worker then locks each index key and calls table.Index.Create inside the same transaction. The transaction commits the batch together, or returns an error for the DDL job to handle. The nextKey returned by the scan marks where the task should continue after this batch; an empty result means the range is done.

One task range [startKey, endKey)
       |
       v
read rows visible at txn.StartTS
       |
       v
decode row -> evaluate email -> form (email, handle) key
       |
       +-- unique collision with another handle? return error
       |
       +-- key already exists for same row? skip it
       |
       v
lock missing index key -> create it in the same KV transaction
       |
       v
commit batch and return nextKey / done / counts

There is an important concurrency detail here. The worker does not copy the entire table into memory and add keys afterward. It processes a bounded batch, records its snapshot timestamp, and writes through the storage transaction API. TiKV’s Prewriter::process_write applies MVCC checks to mutations during the prewrite phase. That is the storage-side transaction machinery beneath the TiDB DDL code; it is not a special index-building protocol.

How to read this path in the source

Start at worker.addIndex to see when a range job is launched. Then follow writePhysicalTableRecord into newTxnBackfillExecutor. Its adjustWorkerSize creates addIndexTxnWorker instances. The worker’s BackfillData calls fetchRowColVals, checks unique keys, and writes each new entry with Index.Create.

The transactional path is selected by pickBackfillType when the DDL job’s IsFastReorg flag is false. When fast reorganization is enabled and the Lightning ingest environment is ready, TiDB can choose an ingest path instead; if that environment is unavailable, the code can fall back to a transaction-merge path. These modes share the goal of filling the index but use different machinery.

Three settings shape the workload

The stable system-variable reference documents these current defaults. Check the reference for the version and deployment you run; managed TiDB offerings may restrict some settings.

The two worker settings are related: a larger batch with more workers can send more index writes to TiKV at once. For the transactional mode, the system-variable documentation specifically warns that larger batches can increase conflicts when application updates touch the indexed columns. For fast reorganization, larger batches may improve speed while adding write pressure.

References

1. TiDB source, worker.addIndex state transitions and backfill dispatch.
2. TiDB source, TableCommon.updateRecord writing writable indexes, IsIndexWritable, and public-only index lookup.
3. TiDB source, pickBackfillType and mode selection.
4. TiDB source, writePhysicalTableRecord and range-task dispatch.
5. TiDB source, txnBackfillExecutor worker creation and worker sizing, including the 16-worker cap.
6. TiDB source, fetchRowColVals, uniqueness checks, and BackfillData and addIndexTxnWorker.BackfillData.
7. TiKV source, Prewriter::process_write — MVCC validation during transaction prewrite.
8. TiDB documentation, System variables — tidb_ddl_enable_fast_reorg, tidb_ddl_reorg_worker_cnt, and tidb_ddl_reorg_batch_size.
9. PingCAP Engineering, In-Depth Analysis of TiDB DDL Framework Optimizations — background on DDL scheduling and the move toward distributed execution.
10. TiDB documentation, DDL introduction — overview of TiDB DDL behavior.