[EMAIL PROTECTED] wrote: > > The query as you have specified it runs in O(NlogN) time > where N is the number of rows in the table.
Actually, the original query runs in O(N) time. I was mistaken. But I still think I am right in saying that my "manual" scheme runs in O(MlogN) time. So the manual scheme will only be faster if O(N)>O(MlogN). So your choice of algorithm will depend a lot on the values of M and N. > > I suggest you do the query "manually". To begin with, use > SQLite version 3.3.0 (which supports DESC indices) and create > your table with a separate index like this: > > CREATE TABLE user_actions ( > uid INTEGER NOT NULL, > actionid INTEGER NOT NULL, > time INTEGER NOT NULL, > status INTEGER NOT NULL > ); > CREATE INDEX user_actions_pk > ON user_actions(uid,actionid,time DESC,status); > > The DESC attribute on the time field of the index means that > index entries will be in descending time order instead of > the default ascending. Hence, the first entry in the index > for a particular uid+actionid will be the one with the largest > time value. > > Find the first record in O(logN) time like this: > > SELECT * FROM user_actions > ORDER BY uid, actionid, time DESC > LIMIT 1; > > Find all other actions for the same user this way: > > SELECT * FROM user_actions > WHERE uid=:previous_uid AND actionid>:previous_actionid > ORDER BY uid, actionid, time DESC > LIMIT 1; > > Once you have all records for a single user, advance to the > next user this way: > > SELECT * FROM user_actions > WHERE uid>:previous_uid > ORDER BY uid, actionid, time DESC > LIMIT 1 > > Repeat until done. Runtime is O(MlogN) where N is the number > of rows in the table and M is the number of rows of output. > Since M is likely much less than N, this approach will be much > faster. > -- D. Richard Hipp <[EMAIL PROTECTED]>
