On Fri, May 16, 2008 at 04:44:10PM -0700, [EMAIL PROTECTED] scratched on the wall: > Sorry if this is a silly question - I don't have much experience with > databases. > > Say I have a table with many (millions+) of rows and I have a query: > > SELECT * FROM mytable WHERE some_condition ORDER BY rowid > > First, I'm assuming that in addition to whatever time some_condition > takes, I'll see an overhead of O( N log N ) for the sort in the worst > case, but probably much less (O(N) or O(1)?) because it's probably be > sorted anyway by rowid. Is that correct?
If "some_condition" doesn't trigger the use of another index, then yes... the table will be scanned sequentially by rowid, so after the condition is assessed there shouldn't be any sorting overhead. If some_condition causes the use of a different index, then the sorting will be post-processed and the sort costs will be higher-- but your conditional costs might be much lower. Which is better depends a lot on the percentage of total rows returned. If you have a large table, but only return a dozen or so rows, you want to make the condition efficient. If you're returning 20% of the table, you want to sort to be cheap. > My real question is if there is an efficient way to index the results > of such a query. In other words, I'm looking for rows N through N+100 > of the result. Can I do much better than just executing the query and > throwing away the first N rows? I thought of making an auxiliary > table to map rowid in the table with row number of the query for large > chunks of the table, but that can get to be a big memory footprint if > some_condition changes often. If you scan things in order-- e.g. 1-100, 101-200, etc. just remember the row id of the last item in the last results set and add a "rowid > [last]" condition to the next query. Use a limit clause to define the size of your window. The big thing is that you'd like to avoid using an OFFSET. Have a look here for more ideas: http://www.sqlite.org/cvstrac/wiki?p=ScrollingCursor -j -- Jay A. Kreibich < J A Y @ K R E I B I.C H > "'People who live in bamboo houses should not throw pandas.' Jesus said that." - "The Ninja", www.AskANinja.com, "Special Delivery 10: Pop!Tech 2006" _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
