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

11–20 of 63 posts

Re: Subtleties of SQLite Indexes

#11

Post by SkiFire13 »

Ameo wrote: post #6

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…

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

There's only so much you can do with this approach due how to the algorithmic complexity scales as more joins are added. At some points you'll need some additional data structures to speed things up, though they not be indexes in name (e.g. materialized views)

Re: Subtleties of SQLite Indexes

#12

Post by kccqzy »

> 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 tells the production data store to create such indexes. I thought this was a genius idea. Not sure if something similar exists for SQLite.

Re: Subtleties of SQLite Indexes

#13

Post by crazygringo »

Ameo wrote: post #6

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…

> 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 understand how they work as a tree, it becomes very clear what can be optimized and what can't.

It is true that occasionally query planners get it wrong, but it's also often the case that your query was written in a non-obvious way that is equivalent in terms of its formal results, but is not idiomatic -- and making it more idiomatic means the query planner can more easily understand which indexes to use where.

Re: Subtleties of SQLite Indexes

#14

Post by crazygringo »

I agree with other commenters that there's nothing new or surprising here [1] if you actually understand how indexes work. Which, if you're working in SQL, you should.

But the main takeaway, I disagree with. The author explains:

> When I first set up Scour's database, I put a bunch of indexes on the items table without really thinking about whether they would help. For example, I had separate indexes on the published date, the language, and the quality rating. Useless. It's more important to have one or a small handful of good composite indexes on multiple columns than to have separate indexes on each column.

Yes, the biggest error is throwing indexes at a table without having the slightest idea if they're helpful. But the idea that a smaller number of composite indexes is not the answer either.

The answer is to go through every single query and make sure you have an index that matches the query, adding/changing indexes (including composite indexes) or rewriting queries as required.

Indexes don't exist in a vacuum. They are optimizations for specific queries. Proper database design requires knowing exactly what information you will need to look up using which parameters, and designing the tables and indexes to produce that performantly. When you need to look up data in new ways, you often need to add new indexes or rearchitect tables entirely.

[1] Except that the partial index match condition treats 0.9 and .9 as different. That is unexpected to me, but it is kind of in the docs at "The terms in W and X must match exactly": https://www.sqlite.org/partialindex.html

Re: Subtleties of SQLite Indexes

#15

Post by [deleted] »

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…

[deleted]

Re: Subtleties of SQLite Indexes

#16

Post by DaiPlusPlus »

crazygringo wrote: post #14

I agree with other commenters that there's nothing new or surprising here [1] if you actually understand how indexes work. Which, if you're working in SQL, you should. But the main takeaway, I disagree with. The author explains: > When I first set up Scour's database, I put a bunch of indexes on the items table without really thinking about whether they would help. For example, I had separate indexes on the published…

> Yes, the biggest error is throwing indexes at a table without having the slightest idea if they're helpful

Unless you have a small number of static queries, this task isn’t really possible without an observability-solution (reporting the raw query text, the actual execution plan, and runtime and IO stats, et cetera) - otherwise it’s guesswork.

…and worse-still if your application has runtime-defined queries, such as having a custom filter builder in your UI. Actually I’ll admit I have no idea how platforms like Jira are able to do that with decent performance (can anyone let me know?)

I heap praise on MSSQL’s Query Store feature - which is still a relatively recent addition. I have no idea how anyone could manage query performance without needing 10x the time and effort needed to attach a profiler to a prod DB. …and if these are “edge” databases running on a 100k IoT devices then have fun, I guess.

Re: Subtleties of SQLite Indexes

#17

Post by crazygringo »

DaiPlusPlus wrote: post #16
crazygringo wrote: post #14

I agree with other commenters that there's nothing new or surprising here [1] if you actually understand how indexes work. Which, if you're working in SQL, you should. But the main takeaway, I disagree with. The author explains: > When I first set up Scour's database, I put a bunch of indexes on the items table without really thinking about whether they would help. For example, I had separate indexes on the published…

> Yes, the biggest error is throwing indexes at a table without having the slightest idea if they're helpful Unless you have a small number of static queries, this task isn’t really possible without an observability-solution (reporting the raw query text, the actual execution plan, and runtime and IO stats, et cetera) - otherwise it’s guesswork. …and worse-still if your application has runtime-defined queries, such a…

It's not guesswork at all. It basically just requires knowing what it is allowed to look up rows by. Execution plans generally aren't rocket science. And if someone messes up in writing their query, yes that should show up in query execution time stats. You don't need 10x anything to track average query times and spot outliers.

For runtime-defined queries, those are obviously not going to have global indexes if there are more than a couple possible fields. But as long as you're only iterating over, say, 10K rows that an index can determine belong to that customer, and this query is happening once per page rather than 200 times per page, that's fine. That's why you can search over 10K bug reports for a project without a problem, because they only belong to a specific project. You're not searching all 100M bug reports belonging to all clients.

Re: Subtleties of SQLite Indexes

#18

Post by setr »

SkiFire13 wrote: post #11
Ameo wrote: post #6

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…

> 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. There's only so much you can do with this approach due how to the algorithmic complexity scales as more joins are added. At some points you'll need some additional data structures to speed things up, though they not be indexes in na…

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 data, whereas SQLite would end up iterating over literally everything — a table-scan doesn’t really mean the same thing between the two (a columnar database’s worst fear is selecting every column; a row-base database wants to avoid selecting every row)

Their problem is instead that getting back to a row, even within a table, is essentially a join. Which is why they fundamentally suck at point lookups, and they strongly favor analytic queries that largely work column-wise.

Re: Subtleties of SQLite Indexes

#19

Post by immibis »

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)

Re: Subtleties of SQLite Indexes

#20

Post by immibis »

DaiPlusPlus wrote: post #16
crazygringo wrote: post #14

I agree with other commenters that there's nothing new or surprising here [1] if you actually understand how indexes work. Which, if you're working in SQL, you should. But the main takeaway, I disagree with. The author explains: > When I first set up Scour's database, I put a bunch of indexes on the items table without really thinking about whether they would help. For example, I had separate indexes on the published…

> Yes, the biggest error is throwing indexes at a table without having the slightest idea if they're helpful Unless you have a small number of static queries, this task isn’t really possible without an observability-solution (reporting the raw query text, the actual execution plan, and runtime and IO stats, et cetera) - otherwise it’s guesswork. …and worse-still if your application has runtime-defined queries, such a…

People who are deeper into databases differentiate between OLTP and OLAP workloads. OLTP - on-line transaction processing - mostly consists of a finite set of queries that each access a small amount of data, like you when you pay a bill at a bank. OLAP - on-line analytical processing - consists of mostly summaries of large amounts of data which can be ad-hoc, like the banker who wants to know the total transactions for the day. The two kinds of workloads are very different - so much so that some systems even periodically export the whole transaction database and re-import into a separate analytics DBMS designed for OLAP work.
Post reply on HN