Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Subtleties of SQLite Indexes

emschwartz.me

Post reply on HN
Print view View original

31–40 of 63 posts

Re: Subtleties of SQLite Indexes

#31

Post by Waterluvian »

kccqzy wrote: post #12

> It's worth being careful to only add indexes that will be used by real queries. This reminds me of a technique used by Google App Engine SDK a long time ago before it was called cloud. Basically in development mode, the SDK captures the kind of queries you make, and then automatically add any index that would speed up this query into a configuration file. You then later deploy with this configuration file, which te…

This seems like the kind of tool that would be useful for all indexable databases.

I imagine you can’t definitively know and therefore just make this automagical. But I bet the result is a pretty solid shortlist for consideration.

Re: Subtleties of SQLite Indexes

#32

Post by Sesse__ »

lelandbatey wrote: post #28
ComputerGuru wrote: post #10

Earlier quoted context omitted.

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 +----------------+ +----------------+ +---------------…

The key thing is "an index is a flattened tree", and for all us devs who haven't thought about trees in many years or younger folks who might not yet know, that means it's conceptually a bunch of nested maps/objects/dictionaries where the keys at each "level" are the columns in that same "level" of the index. To use a little bit of python, here's a list of the raw maps in your ascii art DB: [ {"date": 10, "color": "r…

Indexes in general are not flattened trees; they are just trees. Using a Python map as a mental model is fraught with peril since those are implemented as hash tables, which don't have ordering (which most database indexes need to support). So it's the wrong model.

For multidimensional indexes, you don't need to do anything fancy about nesting; you just need to have keys that have more than one component. To a first order, string concatenation is a good enough model. So in your case, here's what the index looks like:

    ['10 red',   101],
    ['11 blue',  111],
    ['12 green', 121],
    ['13 red',   131],
    ['14 blue',  141],
    ['14 red',   142],
    more values…
which is then organized in some sort of tree structure, like (the exact details don't matter):

    ['10 red', '12 green',  # min and max values for the tree below
      [
        ['10 red',   101],
        ['11 blue',  111],
        ['12 green', 121]
      ]],
    ['13 red', '14 red',    # similar
      [
        ['13 red',   131],
        ['14 blue',  141],
        ['14 red',   142]
      ]],
    more nodes…

Re: Subtleties of SQLite Indexes

#33

Post by Sesse__ »

immibis wrote: post #19
nikeee wrote: post #3

I use the mental model of nested maps for "column order matters". For example, an index "published, low_quality_probability, lang" is just a Map >> in my mental model. These maps are ordered by the order the index possesses. That explains why column order matters and why one cannot skip columns and why it stops at range queries. Just imagine getting a final rowId from these nested maps and you'll see why the index wo…

It's actually a List >> in sorted order, and queries are more akin to binary search (they are not actually binary but use a wider fanout depending on many factors)

It's _not_ just a list in sorted order; if it were, you could not insert efficiently into it. But the tuple is the right mental model, indeed.

Re: Subtleties of SQLite Indexes

#34

Post by emschwartz »

kccqzy wrote: post #12

> It's worth being careful to only add indexes that will be used by real queries. This reminds me of a technique used by Google App Engine SDK a long time ago before it was called cloud. Basically in development mode, the SDK captures the kind of queries you make, and then automatically add any index that would speed up this query into a configuration file. You then later deploy with this configuration file, which te…

The SQLite CLI has a `.expert` command that will give index recommendations when you run queries: https://sqlite.org/cli.html#index_recommendations_sqlite_exp...

It's not quite the same as capturing all of the queries used in development (or production), but it seems somewhat useful.

I'll also note that I had an LLM generate quite a useful script to identify unused indexes (it scanned the code base for SQL queries, ran `EXPLAIN QUERY PLAN` on each one to identify which indexes were being used, and cross-referenced that against the indexes in the database to find unused ones). It would probably be possible to do something similar (but definitely imperfect) where you find all of the queries, get the query plans, and use an LLM to make suggestions about what indexes would speed up those queries.

Re: Subtleties of SQLite Indexes

#35

Post by andersmurphy »

emschwartz wrote: post #25
wodenokoto wrote: post #23

The article is a developers journey into indexes and not a bad journey or travelogue imho. Sure, if you are a database expert, it might be disappointing but I enjoyed reading it.

Thanks for saying that! That’s exactly how it was intended and I’m glad to hear you enjoyed it

Fun read.

I've been tripped up by the where in partial indexes before. Same goes for expression indexes.

Re: Subtleties of SQLite Indexes

#36

Post by crazygringo »

Ameo wrote: post #30
crazygringo wrote: post #13

Earlier quoted context omitted.

> The main takeaway from this for me is that SQLite’s query planner seems to be pretty limited. This doesn't appear to be true at all. The order of WHERE conditions does not matter; the order of columns in an index does. Everything you're describing is pretty much just how indexes fundamentally work in all databases. Which is why you're saying it hasn't been "solved" by anyone. Indexes aren't magic -- if you understa…

(copying my reply from the other comment that said the same thing as you) The order of conditions in a WHERE definitely does matter, especially in cases where the conditions are on non-indexed columns or there are CPU-intensive search operations like regex, string ops, etc. I just ran this test locally with a table I created that has 50 million rows: ``` » time sqlite3 test.db "select count( ) from test WHERE a != 'a…

Sorry, I should have clarified -- the order of WHERE conditions doesn't matter for whether an index is utilized. I thought that was the context of the original comment, but now I realize maybe it was unclear.

Yes, of course you can skip evaluating other conditions if an AND fails and that can affect speed. So that's the same as most programming languages.

Re: Subtleties of SQLite Indexes

#37

Post by emschwartz »

andersmurphy wrote: post #35
emschwartz wrote: post #25

Earlier quoted context omitted.

Thanks for saying that! That’s exactly how it was intended and I’m glad to hear you enjoyed it

Fun read. I've been tripped up by the where in partial indexes before. Same goes for expression indexes.

Thank you for saying that too!

Hope this explanation helped explain why, at least a little bit.

Re: Subtleties of SQLite Indexes

#38

Post by jasonwatkinspdx »

masklinn wrote: post #22
nikeee wrote: post #3

I use the mental model of nested maps for "column order matters". For example, an index "published, low_quality_probability, lang" is just a Map >> in my mental model. These maps are ordered by the order the index possesses. That explains why column order matters and why one cannot skip columns and why it stops at range queries. Just imagine getting a final rowId from these nested maps and you'll see why the index wo…

It’s way easier if you think of the indexes as tuple keys in a binary tree. Because they’re tuple keys in a b-tree. That also explains how ranges work efficiently.

Yeah, if you're going to work with databases regularly I think it's worth learning how b-trees work. It'll make a lot of things much more intuitive.

If you wanna get a very complete grounding in how the big rdbmses work, Andy Pavlo's lectures and class notes are fantastic.

Re: Subtleties of SQLite Indexes

#39

Post by simscitizen »

ComputerGuru wrote: post #4

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 f…

I agree, all of these rules aren't the right way to teach about how to reason about this. All of the perf properties described should fall out of the understanding that both tables and indices in SQLite are B-trees. B-trees have the following properties:

- can look up a key or key prefix in O(log N) time ("seek a cursor" in DB parlance, or maybe "find/find prefix and return an iterator" for regular programmers)

- can iterate to next row in amortized O(1) time ("advance a cursor" in DB parlance, or maybe "advance an iterator" for regular programmers). Note that unordered data structures like hash maps don't have this property. So the mental model has to start with thinking that tables/indices are ordered data structures or you're already lost.

A table is a b+tree where the key is the rowid and the value is the row (well, except for WITHOUT ROWID tables).

An index is a b-tree where the key is the indexed column(s) and the value is a rowid.

And SQLite generally only does simple nested loop joins. No hash joins etc. Just the most obvious joining that you could do if you yourself wrote database-like logic using ordered data structures with the same perf properties e.g. std::map.

From this it ought to be pretty obvious why column order in an index matters, etc.

Re: Subtleties of SQLite Indexes

#40

Post by jasonwatkinspdx »

immibis wrote: post #21
setr wrote: post #18

Earlier quoted context omitted.

Clickhouse isn’t fast at table scans, it’s just columnar. Indexes are basically a maintained transform from row storage to column storage; columnar databases are essentially already “indexed” by their nature (and they auto-apply some additional indexes on top, like zone maps). It’s only fast for table-scans in the sense that you probably aren’t doing a select * from table, so it’s only iterating over a few columns of…

Columnar databases are not "already "indexed"". Their advantage instead comes from their ability to only load the relevant parts of rows when doing scans.

"The indexes are the database" is a common perspective in column database implementations because it works quite well for ad hoc OLAP.
Post reply on HN