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

51–60 of 63 posts

Re: Subtleties of SQLite Indexes

#51

Post by rtpg »

Postgres is pretty good about using index data from multiple single column indices... if you don't order results! Otherwise the planner will get in the way and do nonsense.

A bunch of people spend years studying computer science and trees etc, and then when we actually need to care about that stuff the databases absolutely do not want us to declare the plan. Very annoying.

Think about how people would be guided to do the right thing on indices if they had to say "go along this index to get my data" in a "planned mode" when dealing with bad performance? So many data layout and index issues would become immediately obvious. You wouldn't magically get as many benefits from DB updates, granted.

Re: Subtleties of SQLite Indexes

#52

Post by zeroq »

emschwartz wrote: post #34
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, r…

wow!

I used to bruteforce a bunch of indexes until EXPLAIN on queries gave satisfactory results!

I actually looked for a tool where I could provide a schema and all queries to get optimal indexes but never found one that actually worked.

Re: Subtleties of SQLite Indexes

#53

Post by SQLite »

emmelaich wrote: post #50
SQLite wrote: post #47

Earlier quoted context omitted.

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!

The top-level routine is here: https://sqlite.org/src/info/aae36a5fbd17?ln=6767-6818>. Small (32-bit) integer literals are compared numerically, here: https://sqlite.org/src/info/aae36a5fbd17?ln=6526>. They don't have to exactly match. So if you say "x=0x123" in the WHERE clause of the partial index and "x=291" in the WHERE clause of the query, and that will still work. However, 64-bit integer literals and floating-point literals are compared using strcmp(), here: https://sqlite.org/src/info/aae36a5fbd17?ln=6570>, so they do need to match exactly, at least in the current implementation. Maybe that is something I should work on...

Re: Subtleties of SQLite Indexes

#54

Post by SkiFire13 »

setr wrote: post #49
immibis wrote: post #21

Earlier quoted context omitted.

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.

What does it even mean to be "halfway" to the structure of an index? Do they allow filtering a subset of rows with a complexity that's less than linear in the total number of rows or not?

Re: Subtleties of SQLite Indexes

#55

Post by Dylan16807 »

derefr wrote: post #46
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…

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

Looking at the documentation, MySQL definitely has this feature now.

I don't think it understands when to use it.

I have a table where the primary key (A,B) is two integers. The first one is a single byte and only has a dozen distinct values. Any query I do based on just B ends up doing a table scan and being extremely slow. But if I add "WHERE A IN (1,2,3,4,5,6,7,8,9,10,11) AND" suddenly it's super fast.

So I'm stuck with a redundant index on just B if I don't want to add that cruft all over.

Anyway, yes, optimization is often possible in this kind of situation but don't trust your database engine to figure it out.

Re: Subtleties of SQLite Indexes

#56

Post by ComputerGuru »

derefr wrote: post #46
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…

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

Well, yes, I omitted anything that may or may not happen to explain the general principle. Cardinality-based optimizations can and do take place, but they depend on the db being aware of the shape of your data (you need to analyze the tables often) and depend on internal factors and heuristics that are subject to change between releases, can't be assumed across different databases, and may or may not actually speed up the query (pathological cases certainly exist, even in the real world).

Re: Subtleties of SQLite Indexes

#57

Post by setr »

SkiFire13 wrote: post #54
setr wrote: post #49

Earlier quoted context omitted.

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.

What does it even mean to be "halfway" to the structure of an index? Do they allow filtering a subset of rows with a complexity that's less than linear in the total number of rows or not?

A row-based index is a column-wise copy of the data, with mechanisms to skip forward during scanning. You maintain a separate copy of the column to support this, making indexes expensive, and thus the DBA is asked to maintain a minimal subset.

A columnar database’s index is simply laid out on top of the column data. If the column is the key, then it’s sorted by definition, and no index is really required outside of maybe a zone map, because you can binary search. A non-key column gets a zone map / skip index laid out on top, which is cheap to maintain… because it’s already a column-wise slice of the data.

You don’t often add indexes to an OLAP system because every column is indexed by default — because it’s cheap to maintain, because you don’t need a separate column-wise copy of the data because it’s already a column-wise copy of the data.

Re: Subtleties of SQLite Indexes

#58

Post by SkiFire13 »

setr wrote: post #57
SkiFire13 wrote: post #54

Earlier quoted context omitted.

What does it even mean to be "halfway" to the structure of an index? Do they allow filtering a subset of rows with a complexity that's less than linear in the total number of rows or not?

A row-based index is a column-wise copy of the data, with mechanisms to skip forward during scanning. You maintain a separate copy of the column to support this, making indexes expensive, and thus the DBA is asked to maintain a minimal subset. A columnar database’s index is simply laid out on top of the column data. If the column is the key, then it’s sorted by definition, and no index is really required outside of m…

> A non-key column gets a zone map / skip index laid out on top, which is cheap to maintain… because it’s already a column-wise slice of the data.

I don't see how that's different from storing a traditional index. You can't just lay it on top of the column, because the column is stored in a different order than what the index wants.

Re: Subtleties of SQLite Indexes

#59

Post by setr »

SkiFire13 wrote: post #58
setr wrote: post #57

Earlier quoted context omitted.

A row-based index is a column-wise copy of the data, with mechanisms to skip forward during scanning. You maintain a separate copy of the column to support this, making indexes expensive, and thus the DBA is asked to maintain a minimal subset. A columnar database’s index is simply laid out on top of the column data. If the column is the key, then it’s sorted by definition, and no index is really required outside of m…

> A non-key column gets a zone map / skip index laid out on top, which is cheap to maintain… because it’s already a column-wise slice of the data. I don't see how that's different from storing a traditional index. You can't just lay it on top of the column, because the column is stored in a different order than what the index wants.

Zonemap / skip indexes don’t require sorting, still provide significantly improved searching over full tablescans, and typically applied to every column by default. Sorting is even better, just at the cost of a second copy of the dataset.

In a row-based rdbms, any indexing whatsoever is a copy of the column-data, so you might as well store it sorted every time. It’s not inherent to the definition.

Re: Subtleties of SQLite Indexes

#60

Post by joelwallis »

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 wouldn’t say it’s so intuitive. We need more of these articles coming in — I learned nice things from this text, specially about the exact match over partial indexes, and to always QUERY EXPLAIN instead of assuming you’re right (my case haha).

What’s obvious for you might not be for someone else.

Post reply on HN