Query Performance Degrades 25x with ORDER BY in SQLite

Understanding the Query Performance Drop with ORDER BY

The core issue revolves around a significant performance degradation when an ORDER BY clause is introduced into a SQLite query. Without the ORDER BY, the query executes in approximately 20 seconds, but with the ORDER BY, the execution time balloons to around 500 seconds. This drastic difference suggests a fundamental shift in how SQLite processes the query when sorting is involved. The query in question involves a temporary table creation, a join between a view and a table, and filtering based on subqueries. The view itself is derived from a large table (lookups) with 18 million records, and the query is further complicated by the use of subqueries and joins.

The query plan reveals that SQLite chooses different strategies for executing the query with and without the ORDER BY. Without the ORDER BY, SQLite performs a full table scan on the lookups table, which, while seemingly inefficient, actually results in a faster execution time due to the way the data is accessed and joined. However, when the ORDER BY is introduced, SQLite opts to use an index on content_id to retrieve the data in sorted order, which disrupts the natural order of the join keys (url_id). This disruption forces SQLite to perform numerous random accesses across the urls table, significantly slowing down the query.

Why ORDER BY Forces a Different Query Plan

The primary reason for the performance drop lies in how SQLite’s query planner handles the ORDER BY clause. When the ORDER BY is present, SQLite prioritizes retrieving the data in the specified order, which in this case is content_id. To achieve this, SQLite uses the index on content_id (content_id_idx), which allows it to avoid an expensive in-memory sort operation at the end of the query. However, this decision comes at a cost: the data retrieved from the lookups table is no longer in the order of url_id, which is the join key used to match rows with the urls table.

In the absence of the ORDER BY, SQLite performs a full table scan on the lookups table, which keeps the rows in their natural order (likely the order of insertion). This natural order happens to align with the order of url_id in the urls table, allowing SQLite to perform a merge-join-like operation. In this scenario, both tables are scanned sequentially, and rows are matched as the cursors move through the tables. This approach minimizes cursor movement and results in a much faster join operation.

However, when the ORDER BY is introduced, SQLite cannot assume that the url_id values in the lookups table will align with those in the urls table. As a result, it must use the index on content_id to retrieve the data in sorted order, which disrupts the natural alignment of url_id values. This misalignment forces SQLite to perform numerous random accesses across the urls table, as it must repeatedly seek to different positions in the table to find matching rows. These random accesses are significantly more expensive than the sequential accesses performed during the full table scan, leading to the observed performance degradation.

Optimizing the Query with ORDER BY

Given the nature of the problem, there are several strategies to mitigate the performance impact of the ORDER BY clause. One approach is to restructure the query to maintain the natural order of the join keys while still achieving the desired sorting. This can be done by using a subquery to first retrieve the data in the required order and then performing the join. For example:

CREATE TEMP TABLE IF NOT EXISTS t_with_urls AS
SELECT
    u.url,
    l.content_id
FROM
    (SELECT * FROM v_all_lookups_for_last_scrape ORDER BY content_id) l
JOIN
    urls u USING (url_id)
WHERE
    u.type_id IN (SELECT type_id FROM content_types WHERE getcap = 1)
    AND
    response_code = 200
    AND
    error_code = 0;

In this version of the query, the subquery (SELECT * FROM v_all_lookups_for_last_scrape ORDER BY content_id) ensures that the data from the lookups table is retrieved in the correct order before the join is performed. This approach allows SQLite to maintain the natural order of the join keys while still satisfying the ORDER BY requirement. However, this solution may not always be feasible, especially if the subquery itself is expensive to execute.

Another approach is to use a covering index that includes both the content_id and url_id columns. This index would allow SQLite to retrieve the data in the correct order without disrupting the join operation. For example:

CREATE INDEX lookups_content_id_url_id_idx ON lookups(content_id, url_id);

With this index in place, SQLite can use it to retrieve the data in content_id order while still maintaining the alignment of url_id values. This approach reduces the need for random accesses across the urls table, as the join keys remain in a consistent order. However, creating such an index may increase the storage requirements and could impact the performance of write operations.

Finally, if the ORDER BY clause is not strictly necessary, it can be removed to restore the original query performance. In some cases, the sorting can be deferred to the application layer, where it may be more efficient to handle. For example, the application could retrieve the unsorted data and then sort it in memory, avoiding the need for SQLite to perform the expensive sorting operation.

In conclusion, the performance degradation observed when adding an ORDER BY clause to the query is a result of SQLite’s query planner prioritizing the retrieval of sorted data over the natural order of the join keys. By understanding the underlying mechanisms and exploring alternative query structures or indexing strategies, it is possible to mitigate this performance impact and achieve a more efficient execution.