It's been a while since I looked at this, but I think MySQL and Postgres both take this into account and will let you add indexes to small tables but will actually ignore them and do a full table scan for all queries if the table is small enough.
It's been a while since I looked at this, but I think MySQL and Postgres both take this into account and will let you add indexes to small tables but will actually ignore them and do a full table scan for all queries if the table is small enough.
Some of his examples aren't great, though. The cost of adding an index to a database you're already using and which has a reasonably small amount of data is low, and the benefit of getting a few hundred ms less latency for your users is underappreciated. A hundred million records is definitely above the limit at which e.g. prefix search on a mobile device becomes painful.
I think folks writing databases know a thing or two about writing faster search and sort algorithms.
What exactly do you mean with "writing faster search and sort algorithms"?
- Branchless binary search: https://news.ycombinator.com/item?id=35737862 / https://news.ycombinator.com/item?id=14598098
- Static B-Trees for faster binary search: https://news.ycombinator.com/item?id=30376140
Presumably there's even more literature on the topic.
But I see now you were referring to the branch predictor part specifically, so all good.
Re: binary search, the biggest cost to scanning data in a database is loading that data from persistent storage. A few mispredicted branches aren’t going to matter much if it means you can do fewer reads.
It depends.
If you measure or determine somehow the sizes of the L1-L2-L3 caches in the CPU, the relative speed and size of the main memory, and the relative speed and size of the local storage (in contrast with for example network-remote data), then it is a matter of performing some arithmetic, and just to be on the safe side, some benchmarks.
Any data set that fits into the CPU cache is definitely small, for a particular CPU.
If you want to decide a number that applies to every and all hardware, then it goes from hard to basically impossible.
https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...
I did not read this entire thing so it's very possible it contains a benchmark somewhere but I couldn't find any when doing a quick skim.
Yes that's exactly how I knew about this!
Or in other words add the index every single time, unless you have so many writes and such a large table that the actual writes slow down the index.
Leaving out an index on a small table never helps anything.