» ENGLISH | FRANÇAIS

Translated from French to English with the help of an AI.

• An ordinary table
• An ordinary query
  • Let’s verify what I’m telling you
  • Query performance
• But what’s happening?
• The mystery solved
• Conclusion

I recently discovered a somewhat surprising optimization that can be done with SQLite. But first, what is a covering index? It’s an index that contains all the columns necessary to answer the query without the SQL engine needing to access the table. This obviously saves time. But like any index, we’ll lose time on insertion, as long as we consider that significant for our application, which isn’t a problem in my case.

An ordinary table

There’s nothing special about having covering indexes. But before going further, I’ll present you with a very simple table like you might see in many software applications.

CREATE TABLE data (
  rowid     INTEGER PRIMARY KEY AUTOINCREMENT,
  timestamp TEXT,
  payload   JSON,
  commitId  TEXT DEFAULT NULL
);

CREATE INDEX commitId ON data (commitId);

This table has an index which is the primary key rowid and auto-incremented. The rowid column is special in SQLite because it always exists even if we don’t explicitly declare it in the schema and don’t explicitly request a table without rowid (WITHOUT ROWID).

The goal with this table is that the rowid is never recycled in case of row deletion. By not explicitly declaring an INTEGER PRIMARY KEY column in the schema, it’s entirely possible for a rowid to be reused. For our usage here, we’ll guarantee that the rowid only increments. The rowid being a 64-bit identifier used at the storage level, it’s not an index like others. Data access based on the rowid is much faster and more optimized than with an ordinary index.

An ordinary query

Here’s a query needed in this application. It will count how many rows there are with a rowid greater than the largest rowid that exists for a given commitId. You should understand that the same commitId can appear multiple times in the table; moreover, it’s not a unique index.

SELECT count(*)
FROM data
WHERE rowid > (
  SELECT max(rowid)
  FROM data
  WHERE commitId = 'abcd'
);

Example with some data:

For the commitId abcd, the query will return the value 2 (the rowids 13 and 14 are greater than the largest rowid used by the commitId abcd which is 11).

I think that like me, you find all this quite simple and ordinary. The only particularity of this query is the use of a subquery to retrieve the largest rowid associated with a commitId. You certainly agree with me that this should be quite efficient because the subquery can exploit the commitId index to reduce the amount of data in which to find the max. Moreover, in the application, there are very rarely many rows for the same commitId (less than ten).

Let’s verify what I’m telling you

Using EXPLAIN QUERY PLAN with our SELECT ... we’ll be able to verify that I’m not telling you nonsense.

This seems very good and even wonderful. The subquery indeed uses the commitId index and moreover in covering mode because we don’t access anything other than the index to resolve the condition commitId = 'abcd'. Regarding the condition with rowid > (...) we access the primary key index. We can imagine that it’s very performant because we directly use the rowid of the SQLite table.

Query performance

Let’s then take a look at performance with a table that contains about 200,000 rows and a commitId that is located almost in the middle of it. There are only 3 rows (with the subquery) for this commitId.

$ sqlite3 data.db
SQLite version 3.46.1 2024-08-13 09:16:08
Enter ".help" for usage hints.
sqlite> .timer on
sqlite> SELECT count(*)
FROM data
WHERE rowid > (
  SELECT max(rowid)
  FROM data
  WHERE commitId = '81b5f0ae-7f4a-4db2-ae3f-dea5bd35e0ad'
);
93356
Run Time: real 0.031 user 0.007897 sys 0.023278
sqlite> SELECT count(*) ...
93356
Run Time: real 0.038 user 0.007570 sys 0.030460
sqlite> SELECT count(*) ...
93356
Run Time: real 0.038 user 0.003727 sys 0.033857
sqlite> SELECT count(*) ...
93356
Run Time: real 0.033 user 0.011919 sys 0.020516

The .timer on instruction enables a timer for each executed query. Here’s what emerges:

I don’t know what you think about it, but I’m not satisfied with the result. I can execute this query dozens of times, it never goes below 30 ms. Don’t you find that it’s a bit slow? There aren’t that many rows, the schema is simple, the queries are simple, the query planner is satisfied.

But what’s happening?

That’s an excellent question and it’s the whole subject of this article. There’s a way to drastically improve the performance of this query. Here’s a measurement with the change that I’ll present to you below (don’t jump directly to the end of the article, try to imagine how to improve the performance of this SELECT by going back to review the schema and what the query planner said).

$ sqlite3 data.db
SQLite version 3.46.1 2024-08-13 09:16:08
Enter ".help" for usage hints.
sqlite> .timer on
sqlite> SELECT count(*)
FROM data
WHERE rowid > (
  SELECT max(rowid)
  FROM data
  WHERE commitId = '81b5f0ae-7f4a-4db2-ae3f-dea5bd35e0ad'
);
93356
Run Time: real 0.002 user 0.000577 sys 0.001397
sqlite> SELECT count(*) ...
93356
Run Time: real 0.002 user 0.000456 sys 0.001106
sqlite> SELECT count(*) ...
93356
Run Time: real 0.005 user 0.004119 sys 0.000222
sqlite> SELECT count(*) ...
93356
Run Time: real 0.004 user 0.004134 sys 0.000268

We go from more than 30 ms to a few milliseconds. To understand what’s happening here, we need to re-examine what the query planner told us earlier and especially the first line SEARCH data USING INTEGER PRIMARY KEY (rowid>?). Here it’s not said that SQLite will use a covering index, but only that SQLite will use the index on the primary key. But ultimately, what does that mean in this case?

This primary key is not an ordinary index because it’s the identifier that allows finding a record in the table. Which means you have to access the table to access this key. It’s very performant if you want to extract a record from the table like for example with a simple SELECT * FROM data WHERE rowid = 101256;. A SELECT of this type must necessarily go fetch the data and it’s better to know the identifier directly and not waste time with an intermediate index.

But what to do for the SELECT count(*) ...? We need a covering index. Thus SQLite won’t access the storage pages to find the rowids. Not accessing storage avoids loading the other columns of the table. If you look carefully at the schema, there’s a payload column. This column can contain large JSON documents. It’s a rather heavy column and here, it’s sufficient to make the query less efficient even though we’re not interested in the payload at all.

The mystery solved

CREATE INDEX rowId ON data (rowId);

OMG ?! 😱

We’re creating an index on top of a primary key. Have we gone mad? Even the Great Richard Hipp (author of SQLite) tells us:

(2) By Richard Hipp (drh) on 2020-09-26 18:18:07 in reply to 1

An INTEGER PRIMARY KEY becomes the actual key used in the B-tree that stores your table. So no index is required for efficient operation.

You should always omit indexes on PRIMARY KEY columns, regardless of the type. The best case for an index on a PRIMARY KEY is that it will be a no-op. The worst case is that it will make things run slower. So avoid the worst-case and just leave it off.

– https://sqlite.org/forum/info/8876e4e648bf8f93

Let’s see what the query planner tells us…

Now it’s indeed the covering index that’s being used. We’re then faced with a case where adding an index on top of a primary key will drastically improve the performance of this SELECT.

Note that if I remove the payload column and retest the query without the covering index on rowid, I get about 9 ms instead of more than 30 ms.

Conclusion

What you should remember is that with an INTEGER PRIMARY KEY, SQLite must load complete pages (with payload). But with the covering index, SQLite only reads the lightweight index.

These different experiments show a little-known particularity of the SQLite engine. We can probably consider this behavior as an edge case with subtleties between the query optimizer, covering indexes and aggregation operations with large volumes. I won’t advise you to do it, but I encourage you to inspect and measure your queries with and without this index that nevertheless seems ill-advised.