/ Check-in [49d20ede]
Login

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

Overview
Comment:Performance improvements for the RowSet object when it undergoes many cycles between RowSetInsert and RowSetTest.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:49d20ede5f4c0895a165126d5cf7c95a0510ba35
User & Date: drh 2012-04-05 01:37:32
Context
2012-04-05
20:04
Ignore the value of SQLITE_FCNTL_CHUNK_SIZE if it is negative. check-in: 1b08fef9 user: drh tags: trunk
01:37
Performance improvements for the RowSet object when it undergoes many cycles between RowSetInsert and RowSetTest. check-in: 49d20ede user: drh tags: trunk
2012-04-04
16:56
Add the ".trace" option to the command-line shell. check-in: b9ac3d7e user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/rowset.c.

    72     72   ** The number of rowset entries per allocation chunk.
    73     73   */
    74     74   #define ROWSET_ENTRY_PER_CHUNK  \
    75     75                          ((ROWSET_ALLOCATION_SIZE-8)/sizeof(struct RowSetEntry))
    76     76   
    77     77   /*
    78     78   ** Each entry in a RowSet is an instance of the following object.
           79  +**
           80  +** This same object is reused to store a linked list of trees of RowSetEntry
           81  +** objects.  In that alternative use, pRight points to the next entry
           82  +** in the list, pLeft points to the tree, and v is unused.  The
           83  +** RowSet.pForest value points to the head of this forest list.
    79     84   */
    80     85   struct RowSetEntry {            
    81     86     i64 v;                        /* ROWID value for this entry */
    82     87     struct RowSetEntry *pRight;   /* Right subtree (larger entries) or list */
    83     88     struct RowSetEntry *pLeft;    /* Left subtree (smaller entries) */
    84     89   };
    85     90   
................................................................................
   101    106   */
   102    107   struct RowSet {
   103    108     struct RowSetChunk *pChunk;    /* List of all chunk allocations */
   104    109     sqlite3 *db;                   /* The database connection */
   105    110     struct RowSetEntry *pEntry;    /* List of entries using pRight */
   106    111     struct RowSetEntry *pLast;     /* Last entry on the pEntry list */
   107    112     struct RowSetEntry *pFresh;    /* Source of new entry objects */
   108         -  struct RowSetEntry *pTree;     /* Binary tree of entries */
          113  +  struct RowSetEntry *pForest;   /* List of binary trees of entries */
   109    114     u16 nFresh;                    /* Number of objects on pFresh */
   110         -  u8 isSorted;                   /* True if pEntry is sorted */
          115  +  u8 rsFlags;                    /* Various flags */
   111    116     u8 iBatch;                     /* Current insert batch */
   112    117   };
   113    118   
          119  +/*
          120  +** Allowed values for RowSet.rsFlags
          121  +*/
          122  +#define ROWSET_SORTED  0x01   /* True if RowSet.pEntry is sorted */
          123  +#define ROWSET_NEXT    0x02   /* True if sqlite3RowSetNext() has been called */
          124  +
   114    125   /*
   115    126   ** Turn bulk memory into a RowSet object.  N bytes of memory
   116    127   ** are available at pSpace.  The db pointer is used as a memory context
   117    128   ** for any subsequent allocations that need to occur.
   118    129   ** Return a pointer to the new RowSet object.
   119    130   **
   120    131   ** It must be the case that N is sufficient to make a Rowset.  If not
................................................................................
   127    138     RowSet *p;
   128    139     assert( N >= ROUND8(sizeof(*p)) );
   129    140     p = pSpace;
   130    141     p->pChunk = 0;
   131    142     p->db = db;
   132    143     p->pEntry = 0;
   133    144     p->pLast = 0;
   134         -  p->pTree = 0;
          145  +  p->pForest = 0;
   135    146     p->pFresh = (struct RowSetEntry*)(ROUND8(sizeof(*p)) + (char*)p);
   136    147     p->nFresh = (u16)((N - ROUND8(sizeof(*p)))/sizeof(struct RowSetEntry));
   137         -  p->isSorted = 1;
          148  +  p->rsFlags = ROWSET_SORTED;
   138    149     p->iBatch = 0;
   139    150     return p;
   140    151   }
   141    152   
   142    153   /*
   143    154   ** Deallocate all chunks from a RowSet.  This frees all memory that
   144    155   ** the RowSet has allocated over its lifetime.  This routine is
................................................................................
   150    161       pNextChunk = pChunk->pNextChunk;
   151    162       sqlite3DbFree(p->db, pChunk);
   152    163     }
   153    164     p->pChunk = 0;
   154    165     p->nFresh = 0;
   155    166     p->pEntry = 0;
   156    167     p->pLast = 0;
   157         -  p->pTree = 0;
   158         -  p->isSorted = 1;
          168  +  p->pForest = 0;
          169  +  p->rsFlags = ROWSET_SORTED;
          170  +}
          171  +
          172  +/*
          173  +** Allocate a new RowSetEntry object that is associated with the
          174  +** given RowSet.  Return a pointer to the new and completely uninitialized
          175  +** objected.
          176  +**
          177  +** In an OOM situation, the RowSet.db->mallocFailed flag is set and this
          178  +** routine returns NULL.
          179  +*/
          180  +static struct RowSetEntry *rowSetEntryAlloc(RowSet *p){
          181  +  assert( p!=0 );
          182  +  if( p->nFresh==0 ){
          183  +    struct RowSetChunk *pNew;
          184  +    pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew));
          185  +    if( pNew==0 ){
          186  +      return 0;
          187  +    }
          188  +    pNew->pNextChunk = p->pChunk;
          189  +    p->pChunk = pNew;
          190  +    p->pFresh = pNew->aEntry;
          191  +    p->nFresh = ROWSET_ENTRY_PER_CHUNK;
          192  +  }
          193  +  p->nFresh--;
          194  +  return p->pFresh++;
   159    195   }
   160    196   
   161    197   /*
   162    198   ** Insert a new value into a RowSet.
   163    199   **
   164    200   ** The mallocFailed flag of the database connection is set if a
   165    201   ** memory allocation fails.
   166    202   */
   167    203   void sqlite3RowSetInsert(RowSet *p, i64 rowid){
   168    204     struct RowSetEntry *pEntry;  /* The new entry */
   169    205     struct RowSetEntry *pLast;   /* The last prior entry */
   170         -  assert( p!=0 );
   171         -  if( p->nFresh==0 ){
   172         -    struct RowSetChunk *pNew;
   173         -    pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew));
   174         -    if( pNew==0 ){
   175         -      return;
   176         -    }
   177         -    pNew->pNextChunk = p->pChunk;
   178         -    p->pChunk = pNew;
   179         -    p->pFresh = pNew->aEntry;
   180         -    p->nFresh = ROWSET_ENTRY_PER_CHUNK;
   181         -  }
   182         -  pEntry = p->pFresh++;
   183         -  p->nFresh--;
          206  +
          207  +  /* This routine is never called after sqlite3RowSetNext() */
          208  +  assert( p!=0 && (p->rsFlags & ROWSET_NEXT)==0 );
          209  +
          210  +  pEntry = rowSetEntryAlloc(p);
          211  +  if( pEntry==0 ) return;
   184    212     pEntry->v = rowid;
   185    213     pEntry->pRight = 0;
   186    214     pLast = p->pLast;
   187    215     if( pLast ){
   188         -    if( p->isSorted && rowid<=pLast->v ){
   189         -      p->isSorted = 0;
          216  +    if( (p->rsFlags & ROWSET_SORTED)!=0 && rowid<=pLast->v ){
          217  +      p->rsFlags &= ~ROWSET_SORTED;
   190    218       }
   191    219       pLast->pRight = pEntry;
   192    220     }else{
   193         -    assert( p->pEntry==0 ); /* Fires if INSERT after SMALLEST */
   194    221       p->pEntry = pEntry;
   195    222     }
   196    223     p->pLast = pEntry;
   197    224   }
   198    225   
   199    226   /*
   200    227   ** Merge two lists of RowSetEntry objects.  Remove duplicates.
   201    228   **
   202    229   ** The input lists are connected via pRight pointers and are 
   203    230   ** assumed to each already be in sorted order.
   204    231   */
   205         -static struct RowSetEntry *rowSetMerge(
          232  +static struct RowSetEntry *rowSetEntryMerge(
   206    233     struct RowSetEntry *pA,    /* First sorted list to be merged */
   207    234     struct RowSetEntry *pB     /* Second sorted list to be merged */
   208    235   ){
   209    236     struct RowSetEntry head;
   210    237     struct RowSetEntry *pTail;
   211    238   
   212    239     pTail = &head;
................................................................................
   232    259       assert( pB==0 || pB->pRight==0 || pB->v<=pB->pRight->v );
   233    260       pTail->pRight = pB;
   234    261     }
   235    262     return head.pRight;
   236    263   }
   237    264   
   238    265   /*
   239         -** Sort all elements on the pEntry list of the RowSet into ascending order.
          266  +** Sort all elements on the list of RowSetEntry objects into order of
          267  +** increasing v.
   240    268   */ 
   241         -static void rowSetSort(RowSet *p){
          269  +static struct RowSetEntry *rowSetEntrySort(struct RowSetEntry *pIn){
   242    270     unsigned int i;
   243         -  struct RowSetEntry *pEntry;
   244         -  struct RowSetEntry *aBucket[40];
          271  +  struct RowSetEntry *pNext, *aBucket[40];
   245    272   
   246         -  assert( p->isSorted==0 );
   247    273     memset(aBucket, 0, sizeof(aBucket));
   248         -  while( p->pEntry ){
   249         -    pEntry = p->pEntry;
   250         -    p->pEntry = pEntry->pRight;
   251         -    pEntry->pRight = 0;
          274  +  while( pIn ){
          275  +    pNext = pIn->pRight;
          276  +    pIn->pRight = 0;
   252    277       for(i=0; aBucket[i]; i++){
   253         -      pEntry = rowSetMerge(aBucket[i], pEntry);
          278  +      pIn = rowSetEntryMerge(aBucket[i], pIn);
   254    279         aBucket[i] = 0;
   255    280       }
   256         -    aBucket[i] = pEntry;
          281  +    aBucket[i] = pIn;
          282  +    pIn = pNext;
   257    283     }
   258         -  pEntry = 0;
          284  +  pIn = 0;
   259    285     for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){
   260         -    pEntry = rowSetMerge(pEntry, aBucket[i]);
          286  +    pIn = rowSetEntryMerge(pIn, aBucket[i]);
   261    287     }
   262         -  p->pEntry = pEntry;
   263         -  p->pLast = 0;
   264         -  p->isSorted = 1;
          288  +  return pIn;
   265    289   }
   266    290   
   267    291   
   268    292   /*
   269    293   ** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects.
   270    294   ** Convert this tree into a linked list connected by the pRight pointers
   271    295   ** and return pointers to the first and last elements of the new list.
................................................................................
   351    375       p->pLeft = pLeft;
   352    376       p->pRight = rowSetNDeepTree(&pList, iDepth);
   353    377     }
   354    378     return p;
   355    379   }
   356    380   
   357    381   /*
   358         -** Convert the list in p->pEntry into a sorted list if it is not
   359         -** sorted already.  If there is a binary tree on p->pTree, then
   360         -** convert it into a list too and merge it into the p->pEntry list.
          382  +** Take all the entries on p->pEntry and on the trees in p->pForest and
          383  +** sort them all together into one big ordered list on p->pEntry.
          384  +**
          385  +** This routine should only be called once in the life of a RowSet.
   361    386   */
   362    387   static void rowSetToList(RowSet *p){
   363         -  if( !p->isSorted ){
   364         -    rowSetSort(p);
          388  +
          389  +  /* This routine is called only once */
          390  +  assert( p!=0 && (p->rsFlags & ROWSET_NEXT)==0 );
          391  +
          392  +  if( (p->rsFlags & ROWSET_SORTED)==0 ){
          393  +    p->pEntry = rowSetEntrySort(p->pEntry);
   365    394     }
   366         -  if( p->pTree ){
   367         -    struct RowSetEntry *pHead, *pTail;
   368         -    rowSetTreeToList(p->pTree, &pHead, &pTail);
   369         -    p->pTree = 0;
   370         -    p->pEntry = rowSetMerge(p->pEntry, pHead);
          395  +
          396  +  /* While this module could theoretically support it, sqlite3RowSetNext()
          397  +  ** is never called after sqlite3RowSetText() for the same RowSet.  So
          398  +  ** there is never a forest to deal with.  Should this change, simply
          399  +  ** remove the assert() and the #if 0. */
          400  +  assert( p->pForest==0 );
          401  +#if 0
          402  +  while( p->pForest ){
          403  +    struct RowSetEntry *pTree = p->pForest->pLeft;
          404  +    if( pTree ){
          405  +      struct RowSetEntry *pHead, *pTail;
          406  +      rowSetTreeToList(pTree, &pHead, &pTail);
          407  +      p->pEntry = rowSetEntryMerge(p->pEntry, pHead);
          408  +    }
          409  +    p->pForest = p->pForest->pRight;
   371    410     }
          411  +#endif
          412  +  p->rsFlags |= ROWSET_NEXT;  /* Verify this routine is never called again */
   372    413   }
   373    414   
   374    415   /*
   375    416   ** Extract the smallest element from the RowSet.
   376    417   ** Write the element into *pRowid.  Return 1 on success.  Return
   377    418   ** 0 if the RowSet is already empty.
   378    419   **
   379    420   ** After this routine has been called, the sqlite3RowSetInsert()
   380    421   ** routine may not be called again.  
   381    422   */
   382    423   int sqlite3RowSetNext(RowSet *p, i64 *pRowid){
   383         -  rowSetToList(p);
          424  +  assert( p!=0 );
          425  +
          426  +  /* Merge the forest into a single sorted list on first call */
          427  +  if( (p->rsFlags & ROWSET_NEXT)==0 ) rowSetToList(p);
          428  +
          429  +  /* Return the next entry on the list */
   384    430     if( p->pEntry ){
   385    431       *pRowid = p->pEntry->v;
   386    432       p->pEntry = p->pEntry->pRight;
   387    433       if( p->pEntry==0 ){
   388    434         sqlite3RowSetClear(p);
   389    435       }
   390    436       return 1;
................................................................................
   392    438       return 0;
   393    439     }
   394    440   }
   395    441   
   396    442   /*
   397    443   ** Check to see if element iRowid was inserted into the the rowset as
   398    444   ** part of any insert batch prior to iBatch.  Return 1 or 0.
          445  +**
          446  +** If this is the first test of a new batch and if there exist entires
          447  +** on pRowSet->pEntry, then sort those entires into the forest at
          448  +** pRowSet->pForest so that they can be tested.
   399    449   */
   400    450   int sqlite3RowSetTest(RowSet *pRowSet, u8 iBatch, sqlite3_int64 iRowid){
   401         -  struct RowSetEntry *p;
          451  +  struct RowSetEntry *p, *pTree;
          452  +
          453  +  /* This routine is never called after sqlite3RowSetNext() */
          454  +  assert( pRowSet!=0 && (pRowSet->rsFlags & ROWSET_NEXT)==0 );
          455  +
          456  +  /* Sort entries into the forest on the first test of a new batch 
          457  +  */
   402    458     if( iBatch!=pRowSet->iBatch ){
   403         -    if( pRowSet->pEntry ){
   404         -      rowSetToList(pRowSet);
   405         -      pRowSet->pTree = rowSetListToTree(pRowSet->pEntry);
          459  +    p = pRowSet->pEntry;
          460  +    if( p ){
          461  +      struct RowSetEntry **ppPrevTree = &pRowSet->pForest;
          462  +      if( (pRowSet->rsFlags & ROWSET_SORTED)==0 ){
          463  +        p = rowSetEntrySort(p);
          464  +      }
          465  +      for(pTree = pRowSet->pForest; pTree; pTree=pTree->pRight){
          466  +        ppPrevTree = &pTree->pRight;
          467  +        if( pTree->pLeft==0 ){
          468  +          pTree->pLeft = rowSetListToTree(p);
          469  +          break;
          470  +        }else{
          471  +          struct RowSetEntry *pAux, *pTail;
          472  +          rowSetTreeToList(pTree->pLeft, &pAux, &pTail);
          473  +          pTree->pLeft = 0;
          474  +          p = rowSetEntryMerge(pAux, p);
          475  +        }
          476  +      }
          477  +      if( pTree==0 ){
          478  +        *ppPrevTree = pTree = rowSetEntryAlloc(pRowSet);
          479  +        if( pTree ){
          480  +          pTree->v = 0;
          481  +          pTree->pRight = 0;
          482  +          pTree->pLeft = rowSetListToTree(p);
          483  +        }
          484  +      }
   406    485         pRowSet->pEntry = 0;
   407    486         pRowSet->pLast = 0;
          487  +      pRowSet->rsFlags |= ROWSET_SORTED;
   408    488       }
   409    489       pRowSet->iBatch = iBatch;
   410    490     }
   411         -  p = pRowSet->pTree;
   412         -  while( p ){
   413         -    if( p->v<iRowid ){
   414         -      p = p->pRight;
   415         -    }else if( p->v>iRowid ){
   416         -      p = p->pLeft;
   417         -    }else{
   418         -      return 1;
          491  +
          492  +  /* Test to see if the iRowid value appears anywhere in the forest.
          493  +  ** Return 1 if it does and 0 if not.
          494  +  */
          495  +  for(pTree = pRowSet->pForest; pTree; pTree=pTree->pRight){
          496  +    p = pTree->pLeft;
          497  +    while( p ){
          498  +      if( p->v<iRowid ){
          499  +        p = p->pRight;
          500  +      }else if( p->v>iRowid ){
          501  +        p = p->pLeft;
          502  +      }else{
          503  +        return 1;
          504  +      }
   419    505       }
   420    506     }
   421    507     return 0;
   422    508   }