Optimizing Slow SELECT COUNT(DISTINCT) Queries in SQLite

Understanding the Performance Bottleneck in SELECT COUNT(DISTINCT) Queries

The core issue revolves around the performance of a SELECT COUNT(DISTINCT) query on a large SQLite table. The table in question, my_data, contains approximately 4 million records, with a data_id column that stores 16-character hexadecimal strings. While the data_id column is indexed, the query performance degrades significantly when filtering by a boolean column, keep_flag. The query in question is:

SELECT COUNT(DISTINCT(data_id)) AS num
FROM my_data
WHERE keep_flag = 1;

On an SSD, this query takes around 3 minutes to execute, and on an HDD, it can take up to 40-60 minutes. This is despite the fact that the entire database is only 5GB in size, and the data_id column is indexed. The query plan reveals that SQLite is using the index on data_id, but the performance is still suboptimal. This raises questions about why the SQLite query optimizer is not choosing a more efficient execution plan, such as creating a temporary index or using a covering index.

Why the Query Optimizer Struggles with COUNT(DISTINCT) and Filtered Queries

The primary reason for the poor performance lies in the interaction between the COUNT(DISTINCT) operation and the WHERE clause filtering on keep_flag. The COUNT(DISTINCT) operation requires SQLite to scan the table, identify unique values of data_id, and count them. When combined with the WHERE clause, SQLite must first filter the rows where keep_flag = 1 and then perform the distinct count operation. The existing index on data_id does not include keep_flag, which means SQLite cannot use the index to efficiently filter rows based on keep_flag. As a result, the query planner defaults to a full table scan, which is time-consuming, especially on slower storage devices like HDDs.

The query plan provided in the discussion shows that SQLite is using the my_data__data_id__idx index, but it is not leveraging it effectively for the WHERE clause. The DeferredSeek operation in the query plan indicates that SQLite is attempting to use the index, but the lack of a covering index for both data_id and keep_flag forces it to perform additional work to filter rows. This inefficiency is compounded by the fact that the COUNT(DISTINCT) operation requires SQLite to track unique values, which adds computational overhead.

Step-by-Step Troubleshooting and Solutions for Improving Query Performance

To address the performance issues with the SELECT COUNT(DISTINCT) query, several strategies can be employed. Each solution targets a specific aspect of the problem, from index optimization to query restructuring.

1. Creating a Covering Index for data_id and keep_flag

One of the most effective solutions is to create a covering index that includes both data_id and keep_flag. A covering index allows SQLite to satisfy the query entirely from the index, without needing to access the underlying table. This significantly reduces the amount of data that needs to be read and processed. The following index can be created:

CREATE INDEX my_data__data_id_keep_flag__idx ON my_data (
  data_id, keep_flag
);

With this index in place, SQLite can use it to filter rows based on keep_flag and retrieve the distinct values of data_id directly from the index. This reduces the query execution time from minutes to seconds, as demonstrated in the discussion where a similar approach using a temporary table and covering index yielded results in under 20 seconds.

2. Using a Subselect with GROUP BY for Efficient Distinct Counting

Another approach is to rewrite the query using a subselect with a GROUP BY clause. This method leverages SQLite’s ability to optimize GROUP BY queries, which can be more efficient than COUNT(DISTINCT) in certain scenarios. The rewritten query looks like this:

SELECT COUNT(1)
FROM (
  SELECT 1
  FROM my_data
  WHERE keep_flag = 1
  GROUP BY data_id
);

This query first groups the rows by data_id and then counts the number of groups, which is equivalent to counting the distinct values of data_id. In the discussion, this approach reduced the query execution time to just over 2 minutes with the index and 15 seconds without the index. The performance improvement is due to the fact that the GROUP BY operation can be optimized more effectively than COUNT(DISTINCT).

3. Leveraging Temporary Tables and In-Memory Indexes

For one-off queries or scenarios where creating permanent indexes is not desirable, using temporary tables and in-memory indexes can be a viable solution. This approach involves creating a temporary table that contains only the relevant rows and columns, and then applying an index to the temporary table. The steps are as follows:

1. Create a temporary table with the filtered data:

   CREATE TEMP TABLE temp_data AS
   SELECT data_id
   FROM my_data
   WHERE keep_flag = 1;
   

2. Create an index on the temporary table:

   CREATE INDEX temp_data__data_id__idx ON temp_data (data_id);
   

3. Perform the COUNT(DISTINCT) operation on the temporary table:

   SELECT COUNT(DISTINCT(data_id)) AS num
   FROM temp_data;
   

This method isolates the filtering and counting operations, allowing SQLite to optimize each step independently. In the discussion, this approach resulted in a total execution time of less than 20 seconds, including the time required to create the temporary table and index.

4. Exploring Query-Time Index Creation and Optimizer Behavior

While SQLite does not automatically create query-time indexes, understanding the optimizer’s behavior can help in crafting more efficient queries. The optimizer’s decision to use or avoid an index is based on cost estimates, which may not always align with the actual performance characteristics of the query. In cases where the optimizer’s choices are suboptimal, manually guiding the query execution can yield better results.

For example, forcing SQLite to use a specific index or rewriting the query to make better use of existing indexes can improve performance. However, this requires a deep understanding of the query plan and the underlying data distribution. Tools like EXPLAIN QUERY PLAN can be used to analyze the query execution and identify potential bottlenecks.

5. Considering Filesystem Caching and Storage Performance

Finally, it is important to consider the impact of filesystem caching and storage performance on query execution times. In the discussion, the query execution times varied significantly between SSDs and HDDs, highlighting the role of storage speed in database performance. Ensuring that the database file is stored on a fast storage device and leveraging filesystem caching can help mitigate performance issues.

Additionally, monitoring the database’s interaction with the filesystem and optimizing the storage configuration can further improve query performance. For example, using a database connection with PRAGMA journal_mode = WAL (Write-Ahead Logging) can reduce contention and improve read performance.

Conclusion

Optimizing SELECT COUNT(DISTINCT) queries in SQLite requires a combination of index optimization, query restructuring, and understanding the query optimizer’s behavior. By creating covering indexes, using subselects with GROUP BY, leveraging temporary tables, and considering storage performance, it is possible to achieve significant performance improvements. While SQLite’s query optimizer is powerful, it is not infallible, and manual intervention may be necessary to achieve optimal results in complex scenarios.