/ Check-in [abbb999d]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Change the btree node balancers to sort nodes into accending order. This improves insert and delete speed by 25%. (CVS 409)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: abbb999d4fc3fe142567b6ede5e625e7bf0da714
User & Date: drh 2002-03-02 19:00:31
Context
2002-03-02
20:41
Pager optimization: do not write or journal free pages. This results in a 2x performance gain for large INSERTs and a 5x performance gain for large DELETEs. (CVS 410) check-in: cf1ebcfb user: drh tags: trunk
19:00
Change the btree node balancers to sort nodes into accending order. This improves insert and delete speed by 25%. (CVS 409) check-in: abbb999d user: drh tags: trunk
17:04
Subquery flattening is implemented and passes all regression tests. We still need to add addition tests to the suite to further exercise the flattener, however. (CVS 408) check-in: d5d3e79c user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
2099
2100
2101
2102
2103
2104
2105


































2106
2107
2108
2109
2110
2111
2112
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.55 2002/02/19 22:43:59 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
  for(i=0; i<k; i++){
    rc = allocatePage(pBt, &apNew[i], &pgnoNew[i]);
    if( rc ) goto balance_cleanup;
    nNew++;
    zeroPage(apNew[i]);
    apNew[i]->isInit = 1;
  }



































  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
  for(i=0; i<nNew; i++){







|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.56 2002/03/02 19:00:31 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
  for(i=0; i<k; i++){
    rc = allocatePage(pBt, &apNew[i], &pgnoNew[i]);
    if( rc ) goto balance_cleanup;
    nNew++;
    zeroPage(apNew[i]);
    apNew[i]->isInit = 1;
  }

  /*
  ** Put the new pages in accending order.  This helps to
  ** keep entries in the disk file in order so that a scan
  ** of the table is a linear scan through the file.  That
  ** in turn helps the operating system to deliver pages
  ** from the disk more rapidly.
  **
  ** An O(n^2) insertion sort algorithm is used, but since
  ** n is never more than 3, that should not be a problem.
  **
  ** This one optimization makes the database about 25%
  ** faster for large insertions and deletions.
  */
  for(i=0; i<k-1; i++){
    int minV = pgnoNew[i];
    int minI = i;
    for(j=i+1; j<k; j++){
      if( pgnoNew[j]<minV ){
        minI = j;
        minV = pgnoNew[j];
      }
    }
    if( minI>i ){
      int t;
      MemPage *pT;
      t = pgnoNew[i];
      pT = apNew[i];
      pgnoNew[i] = pgnoNew[minI];
      apNew[i] = apNew[minI];
      pgnoNew[minI] = t;
      apNew[minI] = pT;
    }
  }

  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
  for(i=0; i<nNew; i++){

Changes to src/func.c.

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
...
184
185
186
187
188
189
190







191
192
193
194
195
196
197
...
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
** This file contains the C functions that implement various SQL
** functions of SQLite.  
**
** There is only one exported symbol in this file - the function
** sqliteRegisterBuildinFunctions() found at the bottom of the file.
** All other code has file scope.
**
** $Id: func.c,v 1.12 2002/02/28 04:00:12 drh Exp $
*/
#include <ctype.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include "sqliteInt.h"

................................................................................
  for(i=0; i<argc; i++){
    if( argv[i] ){
      sqlite_set_result_string(context, argv[i], -1);
      break;
    }
  }
}








/*
** An instance of the following structure holds the context of a
** sum() or avg() aggregate computation.
*/
typedef struct SumCtx SumCtx;
struct SumCtx {
................................................................................
    { "round",      1, roundFunc  },
    { "round",      2, roundFunc  },
    { "upper",      1, upperFunc  },
    { "lower",      1, lowerFunc  },
    { "coalesce",  -1, ifnullFunc },
    { "coalesce",   0, 0          },
    { "coalesce",   1, 0          },

  };
  static struct {
    char *zName;
    int nArg;
    void (*xStep)(sqlite_func*,int,const char**);
    void (*xFinalize)(sqlite_func*);
  } aAggs[] = {







|







 







>
>
>
>
>
>
>







 







|







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
...
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
...
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
** This file contains the C functions that implement various SQL
** functions of SQLite.  
**
** There is only one exported symbol in this file - the function
** sqliteRegisterBuildinFunctions() found at the bottom of the file.
** All other code has file scope.
**
** $Id: func.c,v 1.13 2002/03/02 19:00:31 drh Exp $
*/
#include <ctype.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include "sqliteInt.h"

................................................................................
  for(i=0; i<argc; i++){
    if( argv[i] ){
      sqlite_set_result_string(context, argv[i], -1);
      break;
    }
  }
}

/*
** Implementation of random().  Return a random integer.  
*/
static void randomFunc(sqlite_func *context, int argc, const char **argv){
  sqlite_set_result_int(context, sqliteRandomInteger());
}

/*
** An instance of the following structure holds the context of a
** sum() or avg() aggregate computation.
*/
typedef struct SumCtx SumCtx;
struct SumCtx {
................................................................................
    { "round",      1, roundFunc  },
    { "round",      2, roundFunc  },
    { "upper",      1, upperFunc  },
    { "lower",      1, lowerFunc  },
    { "coalesce",  -1, ifnullFunc },
    { "coalesce",   0, 0          },
    { "coalesce",   1, 0          },
    { "random",    -1, randomFunc },
  };
  static struct {
    char *zName;
    int nArg;
    void (*xStep)(sqlite_func*,int,const char**);
    void (*xFinalize)(sqlite_func*);
  } aAggs[] = {