Subtleties of SQLite Indexes

> multiple indices

Yes, sqlite uses only one index per table in FROM clause... Except for when it can use the OR optimization [1]

> Left to right, no skipping, stops at the first range

I don't know if we need a soundbite for this, nor is it sqlite specific. This is a direct consequence of the fact that indexes are basically just sorted lists you can binary search over. They are sorted left to right (you have to choose some order anyhow) meaning all the other orderings cannot avail of the speedup, and thus sqlite chooses to not use it.....

Except if left column of index is measured to be low cardinality by ANALYZE [2]'s output in the sqlite_stats table, in which case it is ok to scan over it and then binary search right column. More at skip-scan optimization [3].

[1] https://www.sqlite.org/optoverview.html#evaluating_or_constr...

[2] https://www.sqlite.org/lang_analyze.html

[3] https://www.sqlite.org/optoverview.html#the_skip_scan_optimi...

Not a great article; I clicked expecting something super technical about SQLite internals and found a mix of rdbms basics and some misconceptions. The limitations in the blog post aren't really specific to SQLite (for the most part), they're just how indexes (indices) and database engines work across the board. And some of the things phrased as "SQLite [can't] do this" is stuff that wouldn't make sense to do in the first place.

If you understand what (multi-column) indexes are at the lowest level (i.e. what data structure they represent, how they are used by the database, what the code reading them would look like) then all of this makes immediate and natural sense. Indexes aren't magic. They're just a shortcut to help the the db engine find your data more effectively.

This doesn't require super complex understanding of data structures, btw. The same limitations and advice would apply if you were trying to, for example, search a stack of resumes sorted by one or more attributes. If you have them sorted by position, years of experience, and applicant's last name; you wouldn't be able to quickly grab all resumes for the HR Manager position that have a last name starting with J - after all, you sorted them by years of experience first! It's physically not possible! You can only use the first part of that index, the position, to jump to HR Manager resumes; then you would need to manually go through them one-by-one to grab only the ones starting with J for each years-of-experience subgroup (if any).

The main takeaway from this for me is that SQLite’s query planner seems to be pretty limited. It’s reliant on stuff like the order in which WHERE conditions are specified, isn’t able to use multiple indexes in queries in many cases, bails out to scans when a variety of different operations show up in queries, etc.

It might be the case that SQLite has a simpler or less sophisticated query planner than other databases like Postgres or MariaDB, but in my experience those DBs struggle a lot with good querying planning as well. I’ve spent many hours in the past with issues like Postgres suddenly starting to ignore an index entirely because its computed table data distribution statistics got out of balance, or having to add manual annotations to MariaDB queries like STRAIGHT_JOIN in order to get a query to run faster.

I’m guessing that this is a really hard problem since it doesn’t seem to be really “solved” by any major DB vendor I’ve seen. A lot of modern DB engines like Clickhouse tend to just work around this problem by being so fast at full table scans that they don’t even need any sophisticated indexing set up at all.

The fact that it stops at the first range isn't intuitive to me at all, and I've been using sqlite for 20 years now.

Given a covering index on (thing_date, thing_color)

I would think a scan would not be needed for the query:

select thing_date, thing_color where thing_date date and thing_color = 'blue'

I also can't think of a reason this is the case given the underlying data structures.

It's a flattened tree, and you've used the index to reach a point where you have multiple child nodes that meet the precondition thing_date I asked an llm to give me an ascii representation so it'll be easier to see what I mean; consider the case where you want thing_date

           Root (internal)
           +---------------------+
           | keys: 14     17     |
           +----+--------+--------+
                |        |        |
                v        v        v
   +----------------+ +----------------+ +----------------+
   | Leaf P0        | | Leaf P1        | | Leaf P2        |
   | (dates 10-13)  | | (dates 14-16)  | | (dates 17-20)  |
   |----------------| |----------------| |----------------|
   | 10 | red   |101 | | 14 | blue  |141| | 17 | green |171|
   | 11 | blue  |111 |*| 14 | red   |142| | 18 | blue  |181|
   | 12 | green |121 | | 15 | yellow|151| | 19 | red   |191|
   | 13 | red   |131 | | 16 | blue  |161|*| 20 | green |201|
   +----------------+ +----------------+ +----------------+

Go back to my resume's example: you have the resumes sorted by application timestamp (chronologically) and position (alphabetically). You want to find all resumes received last Tuesday where position was "Senior Architect". You literally can't skip to the point where the next n consecutive results will be the results you seek, because you can't temporarily re-order them and within the subset of resumes where date > monday and date One important thing to keep in mind is that a SCAN is not the end of the world. You know your data and you know when it's ok (you expect most of the results to match and a few to be filtered out, in which case you're really not saving much time anyway) and when it's not (the scan will cover a huge range that contains only a few, widely interspersed results and you have no way of terminating early).

EDIT: In response to your exact question however, note that with a covering index you might not end up with a SCAN (i.e. you don't hit the table) even though it uses only the partial index (thing_date) and not (thing_date, thing_color)! It's still possible for it to avoid hitting the backing table and might return the results directly from the index - something it wouldn't have been able to do if the index was only (thing_date).