Live data from Hacker News

Subtleties of SQLite Indexes

emschwartz.me

41–50 of 63 posts

Re: Subtleties of SQLite Indexes

#41
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…

Every index you add uses a whole lot more disk space (a big deal) and slows down writes (usually not a big deal).

The idea of a tool automatically adding indexes scares me a little.

Sometimes you specifically want a query to take 0.003s instead of 0.001 because you don't want to use another 10GB of disk space.

Re: Subtleties of SQLite Indexes

#42
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…

[deleted]

Re: Subtleties of SQLite Indexes

#43

Earlier quoted context omitted.

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.

I definitely second Andy Pavlo's lectures.

Re: Subtleties of SQLite Indexes

#44
post #32

Earlier quoted context omitted.

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…

Yes, this is true. I chose a nested-maps example because while it is inaccurate for actual DB applications, it's very helpful for explaining the limits of index ordering and the limits that range queries have when interacting with indexes. It's helpful to use maps as a first explanation because they're one of the most used datastructures that nearly all languages have built in (yes, I know, C, I'm talking about the other 9 of top 10 languages), and many work-a-day developers and dabblers will use nearly _only_ lists and maps (and objects/classes/structs) in their language of choice. I could've used Python's OrderedDict but I figured if I was going to stray away from "the most straightforward possible case using the datastructures everyone is already using daily", I'd have been better off jumping straight to a custom tree, like you've done.

That's a great miniature example of such a tree!

Re: Subtleties of SQLite Indexes

#45

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…

The non-equivalence of .9 and 0.9 was certainly a surprise to me.

Re: Subtleties of SQLite Indexes

#46

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…

> 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).

You're phrasing that like this situation — relying on an index formed by (key 1 that you know, key 2 that you don't know, key 3 that you want to depend on) — necessarily implies a sequential walk of everything within the HR manager subgroup.

But it doesn't; within each key-1 partition of the index, you can binary-search to find the boundaries of the key-2 partitions; and within those, you can binary-search to find the all (or, more commonly, the first) last_name[0] = "J" entry/entries. It's actually not overly slow (i.e. is often still a win over a naive index-partial seq scan) if the cardinality ratio of of key-2 : key-3 isn't too extreme (i.e. if you're saving useful amounts of time by eliminating enough key-3 entries from consideration per key-2 partition.)

(We use this approach quite a bit at $WORK — MySQL and Postgres people like to call this a https://wiki.postgresql.org/wiki/Loose_indexscan. [See the "Making use of a non-leading column of an index" section.])

Re: Subtleties of SQLite Indexes

#47

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…

The non-equivalence of .9 and 0.9 was certainly a surprise to me.

Yeah, but who ever writes "x=0.9" as a constraint on a partial index? Really? Don't you know you aren't suppose to compare floating point quantities for equality?

If P is the expression on the partial index and Q is the WHERE clause of the query, then the partial index is only usable if Q implies P for all possible assignments of variables. A theorem prover is needed to establish this. Every RDBMS has one. The one inside SQLite is not terribly bright, true enough. It leans toward usually little memory and few CPU cycles. It does not do a good job if P contains "x=0.9". On the other hand, SQLite's theorem prover is decent if P contains "x IS NOT NULL", because in actual practice, probably about 90% of partial index WHERE clauses are some variation on "x IS NOT NULL".

The partial index expression does not always have to be exactly the same as what is in the WHERE clause of the query. SQLite will always find the match if P is a subset of Q; if Q can be rewritten as "R AND P". But if P is "x IS NOT NULL" and Q does anything that restricts x from being NULL, for example if Q contains "x>0", then SQLite's theorem prover will find that match too, even if "IS NOT NULL" never appears in Q.

Will the theorem prover in SQLite get better someday? Perhaps. It has gotten better over the years. The question becomes, how much more code space and query-planning CPU cycles are you willing to spend to get a slightly better query planner? This trade-off is different for a client/server database engine. With SQLite being embedded, the trade-off tends to fall more on the side of "keep it simple". If you have followed SQLite over many years, you might have noticed it is shifting toward more complex decision making as memory becomes cheaper and CPUs get faster. It's a tricky balancing act to find the sweet spot.

Re: Subtleties of SQLite Indexes

#48
post #19
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)

Yeah it might be closer to what's actually happening but it doesn't make it obvious why something doesn't work. The map model doesn't even cover non-unique indices. Or different type of indexes.

Re: Subtleties of SQLite Indexes

#49
post #21
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.

They’re indexed in the sense that they’re already halfway to the structure of an index — which is why they’re happy to toss indexes on top arbitrarily, instead of demanding the user to manage a minimum subset.

Re: Subtleties of SQLite Indexes

#50
post #47

Earlier quoted context omitted.

The non-equivalence of .9 and 0.9 was certainly a surprise to me.

Yeah, but who ever writes "x=0.9" as a constraint on a partial index? Really? Don't you know you aren't suppose to compare floating point quantities for equality? If P is the expression on the partial index and Q is the WHERE clause of the query, then the partial index is only usable if Q implies P for all possible assignments of variables. A theorem prover is needed to establish this. Every RDBMS has one. The one in…

> Yeah, but who ever writes "x=0.9" as a constraint on a partial index?

Not me! But you have me curious now; does sqlite do a text comparison for the constraint? Surely (maybe not) 0.9 == .9?

Can you do a constraint as (int)(100 * x) PS. Thanks for sqlite!

Post reply on HN