/ Check-in [ec5d84ba]
Login

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

Overview
Comment:Oops! This check-in was on trunk. But it contains a debugging printf(). Original comment: When the estimated cost to do a sort overwhelms the estimated cost to do individual table lookups, make sure that the table lookup costs are still taken into consideration when selecting the lookup algorithm.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | query-planner-fix
Files: files | file ages | folders
SHA1:ec5d84ba69c100d9565425ed74040a49e410ea03
User & Date: drh 2014-08-07 16:50:00
Original Comment: When the estimated cost to do a sort overwhelms the estimated cost to do individual table lookups, make sure that the table lookup costs are still taken into consideration when selecting the lookup algorithm.
Context
2014-08-07
20:25
Remove the extraneous debugging printf() from the previous check-in. check-in: 8f04d2c0 user: drh tags: query-planner-fix
16:50
Oops! This check-in was on trunk. But it contains a debugging printf(). Original comment: When the estimated cost to do a sort overwhelms the estimated cost to do individual table lookups, make sure that the table lookup costs are still taken into consideration when selecting the lookup algorithm. check-in: ec5d84ba user: drh tags: query-planner-fix
2014-08-06
18:50
A couple more harmless compiler warnings eliminated. check-in: bcf6d775 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

5420
5421
5422
5423
5424
5425
5426

5427
5428
5429
5430
5431
5432
5433
....
5437
5438
5439
5440
5441
5442
5443
5444
5445
5446
5447
5448
5449
5450
5451
....
5525
5526
5527
5528
5529
5530
5531
5532






5533
5534
5535
5536
5537
5538
5539
5540
5541


5542





5543
5544
5545
5546
5547
5548
5549
5550
5551
5552

5553
5554
5555
5556
5557
5558
5559
....
5562
5563
5564
5565
5566
5567
5568
5569




5570
5571
5572
5573
5574
5575
5576
5577
5578
5579
5580

5581
5582
5583
5584
5585

5586
5587
5588
5589
5590
5591
5592
....
5602
5603
5604
5605
5606
5607
5608

5609
5610
5611

5612
5613
5614
5615
5616
5617
5618
  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 */
................................................................................
  db = pParse->db;
  nLoop = pWInfo->nLevel;
  /* TUNING: For simple queries, only the best path is tracked.
  ** For 2-way joins, the 5 best paths are followed.
  ** For joins of 3 or more tables, track the 10 best paths */
  mxChoice = (nLoop<=1) ? 1 : (nLoop==2 ? 5 : 10);
  assert( nLoop<=pWInfo->pTabList->nSrc );
  WHERETRACE(0x002, ("---- begin solver\n"));

  /* Allocate and initialize space for aTo and aFrom */
  ii = (sizeof(WherePath)+sizeof(WhereLoop*)*nLoop)*mxChoice*2;
  pSpace = sqlite3DbMallocRaw(db, ii);
  if( pSpace==0 ) return SQLITE_NOMEM;
  aTo = (WherePath*)pSpace;
  aFrom = aTo+mxChoice;
................................................................................
                rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost,
                sqlite3LogEstAdd(rCost,rSortCost)));
            rCost = sqlite3LogEstAdd(rCost, rSortCost);
          }
        }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 ){





#ifdef WHERETRACE_ENABLED /* 0x4 */
            if( sqlite3WhereTrace&0x4 ){
              sqlite3DebugPrintf("Skip   %s cost=%-3d,%3d order=%c\n",
                  wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
                  isOrdered>=0 ? isOrdered+'0' : '?');
            }
#endif
            continue;
          }
          /* Add a new Path to the aTo[] set */

          if( nTo<mxChoice ){
            /* Increase the size of the aTo set by one */
            jj = nTo++;
          }else{
            /* New path replaces the prior worst to keep count below mxChoice */
            jj = mxI;
          }
................................................................................
          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",
                  wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
                  pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?');
            }
#endif

            testcase( pTo->rCost==rCost );
            continue;
          }
          testcase( pTo->rCost==rCost+1 );
          /* A new and better score for a previously created equivalent path */

#ifdef WHERETRACE_ENABLED /* 0x4 */
          if( sqlite3WhereTrace&0x4 ){
            sqlite3DebugPrintf(
                "Update %s cost=%-3d,%3d order=%c",
                wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
                isOrdered>=0 ? isOrdered+'0' : '?');
            sqlite3DebugPrintf("  was %s cost=%-3d,%3d 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;
            }
          }
        }
      }
    }








>







 







|







 







|
>
>
>
>
>
>









>
>
|
>
>
>
>
>









|
>







 







|
>
>
>
>











>




|
>







 







>

|

>







5420
5421
5422
5423
5424
5425
5426
5427
5428
5429
5430
5431
5432
5433
5434
....
5438
5439
5440
5441
5442
5443
5444
5445
5446
5447
5448
5449
5450
5451
5452
....
5526
5527
5528
5529
5530
5531
5532
5533
5534
5535
5536
5537
5538
5539
5540
5541
5542
5543
5544
5545
5546
5547
5548
5549
5550
5551
5552
5553
5554
5555
5556
5557
5558
5559
5560
5561
5562
5563
5564
5565
5566
5567
5568
5569
5570
5571
5572
5573
5574
....
5577
5578
5579
5580
5581
5582
5583
5584
5585
5586
5587
5588
5589
5590
5591
5592
5593
5594
5595
5596
5597
5598
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
5609
5610
5611
5612
5613
....
5623
5624
5625
5626
5627
5628
5629
5630
5631
5632
5633
5634
5635
5636
5637
5638
5639
5640
5641
  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;         /* nOut value for maximum cost path */
  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 */
................................................................................
  db = pParse->db;
  nLoop = pWInfo->nLevel;
  /* TUNING: For simple queries, only the best path is tracked.
  ** For 2-way joins, the 5 best paths are followed.
  ** For joins of 3 or more tables, track the 10 best paths */
  mxChoice = (nLoop<=1) ? 1 : (nLoop==2 ? 5 : 10);
  assert( nLoop<=pWInfo->pTabList->nSrc );
  WHERETRACE(0x002, ("---- begin solver.  (nRowEst=%d)\n", nRowEst));

  /* Allocate and initialize space for aTo and aFrom */
  ii = (sizeof(WherePath)+sizeof(WhereLoop*)*nLoop)*mxChoice*2;
  pSpace = sqlite3DbMallocRaw(db, ii);
  if( pSpace==0 ) return SQLITE_NOMEM;
  aTo = (WherePath*)pSpace;
  aFrom = aTo+mxChoice;
................................................................................
                rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost,
                sqlite3LogEstAdd(rCost,rSortCost)));
            rCost = sqlite3LogEstAdd(rCost, rSortCost);
          }
        }else{
          revMask = pFrom->revLoop;
        }
        /* Check to see if pWLoop should be added to the set of
        ** mxChoice best-so-far paths.
        **
        ** First look for an existing path among best-so-far paths
        ** that covers the same set of loops and has the same isOrdered
        ** setting as the current path candidate.
        */
        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 ){
          /* None of the existing best-so-far paths match the candidate. */
if( nTo>=mxChoice && rCost==mxCost ) printf("nOut=%d mxOut=%d\n", nOut, mxOut);
          if( nTo>=mxChoice
           && (rCost>mxCost || (rCost==mxCost && nOut>=mxOut))
          ){
            /* The current candidate is no better than any of the mxChoice
            ** paths currently in the best-so-far buffer.  So discard
            ** this candidate as not viable. */
#ifdef WHERETRACE_ENABLED /* 0x4 */
            if( sqlite3WhereTrace&0x4 ){
              sqlite3DebugPrintf("Skip   %s cost=%-3d,%3d order=%c\n",
                  wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
                  isOrdered>=0 ? isOrdered+'0' : '?');
            }
#endif
            continue;
          }
          /* If we reach this points it means that the new candidate path
          ** needs to be added to the set of best-so-far paths. */
          if( nTo<mxChoice ){
            /* Increase the size of the aTo set by one */
            jj = nTo++;
          }else{
            /* New path replaces the prior worst to keep count below mxChoice */
            jj = mxI;
          }
................................................................................
          if( sqlite3WhereTrace&0x4 ){
            sqlite3DebugPrintf("New    %s cost=%-3d,%3d order=%c\n",
                wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
                isOrdered>=0 ? isOrdered+'0' : '?');
          }
#endif
        }else{
          /* Control reaches here if best-so-far path pTo=aTo[jj] covers the
          ** same set of loops and has the sam isOrdered setting as the
          ** candidate path.  Check to see if the candidate should replace
          ** pTo or if the candidate should be skipped */
          if( pTo->rCost<rCost || (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",
                  wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
                  pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?');
            }
#endif
            /* Discard the candidate path from further consideration */
            testcase( pTo->rCost==rCost );
            continue;
          }
          testcase( pTo->rCost==rCost+1 );
          /* Control reaches here if the candidate path is better than the
          ** pTo path.  Replace pTo with the candidate. */
#ifdef WHERETRACE_ENABLED /* 0x4 */
          if( sqlite3WhereTrace&0x4 ){
            sqlite3DebugPrintf(
                "Update %s cost=%-3d,%3d order=%c",
                wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
                isOrdered>=0 ? isOrdered+'0' : '?');
            sqlite3DebugPrintf("  was %s cost=%-3d,%3d 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;
            }
          }
        }
      }
    }

Changes to test/whereJ.test.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
323
324
325
326
327
328
329
330












































331
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# 
# This file implements a single regression test for a complex
# query planning case.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set ::testprefix whereJ

................................................................................
  SELECT aid, sid, MAX(edate) edate
    FROM tx1
   WHERE cid = 115790
     AND sid = 9100
     AND edate <= 20140430 AND edate >= 20120429
   GROUP BY aid;
} {/B-TREE/}













































finish_test







|







 








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

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# 
# This file implements regression tests for a complex
# query planning case.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set ::testprefix whereJ

................................................................................
  SELECT aid, sid, MAX(edate) edate
    FROM tx1
   WHERE cid = 115790
     AND sid = 9100
     AND edate <= 20140430 AND edate >= 20120429
   GROUP BY aid;
} {/B-TREE/}

############################################################################
# Ensure that the sorting cost does not swamp the loop costs and cause
# distinctions between individual loop costs to get lost, and hence for
# sub-optimal loops to be chosen.
#
do_execsql_test whereJ-2.1 {
  CREATE TABLE tab(
    id INTEGER PRIMARY KEY,
    minChild INTEGER REFERENCES t1,
    maxChild INTEGER REFERENCES t1,
    x INTEGER
  );
  EXPLAIN QUERY PLAN
  SELECT t4.x
    FROM tab AS t0, tab AS t1, tab AS t2, tab AS t3, tab AS t4
   WHERE t0.id=0
     AND t1.id BETWEEN t0.minChild AND t0.maxChild
     AND t2.id BETWEEN t1.minChild AND t1.maxChild
     AND t3.id BETWEEN t2.minChild AND t2.maxChild
     AND t4.id BETWEEN t3.minChild AND t3.maxChild
  ORDER BY t4.x;
} {~/SCAN/}
do_execsql_test whereJ-2.2 {
  EXPLAIN QUERY PLAN
  SELECT t4.x
    FROM tab AS t0a, tab AS t0b,
         tab AS t1a, tab AS t1b,
         tab AS t2a, tab AS t2b,
         tab AS t3a, tab AS t3b,
         tab AS t4
   WHERE 1
     AND t0a.id=1
     AND t1a.id BETWEEN t0a.minChild AND t0a.maxChild
     AND t2a.id BETWEEN t1a.minChild AND t1a.maxChild
     AND t3a.id BETWEEN t2a.minChild AND t2a.maxChild
     AND t0b.id=2
     AND t1b.id BETWEEN t0b.minChild AND t0b.maxChild
     AND t2b.id BETWEEN t1b.minChild AND t1b.maxChild
     AND t3b.id BETWEEN t2b.minChild AND t2b.maxChild
     AND t4.id BETWEEN t3a.minChild AND t3b.maxChild
  ORDER BY t4.x;
} {~/SCAN/}


finish_test