Igor Tandetnik wrote:
From: "Dennis Cote" <[EMAIL PROTECTED]>
I don't know of a way to do what you want with a user defined
function, but your example can be solved quite simply using SQL. The
following query will return a table with the required results.
select * from test order by col desc limit 3;
If you have an index on col then it will also be very fast regardless
of the size of the table, if not it will do a single table scan to
find the three maximum values.
Are you sure it will do a single scan, rather than sorting into a
temporary table and picking three topmost records? What if I want 1000
topmost records, would that still be done in a single scan? If so, how
efficiently will this temporary table of 1000 records managed?
The best algorithm for picking M largest elements out of N runs in O(N
log M), and it requires that the table of M best items seen so far be
maintained in a rather fancy data structure (a heap). Does the SQLite
query planner really implement something like that?
Igor,
If you have an index on col then SQLite will use that index to iterate
through the N largest values, it simply goes to the end of the index and
steps backwards through the index one record at a time. The limit clause
causes it to stop after N steps.
SQLite doesn't create a temporary table if it can use an index to step
through a table in the correct order. Temporary tables are only needed
if it has to collect all the records first and then do a sort.
The real work is done when the records are inserted. That is where
SQLite incurs the cost of inserting an index entry at the correct
location. That is an order log N operation for a btree index. For a
table with N records it takes O(N log N) operations to insert all the
records.
There is no free lunch here. Using an index slows all the inserts so
that it can speed up the lookups. This is a good trade off if you do
lots of lookups.
HTH
Dennis Cote
