ONE join? A join is usually just a linear scan through one table, doing hashtable lookups on the other table. If there is no hash table, at the worst both tables have to be sorted on the join key and scanned linearly.

The absolute worst case of a "join" is a cartesian product which runs in quadratic time. 6000^2 = 36000000, which should still easily finish in ~1 second.