I've been working with SQLite 3.2.1 and trying to do database creation
as fast as possible. In my situation, I've been using auto-incremented
key values. One thing that I've noted is that a fair amount of time was
being spent in sqlite3BtreeMoveto(). As I understand it, the general
algorithm there is to do a binary search for an appropriate place for
insertion of a new element. As per standard binary search, the search
is started in the middle of the range ( pCur->idx = (lwr+upr)/2; ). For
the case of auto-incremented keys, it seems that we'd always be finding
an entry at the far right (upper) end of the range. I put in a simple
modification to start the search at the upper end of the range (
pCur->idx = upr; ). With this, I was able to do inserts with the
example program at (http://anchor.homelinux.org/SQLiteTuning) about
10-15% faster.
My simple change to sqlite3BtreeMoveTo() in btree.c was:
...
int firstPass=1;
while( lwr<=upr ){
void *pCellKey;
i64 nCellKey;
/*
* Since we are inserting with auto increment key, we should expect
* to find match at top end of range. Start search there.
*/
if (firstPass) {
pCur->idx = upr;
firstPass=0;
} else {
pCur->idx = (lwr+upr)/2;
}
...
I'm not sure of all of the implications of such a change, so am I not
able to offer complete code for it. I suspect that there may be various
flags that could be examined to know when to use this different starting
point, etc. I mention this as a suggestion for active developers of
SQLite as something to be considered.
Thanks for your consideration,
--Chuck Pahlmeyer
