Rather I think their point is that since O(N) is really X * N, it's not the N that gets you, it's the X.

Right — the network database is also doing O(N) work to return O(N) results from one query but the multiplier is much lower because it doesn't include a network RTT.

...and the difference between "a fancy hash table" (in-process SQLite) and doing a network roundtrip is a few orders of magnitude.