> improving the algorithm or eliminating a SELECT N can make a difference of multiple orders of magnitude

Yes and no. The main source of slowness in modern software is memory access (patterns). Yes, a binary search is just O(log(n)) but if your array isn't to big a linear search will probably be faster, just because the chance of your data being in cache is much higher due to prefetching.

But it's much harder to plan, program or to refactor software to have a cache friendly memory layout and access pattern. And good luck optimizing your Java, Python, etc. code with respect to memory when even integers are pointers to some data on the heap...