Index Maintenance

The three lessons so far treated the index as a pure gain and measured its cost only by the space it occupied at the moment it was built. That moment is the smallest amount of space an index occupies over its lifetime.

The bloat measured for a table in the Dead Row Cleanup lesson also happens to indexes, and for two reasons it is more stubborn there. When a row is deleted, that row’s entry in every index dies with it. When a column is updated, that column’s index entry does not stay in place — it is deleted from its old position and written at a new one, so a single update does two jobs inside the index. This lesson measures the trace those two jobs leave and tells apart what each maintenance tool actually recovers.

Measuring the Bloat

The run below follows five stages on library loan records with the same measurements: row count, the table’s page count, the page count of each of two indexes separately, the database’s total page count, and the file size.

rm -f maintenance.db
cat > setup.sql <<'SQL'
CREATE TABLE member (
  member_id         INTEGER PRIMARY KEY,
  name              TEXT NOT NULL,
  city              TEXT NOT NULL,
  registration_date TEXT NOT NULL
);
CREATE TABLE loan (
  loan_id      INTEGER PRIMARY KEY,
  book_id      INTEGER NOT NULL,
  member_id    INTEGER NOT NULL,
  pickup_date  TEXT NOT NULL,
  return_date  TEXT
);
INSERT INTO member (member_id, name, city, registration_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000)
SELECT n, 'Member ' || n,
       CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir'
                  WHEN 3 THEN 'Bursa' ELSE 'Konya' END,
       date('2015-01-01', '+' || (n % 3200) || ' days')
FROM counter;
INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000)
SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000),
       date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'),
       CASE WHEN n % 9 = 0 THEN NULL
            ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END
FROM counter;
SQL
sqlite3 maintenance.db < setup.sql

cat > measure.sql <<'EOF'
SELECT (SELECT count(*) FROM loan) AS rows_,
       (SELECT count(*) FROM dbstat WHERE name='loan') AS loan_table,
       (SELECT count(*) FROM dbstat WHERE name='loan_member') AS member_index,
       (SELECT count(*) FROM dbstat WHERE name='loan_pickup') AS pickup_index,
       (SELECT page_count FROM pragma_page_count) AS total;
EOF
sqlite3 maintenance.db <<'SQL'
.mode column
.headers on
CREATE INDEX loan_member  ON loan(member_id);
CREATE INDEX loan_pickup ON loan(pickup_date);
.print '--- setup ---'
.read measure.sql
.shell echo "file: $(wc -c < maintenance.db)"
DELETE FROM loan WHERE pickup_date < '2020-01-01';
.print '--- old records deleted ---'
.read measure.sql
.shell echo "file: $(wc -c < maintenance.db)"
UPDATE loan SET pickup_date = date(pickup_date, '+900 days') WHERE loan_id % 3 = 0;
.print '--- one third of the dates updated ---'
.read measure.sql
.shell echo "file: $(wc -c < maintenance.db)"
REINDEX;
.print '--- after REINDEX ---'
.read measure.sql
.shell echo "file: $(wc -c < maintenance.db)"
VACUUM;
.print '--- after VACUUM ---'
.read measure.sql
.shell echo "file: $(wc -c < maintenance.db)"
SQL

--- setup ---
rows_    loan_table  member_index  pickup_index  total
-------  ----------  ------------  ------------  -----
2000000  18013       5754          9346          34261
file:  140333056
--- old records deleted ---
rows_    loan_table  member_index  pickup_index  total
-------  ----------  ------------  ------------  -----
1400893  18013       5755          6549          34261
file:  140333056
--- one third of the dates updated ---
rows_    loan_table  member_index  pickup_index  total
-------  ----------  ------------  ------------  -----
1400893  18013       5755          8157          34261
file:  140333056
--- after REINDEX ---
rows_    loan_table  member_index  pickup_index  total
-------  ----------  ------------  ------------  -----
1400893  18013       4034          6547          34261
file:  140333056
--- after VACUUM ---
rows_    loan_table  member_index  pickup_index  total
-------  ----------  ------------  ------------  -----
1400893  12617       4034          6547          24346
file:  99721216

This five-row table carries every finding in the lesson. The sections below read it as three questions: why the two indexes behaved differently under deletion, what reindexing and a full rewrite each recover, and at which stage the total page count actually changed.

Two Indexes, Two Different Behaviors

The second stage is, on its own, the lesson’s main finding. Roughly thirty percent of the rows were deleted. The pickup-date index fell from 9,346 pages to 6,549 pages — a drop close to the deleted proportion. The member index rose from 5,754 to 5,755 pages instead.

Both indexes lost the same rows; what produces the difference is how the entries were ordered. The delete condition was a date range, and in the date index that range’s entries sit next to each other: whole pages emptied out and moved to the free list. In the member index, the same rows’ entries are scattered across one hundred twenty thousand members; no page emptied out completely, they all emptied out partially. A page with empty room inside it does not give that room back.

The rule is the index-side counterpart of the rule established for tables in the Dead Row Cleanup lesson: if the delete criterion overlaps with the index order, the space comes back; if it does not, it stays. The same delete operation produces a saving in one index and dead space in another.

The third stage shows the update’s second job inside an index. A third of the rows had their date pushed forward; the table’s page count did not change, while the pickup-date index rose from 6,549 to 8,157 pages. No row was deleted, no row was added — only index entries moved from their old position to a new one, and the gap the old positions left did not close. The member index did not change at all at this stage (5,755), because the updated column is not its key.

Reindexing and a Full Rewrite

The fourth stage runs REINDEX: the indexes are rebuilt from scratch. The member index falls from 5,755 to 4,034 pages — a drop that matches the live-row ratio (1,400,893 / 2,000,000 ≈ 0.70) exactly, because no dead space is left. The pickup-date index falls from 8,157 to 6,547, that is, back to close to its post-delete value.

What deserves attention is the total page count of that same row: 34,261, unchanged. The file size did not change either. Reindexing freed the gap inside the database; it did not give it back to the operating system. That freed space is available for new data, but it does not lower disk usage and does not shorten backup time.

The fifth stage runs a full rewrite. The total falls from 34,261 to 24,346 pages, the file falls from 140,333,056 bytes to 99,721,216 bytes. The table also shrinks (18,013 → 12,617), because a full rewrite copies the table and its indexes together into a new file.

The distinction between the two tools fits in one sentence: reindexing repairs only the indexes and leaves the gap inside the database; a full rewrite repairs everything and gives the gap back to the file system. Their costs follow the same distinction. Reindexing locks only the affected index and scales with that index’s size, independent of table size. A full rewrite locks the table, needs temporary space equal to the table’s size, and reads all the data. On a live system the first fits inside a maintenance window; the second usually requires a planned outage.

Some engines offer a way to reindex without locking the table against writes: a new index is built in the background and swapped in once ready. The name and limits of this path are engine-specific; the concept is that the index is built as a duplicate copy and then swapped in, at the cost of both indexes temporarily occupying space at once.

Write Cost Grows With the Number of Indexes

The other side of maintenance is the cost an index’s mere existence adds to every write. The run below inserts the same two hundred thousand rows into five copies whose index count rises from zero to four.

rm -f template.db idx0.db idx1.db idx2.db idx3.db idx4.db
sqlite3 template.db < setup.sql
for k in 0 1 2 3 4; do cp template.db "idx$k.db"; done
sqlite3 idx1.db 'CREATE INDEX i1 ON loan(member_id);'
sqlite3 idx2.db 'CREATE INDEX i1 ON loan(member_id); CREATE INDEX i2 ON loan(pickup_date);'
sqlite3 idx3.db 'CREATE INDEX i1 ON loan(member_id); CREATE INDEX i2 ON loan(pickup_date);
               CREATE INDEX i3 ON loan(book_id);'
sqlite3 idx4.db 'CREATE INDEX i1 ON loan(member_id); CREATE INDEX i2 ON loan(pickup_date);
               CREATE INDEX i3 ON loan(book_id); CREATE INDEX i4 ON loan(return_date);'
for k in 0 1 2 3 4; do
  printf 'index count %s: ' "$k"
  sqlite3 "idx$k.db" <<'SQL' | grep 'Run Time'
.timer on
INSERT INTO loan (book_id, member_id, pickup_date, return_date)
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 200000)
SELECT 1 + ((n*7) % 200000), 1 + ((n*13) % 120000),
       date('2024-01-01','+'||(n%300)||' days'),
       CASE WHEN n % 9 = 0 THEN NULL ELSE date('2024-01-20','+'||(n%300)||' days') END
FROM s;
SQL
done

index count 0: Run Time: real 0.086 user 0.078935 sys 0.003910
index count 1: Run Time: real 0.204 user 0.146588 sys 0.049993
index count 2: Run Time: real 0.296 user 0.228903 sys 0.058341
index count 3: Run Time: real 0.431 user 0.310440 sys 0.106127
index count 4: Run Time: real 0.514 user 0.392024 sys 0.108754

The increase is close to linear: in this environment each index added roughly 0.11 seconds to insert time, and the four-index copy took about six times as long as the index-free copy. Run times depend on the environment; what is stable is that cost grows in proportion to the number of indexes. The reason is direct: for every new row, a separate key is written into every index tree.

The arithmetic for update is different — only indexes containing the updated column pay a cost. The run below performs the same update on two copies that both carry two indexes; the only difference is that in one copy the updated column is indexed.

rm -f update_outside.db update_inside.db
cp template.db update_outside.db
cp template.db update_inside.db
sqlite3 update_outside.db 'CREATE INDEX i1 ON loan(member_id); CREATE INDEX i2 ON loan(book_id);'
sqlite3 update_inside.db  'CREATE INDEX i1 ON loan(member_id); CREATE INDEX i2 ON loan(pickup_date);'
for db in update_outside.db update_inside.db; do
  printf '%-16s ' "$db"
  sqlite3 "$db" <<'SQL' | grep 'Run Time'
.timer on
UPDATE loan SET pickup_date = date(pickup_date, '+1 day') WHERE loan_id % 5 = 0;
SQL
done

update_outside.db Run Time: real 0.236 user 0.091817 sys 0.127090
update_inside.db Run Time: real 0.667 user 0.406798 sys 0.235992

Same row count, same number of indexes, and in this environment nearly a threefold difference in time. The practical consequence is this: indexing a frequently updated column does not cost the same as indexing a column that is never updated. Choosing an index means looking not only at how a column is queried, but also at how often it changes.

Indexes Paid For but Never Collected

Maintenance’s last job is finding indexes that should not exist. The pattern established in the System Catalog lesson is used a second time here: an index whose column list is another index’s leftmost prefix is, by the leftmost prefix rule, never required on its own for any query.

rm -f audit.db
cp template.db audit.db
sqlite3 audit.db <<'SQL'
.mode column
.headers on
CREATE INDEX loan_member        ON loan(member_id);
CREATE INDEX loan_member_pickup ON loan(member_id, pickup_date);
CREATE INDEX loan_pickup        ON loan(pickup_date);
CREATE INDEX loan_book          ON loan(book_id);
-- Indexes whose column list is another index's prefix: they waste space for nothing.
WITH d AS (
  SELECT m.name AS tbl, il.name AS idx,
         (SELECT group_concat(ii.name, ',') FROM pragma_index_info(il.name) ii) AS cols
  FROM sqlite_schema m JOIN pragma_index_list(m.name) il
  WHERE m.type = 'table' AND il.origin = 'c'
)
SELECT a.idx AS redundant, a.cols AS its_columns, b.idx AS covered_by,
       (SELECT count(*) FROM dbstat WHERE name = a.idx) AS pages
FROM d a JOIN d b ON a.tbl = b.tbl AND a.idx <> b.idx
WHERE b.cols LIKE a.cols || ',%';
SQL

redundant    its_columns  covered_by          pages
-----------  -----------  ------------------  -----
loan_member  member_id    loan_member_pickup  5754

The audit produced a single finding, and it also reported the cost: the single-column index on member_id is redundant because it is the leftmost prefix of the (member_id, pickup_date) index, and it occupies 5,754 pages. Removing it recovers both that space and the share paid on every write.

There is a second category this audit cannot find: indexes whose column list is unique yet that no query ever uses. Those are found not from the catalog but from the engine’s own usage counters; the name and existence of those counters is engine-specific. The common method is to reset the counter, wait through one work cycle, and add any index that never incremented to a list of candidates. The decision is not made right away — a report that runs once a month does not show up in a one-week observation.

Summary

• Deletion and update leave gaps in indexes; an update does two jobs inside an index, deleting from the old position and writing at the new one.
• Whether the space comes back is decided by index order: on a delete by date range, the date index fell from 9,346 to 6,549 pages, while the member index rose from 5,754 to 5,755 on the same delete.
• Reindexing repairs the indexes and leaves the gap inside the database (the total stayed at 34,261 pages); a full rewrite also shrinks the file (24,346 pages, 99,721,216 bytes).
• Insert cost grows in proportion to the number of indexes; in the measurement each index added roughly 0.11 seconds, and the four-index copy took about six times as long as the index-free one.
• On update, only indexes containing the updated column pay a cost: with the same index count the difference came out close to threefold; the leftmost prefix audit found one redundant index occupying 5,754 pages.

Next Step

This lesson ran into the same fact twice: when the delete criterion overlapped with index order, space came back on its own; when it did not, maintenance was required. The table-side counterpart of that same fact was measured in the Dead Row Cleanup lesson, and a question was left open there: instead of deleting old data, can old data be kept in a separate place? The next lesson answers that question. When a table is split into partitions by range, list, or hash, a query touching only the relevant partition will be shown by the plan, deleting old data will turn into dropping a partition, and the distribution of the partition key will be measured by number.