4 ms·
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<date, Map<numbe
by nikeee 1y ago
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<date, Map<number, Map<lang, rowId>>> 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 works for some queries and doesn't for others.
- adzm 1y agoI use this same approach to explain indexes to database novices; it usually helps a lot, especially with how the leaf nodes / included indexes work as well (using that info instead of or in addition to rowid/primary key as the last value there)
- emschwartz 1y agoThat is a helpful way of thinking about it. Thanks for sharing!
- immibis 1y agoIt's actually a List<Tuple<date, number, rowid>>> 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)
- Sesse__ 1y agoIt'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.
- nikeee 1y agoYeah 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.
- masklinn 1y agoIt’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.
- jasonwatkinspdx 1y agoYeah, 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.
- runlaszlorun 1y agoI definitely second Andy Pavlo's lectures.
- deleted 1y ago[deleted]