I think the main hit to be avoided is in reading all of the interior and leaf pages into the page cache. Once you've done that the additional cost of actually processing the contents of those pages is going to be really small.
-scott On Fri, Apr 4, 2008 at 9:48 AM, Noah Hart <[EMAIL PROTECTED]> wrote: > Questions to the SQLite maintainers... > > The docs tell us that ... > ** The page headers looks like this: > ** > ** OFFSET SIZE DESCRIPTION > ** 0 1 Flags. 1: intkey, 2: zerodata, 4: leafdata, > 8: leaf > ** 1 2 byte offset to the first freeblock > ** 3 2 number of cells on this page > > Since the count of cells in use stored in for each btree page? > Wouldn't it be pretty easy to optimize count(*) by > > <PSEUDO CODE> > count = 0 > Btree_MOVE_TO_FIRST_ENTRY > while not Btree_END_OF_TREE > count += NUMBER_OF_ENTRIES_ON_THIS_CHILD_PAGE > Btree_MOVE_TO_NEXT_CHILD_PAGE > return count; > </PSEUDO CODE> > > With large rows contents lengths, the savings would be minimal > However even with rows contents lengths around 100, the savings would be > 10x > > Regards -- Noah > > > > > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Scott Hess > Sent: Friday, April 04, 2008 9:15 AM > To: General Discussion of SQLite Database > Subject: Re: [sqlite] Count(1) > > What I meant when I said "full table scan" is that it has to read at > least something for every single row in the table. So the following > are going to be the same: > > SELECT COUNT(*) FROM t; > SELECT COUNT(rowid) FROM t; > > It won't have to scan any overflow pages, but it will have to hit all > the leaf nodes. > > You could certainly do a full scan on an index other than the rowid. > It might involve much less reading if the indexed items are small > relative to the overall row. Not sure if SQLite does this > optimization for you or not (I don't think it much matters - it's > still going to bel O(N), just with a lower constant). > > -scott > > > On Fri, Apr 4, 2008 at 8:19 AM, Samuel Neff <[EMAIL PROTECTED]> > wrote: > > Scott, > > > > Is it really a full table scan or just an index scan (at least in the > case > > where no data is needed from the table as in the original sample that > had no > > join or where clause). > > > > Thanks, > > > > Sam > > > > > > > > On Thu, Apr 3, 2008 at 4:12 PM, Scott Hess <[EMAIL PROTECTED]> wrote: > > > > > A little bit more info: SELECT COUNT(*) is implemented as a full > > > table scan, so SQLite is visiting every row in the table, which > will > > > get slower and slower as the table gets bigger and the database > > > fragments. This differs from many database engines (which > implement > > > an optimization for this) Doing the trigger thing means that it > only > > > visits the specific row that contains the count. > > > > > > -scott > > > > > > > > -- > > ----------------------------------------------------------------- > > We're Hiring! Seeking passionate Flex, C#, or C++ (RTSP, H264) > developer. > > Position is in the Washington D.C. metro area. Contact > > [EMAIL PROTECTED] > > > > > > _______________________________________________ > > sqlite-users mailing list > > [email protected] > > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > > > _______________________________________________ > sqlite-users mailing list > [email protected] > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > > > > CONFIDENTIALITY NOTICE: > This message may contain confidential and/or privileged information. If you > are not the addressee or authorized to receive this for the addressee, you > must not use, copy, disclose, or take any action based on this message or any > information herein. If you have received this message in error, please advise > the sender immediately by reply e-mail and delete this message. Thank you for > your cooperation. > > > > > _______________________________________________ > sqlite-users mailing list > [email protected] > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > _______________________________________________ sqlite-users mailing list [email protected] http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
