/ Check-in [58805eb3]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Improved detection of unnecessary ORDER BY clauses.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 58805eb36b9975706e2c4e382689519454e9a504
User & Date: drh 2013-05-31 12:43:55
Context
2013-05-31
13:36
Futher enhancements to the ORDER BY optimizer. check-in: d8efa5f8 user: drh tags: nextgen-query-plan-exp
12:43
Improved detection of unnecessary ORDER BY clauses. check-in: 58805eb3 user: drh tags: nextgen-query-plan-exp
11:57
Fix the constructAutomaticIndex() routine so that it works with NGQP. check-in: 5e1e6139 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
....
3844
3845
3846
3847
3848
3849
3850


3851
3852
3853
3854
3855
3856
3857
....
4096
4097
4098
4099
4100
4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
....
4175
4176
4177
4178
4179
4180
4181

4182
4183
4184
4185
4186
4187
4188
....
4509
4510
4511
4512
4513
4514
4515
4516
4517

4518
4519
4520
4521
4522
4523
4524
....
4543
4544
4545
4546
4547
4548
4549




4550
4551
4552
4553
4554
4555
4556
....
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
....
4625
4626
4627
4628
4629
4630
4631

4632
4633
4634
4635
4636
4637
4638
/*
** 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
................................................................................
** 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;

................................................................................
  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) );
................................................................................
    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;
................................................................................
  int nLoop,            /* Number of entries in pPath->aLoop[] */
  WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  Bitmask *pRevMask     /* Mask of WhereLoops to run in reverse order */
){
  u8 revSet;            /* True if rev is known */
  u8 rev;               /* Composite sort order */
  u8 revIdx;            /* Index sort order */
  u8 isUnique;
  u8 requireUnique = 0;

  u16 nColumn;
  u16 nOrderBy;
  int i, j;
  int nUsed = 0;
  int iCur;
  int iColumn;
  WhereLoop *pLoop;
................................................................................
  **  (2) If the current WhereLoop is not one-row, then all subsequent
  **      WhereLoops must be one-row.
  **
  **  (3) Optionally match any ORDER BY terms against the first nEq columns
  **      of the index.
  **
  **  (4) Index columns past nEq must match ORDER BY terms one-for-one.




  */

  assert( pOrderBy!=0 );

  /* Sortability of virtual tables is determined by the xBestIndex method
  ** of the virtual table itself */
  if( pLast->wsFlags & WHERE_VIRTUALTABLE ){
................................................................................
    pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
    if( pOBExpr->op!=TK_COLUMN ) return 0;
  }
    
  for(i=0; i<=nLoop && nUsed<nOrderBy; i++){
    pLoop = i<nLoop ? pPath->aLoop[i] : pLast;
    assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
    isUnique = 1;
    if( pLoop->wsFlags & WHERE_IPK ){
      if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isUnique = 0;
      if( pLoop->u.btree.nEq!=1 ) isUnique = 0;
      pIndex = 0;
      nColumn = 0;
    }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
      return 0;
    }else{
      nColumn = pIndex->nColumn;
      if( pIndex->onError==OE_None ){
        isUnique = 0;
      }else if( (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_RANGE
                                   |WHERE_COLUMN_NULL))!=0 ){
        isUnique = 0;
      }else if( pLoop->u.btree.nEq < pIndex->nColumn ){
        isUnique = 0;
      }
    }
    if( !isUnique && requireUnique ) return 0;
    requireUnique = !isUnique;
    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
    j = 0;
    revSet = rev = 0;
    for(j=0; j<=nColumn && nUsed<nOrderBy; j++, nUsed++){
      int skipable;
      pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
      assert( pOBExpr->op==TK_COLUMN );
      if( pOBExpr->iTable!=iCur ) break;
      if( isUnique ) continue;
      if( j<nColumn ){
        /* Normal index columns */
        iColumn = pIndex->aiColumn[j];
        revIdx = pIndex->aSortOrder[j];
        if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
      }else{
        /* The ROWID column at the end */
................................................................................
        if( revSet ){
          if( (rev ^ revIdx)!=pOrderBy->a[nUsed].sortOrder ) return 0;
        }else{
          rev = revIdx ^ pOrderBy->a[nUsed].sortOrder;
          revSet = 1;
        }
      }

    }
    if( rev ) revMask |= ((Bitmask)1)<<i;
  }
  if( nUsed==nOrderBy ){
    *pRevMask = revMask;
    return 1;
  }







|







 







>
>







 







|







 







>







 







|
|
>







 







>
>
>
>







 







|

|
|







|


|

|


|
|








|







 







>







3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
....
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
....
4098
4099
4100
4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
....
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
....
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
4525
4526
4527
4528
....
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
....
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
....
4633
4634
4635
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
/*
** 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 on 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
................................................................................
** 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
**    (5)  The template uses more terms of the same index but has no additional
**         dependencies          
*/
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;

................................................................................
  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 = 1;           /* 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) );
................................................................................
    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->iSortIdx = b ? iSortIdx : 0;
      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;
................................................................................
  int nLoop,            /* Number of entries in pPath->aLoop[] */
  WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  Bitmask *pRevMask     /* Mask of WhereLoops to run in reverse order */
){
  u8 revSet;            /* True if rev is known */
  u8 rev;               /* Composite sort order */
  u8 revIdx;            /* Index sort order */
  u8 isOneRow;          /* Current WhereLoop is a one-row loop */
  u8 requireOneRow = 0; /* All subsequent loops must be one-row */
  u8 isUniqueIdx;       /* Current WhereLoop uses a unique index */
  u16 nColumn;
  u16 nOrderBy;
  int i, j;
  int nUsed = 0;
  int iCur;
  int iColumn;
  WhereLoop *pLoop;
................................................................................
  **  (2) If the current WhereLoop is not one-row, then all subsequent
  **      WhereLoops must be one-row.
  **
  **  (3) Optionally match any ORDER BY terms against the first nEq columns
  **      of the index.
  **
  **  (4) Index columns past nEq must match ORDER BY terms one-for-one.
  **
  **  (5) If all columns of a UNIQUE index have been matched against ORDER BY
  **      terms, then any subsequent entries in the ORDER BY clause against the
  **      same table can be skipped.
  */

  assert( pOrderBy!=0 );

  /* Sortability of virtual tables is determined by the xBestIndex method
  ** of the virtual table itself */
  if( pLast->wsFlags & WHERE_VIRTUALTABLE ){
................................................................................
    pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
    if( pOBExpr->op!=TK_COLUMN ) return 0;
  }
    
  for(i=0; i<=nLoop && nUsed<nOrderBy; i++){
    pLoop = i<nLoop ? pPath->aLoop[i] : pLast;
    assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
    isOneRow = isUniqueIdx = 1;
    if( pLoop->wsFlags & WHERE_IPK ){
      if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isOneRow = 0;
      if( pLoop->u.btree.nEq!=1 ) isOneRow = 0;
      pIndex = 0;
      nColumn = 0;
    }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
      return 0;
    }else{
      nColumn = pIndex->nColumn;
      if( pIndex->onError==OE_None ){
        isOneRow = isUniqueIdx = 0;
      }else if( (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_RANGE
                                   |WHERE_COLUMN_NULL))!=0 ){
        isOneRow = 0;
      }else if( pLoop->u.btree.nEq < pIndex->nColumn ){
        isOneRow = 0;
      }
    }
    if( !isOneRow && requireOneRow ) return 0;
    requireOneRow = !isOneRow;
    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
    j = 0;
    revSet = rev = 0;
    for(j=0; j<=nColumn && nUsed<nOrderBy; j++, nUsed++){
      int skipable;
      pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
      assert( pOBExpr->op==TK_COLUMN );
      if( pOBExpr->iTable!=iCur ) break;
      if( isOneRow ){ j--; continue; }
      if( j<nColumn ){
        /* Normal index columns */
        iColumn = pIndex->aiColumn[j];
        revIdx = pIndex->aSortOrder[j];
        if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
      }else{
        /* The ROWID column at the end */
................................................................................
        if( revSet ){
          if( (rev ^ revIdx)!=pOrderBy->a[nUsed].sortOrder ) return 0;
        }else{
          rev = revIdx ^ pOrderBy->a[nUsed].sortOrder;
          revSet = 1;
        }
      }
      if( j>=nColumn-1 && isUniqueIdx ){ j--; isOneRow = 1; }
    }
    if( rev ) revMask |= ((Bitmask)1)<<i;
  }
  if( nUsed==nOrderBy ){
    *pRevMask = revMask;
    return 1;
  }