Query on an un-indexed column and it'll take forever every time. (There's an Oracle database I deal with occasionally that takes 50 seconds to count 78 rows. No we can't add an index.)
All NoSQL (eewww) non-RDBMSs do is move the pain around. The efficiency and lookup times are (usually, mostly) orthogonal to the orientation of the data, all you can do is align your use case to hit as few pain points as posisble.
I don't know what's going on with your Oracle install but even taking the small example of 1k rows, an unindexed ad hoc query in MySQL will return pretty quickly, well under a second on a decent machine/disk. That might be fine for, say, occasional use of a "reports" web page - and you don't need to then store and update an index. The same query on CouchDB will be at least 10 times slower, possibly making the page unusably slow, and if you want it to be usable you need to store the index - no choice.
But yeah, just "moving the pain around" is absolutely right. Ain't no silver bullets.