SQLite

Check-in [8e5aad3752]
Login

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
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.354
Context
2013-05-08
14:13
Fix the wholenumber virtual table so that it returns higher costs for unconstrained usage. (check-in: ceff895502 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: 8e5aad3752 user: drh tags: nextgen-query-plan-exp)
03:22
Bug fixes in the solver. (check-in: b36034bbd1 user: drh tags: nextgen-query-plan-exp)
Changes
Unified Diff 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

  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 );








<
<
<
<
<
<
<
<
<








706
707
708
709
710
711
712









713
714
715
716
717
718
719

  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 );
︙︙
749
750
751
752
753
754
755







756
757
758
759
760
761
762

              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;
          }
        }
      }








>
>
>
>
>
>
>








740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760

              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;
          }
        }
      }
︙︙
5054
5055
5056
5057
5058
5059
5060
5061

5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074

/*
** 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








|
>
|


|

|








5052
5053
5054
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073

/*
** 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
︙︙
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
5290
5291
5292

  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








|








5277
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
5290
5291

  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
︙︙
5456
5457
5458
5459
5460
5461
5462
5463
5464
5465
5466
5467
5468
5469
5470

        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;








|








5455
5456
5457
5458
5459
5460
5461
5462
5463
5464
5465
5466
5467
5468
5469

        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;
︙︙