On Fri, Jan 26, 2007 at 09:16:41AM -0700, Dennis Cote wrote:
> The offset mechanism proposed by Igor earlier is far more efficient as
> long as you know the size of the table. You can always get the size from
> a count query, which also requires a table scan, but even that is less
> expensive than duplicating the table since it is only reading not
> writing. On average the offset mechanism will scan half the table to
> find the random record.
>
> count O(N) + select O(N/2)
>
> If your table is large this will be a lot faster.
You can go faster still by using querying the last rowid rather than the
count of rows. That's O(1) instead of O(N). And this works because you
need the max rowid not the row count, and OP_Last is O(1).
SELECT rowid FROM foo ORDER BY rowid DESC LIMIT 1;
You should take negative rowids into account too though (switch DESC to
ASC to get the first rowid).
And use Joe's scheme for quickly selecting a random row.
Sparse tables are a problem. I've tried this sort of thing but it
doesn't work every time for sparse tables:
SELECT * FROM foo ORDER BY rowid DESC LIMIT 1 OFFSET (abs(random()) %
(SELECT rowid FROM foo ORDER BY rowid DESC LIMIT 1)) - 1;
I can't see why this doesn't work reliably, but if it did it would be
O(1).
Can someone explain this:
sqlite> select rowid, * from foo;
rowi bar
---- --------------
-5 x
5 y
sqlite> select * from foo order by rowid limit 1 offset 0;
bar
----
x
sqlite> select * from foo order by rowid limit 1 offset -1;
bar
----
x
sqlite> select * from foo order by rowid limit 1 offset 1;
bar
----
y
sqlite>
Is that a bug?
Nico
--
-----------------------------------------------------------------------------
To unsubscribe, send email to [EMAIL PROTECTED]
-----------------------------------------------------------------------------
