/ Check-in [f270fb6e]
Login

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

Overview
Comment:A different approach to the autoindex problem that deletes query-planner code rather than adding it.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | autoindex-improvements
Files: files | file ages | folders
SHA1:f270fb6e9e0b5e77f918081962008c6195ab1e36
User & Date: drh 2014-06-17 12:33:55
Context
2014-06-17
13:23
Add the autoindex2.test testing module. check-in: ffe3fea4 user: drh tags: autoindex-improvements
12:33
A different approach to the autoindex problem that deletes query-planner code rather than adding it. check-in: f270fb6e user: drh tags: autoindex-improvements
09:52
Simplification to the logic that prevents automatic indexes from being formed on constant expressions. check-in: 36d67e1d user: drh tags: autoindex-improvements
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree6.test.

98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 
  0 1 1 {SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX (v=?)}
}
do_eqp_test rtree6.2.4.2 {
  SELECT * FROM t1,t2 WHERE v=10 and x1<10 and x2>10
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 
  0 1 1 {SCAN TABLE t2}
}

do_eqp_test rtree6.2.5 {
  SELECT * FROM t1,t2 WHERE k=ii AND x1<v
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 
  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}







|







98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 
  0 1 1 {SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX (v=?)}
}
do_eqp_test rtree6.2.4.2 {
  SELECT * FROM t1,t2 WHERE v=10 and x1<10 and x2>10
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 
  0 1 1 {SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX (v=?)}
}

do_eqp_test rtree6.2.5 {
  SELECT * FROM t1,t2 WHERE k=ii AND x1<v
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 
  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}

Changes to src/where.c.

4525
4526
4527
4528
4529
4530
4531
4532
4533
4534
4535
4536
4537
4538
4539
....
5275
5276
5277
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
....
5385
5386
5387
5388
5389
5390
5391
5392
5393
5394
5395
5396
5397
5398
5399
5400
....
5420
5421
5422
5423
5424
5425
5426
5427
5428
5429
5430
5431
5432
5433
5434
....
5460
5461
5462
5463
5464
5465
5466
5467
5468
5469
5470
5471
5472
5473
5474
5475
5476
5477
5478
   && !pSrc->isRecursive
  ){
    /* Generate auto-index WhereLoops */
    WhereTerm *pTerm;
    WhereTerm *pWCEnd = pWC->a + pWC->nTerm;
    for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){
      if( pTerm->prereqRight & pNew->maskSelf ) continue;
      if( sqlite3ExprIsConstant(pTerm->pExpr->pRight) ) continue;
      if( termCanDriveIndex(pTerm, pSrc, 0) ){
        pNew->u.btree.nEq = 1;
        pNew->u.btree.nSkip = 0;
        pNew->u.btree.pIndex = 0;
        pNew->nLTerm = 1;
        pNew->aLTerm[0] = pTerm;
        /* TUNING: One-time cost for computing the automatic index is
................................................................................
  int iLoop;                /* Loop counter over the terms of the join */
  int ii, jj;               /* Loop counters */
  int mxI = 0;              /* Index of next entry to replace */
  int nOrderBy;             /* Number of ORDER BY clause terms */
  LogEst rCost;             /* Cost of a path */
  LogEst nOut;              /* Number of outputs */
  LogEst mxCost = 0;        /* Maximum cost of a set of paths */
  LogEst mxOut = 0;         /* Maximum nOut value on the set of paths */
  int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
  WherePath *aFrom;         /* All nFrom paths at the previous level */
  WherePath *aTo;           /* The nTo best paths at the current level */
  WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  WherePath *pTo;           /* An element of aTo[] that we are working on */
  WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  WhereLoop **pX;           /* Used to divy up the pSpace memory */
................................................................................
        }else{
          revMask = pFrom->revLoop;
        }
        /* Check to see if pWLoop should be added to the mxChoice best so far */
        for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){
          if( pTo->maskLoop==maskNew
           && ((pTo->isOrdered^isOrdered)&80)==0
           && ((pTo->rCost<=rCost && pTo->nRow<=nOut) ||
                (pTo->rCost>=rCost && pTo->nRow>=nOut))
          ){
            testcase( jj==nTo-1 );
            break;
          }
        }
        if( jj>=nTo ){
          if( nTo>=mxChoice && rCost>=mxCost ){
................................................................................
          if( sqlite3WhereTrace&0x4 ){
            sqlite3DebugPrintf("New    %s cost=%-3d,%3d order=%c\n",
                wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
                isOrdered>=0 ? isOrdered+'0' : '?');
          }
#endif
        }else{
          if( pTo->rCost<=rCost && pTo->nRow<=nOut ){
#ifdef WHERETRACE_ENABLED /* 0x4 */
            if( sqlite3WhereTrace&0x4 ){
              sqlite3DebugPrintf(
                  "Skip   %s cost=%-3d,%3d order=%c",
                  wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
                  isOrdered>=0 ? isOrdered+'0' : '?');
              sqlite3DebugPrintf("   vs %s cost=%-3d,%d order=%c\n",
................................................................................
        pTo->rCost = rCost;
        pTo->isOrdered = isOrdered;
        memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
        pTo->aLoop[iLoop] = pWLoop;
        if( nTo>=mxChoice ){
          mxI = 0;
          mxCost = aTo[0].rCost;
          mxOut = aTo[0].nRow;
          for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){
            if( pTo->rCost>mxCost || (pTo->rCost==mxCost && pTo->nRow>mxOut) ){
              mxCost = pTo->rCost;
              mxOut = pTo->nRow;
              mxI = jj;
            }
          }
        }
      }
    }








<







 







<







 







<
<







 







|







 







<

|

<







4525
4526
4527
4528
4529
4530
4531

4532
4533
4534
4535
4536
4537
4538
....
5274
5275
5276
5277
5278
5279
5280

5281
5282
5283
5284
5285
5286
5287
....
5383
5384
5385
5386
5387
5388
5389


5390
5391
5392
5393
5394
5395
5396
....
5416
5417
5418
5419
5420
5421
5422
5423
5424
5425
5426
5427
5428
5429
5430
....
5456
5457
5458
5459
5460
5461
5462

5463
5464
5465

5466
5467
5468
5469
5470
5471
5472
   && !pSrc->isRecursive
  ){
    /* Generate auto-index WhereLoops */
    WhereTerm *pTerm;
    WhereTerm *pWCEnd = pWC->a + pWC->nTerm;
    for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){
      if( pTerm->prereqRight & pNew->maskSelf ) continue;

      if( termCanDriveIndex(pTerm, pSrc, 0) ){
        pNew->u.btree.nEq = 1;
        pNew->u.btree.nSkip = 0;
        pNew->u.btree.pIndex = 0;
        pNew->nLTerm = 1;
        pNew->aLTerm[0] = pTerm;
        /* TUNING: One-time cost for computing the automatic index is
................................................................................
  int iLoop;                /* Loop counter over the terms of the join */
  int ii, jj;               /* Loop counters */
  int mxI = 0;              /* Index of next entry to replace */
  int nOrderBy;             /* Number of ORDER BY clause terms */
  LogEst rCost;             /* Cost of a path */
  LogEst nOut;              /* Number of outputs */
  LogEst mxCost = 0;        /* Maximum cost of a set of paths */

  int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
  WherePath *aFrom;         /* All nFrom paths at the previous level */
  WherePath *aTo;           /* The nTo best paths at the current level */
  WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  WherePath *pTo;           /* An element of aTo[] that we are working on */
  WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  WhereLoop **pX;           /* Used to divy up the pSpace memory */
................................................................................
        }else{
          revMask = pFrom->revLoop;
        }
        /* Check to see if pWLoop should be added to the mxChoice best so far */
        for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){
          if( pTo->maskLoop==maskNew
           && ((pTo->isOrdered^isOrdered)&80)==0


          ){
            testcase( jj==nTo-1 );
            break;
          }
        }
        if( jj>=nTo ){
          if( nTo>=mxChoice && rCost>=mxCost ){
................................................................................
          if( sqlite3WhereTrace&0x4 ){
            sqlite3DebugPrintf("New    %s cost=%-3d,%3d order=%c\n",
                wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
                isOrdered>=0 ? isOrdered+'0' : '?');
          }
#endif
        }else{
          if( pTo->rCost<=rCost ){
#ifdef WHERETRACE_ENABLED /* 0x4 */
            if( sqlite3WhereTrace&0x4 ){
              sqlite3DebugPrintf(
                  "Skip   %s cost=%-3d,%3d order=%c",
                  wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
                  isOrdered>=0 ? isOrdered+'0' : '?');
              sqlite3DebugPrintf("   vs %s cost=%-3d,%d order=%c\n",
................................................................................
        pTo->rCost = rCost;
        pTo->isOrdered = isOrdered;
        memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
        pTo->aLoop[iLoop] = pWLoop;
        if( nTo>=mxChoice ){
          mxI = 0;
          mxCost = aTo[0].rCost;

          for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){
            if( pTo->rCost>mxCost ){
              mxCost = pTo->rCost;

              mxI = jj;
            }
          }
        }
      }
    }