[credulousperson]

Unfortunately, it's impossible to do true uniform random over set of rows without doing something like count() over the things you are sampling over. You are looking to select something with probability 1/n, where n is the number of rows, so you must somehow, possibly implicitly, compute n, which is the count. So you'll always end up with at least O(n) assuming you have no pregenerated structure before running the query.

[alecco]

Exactly. And in case of SQL, it's worse because some rows may have been deleted so you can't even count of id (or rowid) to be contiguous.