/ Check-in [8e5aad37]
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:More bug fixes to the WhereLoop generator and the solver in NGQP. Now finds the best plan for TPC-H Q8. This seems to prove the concept, but there is still much work to be done.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 8e5aad37529ec3042e3468acf15186f566e2df8a
User & Date: drh 2013-05-08 04:22:59
Context
2013-05-08
14:13
Fix the wholenumber virtual table so that it returns higher costs for unconstrained usage. check-in: ceff8955 user: drh tags: nextgen-query-plan-exp
04:22
More bug fixes to the WhereLoop generator and the solver in NGQP. Now finds the best plan for TPC-H Q8. This seems to prove the concept, but there is still much work to be done. check-in: 8e5aad37 user: drh tags: nextgen-query-plan-exp
03:22
Bug fixes in the solver. check-in: b36034bb user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
...
749
750
751
752
753
754
755







756
757
758
759
760
761
762
....
5054
5055
5056
5057
5058
5059
5060
5061

5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
....
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
5290
5291
5292
....
5456
5457
5458
5459
5460
5461
5462
5463
5464
5465
5466
5467
5468
5469
5470
  WhereTerm *pTerm;    /* The term being tested */

  while( pScan->iEquiv<=pScan->nEquiv ){
    iCur = pScan->aEquiv[pScan->iEquiv-2];
    iColumn = pScan->aEquiv[pScan->iEquiv-1];
    while( (pWC = pScan->pWC)!=0 ){
      for(pTerm=pWC->a+pScan->k; pScan->k<pWC->nTerm; pScan->k++, pTerm++){
        if( pTerm->iParent>=0 ){
          WhereTerm *pParent = &pWC->a[pTerm->iParent];
          int j;
          for(j=pScan->iEquiv-4; j>=0; j-=2 ){
            if( pParent->leftCursor==pScan->aEquiv[j]
             && pParent->u.leftColumn==pScan->aEquiv[j+1] ) break;
          }
          if( j>=0 ) continue;
        }
        if( pTerm->leftCursor==iCur && pTerm->u.leftColumn==iColumn ){
          if( (pTerm->eOperator & WO_EQUIV)!=0
           && pScan->nEquiv<ArraySize(pScan->aEquiv)
          ){
            int j;
            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
            assert( pX->op==TK_COLUMN );
................................................................................
              assert(pX->pLeft);
              pColl = sqlite3BinaryCompareCollSeq(pWC->pParse,
                                                  pX->pLeft, pX->pRight);
              if( pColl==0 ) pColl = pWC->pParse->db->pDfltColl;
              if( sqlite3StrICmp(pColl->zName, pScan->zCollName) ){
                continue;
              }







            }
            pScan->pCurrent = pTerm;
            pScan->k++;
            return pTerm;
          }
        }
      }
................................................................................
/*
** Print a WhereLoop object for debugging purposes
*/
static void whereLoopPrint(WhereLoop *p, SrcList *pTabList){
  int nb = 2*((pTabList->nSrc+15)/16);
  struct SrcList_item *pItem = pTabList->a + p->iTab;
  Table *pTab = pItem->pTab;
  sqlite3DebugPrintf("%02d.%0*llx", p->iTab, nb, p->prereq);

  sqlite3DebugPrintf(" %6s",
                     pItem->zAlias ? pItem->zAlias : pTab->zName);
  if( p->pIndex ){
    sqlite3DebugPrintf(".%-8s %2d", p->pIndex->zName, p->nEq);
  }else{
    sqlite3DebugPrintf("%12s","");
  }
  sqlite3DebugPrintf(" fg %08x OB %d,%d N %2d",
                     p->wsFlags, p->iOb, p->nOb, p->nTerm);
  sqlite3DebugPrintf(" cost %.4g,%.4g,%.4g\n",
                     p->prereq, p->rSetup, p->rRun, p->nOut);
}
#endif
................................................................................
  struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  sqlite3 *db;                /* The database connection */
  WhereLoop *pNew;            /* Template WhereLoop object */

  pNew = pBuilder->pNew;
  db = pBuilder->db;
  pSrc = pBuilder->pTabList->a + iTab;
  pNew->maskSelf = getMask(pBuilder->pWC->pMaskSet, iTab);

  if( pSrc->pIndex ){
    /* An INDEXED BY clause specifies a particular index to use */
    pProbe = pSrc->pIndex;
  }else{
    /* There is no INDEXED BY clause.  Create a fake Index object in local
    ** variable sPk to represent the rowid primary key index.  Make this
................................................................................
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        for(jj=0, pTo=aTo; jj<nTo && pTo->maskLoop!=maskNew; jj++){}
        if( jj>=nTo ){
          if( nTo>=mxChoice && rCost>=mxCost ) continue;
          if( nTo<mxChoice ){
            jj = nTo++;
          }else{
            for(jj=nTo-1; aTo[jj].rCost>=mxCost; jj++){ assert(jj>0); }
          }
          pTo = &aTo[jj];
        }else{
          if( pTo->rCost<=rCost ) continue;
        }
        pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
        pTo->nRow = pFrom->nRow * pWLoop->nOut;







<
<
<
<
<
<
<
<
<







 







>
>
>
>
>
>
>







 







|
>
|


|

|







 







|







 







|







706
707
708
709
710
711
712









713
714
715
716
717
718
719
...
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
....
5052
5053
5054
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
....
5277
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
5290
5291
....
5455
5456
5457
5458
5459
5460
5461
5462
5463
5464
5465
5466
5467
5468
5469
  WhereTerm *pTerm;    /* The term being tested */

  while( pScan->iEquiv<=pScan->nEquiv ){
    iCur = pScan->aEquiv[pScan->iEquiv-2];
    iColumn = pScan->aEquiv[pScan->iEquiv-1];
    while( (pWC = pScan->pWC)!=0 ){
      for(pTerm=pWC->a+pScan->k; pScan->k<pWC->nTerm; pScan->k++, pTerm++){









        if( pTerm->leftCursor==iCur && pTerm->u.leftColumn==iColumn ){
          if( (pTerm->eOperator & WO_EQUIV)!=0
           && pScan->nEquiv<ArraySize(pScan->aEquiv)
          ){
            int j;
            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
            assert( pX->op==TK_COLUMN );
................................................................................
              assert(pX->pLeft);
              pColl = sqlite3BinaryCompareCollSeq(pWC->pParse,
                                                  pX->pLeft, pX->pRight);
              if( pColl==0 ) pColl = pWC->pParse->db->pDfltColl;
              if( sqlite3StrICmp(pColl->zName, pScan->zCollName) ){
                continue;
              }
            }
            if( (pTerm->eOperator & WO_EQ)!=0
             && (pX = pTerm->pExpr->pRight)->op==TK_COLUMN
             && pX->iTable==pScan->aEquiv[0]
             && pX->iColumn==pScan->aEquiv[1]
            ){
              continue;
            }
            pScan->pCurrent = pTerm;
            pScan->k++;
            return pTerm;
          }
        }
      }
................................................................................
/*
** Print a WhereLoop object for debugging purposes
*/
static void whereLoopPrint(WhereLoop *p, SrcList *pTabList){
  int nb = 2*((pTabList->nSrc+15)/16);
  struct SrcList_item *pItem = pTabList->a + p->iTab;
  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->pIndex ){
    sqlite3DebugPrintf(".%-12s %2d", p->pIndex->zName, p->nEq);
  }else{
    sqlite3DebugPrintf("%16s","");
  }
  sqlite3DebugPrintf(" fg %08x OB %d,%d N %2d",
                     p->wsFlags, p->iOb, p->nOb, p->nTerm);
  sqlite3DebugPrintf(" cost %.4g,%.4g,%.4g\n",
                     p->prereq, p->rSetup, p->rRun, p->nOut);
}
#endif
................................................................................
  struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  sqlite3 *db;                /* The database connection */
  WhereLoop *pNew;            /* Template WhereLoop object */

  pNew = pBuilder->pNew;
  db = pBuilder->db;
  pSrc = pBuilder->pTabList->a + iTab;
  pNew->maskSelf = getMask(pBuilder->pWC->pMaskSet, pSrc->iCursor);

  if( pSrc->pIndex ){
    /* An INDEXED BY clause specifies a particular index to use */
    pProbe = pSrc->pIndex;
  }else{
    /* There is no INDEXED BY clause.  Create a fake Index object in local
    ** variable sPk to represent the rowid primary key index.  Make this
................................................................................
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        for(jj=0, pTo=aTo; jj<nTo && pTo->maskLoop!=maskNew; jj++){}
        if( jj>=nTo ){
          if( nTo>=mxChoice && rCost>=mxCost ) continue;
          if( nTo<mxChoice ){
            jj = nTo++;
          }else{
            for(jj=nTo-1; aTo[jj].rCost>=mxCost; jj--){ assert(jj>0); }
          }
          pTo = &aTo[jj];
        }else{
          if( pTo->rCost<=rCost ) continue;
        }
        pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
        pTo->nRow = pFrom->nRow * pWLoop->nOut;