Dead Row Cleanup

The previous lesson showed that a version becomes reclaimable only once no open snapshot sees it anymore. Being reclaimable and being reclaimed are separate things. A separate process collects versions, and if that process cannot keep up with the dead versions being produced, a table keeps growing even when its row count never rises.

This lesson’s questions can be measured: where does a deleted row’s space go, when is it reused, how much does the file grow when it is not, and what does reversing that growth cost?

Dead Tuples and Bloat

A dead tuple is a row version no transaction sees anymore. It comes from two sources: a deleted row itself, and an updated row’s old version. Under the model from the previous lesson, an update also leaves behind a dead version, because a new version is physically written.

Bloat is how much larger the space a table or index occupies is than the space needed to hold its live data. It is measured as a ratio: the number of pages occupied divided by the number of pages the same data would occupy compacted.

Bloat is not itself a defect; some of it is unavoidable and useful, because the free space leaves room for new rows. The problem is the ratio continuing to grow. Scanning a bloated table reads more pages, holds more space in the buffer pool, and makes backups larger — all for the same data.

Where Deleted Space Goes

The run below tracks four stages using the same three measurements: row count, page count, and in-page fill. The file size is also printed at each stage.

rm -f cleanup.db
cat > status.sql <<'EOF'
SELECT (SELECT count(*) FROM loan) AS rows_count,
       (SELECT page_count FROM pragma_page_count) AS pages,
       (SELECT round(100.0*sum(payload)/sum(pgsize),1) FROM dbstat WHERE name='loan') AS fill_pct;
EOF
sqlite3 cleanup.db <<'SQL'
.mode column
.headers on
CREATE TABLE loan(loan_id INTEGER PRIMARY KEY, book_id INT, member_id INT,
                   pickup_date TEXT, return_date TEXT);
INSERT INTO loan SELECT n, 1+(n*7)%200000, 1+(n*13)%120000,
       date('2018-01-01','+'||((n*37)%2437)||' days'), NULL
  FROM (WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n<400000) SELECT n FROM s);
.print '--- start ---'
.read status.sql
.shell echo "file: $(wc -c < cleanup.db)"
DELETE FROM loan WHERE pickup_date < '2020-01-01';
.print '--- 119822 rows deleted ---'
.read status.sql
.shell echo "file: $(wc -c < cleanup.db)"
INSERT INTO loan SELECT 500000+n, 1+(n*7)%200000, 1+(n*13)%120000, '2025-01-01', NULL
  FROM (WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n<100000) SELECT n FROM s);
.print '--- 100000 new rows (with an increasing key) ---'
.read status.sql
.shell echo "file: $(wc -c < cleanup.db)"
VACUUM;
.print '--- after VACUUM ---'
.read status.sql
.shell echo "file: $(wc -c < cleanup.db)"
SQL

--- start ---
rows_count  pages  fill_pct
----------  -----  --------
400000      2723   77.3    
file:  11153408
--- 119822 rows deleted ---
rows_count  pages  fill_pct
----------  -----  --------
280178      2723   54.2    
file:  11153408
--- 100000 new rows (with an increasing key) ---
rows_count  pages  fill_pct
----------  -----  --------
380178      3403   58.8    
file:  13938688
--- after VACUUM ---
rows_count  pages  fill_pct
----------  -----  --------
380178      2589   77.3    
file:  10604544

The second stage gives the first result. Roughly a third of the rows were deleted; the page count did not drop by even one, and the file size did not shrink by a single byte. The only thing that changed is fill: it dropped from 77.3% to 54.2%. The delete did not free the pages — it emptied the pages out.

The reason for this behavior is direct. Deleted rows are scattered across the whole file; a page only fully empties out once every row on it has been deleted. A partially emptied page cannot be removed from the file, because — under the relationship measured in the Physical Storage Layout lesson — the file consists of nothing but pages laid end to end; removing a page in the middle would mean moving everything after it.

Why Space Is Not Always Reused

The third stage gives a more interesting result. With 119,822 rows’ worth of empty space in the table, 100,000 rows were inserted, and the file did not shrink — it grew: from 2,723 pages to 3,403 pages.

The reason is key selection. loan_id is a continuously increasing value, and new rows are appended to the far right edge of the tree. The gaps left by deleted rows, though, sit in the middle of the tree — the new keys do not belong there. In a sequential structure, the engine cannot place a key anywhere other than where it belongs.

This is one of the most concrete links between schema design and storage. In a table that is appended to with a continuously increasing key and has old records deleted by date, empty space does not close up on its own: new data always gets written to the end, and the gaps always stay in the middle. If the same table were filled with random keys instead, some of the gaps would naturally get used — but at the cost of more page splits. The Table Partitioning topic will bring a structural answer to this problem: instead of deleting old data, dropping the entire old partition.

Reclaiming Space

The fourth stage runs VACUUM, and the table drops from 3,403 pages to 2,589 pages; fill returns to 77.3%, matching the first day’s value. The bloat ratio was 3403 / 2589 ≈ 1.31; the rewrite brought it down to 1.00.

Knowing what this operation does comes before knowing when to use it: the table is read from start to end and written out compacted in a new location, then the old copy’s space is released. It has three costs.

Locking. During a full rewrite, the table cannot be modified (in most engines), and in some it cannot even be read. In a running system, this means planned downtime.

Temporary space. While the new copy is being written, the old copy is still in place; the operation needs extra space roughly equal to the table’s size. On a server that is nearly out of disk, running a rewrite to free up space does not work, because it requires space that is not available.

Duration. The cost is proportional to the whole table, not to the space being reclaimed.

For this reason, engines offer two lighter-weight paths: a background cleanup that makes space reusable without locking, and a reorganization that builds a new copy while keeping the table available. Their names and limits are specific to the engine; a full rewrite is, as a rule, the last resort.

The Balance of Cleanup

The real administrative question is not “when should we rewrite,” but “what keeps bloat from climbing past a given ratio.” The model below varies two variables separately: how often cleanup runs and how long a transaction stays open. It is not the actual cleanup process; what it tracks is the highest amount of space ever allocated, relative to the live data.

cat > cleanup2.mjs <<'JS'
// Model: the balance between dead version buildup and cleanup. Not the actual engine.
// At each step, UPDATES rows are updated; each update leaves one dead version.
// Cleanup runs once every INTERVAL steps and only collects dead versions older
// than the oldest open snapshot. Allocated space is not returned to the operating system.
function run({ interval, longTxn = null, steps = 600 }) {
  const LIVE = 100000, UPDATES = 2000;
  let dead = [];                                   // each entry: the step it was created at
  let allocated = LIVE, peak = LIVE;
  for (let i = 1; i <= steps; i++) {
    for (let k = 0; k < UPDATES; k++) dead.push(i);
    allocated = Math.max(allocated, LIVE + dead.length);
    peak = Math.max(peak, allocated);
    if (i % interval === 0) {
      const cutoff = (longTxn && i >= longTxn.start && i <= longTxn.end) ? longTxn.start : i;
      dead = dead.filter((d) => d >= cutoff);        // entries older than the open snapshot are collected
    }
  }
  return { remaining: dead.length, bloat: peak / LIVE };
}
console.log('— cleanup frequency —');
console.log('interval (steps)   remaining dead versions   bloat ratio');
for (const a of [1, 5, 25, 100, 600])
  { const s = run({ interval: a });
    console.log(String(a).padStart(17), String(s.remaining).padStart(25), (s.bloat.toFixed(2) + '×').padStart(12)); }
console.log('— same cleanup (interval 5), with an open long transaction —');
for (const length of [0, 100, 300, 600]) {
  const s = run({ interval: 5, longTxn: length ? { start: 1, end: length } : null });
  console.log(`long txn ${String(length).padStart(3)} steps →`, String(s.remaining).padStart(7),
              'dead versions,', (s.bloat.toFixed(2) + '×').padStart(6), 'bloat');
}
JS
node cleanup2.mjs

— cleanup frequency —
interval (steps)   remaining dead versions   bloat ratio
                1                      2000        1.04×
                5                      2000        1.12×
               25                      2000        1.52×
              100                      2000        3.02×
              600                      2000       13.00×
— same cleanup (interval 5), with an open long transaction —
long txn   0 steps →    2000 dead versions,  1.12× bloat
long txn 100 steps →    2000 dead versions,  3.10× bloat
long txn 300 steps →    2000 dead versions,  7.10× bloat
long txn 600 steps → 1200000 dead versions, 13.00× bloat

The first table is as expected: the more infrequently cleanup runs, the more dead versions pile up and the higher the peak allocated space climbs. Cleanup running at every step keeps bloat at 1.04; running once every six hundred steps drives it to 13.00. Do not be misled by the remaining dead version count coming out the same in every row — what is measured is not the final state but the peak reached over the run; once space is allocated, it is not given back.

The second table gives the real warning. Cleanup frequency never changed — it still runs every five steps — but a single transaction staying open for three hundred steps drove bloat from 1.12 to 7.10. Cleanup is running, but it finds nothing to collect: every dead version produced since that transaction’s snapshot is still visible.

The result comes down to two sentences. What sets the upper bound on bloat is whichever is larger: how often cleanup runs, or how old the oldest open transaction is. This is why investigating bloat problems starts not from cleanup settings, but from the list of transactions that have been open for a long time.

Summary

• A dead tuple is a row version no transaction sees anymore; both deletes and updates produce it. Bloat is the ratio of occupied space to needed space.
• In the measurement, deleting a third of the rows left the page count and file size completely unchanged; only in-page fill dropped, from 77.3% to 54.2%.
• New rows inserted with a continuously increasing key cannot use the gaps in the middle; with 119,822 rows’ worth of empty space available, inserting 100,000 rows grew the file from 2,723 to 3,403 pages.
• A full rewrite returned fill to its first-day value (2,589 pages), but it requires locking, temporary space equal to the table’s size, and a duration proportional to the whole table.
• In the model, two factors set the bloat ratio: cleanup frequency and the age of the oldest open transaction; a single transaction staying open for three hundred steps drove bloat from 1.12 to 7.10.

Next Step

Every question asked so far in this course has been answered with a number: page count, fill, frame count, hit rate. These numbers do not sit off to the side; the engine keeps information about its own structure in ordinary tables and hands it out through ordinary queries. The next lesson takes up that information: where the definitions of tables, columns, indexes, and constraints are stored, what administrative questions can be answered from there, and why querying the schema is superior to hand-maintained lists.