3 ms·
I always first try to teach the intuition that an index is a different sorting of the data (with the full table scan being insertion order/sort by rowid). Every
by maweki 5y ago
I always first try to teach the intuition that an index is a different sorting of the data (with the full table scan being insertion order/sort by rowid). Everything that's faster with data sorted in this manner is faster in the database. That's for 2nd semester students who should have heard of sorted-list merging and binary search.
That overlooks hash indexes or index-only queries, of course.
Love the article but I'm not sure that the indirection of the index being an additional data structure really helps understanding it better.
I think you basically only need to understand that once we have some degenerated indexes with bad selectivity where a full table scan would be better. Here the additional index access is neck breaking.
Of course, this sorting-intuition doesn't help in understanding the different kind of indexes. Is that a topic for newbies though?
- eatonphil 5y ago> with the full table scan being insertion order/sort by rowid I'm not sure that makes sense. As far as I'm aware selecting without sorting has no guaranteed order across vendors at all.
- haimez 5y agoNo guaranteed order, but very typically a predictable order depending on the query plan chosen. If you’re relying on an ordering, you need to specify it in the query. However, the scan order is predictable for a given engine depending on the query plan. If it’s doing an index scan, you’ll get results in index order and if it’s doing a table scan you’ll get it in table storage order (assuming a transactional, single node [edit: also single threaded] OLTP database- this goes out the window when outputs are aggregated across multi node (edit: or multi threaded) scans without an ORDER BY)