/ Check-in [cad47917]
Login

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

Overview
Comment:Performance improvements (CVS 1379)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: cad47917267d32ab00c8b949151c8bc3c6638479
User & Date: drh 2004-05-14 15:27:28
Context
2004-05-14
16:50
Optimized varint routines and tests added. (CVS 1380) check-in: d4e0933d user: drh tags: trunk
15:27
Performance improvements (CVS 1379) check-in: cad47917 user: drh tags: trunk
12:17
Table 1 of a database (the sqlite_master table) defaults to use B+trees. (CVS 1378) check-in: 45b60de5 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
...
737
738
739
740
741
742
743
744

745
746
747
748
749
750


751
752
753
754
755
756
757
758
759
760
761
762
...
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
...
797
798
799
800
801
802
803
804
805
806
807

808
809
810
811
812
813
814
...
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
** 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.135 2004/05/14 12:17:46 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.
................................................................................
static int initPage(
  MemPage *pPage,        /* The page to be initialized */
  MemPage *pParent       /* The parent.  Might be NULL */
){
  int c, pc, i, hdr;
  unsigned char *data;
  int usableSize;
  int sumCell = 0;       /* Total size of all cells */


  assert( pPage->pBt!=0 );
  assert( pParent==0 || pParent->pBt==pPage->pBt );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  assert( pPage->aData == &((unsigned char*)pPage)[-pPage->pBt->pageSize] );
  assert( pPage->pParent==0 || pPage->pParent==pParent );


  if( pPage->pParent==0 && pParent!=0 ){
    pPage->pParent = pParent;
    sqlite3pager_ref(pParent->aData);
  }
  if( pPage->isInit ) return SQLITE_OK;
  pPage->nCell = pPage->nCellAlloc = 0;
  assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & (PTF_INTKEY|PTF_LEAFDATA))!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;
................................................................................
  }
  if( resizeCellArray(pPage, pPage->nCell) ){
    return SQLITE_NOMEM;
  }
  pc = get2byte(&data[hdr+3]);
  for(i=0; pc>0; i++){
    pPage->aCell[i] = &data[pc];
    sumCell += cellSize(pPage, &data[pc]);
    pc = get2byte(&data[pc]);
  }

  /* Compute the total free space on the page */
  pPage->nFree = data[hdr+5];
  pc = get2byte(&data[hdr+1]);
  while( pc>0 ){
................................................................................
    if( next>0 && next<=pc+size+3 ) return SQLITE_CORRUPT;
    pPage->nFree += size;
    pc = next;
  }
  if( pPage->nFree>=usableSize ) return SQLITE_CORRUPT;

  /* Sanity check:  Cells and freespace and header must sum to the size
  ** a page. */
  if( sumCell+pPage->nFree+hdr+10-pPage->leaf*4 != usableSize ){
    return SQLITE_CORRUPT;
  }


  pPage->isInit = 1;
  pageIntegrity(pPage);
  return SQLITE_OK;
}

/*
................................................................................
  Btree *pBt,          /* The database file */
  Pgno pgno,           /* Number of the page to get */
  MemPage **ppPage,    /* Write the page pointer here */
  MemPage *pParent     /* Parent of the page */
){
  int rc;
  rc = getPage(pBt, pgno, ppPage);
  if( rc==SQLITE_OK ){
    rc = initPage(*ppPage, pParent);
  }
  return rc;
}

/*
** Release a MemPage.  This should be called once for each prior







|







 







|
>






>
>




<







 







|







 







|



>







 







|







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757

758
759
760
761
762
763
764
...
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
...
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
...
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
** 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.136 2004/05/14 15:27:28 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.
................................................................................
static int initPage(
  MemPage *pPage,        /* The page to be initialized */
  MemPage *pParent       /* The parent.  Might be NULL */
){
  int c, pc, i, hdr;
  unsigned char *data;
  int usableSize;
  /* int sumCell = 0;       // Total size of all cells */


  assert( pPage->pBt!=0 );
  assert( pParent==0 || pParent->pBt==pPage->pBt );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  assert( pPage->aData == &((unsigned char*)pPage)[-pPage->pBt->pageSize] );
  assert( pPage->pParent==0 || pPage->pParent==pParent );
  assert( pPage->pParent==pParent || !pPage->isInit );
  if( pPage->isInit ) return SQLITE_OK;
  if( pPage->pParent==0 && pParent!=0 ){
    pPage->pParent = pParent;
    sqlite3pager_ref(pParent->aData);
  }

  pPage->nCell = pPage->nCellAlloc = 0;
  assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & (PTF_INTKEY|PTF_LEAFDATA))!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;
................................................................................
  }
  if( resizeCellArray(pPage, pPage->nCell) ){
    return SQLITE_NOMEM;
  }
  pc = get2byte(&data[hdr+3]);
  for(i=0; pc>0; i++){
    pPage->aCell[i] = &data[pc];
    /* sumCell += cellSize(pPage, &data[pc]); */
    pc = get2byte(&data[pc]);
  }

  /* Compute the total free space on the page */
  pPage->nFree = data[hdr+5];
  pc = get2byte(&data[hdr+1]);
  while( pc>0 ){
................................................................................
    if( next>0 && next<=pc+size+3 ) return SQLITE_CORRUPT;
    pPage->nFree += size;
    pc = next;
  }
  if( pPage->nFree>=usableSize ) return SQLITE_CORRUPT;

  /* Sanity check:  Cells and freespace and header must sum to the size
  ** a page.
  if( sumCell+pPage->nFree+hdr+10-pPage->leaf*4 != usableSize ){
    return SQLITE_CORRUPT;
  }
  */

  pPage->isInit = 1;
  pageIntegrity(pPage);
  return SQLITE_OK;
}

/*
................................................................................
  Btree *pBt,          /* The database file */
  Pgno pgno,           /* Number of the page to get */
  MemPage **ppPage,    /* Write the page pointer here */
  MemPage *pParent     /* Parent of the page */
){
  int rc;
  rc = getPage(pBt, pgno, ppPage);
  if( rc==SQLITE_OK && (*ppPage)->isInit==0 ){
    rc = initPage(*ppPage, pParent);
  }
  return rc;
}

/*
** Release a MemPage.  This should be called once for each prior

Changes to src/vdbe.c.

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
....
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
....
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
....
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
....
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.290 2004/05/14 12:16:11 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
    }else{
      zData = (char *)sqlite3BtreeDataFetch(pCrsr, max_space);
    }
    if( !zData ){
      /* This code will run very infrequently (e.g. tables with several
      ** hundred columns).
      */
      zData = (char *)sqliteMalloc(offset+max_space);
      if( !zData ){
        rc = SQLITE_NOMEM;
        goto abort_due_to_error;
      }
      if( pC->keyAsData ){
        rc = sqlite3BtreeKey(pCrsr, 0, max_space, zData);
      }else{
................................................................................
    }
  }

  /* Dynamically allocate space for the aTypes array. and read all
  ** the serial types for the record. At the end of this block variable
  ** offset is set to the offset to the start of Data0 in the record.
  */
  aTypes = (u64 *)sqliteMalloc(sizeof(u64)*nFields);
  if( !aTypes ){
    if( freeZdata ){
      sqliteFree(zData);
      freeZdata = 0;
    }
    rc = SQLITE_NOMEM;
    goto abort_due_to_error;
................................................................................
    */
    if( pC->keyAsData ){
      zData = (char *)sqlite3BtreeKeyFetch(pCrsr, offset+len);
    }else{
      zData = (char *)sqlite3BtreeDataFetch(pCrsr, offset+len);
    }
    if( !zData && len>0 ){
      zData = (char *)sqliteMalloc(len);
      if( !zData ){
        sqliteFree(aTypes);
        rc = SQLITE_NOMEM;
        goto abort_due_to_error;
      }
      if( pC->keyAsData ){
        rc = sqlite3BtreeKey(pCrsr, offset, len, zData);
................................................................................

  if( nBytes>MAX_BYTES_PER_ROW ){
    rc = SQLITE_TOOBIG;
    goto abort_due_to_error;
  }

  /* Allocate space for the new record. */
  zNewRecord = sqliteMalloc(nBytes);
  if( !zNewRecord ){
    rc = SQLITE_NOMEM;
    goto abort_due_to_error;
  }

  /* Write the record */
  zCsr = zNewRecord;
................................................................................
  
  if( nByte>MAX_BYTES_PER_ROW ){
    rc = SQLITE_TOOBIG;
    goto abort_due_to_error;
  }

  /* Allocate space for the new key */
  zKey = (char *)sqliteMalloc(nByte);
  if( !zKey ){
    rc = SQLITE_NOMEM;
    goto abort_due_to_error;
  }
  
  /* Build the key in the buffer pointed to by zKey. */
  for(pRec=pData0; pRec<=pTos; pRec++){







|







 







|







 







|







 







|







 







|







 







|







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
....
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
....
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
....
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
....
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.291 2004/05/14 15:27:29 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
    }else{
      zData = (char *)sqlite3BtreeDataFetch(pCrsr, max_space);
    }
    if( !zData ){
      /* This code will run very infrequently (e.g. tables with several
      ** hundred columns).
      */
      zData = (char *)sqliteMallocRaw(offset+max_space);
      if( !zData ){
        rc = SQLITE_NOMEM;
        goto abort_due_to_error;
      }
      if( pC->keyAsData ){
        rc = sqlite3BtreeKey(pCrsr, 0, max_space, zData);
      }else{
................................................................................
    }
  }

  /* Dynamically allocate space for the aTypes array. and read all
  ** the serial types for the record. At the end of this block variable
  ** offset is set to the offset to the start of Data0 in the record.
  */
  aTypes = (u64 *)sqliteMallocRaw(sizeof(u64)*nFields);
  if( !aTypes ){
    if( freeZdata ){
      sqliteFree(zData);
      freeZdata = 0;
    }
    rc = SQLITE_NOMEM;
    goto abort_due_to_error;
................................................................................
    */
    if( pC->keyAsData ){
      zData = (char *)sqlite3BtreeKeyFetch(pCrsr, offset+len);
    }else{
      zData = (char *)sqlite3BtreeDataFetch(pCrsr, offset+len);
    }
    if( !zData && len>0 ){
      zData = (char *)sqliteMallocRaw(len);
      if( !zData ){
        sqliteFree(aTypes);
        rc = SQLITE_NOMEM;
        goto abort_due_to_error;
      }
      if( pC->keyAsData ){
        rc = sqlite3BtreeKey(pCrsr, offset, len, zData);
................................................................................

  if( nBytes>MAX_BYTES_PER_ROW ){
    rc = SQLITE_TOOBIG;
    goto abort_due_to_error;
  }

  /* Allocate space for the new record. */
  zNewRecord = sqliteMallocRaw(nBytes);
  if( !zNewRecord ){
    rc = SQLITE_NOMEM;
    goto abort_due_to_error;
  }

  /* Write the record */
  zCsr = zNewRecord;
................................................................................
  
  if( nByte>MAX_BYTES_PER_ROW ){
    rc = SQLITE_TOOBIG;
    goto abort_due_to_error;
  }

  /* Allocate space for the new key */
  zKey = (char *)sqliteMallocRaw(nByte);
  if( !zKey ){
    rc = SQLITE_NOMEM;
    goto abort_due_to_error;
  }
  
  /* Build the key in the buffer pointed to by zKey. */
  for(pRec=pData0; pRec<=pTos; pRec++){

Changes to src/vdbeaux.c.

1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
....
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
  if( nCellKey<=0 ){
    *res = 0;
    return SQLITE_OK;
  }

  pCellKey = (unsigned char *)sqlite3BtreeKeyFetch(pCur, nCellKey);
  if( !pCellKey ){
    pCellKey = (unsigned char *)sqliteMalloc(nCellKey);
    if( !pCellKey ){
      return SQLITE_NOMEM;
    }
    freeCellKey = 1;
    rc = sqlite3BtreeKey(pCur, 0, nCellKey, pCellKey);
    if( rc!=SQLITE_OK ){
      sqliteFree(pCellKey);
................................................................................
  *res = sqlite3VdbeKeyCompare(pC, len, pCellKey, nKey, pKey);
  
  if( freeCellKey ){
    sqliteFree(pCellKey);
  }
  return SQLITE_OK;
}










|







 







<
<
<
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
....
1543
1544
1545
1546
1547
1548
1549



  if( nCellKey<=0 ){
    *res = 0;
    return SQLITE_OK;
  }

  pCellKey = (unsigned char *)sqlite3BtreeKeyFetch(pCur, nCellKey);
  if( !pCellKey ){
    pCellKey = (unsigned char *)sqliteMallocRaw(nCellKey);
    if( !pCellKey ){
      return SQLITE_NOMEM;
    }
    freeCellKey = 1;
    rc = sqlite3BtreeKey(pCur, 0, nCellKey, pCellKey);
    if( rc!=SQLITE_OK ){
      sqliteFree(pCellKey);
................................................................................
  *res = sqlite3VdbeKeyCompare(pC, len, pCellKey, nKey, pKey);
  
  if( freeCellKey ){
    sqliteFree(pCellKey);
  }
  return SQLITE_OK;
}