SQLite

Check-in [67367f1e1f]
Login

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

Overview
Comment:Work toward improving the NGQP's ability to optimize out ORDER BY clauses.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 67367f1e1f0c3eb6be65eea9873910aa62b49884
User & Date: drh 2013-05-21 15:52:07.219
Context
2013-05-21
19:23
Enhanced "wheretrace" output in the NGQP solver routine. (check-in: 04dfb85a2a user: drh tags: nextgen-query-plan-exp)
15:52
Work toward improving the NGQP's ability to optimize out ORDER BY clauses. (check-in: 67367f1e1f user: drh tags: nextgen-query-plan-exp)
2013-05-20
15:14
Merge in all trunk changes up through the 3.7.17 release. (check-in: 14ab6675e5 user: drh tags: nextgen-query-plan-exp)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/sqliteInt.h.
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
** But sqlite3SrcListShiftJoinType() later shifts the jointypes so that each
** jointype expresses the join between the table and the previous table.
**
** In the colUsed field, the high-order bit (bit 63) is set if the table
** contains more than 63 columns and the 64-th or later column is used.
*/
struct SrcList {
  i16 nSrc;        /* Number of tables or subqueries in the FROM clause */
  i16 nAlloc;      /* Number of entries allocated in a[] below */
  struct SrcList_item {
    Schema *pSchema;  /* Schema to which this item is fixed */
    char *zDatabase;  /* Name of database holding this table */
    char *zName;      /* Name of the table */
    char *zAlias;     /* The "B" part of a "A AS B" phrase.  zName is the "A" */
    Table *pTab;      /* An SQL table corresponding to zName */
    Select *pSelect;  /* A SELECT statement used in place of a table name */







|
|







1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
** But sqlite3SrcListShiftJoinType() later shifts the jointypes so that each
** jointype expresses the join between the table and the previous table.
**
** In the colUsed field, the high-order bit (bit 63) is set if the table
** contains more than 63 columns and the 64-th or later column is used.
*/
struct SrcList {
  u8 nSrc;        /* Number of tables or subqueries in the FROM clause */
  u8 nAlloc;      /* Number of entries allocated in a[] below */
  struct SrcList_item {
    Schema *pSchema;  /* Schema to which this item is fixed */
    char *zDatabase;  /* Name of database holding this table */
    char *zName;      /* Name of the table */
    char *zAlias;     /* The "B" part of a "A AS B" phrase.  zName is the "A" */
    Table *pTab;      /* An SQL table corresponding to zName */
    Select *pSelect;  /* A SELECT statement used in place of a table name */
Changes to src/where.c.
52
53
54
55
56
57
58
59

60
61
62
63
64
65
66
** term of a join.  The WhereClause object holds a table of these
** objects using (maskSelf,prereq,) as the primary key.  Note that the
** same join term might have multiple associated WhereLoop objects.
*/
struct WhereLoop {
  Bitmask prereq;       /* Bitmask of other loops that must run first */
  Bitmask maskSelf;     /* Bitmask identifying table iTab */
  u16 iTab;             /* Index of the table coded by this loop */

  u16 nTerm;            /* Number of entries in aTerm[] */
  u32 wsFlags;          /* WHERE_* flags describing the plan */
  double rSetup;        /* One-time setup cost (ex: create transient index) */
  double rRun;          /* Cost of running each loop */
  double nOut;          /* Estimated number of output rows */
  union {
    struct {               /* Information for internal btree tables */







|
>







52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
** term of a join.  The WhereClause object holds a table of these
** objects using (maskSelf,prereq,) as the primary key.  Note that the
** same join term might have multiple associated WhereLoop objects.
*/
struct WhereLoop {
  Bitmask prereq;       /* Bitmask of other loops that must run first */
  Bitmask maskSelf;     /* Bitmask identifying table iTab */
  u8 iTab;              /* Position in FROM clause of table coded by this loop */
  u8 iSortIdx;          /* Sorting index number.  0==None */
  u16 nTerm;            /* Number of entries in aTerm[] */
  u32 wsFlags;          /* WHERE_* flags describing the plan */
  double rSetup;        /* One-time setup cost (ex: create transient index) */
  double rRun;          /* Cost of running each loop */
  double nOut;          /* Estimated number of output rows */
  union {
    struct {               /* Information for internal btree tables */
1983
1984
1985
1986
1987
1988
1989

1990
1991
1992
1993
1994
1995
1996
  struct SrcList_item *pSrc,     /* Table we are trying to access */
  Bitmask notReady               /* Tables in outer loops of the join */
){
  char aff;
  if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
  if( (pTerm->eOperator & WO_EQ)==0 ) return 0;
  if( (pTerm->prereqRight & notReady)!=0 ) return 0;

  aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
  if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
  return 1;
}
#endif

#ifndef SQLITE_OMIT_AUTOMATIC_INDEX







>







1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
  struct SrcList_item *pSrc,     /* Table we are trying to access */
  Bitmask notReady               /* Tables in outer loops of the join */
){
  char aff;
  if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
  if( (pTerm->eOperator & WO_EQ)==0 ) return 0;
  if( (pTerm->prereqRight & notReady)!=0 ) return 0;
  if( pTerm->u.leftColumn<0 ) return 0;
  aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
  if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
  return 1;
}
#endif

#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
5164
5165
5166
5167
5168
5169
5170















5171
5172
5173
5174
5175
5176
5177





5178
5179
5180
5181
5182
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
** Insert or replace a WhereLoop entry using the template supplied.
**
** An existing WhereLoop entry might be overwritten if the new template
** is better and has fewer dependencies.  Or the template will be ignored
** and no insert will occur if an existing WhereLoop is faster and has
** fewer dependencies than the template.  Otherwise a new WhereLoop is
** added based no the template.















*/
static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0;
  WhereTerm **paTerm = 0;
  sqlite3 *db = pBuilder->db;
  WhereInfo *pWInfo = pBuilder->pWInfo;






  if( (p = pBuilder->pBest)!=0 ){
    if( p->maskSelf!=0 ){
      if( p->rRun+p->rSetup < pTemplate->rRun+pTemplate->rSetup ){
        return SQLITE_OK;
      }
      if( p->rRun+p->rSetup == pTemplate->rRun+pTemplate->rSetup
       && p->prereq <= pTemplate->prereq ){
        return SQLITE_OK;
      }
    }
    *p = *pTemplate;
    p->aTerm = 0;
    p->u.vtab.needFree = 0;
    return SQLITE_OK;
  }

  /* Search for an existing WhereLoop to overwrite, or which takes
  ** priority over pTemplate.
  */
  for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
    if( p->iTab!=pTemplate->iTab ) continue;
    if( (p->prereq & pTemplate->prereq)==p->prereq
     && p->rSetup<=pTemplate->rSetup
     && p->rRun<=pTemplate->rRun
    ){
      /* Already holding an equal or better WhereLoop.
      ** Return without changing or adding anything */
      return SQLITE_OK;







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







>
>
>
>
>




















|







5166
5167
5168
5169
5170
5171
5172
5173
5174
5175
5176
5177
5178
5179
5180
5181
5182
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
5220
5221
5222
5223
5224
5225
5226
5227
** Insert or replace a WhereLoop entry using the template supplied.
**
** An existing WhereLoop entry might be overwritten if the new template
** is better and has fewer dependencies.  Or the template will be ignored
** and no insert will occur if an existing WhereLoop is faster and has
** fewer dependencies than the template.  Otherwise a new WhereLoop is
** added based no the template.
**
** If pBuilder->pBest is not NULL then we only care about the very
** best template and that template should be stored in pBuilder->pBest.
** If pBuilder->pBest is NULL then a list of the best templates are stored
** in pBuilder->pWInfo->pLoops.
**
** When accumulating multiple loops (when pBuilder->pBest is NULL) we
** still might overwrite similar loops with the new template if the
** template is better.  Loops may be overwritten if the following 
** conditions are met:
**
**    (1)  They have the same iTab.
**    (2)  They have the same iSortIdx.
**    (3)  The template has same or fewer dependencies than the current loop
**    (4)  The template has the same or lower cost than the current loop
*/
static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0;
  WhereTerm **paTerm = 0;
  sqlite3 *db = pBuilder->db;
  WhereInfo *pWInfo = pBuilder->pWInfo;

  /* If pBuilder->pBest is defined, then only keep track of the single
  ** best WhereLoop.  pBuilder->pBest->maskSelf==0 indicates that no
  ** prior WhereLoops have been evaluated and that the current pTemplate
  ** is therefore the first and hence the best and should be retained.
  */
  if( (p = pBuilder->pBest)!=0 ){
    if( p->maskSelf!=0 ){
      if( p->rRun+p->rSetup < pTemplate->rRun+pTemplate->rSetup ){
        return SQLITE_OK;
      }
      if( p->rRun+p->rSetup == pTemplate->rRun+pTemplate->rSetup
       && p->prereq <= pTemplate->prereq ){
        return SQLITE_OK;
      }
    }
    *p = *pTemplate;
    p->aTerm = 0;
    p->u.vtab.needFree = 0;
    return SQLITE_OK;
  }

  /* Search for an existing WhereLoop to overwrite, or which takes
  ** priority over pTemplate.
  */
  for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
    if( p->iTab!=pTemplate->iTab || p->iSortIdx!=pTemplate->iSortIdx ) continue;
    if( (p->prereq & pTemplate->prereq)==p->prereq
     && p->rSetup<=pTemplate->rSetup
     && p->rRun<=pTemplate->rRun
    ){
      /* Already holding an equal or better WhereLoop.
      ** Return without changing or adding anything */
      return SQLITE_OK;
5234
5235
5236
5237
5238
5239
5240
5241
5242
5243
5244
5245
5246
5247
5248
  p->pNextLoop = pNext;
  *ppPrev = p;
  p->aTerm = paTerm;
  if( p->nTerm ){
    memcpy(p->aTerm, pTemplate->aTerm, p->nTerm*sizeof(p->aTerm[0]));
  }
  if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
    if( p->u.btree.pIndex && p->u.btree.pIndex->tnum==0 ){
      p->u.btree.pIndex = 0;
    }
  }else{
    pTemplate->u.vtab.needFree = 0;
  }
  return SQLITE_OK;
}







|







5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
5268
5269
5270
  p->pNextLoop = pNext;
  *ppPrev = p;
  p->aTerm = paTerm;
  if( p->nTerm ){
    memcpy(p->aTerm, pTemplate->aTerm, p->nTerm*sizeof(p->aTerm[0]));
  }
  if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
    if( p->u.btree.pIndex && p->u.btree.pIndex && p->u.btree.pIndex->tnum==0 ){
      p->u.btree.pIndex = 0;
    }
  }else{
    pTemplate->u.vtab.needFree = 0;
  }
  return SQLITE_OK;
}
5337
5338
5339
5340
5341
5342
5343






























5344
5345
5346
5347
5348
5349
5350
5351
5352
5353
5354
5355
5356
5357
5358
5359
5360


5361
5362
5363
5364
5365
5366
5367
5368
5369
5370
    ){
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn);
    }
  }
  *pNew = savedLoop;
  return rc;
}































/*
** Add all WhereLoop objects a single table of the join were the table
** is idenfied by pBuilder->pNew->iTab.  That table is guaranteed to be
** a b-tree table, not a virtual table.
*/
static int whereLoopAddBtree(
  WhereLoopBuilder *pBuilder, /* WHERE clause information */
  Bitmask mExtra              /* Extra prerequesites for using this table */
){
  Index *pProbe;              /* An index we are evaluating */
  Index sPk;                  /* A fake index object for the primary key */
  tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
  int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  WhereLoop *pNew;            /* Template WhereLoop object */
  int rc = SQLITE_OK;         /* Return code */


  double rSize;               /* number of rows in the table */
  double rLogSize;            /* Logarithm of the number of rows in the table */

  pNew = pBuilder->pNew;
  pSrc = pBuilder->pTabList->a + pNew->iTab;
  assert( !IsVirtual(pSrc->pTab) );

  if( pSrc->pIndex ){
    /* An INDEXED BY clause specifies a particular index to use */
    pProbe = pSrc->pIndex;







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

















>
>


|







5359
5360
5361
5362
5363
5364
5365
5366
5367
5368
5369
5370
5371
5372
5373
5374
5375
5376
5377
5378
5379
5380
5381
5382
5383
5384
5385
5386
5387
5388
5389
5390
5391
5392
5393
5394
5395
5396
5397
5398
5399
5400
5401
5402
5403
5404
5405
5406
5407
5408
5409
5410
5411
5412
5413
5414
5415
5416
5417
5418
5419
5420
5421
5422
5423
5424
    ){
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn);
    }
  }
  *pNew = savedLoop;
  return rc;
}

/*
** Return True if it is possible that pIndex might be useful in
** implementing the ORDER BY clause in pBuilder.
**
** Return False if pBuilder does not contain an ORDER BY clause or
** if there is no way for pIndex to be useful in implementing that
** ORDER BY clause.
*/
static int indexMightHelpWithOrderBy(
  WhereLoopBuilder *pBuilder,
  Index *pIndex,
  int iCursor
){
  ExprList *pOB;
  int iCol;
  int ii;

  if( (pOB = pBuilder->pOrderBy)==0 ) return 0;
  iCol = pIndex->aiColumn[0];
  for(ii=0; ii<pOB->nExpr; ii++){
    Expr *pExpr = pOB->a[ii].pExpr;
    if( pExpr->op!=TK_COLUMN ) return 0;
    if( pExpr->iTable==iCursor ){
      if( pExpr->iColumn==iCol ) return 1;
      return 0;
    }
  }
  return 0;
}

/*
** Add all WhereLoop objects a single table of the join were the table
** is idenfied by pBuilder->pNew->iTab.  That table is guaranteed to be
** a b-tree table, not a virtual table.
*/
static int whereLoopAddBtree(
  WhereLoopBuilder *pBuilder, /* WHERE clause information */
  Bitmask mExtra              /* Extra prerequesites for using this table */
){
  Index *pProbe;              /* An index we are evaluating */
  Index sPk;                  /* A fake index object for the primary key */
  tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
  int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  WhereLoop *pNew;            /* Template WhereLoop object */
  int rc = SQLITE_OK;         /* Return code */
  int iSortIdx = 0;           /* Index number */
  int b;                      /* A boolean value */
  double rSize;               /* number of rows in the table */
  double rLogSize;            /* Logarithm of the number of rows in the table */
  
  pNew = pBuilder->pNew;
  pSrc = pBuilder->pTabList->a + pNew->iTab;
  assert( !IsVirtual(pSrc->pTab) );

  if( pSrc->pIndex ){
    /* An INDEXED BY clause specifies a particular index to use */
    pProbe = pSrc->pIndex;
5415
5416
5417
5418
5419
5420
5421
5422


5423
5424

5425
5426
5427
5428
5429
5430
5431
5432
5433
5434
5435
5436
5437
5438
5439
5440
5441






5442
5443
5444
5445
5446
5447
5448
5449
5450
5451
5452



5453



5454

5455
5456
5457
5458
5459
5460
5461
        pNew->wsFlags = WHERE_TEMP_INDEX;
        pNew->prereq = mExtra | pTerm->prereqRight;
        rc = whereLoopInsert(pBuilder, pNew);
      }
    }
  }

  /* Insert a full table scan */


  pNew->u.btree.nEq = 0;
  pNew->nTerm = 0;

  pNew->rSetup = (double)0;
  pNew->prereq = mExtra;
  pNew->u.btree.pIndex = 0;
  pNew->wsFlags = 0;
  pNew->nOut = rSize;
  pNew->rRun = rSize + rLogSize;
  /* TBD: Reduce nOut using constraints */
  rc = whereLoopInsert(pBuilder, pNew);

  /* Loop over all indices
  */
  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext){
    pNew->u.btree.nEq = 0;
    pNew->nTerm = 0;
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;






    }else{
      Bitmask m = pSrc->colUsed;
      int j;
      for(j=pProbe->nColumn-1; j>=0; j--){
        int x = pProbe->aiColumn[j];
        if( x<BMS-1 ){
          m &= ~(((Bitmask)1)<<x);
        }
      }
      pNew->wsFlags = m==0 ? WHERE_IDX_ONLY : 0;
    }



    pNew->u.btree.pIndex = pProbe;





    rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 1);

    /* If there was an INDEXED BY clause, then only that one index is
    ** considered. */
    if( pSrc->pIndex ) break;
  }
  return rc;







|
>
>
|
|
>
|
|
|
<
<
<
<
<
|
<
<
<
<
<



>
>
>
>
>
>









|
|
>
>
>
|
>
>
>
|
>







5469
5470
5471
5472
5473
5474
5475
5476
5477
5478
5479
5480
5481
5482
5483
5484





5485





5486
5487
5488
5489
5490
5491
5492
5493
5494
5495
5496
5497
5498
5499
5500
5501
5502
5503
5504
5505
5506
5507
5508
5509
5510
5511
5512
5513
5514
5515
5516
5517
5518
5519
5520
5521
        pNew->wsFlags = WHERE_TEMP_INDEX;
        pNew->prereq = mExtra | pTerm->prereqRight;
        rc = whereLoopInsert(pBuilder, pNew);
      }
    }
  }

  /* Loop over all indices
  */
  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
    pNew->u.btree.nEq = 0;
    pNew->nTerm = 0;
    pNew->iSortIdx = 0;
    pNew->rSetup = (double)0;
    pNew->prereq = mExtra;
    pNew->u.btree.pIndex = pProbe;





    b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);





    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;

      /* Full table scan */
      pNew->nOut = rSize;
      pNew->rRun = (rSize + rLogSize)*(3+b); /* 4x penalty for a full-scan */
      rc = whereLoopInsert(pBuilder, pNew);
      if( rc ) break;
    }else{
      Bitmask m = pSrc->colUsed;
      int j;
      for(j=pProbe->nColumn-1; j>=0; j--){
        int x = pProbe->aiColumn[j];
        if( x<BMS-1 ){
          m &= ~(((Bitmask)1)<<x);
        }
      }
      pNew->wsFlags = (m==0) ? WHERE_IDX_ONLY : 0;

      /* Full scan via index */
      if( m==0 || b ){
        pNew->iSortIdx = b ? iSortIdx : 0;
        pNew->nOut = rSize;
        pNew->rRun = (m==0) ? (rSize + rLogSize)*(1+b) : (rSize*rLogSize);
        rc = whereLoopInsert(pBuilder, pNew);
        if( rc ) break;
      }
    }
    rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 1);

    /* If there was an INDEXED BY clause, then only that one index is
    ** considered. */
    if( pSrc->pIndex ) break;
  }
  return rc;
5677
5678
5679
5680
5681
5682
5683

5684
5685
5686
5687
5688
5689
5690
      pNew->nTerm = 1;
      pNew->aTerm[0] = pTerm;
      pNew->wsFlags = WHERE_MULTI_OR;
      pNew->rSetup = (double)0;
      pNew->rRun = rTotal;
      pNew->nOut = nRow;
      pNew->prereq = prereq;

      rc = whereLoopInsert(pBuilder, pNew);
    }
  }
  return rc;
}

/*







>







5737
5738
5739
5740
5741
5742
5743
5744
5745
5746
5747
5748
5749
5750
5751
      pNew->nTerm = 1;
      pNew->aTerm[0] = pTerm;
      pNew->wsFlags = WHERE_MULTI_OR;
      pNew->rSetup = (double)0;
      pNew->rRun = rTotal;
      pNew->nOut = nRow;
      pNew->prereq = prereq;
      memset(&pNew->u, 0, sizeof(pNew->u));
      rc = whereLoopInsert(pBuilder, pNew);
    }
  }
  return rc;
}

/*