Subtleties of SQLite Indexes • Hacker News Board

Re: Subtleties of SQLite Indexes

#61

Post by SkiFire13 » Sat, Oct 04, 2025, 10:20 AM UTC

setr wrote: post #59

SkiFire13 wrote: post #58

Earlier quoted context omitted.

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

> Zonemap / skip indexes don’t require sorting

That's still a separate index though, no? It's not intrinsic in the column storage itself, although I guess it works best with it if you end up having to do a full-scan of the column section anyway.

> 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 the same thing, no?

Re: Subtleties of SQLite Indexes

#62

Post by setr » Sat, Oct 04, 2025, 6:07 PM UTC

SkiFire13 wrote: post #61

setr wrote: post #59

Earlier quoted context omitted.

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.

> Zonemap / skip indexes don’t require sorting That's still a separate index though, no? It's not intrinsic in the column storage itself, although I guess it works best with it if you end up having to do a full-scan of the column section anyway. > 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 the same thi…

I’m not saying columnar databases don’t have indexes, I’m saying that they get to have indexes for cheap (and importantly: without maintaining a separate copy of the data being indexed), to the point that every column is indexed by definition. It’s a separate data structure, but it’s not a separate db object exposed to the user — it’s just part of the definition

> So the same thing, no? Consider it as like: for a given filtered-query, a row-based storage is doing a table-scan if no index exists. There is no middle ground. Say 0% value or 100%.

A columnar database’s baseline is a decent index, and if there’s a sorted index then even better. Say 60% value vs 100%.

The relative importance of having a separate, explicit, sorted index is much lower in a columnar database, because the baseline is different. (Although maintaining extra sorted indexes is a columnar database is much more expensive — you basically have to keep a second copy of the entire table sorted on the new key(s))

Re: Subtleties of SQLite Indexes

#63

Post by rstuart4133 » Sun, Oct 05, 2025, 11:30 AM UTC

some_old_guy wrote: post #8

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…

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.

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

Ditto.

I suspect like me you are already familiar the underlying data structures. I'm now wondering why they wouldn't do use the B*Tree to search for thing_color. It's downright odd.

Granted in your example, assuming there are only a few colours, it would not be a big win. That's because all the colours for one date would likely fit in one B*Tree Node, which would be a leaf. When you search for a key in a single B*Tree node, you are forced to sequentially scan the sorted list of keys in the node because of the compression they use. Maybe SQLite thinks your example is the typical one that happens in most data sets, and so the extra effort of skipping through the tree isn't worth it.

But in Scour that wasn't true, and it seems to me in indexes with lots of columns it would often not be true.