On 1/11/06, Dan Kennedy <[EMAIL PROTECTED]> wrote: > > > --- Martin O'Leary <[EMAIL PROTECTED]> wrote: > > > Hi guys, > > > > I have a table like the following: > > > > CREATE TABLE user_actions ( > > uid INTEGER NOT NULL, > > actionid INTEGER NOT NULL, > > time INTEGER NOT NULL, > > status INTEGER NOT NULL, > > PRIMARY KEY (uid, actionid, time, status) > > ); > > > > And I want to carry out a query something like this: > > > > SELECT uid, actionid, MAX(time), status FROM user_actions GROUP BY > > uid, actionid; > > > > i.e. finding the last time each user performed each action (numbers of > > users and distinct actions are small in comparison to number of times > > each user performs each action). > > > Secondly, query performance is quite slow. It seems to me that no > > optimisation is being carried out on the MAX(time) expression. Is this > > the case, and if so, why not? Surely it's possible to do this in a > > nice, logarithmic way. > > New versions of SQLite should execute this query in O(N) time. Are you > seeing otherwise? I don't really see how you could improve on that > given the query and index.
Surely it can be done in O(log N), assuming constant numbers of user and action ids? All that needs to be done is to find all distinct (uid, actionid) pairs (which I believe should be O(log N)), and then find the first entry in the index for each (again, O(log N)). Martin
