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
