SQLite

Check-in [b36034bbd1]
Login

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

Overview
Comment:Bug fixes in the solver.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: b36034bbd19bc5677b26a6f60ca96eb2b37db373
User & Date: drh 2013-05-08 03:22:07.536
Context
2013-05-08
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)
03:05
Add the NGQP solver. (check-in: 5d37587c50 user: drh tags: nextgen-query-plan-exp)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
︙︙
5439
5440
5441
5442
5443
5444
5445

5446
5447
5448
5449
5450
5451
5452
5453
5454
5455
5456
5457
5458
5459
5460
5461
5462
5463
5464


5465
5466
5467
5468
5469
5470
5471
5472
5473
5474
5475
5476
5477
5478
5479













5480
5481
5482
5483
5484
5485
5486

  aFrom = aTo+mxChoice;
  memset(aFrom, 0, sizeof(aFrom[0]));
  pX = (WhereLoop**)(aFrom+mxChoice);
  for(ii=0, pFrom=aTo; ii<mxChoice*2; ii++, pFrom++, pX += nLoop){
    pFrom->aLoop = pX;
  }


  nFrom = 1;
  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;
        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        rCost = pWLoop->rSetup + pWLoop->rRun*pFrom->nRow + pFrom->rCost;
        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];


        }
        pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
        pTo->nRow = pFrom->nRow * pWLoop->nOut;
        pTo->rCost = rCost;
        memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
        pTo->aLoop[iLoop] = pWLoop;
        if( nTo>=mxChoice ){
          mxCost = aTo[0].rCost;
          for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){
            if( pTo->rCost>mxCost ) mxCost = pTo->rCost;
          }
        }
      }
    }














    /* Swap the roles of aFrom and aTo in preparation for the next
    ** cycle. */
    pFrom = aTo;
    aTo = aFrom;
    aFrom = pFrom;
    nFrom = nTo;
  }








>



















>
>















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








5439
5440
5441
5442
5443
5444
5445
5446
5447
5448
5449
5450
5451
5452
5453
5454
5455
5456
5457
5458
5459
5460
5461
5462
5463
5464
5465
5466
5467
5468
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

  aFrom = aTo+mxChoice;
  memset(aFrom, 0, sizeof(aFrom[0]));
  pX = (WhereLoop**)(aFrom+mxChoice);
  for(ii=0, pFrom=aTo; ii<mxChoice*2; ii++, pFrom++, pX += nLoop){
    pFrom->aLoop = pX;
  }

  aFrom[0].nRow = (double)1;
  nFrom = 1;
  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;
        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        rCost = pWLoop->rSetup + pWLoop->rRun*pFrom->nRow + pFrom->rCost;
        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;
        pTo->rCost = rCost;
        memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
        pTo->aLoop[iLoop] = pWLoop;
        if( nTo>=mxChoice ){
          mxCost = aTo[0].rCost;
          for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){
            if( pTo->rCost>mxCost ) mxCost = pTo->rCost;
          }
        }
      }
    }

#if 0
    if( sqlite3WhereTrace ){
      sqlite3DebugPrintf("---- round %d ---- nTo=%d\n", iLoop, nTo);
      for(ii=0; ii<nTo; ii++){
        sqlite3DebugPrintf("%03d:  cost=%g  nrow=%g\n",
           ii, aTo[ii].rCost, aTo[ii].nRow);
        for(jj=0; jj<=iLoop; jj++){
          whereLoopPrint(aTo[ii].aLoop[jj], pWInfo->pTabList);
        }
      }
    }
#endif

    /* Swap the roles of aFrom and aTo in preparation for the next
    ** cycle. */
    pFrom = aTo;
    aTo = aFrom;
    aFrom = pFrom;
    nFrom = nTo;
  }
︙︙