Excessive Memory Usage During Large DELETE with Correlated Subquery in SQLite

Understanding SQLite’s Two-Pass DELETE Strategy with Correlated Subqueries

The core challenge revolves around executing a DELETE operation targeting billions of rows using a correlated subquery (NOT EXISTS). SQLite’s query planner employs a two-pass strategy for such operations:

1. Identification Phase: Compile a list of all rowid values satisfying the WHERE clause into an in-memory structure.
2. Deletion Phase: Iterate through the list, deleting rows and maintaining database integrity (index updates, foreign key checks, triggers).

For a nodes table with 2.7 billion rows marked for deletion, storing rowid values (8 bytes each) requires ~21.6 GB of contiguous memory. SQLite’s default configuration prioritizes speed by retaining this list in memory, leading to out-of-memory (OOM) scenarios when system resources are exhausted.

Key Factors Exacerbating Memory Consumption

• Lack of Batching: Single-transaction deletes force SQLite to track all rowid values upfront.
• Temporary Storage Configuration: Default temp_store=0 uses memory-backed temporary files, but SQLite’s pager cache still buffers data in RAM.
• Index Maintenance Overhead: Foreign key references in nodes_ways require index updates during deletion, compounding memory pressure.
• Pager Cache Behavior: Large cache_size values (default: -2000 ≈ 2MB per connection) multiply when handling massive transactions.

Diagnosing and Mitigating Memory-Intensive DELETE Operations

Step 1: Confirm SQLite Version and Configuration

Verify SQLite’s version compatibility and runtime settings:

SELECT sqlite_version(); -- Ensure ≥3.35.0 for RETURNING clause support
PRAGMA temp_store;       -- 0=default, 1=file, 2=memory
PRAGMA cache_size;       -- Pages in memory cache (-2000 = ~2MB)
PRAGMA cache_spill;      -- Enable automatic spilling to disk (default=1)

Action: If temp_store=0, switch to file-backed storage temporarily:

PRAGMA temp_store = FILE;  
PRAGMA cache_size = 100; -- Reduce to 100 pages (~160KB for 16KB page size)

Step 2: Implement Batched Deletion with Intermediate Tables

Break the monolithic DELETE into smaller batches using a temporary table to stage rowid values:

BEGIN IMMEDIATE;
CREATE TEMP TABLE batch_delete AS 
  SELECT id FROM nodes 
  WHERE NOT EXISTS (SELECT 1 FROM nodes_ways WHERE node_id = id) 
  LIMIT 1000000;
DELETE FROM nodes WHERE id IN (SELECT id FROM batch_delete);
DROP TABLE batch_delete;
COMMIT;

Rationale: Each batch processes 1 million rows, minimizing in-memory rowid storage. Adjust LIMIT based on available RAM (e.g., 100K rows ≈ 0.8MB per batch).

Step 3: Leverage RETURNING Clause with LIMIT (If Available)

For SQLite ≥3.35.0 compiled with SQLITE_ENABLE_UPDATE_DELETE_LIMIT:

DELETE FROM nodes 
WHERE NOT EXISTS (SELECT 1 FROM nodes_ways WHERE node_id = id) 
RETURNING count() LIMIT 1000000;

Advantage: Eliminates the need for temporary tables by directly limiting deletion scope.

Step 4: Disable Foreign Key Constraints During Deletion

Temporarily suspend foreign key checks to reduce index maintenance overhead:

PRAGMA foreign_keys = OFF;
-- Execute batched DELETE
PRAGMA foreign_keys = ON;

Caution: Ensure no dangling references remain in nodes_ways after deletion.

Step 5: Optimize Index Usage and Vacuum Strategically

• Drop Redundant Indexes: Remove unused indexes on nodes before deletion.
• Post-Deletion Vacuum: Reclaim disk space and defragment the database after all deletions:

  PRAGMA auto_vacuum = INCREMENTAL; -- Set before deletion if possible
  PRAGMA incremental_vacuum(1000);  -- Vacuum in chunks
  

Step 6: Adjust Page Size and Journal Modes

For future imports, optimize the database schema:

PRAGMA page_size = 16384; -- Larger page sizes reduce I/O overhead
PRAGMA journal_mode = WAL; -- Write-Ahead Logging improves concurrency

Architectural Considerations for High-Volume Data Pruning

Alternative 1: Prevent Unwanted Data During Import

Modify the import pipeline to filter out irrelevant nodes before insertion. For example, use osmium or osm2pgsql tools to preprocess .osm.pbf files, extracting only required entities.

Alternative 2: Partition Tables by Entity Type

Segment nodes into multiple tables (e.g., nodes_highway, nodes_building) during import. This enables dropping entire partitions instead of row-wise deletion.

Alternative 3: Use ATTACH DATABASE for Staging

Import data into a temporary database, apply filters via INSERT INTO main.nodes SELECT ..., then DETACH the staging database. This isolates bulk operations from production data.

Alternative 4: Employ External Sorting Utilities

For extremely large datasets, export node_id values from nodes_ways to a file, sort it, and perform a linear scan of nodes using an external merge-join algorithm (e.g., via Python or C++).

Final Note: While SQLite excels at embedded and moderate-scale data tasks, petabyte-grade datasets often necessitate distributed databases (e.g., PostgreSQL with TimescaleDB, DuckDB) or columnar storage formats (Apache Parquet) optimized for bulk operations.