/ Check-in [ca839723]
Login

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

Overview
Comment:Attempt to disable inner loops of a join that do not generate output. This does not work, since the inner loops might run zero times and thus inhibit all output. Needs to be enhanced to work only for LEFT JOINs or when we know that the inner loop will always run at least once.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | omit-join-table-opt
Files: files | file ages | folders
SHA1: ca839723a21bb13d3e0666a672c15c6f3a267c2f
User & Date: drh 2013-06-21 02:05:06
Context
2013-06-21
02:15
Only eliminate inner loops of a JOIN if they are the RHS of a LEFT JOIN and if they give no more than a single result. This appears to give correct answers in all cases. check-in: d7a25cc7 user: drh tags: omit-join-table-opt
02:05
Attempt to disable inner loops of a join that do not generate output. This does not work, since the inner loops might run zero times and thus inhibit all output. Needs to be enhanced to work only for LEFT JOINs or when we know that the inner loop will always run at least once. check-in: ca839723 user: drh tags: omit-join-table-opt
00:35
Modify the query planner interface so that it always passes in the result set. This is the first step toward adding an optimization that will omit tables from a join that do not contribute to the result. check-in: 2c2577e6 user: drh tags: omit-join-table-opt
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

388
389
390
391
392
393
394

395
396
397
398
399
400
401
402
403
404
405
....
5366
5367
5368
5369
5370
5371
5372
5373
5374

5375
5376
5377
5378
5379
5380
5381
....
5567
5568
5569
5570
5571
5572
5573

5574
5575
5576
5577
5578
5579

5580
5581






5582
5583
5584
5585
5586
5587
5588
....
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
5609
5610
5611
5612
5613
....
5624
5625
5626
5627
5628
5629
5630
5631
5632
5633
5634
5635
5636
5637
5638
5639
5640
5641
5642
5643
....
5714
5715
5716
5717
5718
5719
5720
5721
5722
5723
5724
5725
5726
5727
5728
....
5733
5734
5735
5736
5737
5738
5739
5740
5741
5742
5743
5744
5745
5746
5747
5748
5749
5750
5751
....
5778
5779
5780
5781
5782
5783
5784
5785
5786
5787
5788
5789


















5790
5791
5792
5793
5794
5795
5796
....
5951
5952
5953
5954
5955
5956
5957
5958
5959
5960
5961
5962
5963
5964
5965
  Bitmask revMask;          /* Mask of ORDER BY terms that need reversing */
  WhereCost nRowOut;        /* Estimated number of output rows */
  u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
  u8 bOBSat;                /* ORDER BY satisfied by indices */
  u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
  u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */

  int iTop;                 /* The very beginning of the WHERE loop */
  int iContinue;            /* Jump here to continue with next record */
  int iBreak;               /* Jump here to break out of the loop */
  int nLevel;               /* Number of nested loop */
  int savedNQueryLoop;      /* pParse->nQueryLoop outside the WHERE loop */
  WhereMaskSet sMaskSet;    /* Map cursor numbers to bitmasks */
  WhereClause sWC;          /* Decomposition of the WHERE clause */
  WhereLevel a[1];          /* Information about each nest loop in WHERE */
};

/*
................................................................................
  /* Load the lowest cost path into pWInfo */
  for(iLoop=0; iLoop<nLoop; iLoop++){
    WhereLevel *pLevel = pWInfo->a + iLoop;
    pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop];
    pLevel->iFrom = pWLoop->iTab;
    pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor;
  }
  if( (pWInfo->wctrlFlags & (WHERE_DISTINCTBY|WHERE_WANT_DISTINCT))
                ==WHERE_WANT_DISTINCT

   && nRowEst
  ){
    Bitmask notUsed;
    int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom,
                 WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed);
    if( rc==1 ) pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  }
................................................................................
  int nTabList;              /* Number of elements in pTabList */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  Bitmask notReady;          /* Cursors that are not yet positioned */
  WhereLoopBuilder sWLB;     /* The WhereLoop builder */
  WhereMaskSet *pMaskSet;    /* The expression mask set */
  WhereLevel *pLevel;        /* A single level in pWInfo->a[] */

  int ii;                    /* Loop counter */
  sqlite3 *db;               /* Database connection */
  int rc;                    /* Return code */


  /* Variable initialization */

  memset(&sWLB, 0, sizeof(sWLB));
  sWLB.pOrderBy = pOrderBy;







  /* The number of tables in the FROM clause is limited by the number of
  ** bits in a Bitmask 
  */
  testcase( pTabList->nSrc==BMS );
  if( pTabList->nSrc>BMS ){
    sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
................................................................................
  /* Allocate and initialize the WhereInfo structure that will become the
  ** return value. A single allocation is used to store the WhereInfo
  ** struct, the contents of WhereInfo.a[], the WhereClause structure
  ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
  ** field (type Bitmask) it must be aligned on an 8-byte boundary on
  ** some architectures. Hence the ROUND8() below.
  */
  db = pParse->db;
  nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel));
  pWInfo = sqlite3DbMallocZero(db, nByteWInfo + sizeof(WhereLoop));
  if( db->mallocFailed ){
    sqlite3DbFree(db, pWInfo);
    pWInfo = 0;
    goto whereBeginError;
  }
................................................................................
  sWLB.pWC = &pWInfo->sWC;
  sWLB.pNew = (WhereLoop*)&pWInfo->a[nTabList];
  whereLoopInit(sWLB.pNew);
#ifdef SQLITE_DEBUG
  sWLB.pNew->cId = '*';
#endif

  /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
  ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
  if( OptimizationDisabled(db, SQLITE_DistinctOpt) ){
    wctrlFlags &= ~WHERE_WANT_DISTINCT;
  }

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
  */
  initMaskSet(pMaskSet);
  whereClauseInit(&pWInfo->sWC, pWInfo);
  sqlite3ExprCodeConstants(pParse, pWhere);
  whereSplit(&pWInfo->sWC, pWhere, TK_AND);   /* IMP: R-15842-53296 */
................................................................................
      }
    }
  }

  if( wctrlFlags & WHERE_WANT_DISTINCT ){
    if( isDistinctRedundant(pParse, pTabList, &pWInfo->sWC, pResultSet) ){
      /* The DISTINCT marking is pointless.  Ignore it. */
      wctrlFlags &= ~WHERE_WANT_DISTINCT;
      pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
    }else if( pOrderBy==0 ){
      /* Try to ORDER BY the result set to make distinct processing easier */
      pWInfo->wctrlFlags |= WHERE_DISTINCTBY;
      pWInfo->pOrderBy = pResultSet;
    }
  }
................................................................................
    rc = whereLoopAddAll(&sWLB);
    if( rc ) goto whereBeginError;
  
    /* Display all of the WhereLoop objects if wheretrace is enabled */
#ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace ){
      WhereLoop *p;
      int i = 0;
      static char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz"
                                       "ABCDEFGHIJKLMNOPQRSTUVWYXZ";
      for(p=pWInfo->pLoops; p; p=p->pNextLoop){
        p->cId = zLabel[(i++)%sizeof(zLabel)];
        whereLoopPrint(p, pTabList);
      }
    }
#endif
  
    wherePathSolver(pWInfo, 0);
    if( db->mallocFailed ) goto whereBeginError;
................................................................................
      }
      case WHERE_DISTINCT_UNORDERED: {
        sqlite3DebugPrintf("  DISTINCT=unordered");
        break;
      }
    }
    sqlite3DebugPrintf("\n");
    for(ii=0; ii<nTabList; ii++){
      whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList);
    }
  }
#endif


















  WHERETRACE(0xffff,("*** Optimizer Finished ***\n"));
  pWInfo->pParse->nQueryLoop += pWInfo->nRowOut;

  /* If the caller is an UPDATE or DELETE statement that is requesting
  ** to use a one-pass algorithm, determine if this is appropriate.
  ** The one-pass algorithm only works if the WHERE clause constraints
  ** the statement to update a single row.
................................................................................
  /* The "break" point is here, just past the end of the outer loop.
  ** Set it.
  */
  sqlite3VdbeResolveLabel(v, pWInfo->iBreak);

  /* Close all of the cursors that were opened by sqlite3WhereBegin.
  */
  assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc );
  for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
    Index *pIdx = 0;
    struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
    Table *pTab = pTabItem->pTab;
    assert( pTab!=0 );
    pLoop = pLevel->pWLoop;
    if( (pTab->tabFlags & TF_Ephemeral)==0







>



<







 







|
|
>







 







>






>


>
>
>
>
>
>







 







<







 







<
<
<
<
<
<







 







<







 







|


|
|







 







|




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







 







|







388
389
390
391
392
393
394
395
396
397
398

399
400
401
402
403
404
405
....
5366
5367
5368
5369
5370
5371
5372
5373
5374
5375
5376
5377
5378
5379
5380
5381
5382
....
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
5593
5594
5595
5596
5597
....
5608
5609
5610
5611
5612
5613
5614

5615
5616
5617
5618
5619
5620
5621
....
5632
5633
5634
5635
5636
5637
5638






5639
5640
5641
5642
5643
5644
5645
....
5716
5717
5718
5719
5720
5721
5722

5723
5724
5725
5726
5727
5728
5729
....
5734
5735
5736
5737
5738
5739
5740
5741
5742
5743
5744
5745
5746
5747
5748
5749
5750
5751
5752
....
5779
5780
5781
5782
5783
5784
5785
5786
5787
5788
5789
5790
5791
5792
5793
5794
5795
5796
5797
5798
5799
5800
5801
5802
5803
5804
5805
5806
5807
5808
5809
5810
5811
5812
5813
5814
5815
....
5970
5971
5972
5973
5974
5975
5976
5977
5978
5979
5980
5981
5982
5983
5984
  Bitmask revMask;          /* Mask of ORDER BY terms that need reversing */
  WhereCost nRowOut;        /* Estimated number of output rows */
  u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
  u8 bOBSat;                /* ORDER BY satisfied by indices */
  u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
  u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
  u8 nLevel;                /* Number of nested loop */
  int iTop;                 /* The very beginning of the WHERE loop */
  int iContinue;            /* Jump here to continue with next record */
  int iBreak;               /* Jump here to break out of the loop */

  int savedNQueryLoop;      /* pParse->nQueryLoop outside the WHERE loop */
  WhereMaskSet sMaskSet;    /* Map cursor numbers to bitmasks */
  WhereClause sWC;          /* Decomposition of the WHERE clause */
  WhereLevel a[1];          /* Information about each nest loop in WHERE */
};

/*
................................................................................
  /* Load the lowest cost path into pWInfo */
  for(iLoop=0; iLoop<nLoop; iLoop++){
    WhereLevel *pLevel = pWInfo->a + iLoop;
    pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop];
    pLevel->iFrom = pWLoop->iTab;
    pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor;
  }
  if( (pWInfo->wctrlFlags & WHERE_WANT_DISTINCT)!=0
   && (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0
   && pWInfo->eDistinct==WHERE_DISTINCT_NOOP
   && nRowEst
  ){
    Bitmask notUsed;
    int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom,
                 WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed);
    if( rc==1 ) pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  }
................................................................................
  int nTabList;              /* Number of elements in pTabList */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  Bitmask notReady;          /* Cursors that are not yet positioned */
  WhereLoopBuilder sWLB;     /* The WhereLoop builder */
  WhereMaskSet *pMaskSet;    /* The expression mask set */
  WhereLevel *pLevel;        /* A single level in pWInfo->a[] */
  WhereLoop *pLoop;          /* Pointer to a single WhereLoop object */
  int ii;                    /* Loop counter */
  sqlite3 *db;               /* Database connection */
  int rc;                    /* Return code */


  /* Variable initialization */
  db = pParse->db;
  memset(&sWLB, 0, sizeof(sWLB));
  sWLB.pOrderBy = pOrderBy;

  /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
  ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
  if( OptimizationDisabled(db, SQLITE_DistinctOpt) ){
    wctrlFlags &= ~WHERE_WANT_DISTINCT;
  }

  /* The number of tables in the FROM clause is limited by the number of
  ** bits in a Bitmask 
  */
  testcase( pTabList->nSrc==BMS );
  if( pTabList->nSrc>BMS ){
    sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
................................................................................
  /* Allocate and initialize the WhereInfo structure that will become the
  ** return value. A single allocation is used to store the WhereInfo
  ** struct, the contents of WhereInfo.a[], the WhereClause structure
  ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
  ** field (type Bitmask) it must be aligned on an 8-byte boundary on
  ** some architectures. Hence the ROUND8() below.
  */

  nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel));
  pWInfo = sqlite3DbMallocZero(db, nByteWInfo + sizeof(WhereLoop));
  if( db->mallocFailed ){
    sqlite3DbFree(db, pWInfo);
    pWInfo = 0;
    goto whereBeginError;
  }
................................................................................
  sWLB.pWC = &pWInfo->sWC;
  sWLB.pNew = (WhereLoop*)&pWInfo->a[nTabList];
  whereLoopInit(sWLB.pNew);
#ifdef SQLITE_DEBUG
  sWLB.pNew->cId = '*';
#endif







  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
  */
  initMaskSet(pMaskSet);
  whereClauseInit(&pWInfo->sWC, pWInfo);
  sqlite3ExprCodeConstants(pParse, pWhere);
  whereSplit(&pWInfo->sWC, pWhere, TK_AND);   /* IMP: R-15842-53296 */
................................................................................
      }
    }
  }

  if( wctrlFlags & WHERE_WANT_DISTINCT ){
    if( isDistinctRedundant(pParse, pTabList, &pWInfo->sWC, pResultSet) ){
      /* The DISTINCT marking is pointless.  Ignore it. */

      pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
    }else if( pOrderBy==0 ){
      /* Try to ORDER BY the result set to make distinct processing easier */
      pWInfo->wctrlFlags |= WHERE_DISTINCTBY;
      pWInfo->pOrderBy = pResultSet;
    }
  }
................................................................................
    rc = whereLoopAddAll(&sWLB);
    if( rc ) goto whereBeginError;
  
    /* Display all of the WhereLoop objects if wheretrace is enabled */
#ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace ){
      WhereLoop *p;
      int i;
      static char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz"
                                       "ABCDEFGHIJKLMNOPQRSTUVWYXZ";
      for(p=pWInfo->pLoops, i=0; p; p=p->pNextLoop, i++){
        p->cId = zLabel[i%sizeof(zLabel)];
        whereLoopPrint(p, pTabList);
      }
    }
#endif
  
    wherePathSolver(pWInfo, 0);
    if( db->mallocFailed ) goto whereBeginError;
................................................................................
      }
      case WHERE_DISTINCT_UNORDERED: {
        sqlite3DebugPrintf("  DISTINCT=unordered");
        break;
      }
    }
    sqlite3DebugPrintf("\n");
    for(ii=0; ii<pWInfo->nLevel; ii++){
      whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList);
    }
  }
#endif
  /* Attempt to omit tables from the join that do not effect the result */
  if( pResultSet!=0 && pWInfo->nLevel>=2 ){
    Bitmask tabUsed = exprListTableUsage(pMaskSet, pResultSet);
    if( pOrderBy ) tabUsed |= exprListTableUsage(pMaskSet, pOrderBy);
    while( pWInfo->nLevel>=2 ){
      pLoop = pWInfo->a[pWInfo->nLevel-1].pWLoop;
      if( ((wctrlFlags & WHERE_WANT_DISTINCT)!=0
           || (pLoop->wsFlags & WHERE_ONEROW)!=0)
       && (tabUsed & pLoop->maskSelf)==0
      ){
        WHERETRACE(0xffff, ("-> drop loop %c not used\n", pLoop->cId));
        pWInfo->nLevel--;
        nTabList--;
      }else{
        break;
      }
    }
  }
  WHERETRACE(0xffff,("*** Optimizer Finished ***\n"));
  pWInfo->pParse->nQueryLoop += pWInfo->nRowOut;

  /* If the caller is an UPDATE or DELETE statement that is requesting
  ** to use a one-pass algorithm, determine if this is appropriate.
  ** The one-pass algorithm only works if the WHERE clause constraints
  ** the statement to update a single row.
................................................................................
  /* The "break" point is here, just past the end of the outer loop.
  ** Set it.
  */
  sqlite3VdbeResolveLabel(v, pWInfo->iBreak);

  /* Close all of the cursors that were opened by sqlite3WhereBegin.
  */
  assert( pWInfo->nLevel<=pTabList->nSrc );
  for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
    Index *pIdx = 0;
    struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
    Table *pTab = pTabItem->pTab;
    assert( pTab!=0 );
    pLoop = pLevel->pWLoop;
    if( (pTab->tabFlags & TF_Ephemeral)==0

Changes to test/alter2.test.

116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
} {1 2 10 3 4 {} 5 6 {}}
do_test alter2-1.5 {
  execsql {
    CREATE INDEX abc_i ON abc(c);
  }
} {}
do_test alter2-1.6 {
breakpoint
  execsql {
    SELECT c FROM abc ORDER BY c;
  }
} {{} {} 10}
do_test alter2-1.7 {
  execsql {
    SELECT * FROM abc WHERE c = 10;







<







116
117
118
119
120
121
122

123
124
125
126
127
128
129
} {1 2 10 3 4 {} 5 6 {}}
do_test alter2-1.5 {
  execsql {
    CREATE INDEX abc_i ON abc(c);
  }
} {}
do_test alter2-1.6 {

  execsql {
    SELECT c FROM abc ORDER BY c;
  }
} {{} {} 10}
do_test alter2-1.7 {
  execsql {
    SELECT * FROM abc WHERE c = 10;