Joe Wilson <[EMAIL PROTECTED]> wrote:
> --- [EMAIL PROTECTED] wrote:
> > Joe Wilson <[EMAIL PROTECTED]> wrote:
> > > The reason why I asked is that I haven't had much luck with sqlite3 
> > > performance for databases larger than the size of RAM on my machine
> > > regardless of PRAGMA settings.
> > 
> > This is probably do to the cache locality problem.  We know how
> > to fix this, Joe.  Would you like to have a go at it?
> I think setting aside contiguous pages in the file for exclusive use 
> by each btree would help improve locality of reference on disk.
> For example, let A, B and C represent in-use pages of 3 btrees and 
> a, b and c represent free pages corresponding to the same btrees:
>  AAaAAaAaaaBBbbBBBbbbCCcCCCcccc
> Is this what you had in mind in your post?


The problem is when inserting into large database that is
indexed, the values being indexed are randomly distributed.
So with each insert, SQLite has to seek to a new random
place in the file to insert the new index entry there.
It does not matter that pages of the index are not in
consecutive order.  What matters is that each insertion
is into a different place and that the places are randomly
distributed over a large file - larger than will fit in cache.
In this situation, each new entry probably needs to go on 
a page that is not in cache, and hence a real disk
seek and read is required (as opposed to simply reading
the value out of cache) when inserting each new entry.  Disk
seeks and reads are much, much slower than disk cache hits,
which really slows down insertion performance.

If you do many inserts such that the indexed values are
in sorted order, then most inserts will go on the same page
as the previous.  The previous page is already in cache
so it doesn't need to be read from disk.  It has also
already been journaled, so no excess writing is required.
Disk I/O is greatly reduced. Things go much, much faster.
The problem is that you really have the luxury of being
able to insert entries in sorted order.  And if you are
indexing multiple columns, it is impossible to sort
the entries on both columns at once.

The usual way to work around this problem is to only do random
inserts into indices which are small enough to fit into
your disk cache.  Suppose you start inserting into index A.
Once A gets too big to fit entirely in cache, stop inserting
into it and start inserting into B.  Once B gets to be the
cache size, merge A and B together into a new index C.
The merge operation requires reading A and B straight through
from beginning to end once.  This is a lot of disk I/O but
it is still much faster than jumping around within the file
reading bits here and there.  After creating C, reset A and
B back to being empty (since all records have been transfered
into C).  Start inserting into A again until it fills up.
Then fill up B again.  Merge A and B into D, then merge C and D
into E.  Reset A, B, C, and D.  Keep doing this, merging
smaller indices into larger indices, until you insert all
the records you need to insert.  Then make a single pass
through all of the smaller indices and merge them all
together into a single big index Z.  Z becomes the new
index used for search operations on the database.

The algorithm above should probably go into SQLite 
to construct an index as part of the CREATE INDEX
statement.  When populating a database will a large
amount of data, first put all of the data into an
unindexed table.  This will be very fast because each
new entry goes at the end of the table (and also at the
end of the file.)  After all data is in place, issue
the CREATE INDEX statements to index any fields you
think need indexing.  The CREATE INDEX statement has
to populate the index.  The current algorithm is to
scan through the original table and create and insert
index entries one by one as they are encountered.  I am
proposing that you substitute the algorithm outlined in
the previous paragraph in place of the current algorithm.

D. Richard Hipp <[EMAIL PROTECTED]>

To unsubscribe, send email to [EMAIL PROTECTED]

Reply via email to