/ Check-in [9fe20292]
Login

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

Overview
Comment:First attempt to get ORDER BY optimization working in NGQP.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 9fe20292558bb9422de91e35648cb834cbf3b306
User & Date: drh 2013-05-14 15:31:07
Context
2013-05-20
15:14
Merge in all trunk changes up through the 3.7.17 release. check-in: 14ab6675 user: drh tags: nextgen-query-plan-exp
2013-05-14
15:31
First attempt to get ORDER BY optimization working in NGQP. check-in: 9fe20292 user: drh tags: nextgen-query-plan-exp
2013-05-11
00:06
Minor fixes to the OR-clause processing in the NGQP. check-in: d6946f33 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_DUPLICATES_OK    0x0008 /* Ok to return a row more than once */
#define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
#define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
#define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
#define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */
#define WHREE_GROUPBY          0x0100 /* pOrderBy is really a GROUP BY */

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.







|







2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_DUPLICATES_OK    0x0008 /* Ok to return a row more than once */
#define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
#define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
#define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
#define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */
#define WHERE_GROUPBY          0x0100 /* pOrderBy is really a GROUP BY */

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.

Changes to src/where.c.

80
81
82
83
84
85
86

87
88
89
90
91
92
93
....
5074
5075
5076
5077
5078
5079
5080






5081
5082
5083
5084
5085
5086
5087
5088
5089
....
5730
5731
5732
5733
5734
5735
5736

5737
5738
5739





5740
5741
5742
5743
5744
5745

5746










































5747

5748




















5749
5750
5751
5752
5753



























5754
5755






















5756
5757
5758
5759
5760
5761
5762
....
5827
5828
5829
5830
5831
5832
5833

5834
5835
5836
5837
5838
5839
5840
5841
5842
5843

5844
5845
5846
5847
5848
5849
5850
....
5869
5870
5871
5872
5873
5874
5875

5876
5877
5878
5879
5880
5881
5882
....
6189
6190
6191
6192
6193
6194
6195
6196





6197
6198
6199
6200
6201
6202
6203

/*
** Each instance of this object holds a sequence of WhereLoop objects
** that implement some or all of the entire query plan.  
*/
struct WherePath {
  Bitmask maskLoop;     /* Bitmask of all WhereLoop objects in this path */

  double nRow;          /* Estimated number of rows generated by this path */
  double rCost;         /* Total cost of this path */
  u8 isOrdered;         /* True if this path satisfies ORDER BY */
  u8 isOrderedValid;    /* True if the isOrdered field is valid */
  WhereLoop **aLoop;    /* Array of WhereLoop objects implementing this path */
};

................................................................................
  Table *pTab = pItem->pTab;
  sqlite3DebugPrintf("%2d.%0*llx.%0*llx",
                     p->iTab, nb, p->maskSelf, nb, p->prereq);
  sqlite3DebugPrintf(" %8s",
                     pItem->zAlias ? pItem->zAlias : pTab->zName);
  if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
    if( p->u.btree.pIndex ){






      sqlite3DebugPrintf(".%-12s %2d",
                         p->u.btree.pIndex->zName, p->u.btree.nEq);
    }else{
      sqlite3DebugPrintf("%16s","");
    }
  }else{
    char *z;
    if( p->u.vtab.idxStr ){
      z = sqlite3_mprintf("(%d,\"%s\")", p->u.vtab.idxNum,p->u.vtab.idxStr);
................................................................................
whereLoopAddAll_end:
  whereLoopDelete(db, pBuilder->pNew);
  pBuilder->pNew = 0;
  return rc;
}

/*

** Examine a WherePath to see if it outputs rows in the requested ORDER BY
** (or GROUP BY) without requiring a separate source operation.  Return 1
** if it does and 0 if it does not and -1 if we cannot tell.





*/
static int wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  WherePath *pPath,     /* The WherePath to check */
  int nLoop,            /* Number of entries in pPath->aLoop[] */
  WhereLoop *pLoop      /* Add this WhereLoop to the end of pPath->aLoop[] */

){










































  if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){

    return nLoop==0 && pLoop->u.vtab.isOrdered;




















  }else{
    /* TBD: Check to see if pFrom + pWLoop satisfies the ORDER BY.
    **  (1)  If yes:   set isOrderedValid and isOrdered to 1.
    **  (2)  If no:    set isOrderedValid to 1 and isOrdered to 0.
    **  (3)  unknown:  no-op */



























    return 0;
  }






















}


/*
** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
................................................................................
  ** of WherePaths as the basis for the next.  Keep track of the mxChoice
  ** best paths at each generation */
  for(iLoop=0; iLoop<nLoop; iLoop++){
    nTo = 0;
    for(ii=0, pFrom=aFrom; ii<nFrom; ii++, pFrom++){
      for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){
        Bitmask maskNew;

        u8 isOrderedValid = pFrom->isOrderedValid;
        u8 isOrdered = pFrom->isOrdered;
        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        /* At this point, pWLoop is a candidate to be the next loop. 
        ** Compute its cost */
        rCost = pWLoop->rSetup + pWLoop->rRun*pFrom->nRow + pFrom->rCost;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( !isOrderedValid ){
          switch( wherePathSatisfiesOrderBy(pWInfo, pFrom, iLoop, pWLoop) ){

            case 1:  /* Yes.  pFrom+pWLoop does satisfy the ORDER BY clause */
              isOrdered = 1;
              isOrderedValid = 1;
              break;
            case 0:  /* No.  pFrom+pWLoop will require a separate sort */
              isOrdered = 0;
              isOrderedValid = 1;
................................................................................
          }
          pTo = &aTo[jj];
        }else{
          if( pTo->rCost<=rCost ) continue;
        }
        /* pWLoop is a winner.  Add it to the set of best so far */
        pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;

        pTo->nRow = pFrom->nRow * pWLoop->nOut;
        pTo->rCost = rCost;
        pTo->isOrderedValid = isOrderedValid;
        pTo->isOrdered = isOrdered;
        memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
        pTo->aLoop[iLoop] = pWLoop;
        if( nTo>=mxChoice ){
................................................................................

  wherePathSolver(pWInfo);
  if( db->mallocFailed ) goto whereBeginError;
#if defined(SQLITE_DEBUG) \
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
  if( sqlite3WhereTrace ){
    int ii;
    sqlite3DebugPrintf("------------ Solution ----------------\n");





    for(ii=0; ii<nTabList; ii++){
      whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList);
    }
  }
#endif

  /* Chose the best index to use for each table in the FROM clause.







>







 







>
>
>
>
>
>
|
<







 







>
|
|
<
>
>
>
>
>





|
>

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







 







>









|
>







 







>







 







|
>
>
>
>
>







80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
....
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
5087
5088

5089
5090
5091
5092
5093
5094
5095
....
5736
5737
5738
5739
5740
5741
5742
5743
5744
5745

5746
5747
5748
5749
5750
5751
5752
5753
5754
5755
5756
5757
5758
5759
5760
5761
5762
5763
5764
5765
5766
5767
5768
5769
5770
5771
5772
5773
5774
5775
5776
5777
5778
5779
5780
5781
5782
5783
5784
5785
5786
5787
5788
5789
5790
5791
5792
5793
5794
5795
5796
5797
5798
5799
5800
5801
5802
5803
5804
5805
5806
5807
5808
5809
5810
5811
5812
5813
5814
5815
5816
5817
5818
5819
5820
5821
5822
5823
5824




5825
5826
5827
5828
5829
5830
5831
5832
5833
5834
5835
5836
5837
5838
5839
5840
5841
5842
5843
5844
5845
5846
5847
5848
5849
5850
5851
5852
5853
5854
5855
5856
5857
5858
5859
5860
5861
5862
5863
5864
5865
5866
5867
5868
5869
5870
5871
5872
5873
5874
5875
5876
5877
5878
5879
5880
5881
5882
....
5947
5948
5949
5950
5951
5952
5953
5954
5955
5956
5957
5958
5959
5960
5961
5962
5963
5964
5965
5966
5967
5968
5969
5970
5971
5972
....
5991
5992
5993
5994
5995
5996
5997
5998
5999
6000
6001
6002
6003
6004
6005
....
6312
6313
6314
6315
6316
6317
6318
6319
6320
6321
6322
6323
6324
6325
6326
6327
6328
6329
6330
6331

/*
** Each instance of this object holds a sequence of WhereLoop objects
** that implement some or all of the entire query plan.  
*/
struct WherePath {
  Bitmask maskLoop;     /* Bitmask of all WhereLoop objects in this path */
  Bitmask revLoop;      /* aLoop[]s that should be reversed for ORDER BY */
  double nRow;          /* Estimated number of rows generated by this path */
  double rCost;         /* Total cost of this path */
  u8 isOrdered;         /* True if this path satisfies ORDER BY */
  u8 isOrderedValid;    /* True if the isOrdered field is valid */
  WhereLoop **aLoop;    /* Array of WhereLoop objects implementing this path */
};

................................................................................
  Table *pTab = pItem->pTab;
  sqlite3DebugPrintf("%2d.%0*llx.%0*llx",
                     p->iTab, nb, p->maskSelf, nb, p->prereq);
  sqlite3DebugPrintf(" %8s",
                     pItem->zAlias ? pItem->zAlias : pTab->zName);
  if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
    if( p->u.btree.pIndex ){
      const char *zName = p->u.btree.pIndex->zName;
      if( strncmp(zName, "sqlite_autoindex_", 17)==0 ){
        int i = sqlite3Strlen30(zName) - 1;
        while( zName[i]!='_' ) i--;
        zName += i;
      }
      sqlite3DebugPrintf(".%-12s %2d", zName, p->u.btree.nEq);

    }else{
      sqlite3DebugPrintf("%16s","");
    }
  }else{
    char *z;
    if( p->u.vtab.idxStr ){
      z = sqlite3_mprintf("(%d,\"%s\")", p->u.vtab.idxNum,p->u.vtab.idxStr);
................................................................................
whereLoopAddAll_end:
  whereLoopDelete(db, pBuilder->pNew);
  pBuilder->pNew = 0;
  return rc;
}

/*
** Examine a WherePath (with the addition of the extra WhereLoop of the 4th
** parameters) to see if it outputs rows in the requested ORDER BY
** (or GROUP BY) without requiring a separate source operation.  Return:

** 
**    0:  ORDER BY is not satisfied.  Sorting required
**    1:  ORDER BY is satisfied.      Omit sorting
**   -1:  Unknown at this time
**
*/
static int wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  WherePath *pPath,     /* The WherePath to check */
  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;
  u8 rev;
  u8 isUnique;
  u8 requireUnique = 0;
  u16 nColumn;
  u16 nOrderBy;
  int i, j;
  int nUsed = 0;
  int iCur;
  int iColumn;
  WhereLoop *pLoop;
  ExprList *pOrderBy = pWInfo->pOrderBy;
  Expr *pOBExpr;
  CollSeq *pColl;
  Index *pIndex;
  sqlite3 *db = pWInfo->pParse->db;
  Bitmask revMask = 0;

  /*
  ** We say the WhereLoop is "one-row" if all of the following are true:
  **  (a) All index columns match with WHERE_COLUMN_EQ.
  **  (b) The index is unique
  **
  ** General rules:  (not an algorithm!)
  **
  **  (1) If the current WhereLoop is one-row, then match over any and all
  **      ORDER BY terms for the current WhereLoop and proceed to the next
  **      WhereLoop.
  **
  **  (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 ){
    assert( nLoop==0 );
    return pLast->u.vtab.isOrdered;
  }

  /* Sorting is always required if any term of the ORDER BY is not a 
  ** column reference */
  nOrderBy = pOrderBy->nExpr;
  for(i=0; i<nOrderBy; i++){
    pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].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_EQ)!=0 ) isUnique = 0;
      pIndex = 0;
      nColumn = 1;
    }else if( pLoop->u.btree.pIndex==0 ){
      return 0;
    }else{




      pIndex = pLoop->u.btree.pIndex;
      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++){
      pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
      assert( pOBExpr->op==TK_COLUMN );
      if( pOBExpr->iTable!=iCur ) break;
      if( pIndex==0 ){
        if( pOBExpr->iColumn<0 && j==0 ){
          isUnique = 1;
          rev = pOrderBy->a[nUsed].sortOrder;
        }else if( isUnique ){
          continue;
        }else{
          return 0;
        }
      }
      if( isUnique ) continue;
      iColumn = pIndex->aiColumn[j];
      if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
      if( pOBExpr->iColumn!=iColumn ) return 0;
      pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[nUsed].pExpr);
      if( !pColl ) pColl = db->pDfltColl;
      if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) return 0;
      if( revSet ){
        if( pIndex->aSortOrder[j]!=rev ) return 0;
      }else{
        rev = pIndex->aSortOrder[j];
        revSet = 1;
      }
    }
    if( rev ) revMask |= ((Bitmask)1)<<i;
  }
  if( nUsed==nOrderBy ){
    *pRevMask = revMask;
    return 1;
  }
  return -1;
}


/*
** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
................................................................................
  ** of WherePaths as the basis for the next.  Keep track of the mxChoice
  ** best paths at each generation */
  for(iLoop=0; iLoop<nLoop; iLoop++){
    nTo = 0;
    for(ii=0, pFrom=aFrom; ii<nFrom; ii++, pFrom++){
      for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){
        Bitmask maskNew;
        Bitmask revMask = 0;
        u8 isOrderedValid = pFrom->isOrderedValid;
        u8 isOrdered = pFrom->isOrdered;
        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        /* At this point, pWLoop is a candidate to be the next loop. 
        ** Compute its cost */
        rCost = pWLoop->rSetup + pWLoop->rRun*pFrom->nRow + pFrom->rCost;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( !isOrderedValid ){
          switch( wherePathSatisfiesOrderBy(pWInfo, pFrom, iLoop,
                                            pWLoop, &revMask) ){
            case 1:  /* Yes.  pFrom+pWLoop does satisfy the ORDER BY clause */
              isOrdered = 1;
              isOrderedValid = 1;
              break;
            case 0:  /* No.  pFrom+pWLoop will require a separate sort */
              isOrdered = 0;
              isOrderedValid = 1;
................................................................................
          }
          pTo = &aTo[jj];
        }else{
          if( pTo->rCost<=rCost ) continue;
        }
        /* pWLoop is a winner.  Add it to the set of best so far */
        pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
        pTo->revLoop = revMask;
        pTo->nRow = pFrom->nRow * pWLoop->nOut;
        pTo->rCost = rCost;
        pTo->isOrderedValid = isOrderedValid;
        pTo->isOrdered = isOrdered;
        memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
        pTo->aLoop[iLoop] = pWLoop;
        if( nTo>=mxChoice ){
................................................................................

  wherePathSolver(pWInfo);
  if( db->mallocFailed ) goto whereBeginError;
#if defined(SQLITE_DEBUG) \
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
  if( sqlite3WhereTrace ){
    int ii;
    sqlite3DebugPrintf("------------ Solution -------------");
    if( pWInfo->nOBSat ){
      sqlite3DebugPrintf(" ORDER BY omitted\n");
    }else{
      sqlite3DebugPrintf("\n");
    }
    for(ii=0; ii<nTabList; ii++){
      whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList);
    }
  }
#endif

  /* Chose the best index to use for each table in the FROM clause.