Deleted SQLite Rows Not Visible in Freelist: Recovery Challenges Explained

Understanding Freelist Behavior and Deleted Row Recovery Limitations

Freelist Mechanics and Deleted Row Storage Expectations

SQLite manages database storage via fixed-size pages (default 4KB). When rows are deleted, their storage space is marked as reusable within their respective pages. The freelist (a.k.a. free-page list) tracks entire pages that have been completely emptied of rows and are available for reuse. This distinction between row-level deletion and page-level freelist updates is critical to understanding why deleted rows may not appear in the freelist.

When a row is deleted:

1. The row’s slot in its host page is marked as free space.
2. The page remains part of the table’s B-tree structure if it contains other active rows.
3. Only when all rows on a page are deleted does SQLite move the entire page to the freelist.

The original poster (OP) expected deleted rows to immediately populate the freelist, but this expectation conflicts with SQLite’s design. The freelist does not track individual row deletions—it tracks pages that are entirely unused. This misunderstanding is central to the confusion.

Key factors influencing this behavior include:

• Page Utilization: A page may contain multiple rows. Deleting one row leaves others intact, keeping the page active.
• Auto-Vacuum Configuration: When disabled (default), SQLite does not automatically return empty pages to the OS or reorganize data to consolidate free space.
• Secure Delete Settings: If PRAGMA secure_delete=ON, deleted row content is overwritten with zeros, making recovery impossible.

Why Deleted Rows Fail to Appear in the Freelist

1. Row Deletion ≠ Page Liberation

SQLite’s storage engine operates at the page level, not the row level. A page is added to the freelist only when all its rows are deleted. For example:

• A page contains 10 rows.
• Deleting 1 row leaves 9 active rows. The page remains in the B-tree.
• Deleting all 10 rows marks the page as free, moving it to the freelist.

This explains why the OP’s DELETE FROM personas WHERE nick='bruce' did not update the freelist: the page(s) hosting the deleted row(s) still contained other valid rows.

2. Auto-Vacuum and Journaling Modes

• Auto-Vacuum Disabled (PRAGMA auto_vacuum=0):
  Empty pages are retained in the freelist but not returned to the OS. File size remains constant unless a VACUUM command is executed.
• Journal Modes (WAL vs. Delete/Truncate):
  In Write-Ahead Logging (WAL) mode, changes are stored in a separate log file until checkpointing. Freelist updates may be delayed until checkpoints or transactions commit.

The OP confirmed auto_vacuum was disabled, ruling out automatic space reclamation. However, they observed the database header version incrementing—a sign of transaction commits—without freelist changes. This aligns with SQLite’s behavior: header versions update on transaction boundaries, regardless of freelist activity.

3. Tooling Misalignment for Recovery

Tools like recoversqlite scan freelist pages for recoverable data. If deleted rows reside in partially filled pages (not in the freelist), such tools cannot detect them. The OP’s synthetic tests—creating a new DB, inserting/deleting rows—likely left pages partially filled, resulting in an empty freelist.

Diagnosing and Resolving Freelist Visibility Issues

Step 1: Confirm Page-Level Deletion Requirements

To trigger freelist updates, ensure entire pages are emptied:

1. Determine the database page size:

   PRAGMA page_size;  
   

2. Calculate rows per page:

   RowsPerPage = (PageSize - ReservedSpace) / AvgRowSize  
   

3. Delete enough rows to empty at least one full page.

Example:

• Page size: 4096 bytes
• Reserved space (header): 12 bytes
• Avg row size: 100 bytes
• Rows per page: ~40
  Delete 40 rows to free a page.

Step 2: Validate Auto-Vacuum and Secure Delete Settings

PRAGMA auto_vacuum; -- Expect 0 (disabled)  
PRAGMA secure_delete; -- Ensure OFF to prevent data overwrites  

Step 3: Force Freelist Updates via Manual Vacuuming

If pages are partially empty but not in the freelist, manually trigger page reorganization:

VACUUM;  

This command rebuilds the database, consolidating free space and moving empty pages to the freelist.

Step 4: Inspect Freelist Content Directly

Use sqlite3 command-line tools to dump raw database content:

sqlite3 test.db ".dump"  

Or query freelist page counts:

PRAGMA freelist_count;  

Step 5: Use Low-Level Tools for Partial-Page Recovery

If deleted rows are in active pages (not freelist), employ tools that scan all pages for residual data:

1. SQLite Forensic Toolkit (sqlite-ft): Extracts data from pages regardless of freelist status.
2. Custom Python Scripts: Read raw database bytes and parse row structures.

Example Python Snippet:

import sqlite3  
import struct  

def read_raw_page(db_path, page_num):  
    with open(db_path, 'rb') as f:  
        f.seek((page_num - 1) * 4096)  # Adjust for page size  
        return f.read(4096)  

# Parse page header (12 bytes)  
page_data = read_raw_page('test.db', 5)  
header = struct.unpack('>HBBBBBBBH', page_data[:12])  
cell_count = header[3]  

Step 6: Synthetic Test Case Design

To simulate recoverable deletions:

1. Create a table with rows sized to fill one page exactly.
2. Insert enough rows to populate multiple pages.
3. Delete all rows from specific pages to force freelist inclusion.

Example Schema for Testing:

CREATE TABLE test (  
    id INTEGER PRIMARY KEY,  
    data BLOB  
);  
-- Insert rows to fill pages  
INSERT INTO test (data) VALUES (randomblob(4000));  

Step 7: Address Journaling and Transaction Finalization

Ensure transactions are fully committed to persist freelist changes:

BEGIN;  
DELETE FROM test WHERE id=1;  
COMMIT;  -- Freelist updates occur here  

By methodically addressing page utilization thresholds, configuration settings, and recovery tooling limitations, users can align their expectations with SQLite’s storage mechanics and achieve reliable results in data recovery scenarios.