> tables with billions of rows crossed with millions of rows just to find a single row with data is not something i would call cheap,

Um ..yes? It's cheap if you got your indices right. A hash table doesn't really care if there are 20 or 20B entries.