The Insider News

kellabyte[^]:

The best kind of optimizations are ones that eliminate the need to do expensive but wasteful work. While analyzing internals of some open source databases I’ve found that some of them spend a lot of time trying to do the wrong optimizations at the wrong times resulting in wasteful work. The more interesting implementations try to detect when this expensive wasteful work can be avoided and just don’t do it. You would be surprised at how much processing some databases do just to tell you that the thing you queried for doesn’t exist in the database. A data structure that sometimes can help reduce wasteful work like this is a Bloom Filter.