Optimizing Recursive Queries for Filesystem Traversal in SQLite

Understanding the Filesystem Schema and Recursive Query Structure

The core issue revolves around optimizing a recursive query in SQLite that traverses a filesystem-like structure stored in two tables: devices and objects. The devices table stores mount paths, while the objects table represents files and directories, with directories referencing their parent directories. The recursive query aims to generate a full path for every file and directory in the filesystem.

The schema is designed as follows:

CREATE TABLE devices (
    id INTEGER PRIMARY KEY,
    mountpath TEXT NOT NULL
);

CREATE TABLE objects (
    dev_id INTEGER NOT NULL,
    parent INTEGER NOT NULL,
    inode INTEGER NOT NULL,
    name TEXT NOT NULL,
    FOREIGN KEY (dev_id) REFERENCES devices(id) ON DELETE RESTRICT,
    FOREIGN KEY (dev_id, parent) REFERENCES objects(dev_id, inode) ON DELETE CASCADE ON UPDATE CASCADE
);

The recursive query uses a Common Table Expression (CTE) to build paths from leaf nodes (files) up to the root. The query starts by selecting leaf nodes (files) and recursively appends parent directory names to construct the full path. However, this approach results in a large queue of items being processed, leading to significant memory usage and potential performance issues, especially with a dataset of 10.3 million objects.

The query structure is as follows:

CREATE VIEW allfiles AS
WITH RECURSIVE full_path(dev_id, parent, dir_ino, inode, path) AS (
    SELECT objects.dev_id, objects.parent, objects.parent, objects.inode, '/' || name AS path
    FROM objects
    LEFT JOIN objects o2 ON (o2.dev_id, o2.parent) = (objects.dev_id, objects.inode)
    WHERE o2.inode IS NULL
    UNION ALL
    SELECT obj.dev_id,
        CASE WHEN obj.parent != obj.inode THEN obj.parent ELSE NULL END AS parent,
        fp.dir_ino,
        fp.inode,
        name || '/' || fp.path AS path
    FROM full_path fp
    JOIN objects obj ON (fp.dev_id, fp.parent) = (obj.dev_id, obj.inode)
    WHERE fp.parent IS NOT NULL
)
SELECT devices.mountpath || '/' || fp.path AS path
FROM full_path fp
JOIN devices ON devices.id = fp.dev_id
WHERE parent IS NULL;

This query processes 10.2 million files first, leading to a large initial queue. As it recursively traverses up the directory tree, the queue size decreases, but the memory usage remains high due to the breadth-first nature of the recursion.

Memory and Performance Challenges in Breadth-First Recursion

The primary challenge lies in the breadth-first nature of the recursive query, which processes all leaf nodes (files) before moving up the directory tree. This approach results in a large initial queue, consuming significant memory and potentially causing the query to fail due to resource limitations.

In the given example, the query starts by adding 10.2 million file paths to the queue. As it processes each file, it appends the parent directory’s name to the path and adds the updated path back to the queue. This process continues until the root directory is reached. The queue size decreases as files are processed, but the initial memory footprint is substantial.

The memory usage is exacerbated by the fact that SQLite’s recursive CTE implementation uses a queue to manage the recursion. Each row in the queue contains the full path constructed so far, which can be large, especially for deeply nested directories. With 10.3 million objects, the memory usage can easily exceed available resources, leading to query failures or excessive disk usage for temporary storage.

Additionally, the breadth-first approach may not be the most efficient for this use case. Since the goal is to generate full paths for all files and directories, a depth-first approach could reduce memory usage by processing one branch of the directory tree at a time, rather than processing all files simultaneously.

Implementing Depth-First Recursion and Optimizing Query Performance

To address the memory and performance challenges, the recursive query can be modified to use a depth-first approach. SQLite supports depth-first recursion by using an ORDER BY clause in the recursive CTE. This approach processes one branch of the directory tree at a time, reducing the queue size and memory usage.

The modified query structure for depth-first recursion is as follows:

CREATE VIEW allfiles AS
WITH RECURSIVE full_path(dev_id, parent, dir_ino, inode, path) AS (
    SELECT objects.dev_id, objects.parent, objects.parent, objects.inode, '/' || name AS path
    FROM objects
    LEFT JOIN objects o2 ON (o2.dev_id, o2.parent) = (objects.dev_id, objects.inode)
    WHERE o2.inode IS NULL
    UNION ALL
    SELECT obj.dev_id,
        CASE WHEN obj.parent != obj.inode THEN obj.parent ELSE NULL END AS parent,
        fp.dir_ino,
        fp.inode,
        name || '/' || fp.path AS path
    FROM full_path fp
    JOIN objects obj ON (fp.dev_id, fp.parent) = (obj.dev_id, obj.inode)
    WHERE fp.parent IS NOT NULL
    ORDER BY fp.path DESC -- Depth-first ordering
)
SELECT devices.mountpath || '/' || fp.path AS path
FROM full_path fp
JOIN devices ON devices.id = fp.dev_id
WHERE parent IS NULL;

In this modified query, the ORDER BY fp.path DESC clause ensures that the recursion follows a depth-first approach. This change reduces the queue size by processing one directory branch at a time, rather than processing all files simultaneously. As a result, the memory usage is significantly lower, and the query is less likely to fail due to resource limitations.

The depth-first approach also improves performance by reducing the number of rows in the queue at any given time. Instead of starting with 10.2 million files, the query processes a smaller number of rows at each recursion level, leading to faster execution and lower memory usage.

In addition to modifying the recursion strategy, further optimizations can be applied:

1. Indexing: Ensure that the objects table has appropriate indexes on the dev_id, parent, and inode columns to speed up joins and lookups.
2. Batch Processing: If the dataset is too large to process in a single query, consider breaking the query into smaller batches and processing them sequentially.
3. Temporary Tables: Use temporary tables to store intermediate results and reduce memory usage during query execution.

By implementing these optimizations, the recursive query can efficiently generate full paths for all files and directories in the filesystem, even with a large dataset. The depth-first approach, combined with proper indexing and batch processing, ensures that the query performs well and does not exceed available resources.