SQLite
Check-in [ba897100fe]
Not logged in
Overview
SHA1 Hash:ba897100fed291d2025f68d09334f9985312298b
Date: 2013-06-11 18:59:38
User: drh
Comment:Improved processing of DISTINCT.
Tags And Properties
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/misc/fuzzer.c

1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
....
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
....
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
static int fuzzerBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
  int iPlan = 0;
  int iDistTerm = -1;
  int iRulesetTerm = -1;
  int i;
  int seenMatch = 0;
  const struct sqlite3_index_constraint *pConstraint;
  double rCost = 100000;

  pConstraint = pIdxInfo->aConstraint;
  for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
    if( pConstraint->iColumn==0
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH ){
      seenMatch = 1;
    }
................................................................................
    if( (iPlan & 1)==0 
     && pConstraint->iColumn==0
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH
    ){
      iPlan |= 1;
      pIdxInfo->aConstraintUsage[i].argvIndex = 1;
      pIdxInfo->aConstraintUsage[i].omit = 1;
      rCost /= 1000000.0;
    }
    if( (iPlan & 2)==0
     && pConstraint->iColumn==1
     && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
           || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE)
    ){
      iPlan |= 2;
................................................................................
  pIdxInfo->idxNum = iPlan;
  if( pIdxInfo->nOrderBy==1
   && pIdxInfo->aOrderBy[0].iColumn==1
   && pIdxInfo->aOrderBy[0].desc==0
  ){
    pIdxInfo->orderByConsumed = 1;
  }
  if( seenMatch && (iPlan&1)==0 ) rCost *= 1e30;
  pIdxInfo->estimatedCost = rCost;
   
  return SQLITE_OK;
}

/*
** A virtual table module that implements the "fuzzer".







|







 







|







 







|







1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
....
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
....
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
static int fuzzerBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
  int iPlan = 0;
  int iDistTerm = -1;
  int iRulesetTerm = -1;
  int i;
  int seenMatch = 0;
  const struct sqlite3_index_constraint *pConstraint;
  double rCost = 1e12;

  pConstraint = pIdxInfo->aConstraint;
  for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
    if( pConstraint->iColumn==0
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH ){
      seenMatch = 1;
    }
................................................................................
    if( (iPlan & 1)==0 
     && pConstraint->iColumn==0
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH
    ){
      iPlan |= 1;
      pIdxInfo->aConstraintUsage[i].argvIndex = 1;
      pIdxInfo->aConstraintUsage[i].omit = 1;
      rCost /= 1e6;
    }
    if( (iPlan & 2)==0
     && pConstraint->iColumn==1
     && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
           || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE)
    ){
      iPlan |= 2;
................................................................................
  pIdxInfo->idxNum = iPlan;
  if( pIdxInfo->nOrderBy==1
   && pIdxInfo->aOrderBy[0].iColumn==1
   && pIdxInfo->aOrderBy[0].desc==0
  ){
    pIdxInfo->orderByConsumed = 1;
  }
  if( seenMatch && (iPlan&1)==0 ) rCost = 1e99;
  pIdxInfo->estimatedCost = rCost;
   
  return SQLITE_OK;
}

/*
** A virtual table module that implements the "fuzzer".

Changes to src/sqliteInt.h

1963
1964
1965
1966
1967
1968
1969

1970
1971


1972
1973
1974
1975
1976
1977
1978
....
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_DUPLICATES_OK    0x0008 /* Ok to return a row more than once */
#define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
#define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
#define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
#define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */
#define WHERE_GROUPBY          0x0100 /* pOrderBy is really a GROUP BY */


/* Allowed values for WhereInfo.eDistinct and DistinctCtx.eTnctType */


#define WHERE_DISTINCT_NOOP      0  /* DISTINCT keyword not used */
#define WHERE_DISTINCT_UNIQUE    1  /* No duplicates */
#define WHERE_DISTINCT_ORDERED   2  /* All duplicates are adjacent */
#define WHERE_DISTINCT_UNORDERED 3  /* Duplicates are scattered */

/*
** A NameContext defines a context in which to resolve table and column
................................................................................
  TableLock *aTableLock; /* Required table locks for shared-cache mode */
#endif
  AutoincInfo *pAinc;  /* Information about AUTOINCREMENT counters */

  /* Information used while coding trigger programs. */
  Parse *pToplevel;    /* Parse structure for main program (or NULL) */
  Table *pTriggerTab;  /* Table triggers are being coded for */
  u32 grep nQueryLoop; /* Est number of iterations of a query (10*log2(N)) */
  u32 oldmask;         /* Mask of old.* columns referenced */
  u32 newmask;         /* Mask of new.* columns referenced */
  u8 eTriggerOp;       /* TK_UPDATE, TK_INSERT or TK_DELETE */
  u8 eOrconf;          /* Default ON CONFLICT policy for trigger steps */
  u8 disableTriggers;  /* True to disable triggers */

  /* Above is constant between recursions.  Below is reset before and after







>

<
>
>







 







|







1963
1964
1965
1966
1967
1968
1969
1970
1971

1972
1973
1974
1975
1976
1977
1978
1979
1980
....
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_DUPLICATES_OK    0x0008 /* Ok to return a row more than once */
#define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
#define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
#define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
#define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */
#define WHERE_GROUPBY          0x0100 /* pOrderBy is really a GROUP BY */
#define WHERE_DISTINCTBY       0x0200 /* pOrderby is really a DISTINCT clause */


/* Allowed return values from sqlite3WhereIsDistinct()
*/
#define WHERE_DISTINCT_NOOP      0  /* DISTINCT keyword not used */
#define WHERE_DISTINCT_UNIQUE    1  /* No duplicates */
#define WHERE_DISTINCT_ORDERED   2  /* All duplicates are adjacent */
#define WHERE_DISTINCT_UNORDERED 3  /* Duplicates are scattered */

/*
** A NameContext defines a context in which to resolve table and column
................................................................................
  TableLock *aTableLock; /* Required table locks for shared-cache mode */
#endif
  AutoincInfo *pAinc;  /* Information about AUTOINCREMENT counters */

  /* Information used while coding trigger programs. */
  Parse *pToplevel;    /* Parse structure for main program (or NULL) */
  Table *pTriggerTab;  /* Table triggers are being coded for */
  u32 nQueryLoop;      /* Est number of iterations of a query (10*log2(N)) */
  u32 oldmask;         /* Mask of old.* columns referenced */
  u32 newmask;         /* Mask of new.* columns referenced */
  u8 eTriggerOp;       /* TK_UPDATE, TK_INSERT or TK_DELETE */
  u8 eOrconf;          /* Default ON CONFLICT policy for trigger steps */
  u8 disableTriggers;  /* True to disable triggers */

  /* Above is constant between recursions.  Below is reset before and after

Changes to src/where.c

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
...
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
....
1772
1773
1774
1775
1776
1777
1778


1779
1780
1781

1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
....
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
....
4489
4490
4491
4492
4493
4494
4495
4496


4497
4498
4499
4500
4501
4502
4503
....
4800
4801
4802
4803
4804
4805
4806

4807

4808
4809
4810
4811
4812
4813
4814
4815
4816
4817
4818
....
4819
4820
4821
4822
4823
4824
4825
4826
4827
4828
4829
4830
4831
4832
4833
....
4956
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966
4967
4968
4969
4970
....
5107
5108
5109
5110
5111
5112
5113
5114

5115
5116
5117
5118
5119
5120
5121
5122
....
5245
5246
5247
5248
5249
5250
5251









5252
5253




5254

5255
5256
5257
5258
5259
5260
5261
....
5323
5324
5325
5326
5327
5328
5329
5330

5331
5332
5333
5334
5335
5336
5337
....
5410
5411
5412
5413
5414
5415
5416
5417
5418
5419
5420
5421
5422
5423
5424
5425
5426
5427
5428
5429
5430
5431
5432
....
5553
5554
5555
5556
5557
5558
5559














5560
5561
5562
5563
5564

5565
5566
5567




5568
5569
5570
5571
5572
5573
5574
....
5583
5584
5585
5586
5587
5588
5589
5590
5591
5592
5593
5594
5595
5596
5597
....
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
5609



5610

5611










5612
5613
5614
5615
5616
5617
5618
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;            /* Parsing and code generating context */
  SrcList *pTabList;        /* List of tables in the join */
  ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
  ExprList *pDistinct;      /* DISTINCT ON values, or NULL */

  Bitmask revMask;          /* Mask of ORDER BY terms that need reversing */
  u16 nOBSat;               /* Number of ORDER BY terms satisfied by indices */

  u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */

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

  WhereMaskSet sMaskSet;    /* Map cursor numbers to bitmasks */
  WhereClause sWC;          /* Decomposition of the WHERE clause */
  WhereLoop *pLoops;        /* List of all WhereLoop objects */
  int savedNQueryLoop;      /* pParse->nQueryLoop outside the WHERE loop */
  WhereCost nRowOut;        /* Estimated number of output rows */
  WhereLevel a[1];          /* Information about each nest loop in WHERE */
};

/*
** Bitmasks for the operators that indices are able to exploit.  An
** OR-ed combination of these values can be used when searching for
** terms in the where clause.
................................................................................
}

/*
** Return TRUE if the WHERE clause returns rows in ORDER BY order.
** Return FALSE if the output needs to be sorted.
*/
int sqlite3WhereIsOrdered(WhereInfo *pWInfo){
  return pWInfo->nOBSat>0;
}

/*
** Return the VDBE address or label to jump to in order to continue
** immediately with the next row of a WHERE clause.
*/
int sqlite3WhereContinueLabel(WhereInfo *pWInfo){
................................................................................
  }

  return -1;
}

/*
** Return true if the DISTINCT expression-list passed as the third argument


** is redundant. A DISTINCT list is redundant if the database contains a
** UNIQUE index that guarantees that the result of the query will be distinct
** anyway.

*/
static int isDistinctRedundant(
  Parse *pParse,
  SrcList *pTabList,
  WhereClause *pWC,
  ExprList *pDistinct
){
  Table *pTab;
  Index *pIdx;
  int i;                          
  int iBase;

  /* If there is more than one table or sub-select in the FROM clause of
................................................................................
    ** query, then the caller will only allow the loop to run for
    ** a single iteration. This means that the first row returned
    ** should not have a NULL value stored in 'x'. If column 'x' is
    ** the first one after the nEq equality constraints in the index,
    ** this requires some special handling.
    */
    if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0
     && (pWInfo->nOBSat>0)
     && (pIdx->nColumn>nEq)
    ){
      /* assert( pOrderBy->nExpr==1 ); */
      /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
      isMinQuery = 1;
      nExtraReg = 1;
    }
................................................................................
       && pProbe->bUnordered==0
       && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
       && sqlite3GlobalConfig.bUseCis
       && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;
        pNew->nOut = rSize;
        pNew->rRun = whereCostAdd(rSize,rLogSize) + ((m==0 && b) ? 10 : 0);


        rc = whereLoopInsert(pBuilder, pNew);
        if( rc ) break;
      }
    }
    rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0);

    /* If there was an INDEXED BY clause, then only that one index is
................................................................................
**    0:  ORDER BY is not satisfied.  Sorting required
**    1:  ORDER BY is satisfied.      Omit sorting
**   -1:  Unknown at this time
**
*/
static int wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */

  WherePath *pPath,     /* The WherePath to check */

  int nLoop,            /* Number of entries in pPath->aLoop[] */
  int isLastLoop,       /* True if pLast is the inner-most loop */
  WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  Bitmask *pRevMask     /* Mask of WhereLoops to run in reverse order */
){
  u8 revSet;            /* True if rev is known */
  u8 rev;               /* Composite sort order */
  u8 revIdx;            /* Index sort order */
  u8 isOrderDistinct;   /* All prior WhereLoops are order-distinct */
  u8 distinctColumns;   /* True if the loop has UNIQUE NOT NULL columns */
  u8 isMatch;           /* iColumn matches a term of the ORDER BY clause */
................................................................................
  u16 nColumn;          /* Number of columns in pIndex */
  u16 nOrderBy;         /* Number terms in the ORDER BY clause */
  int iLoop;            /* Index of WhereLoop in pPath being processed */
  int i, j;             /* Loop counters */
  int iCur;             /* Cursor number for current WhereLoop */
  int iColumn;          /* A column number within table iCur */
  WhereLoop *pLoop;     /* Current WhereLoop being processed. */
  ExprList *pOrderBy = pWInfo->pOrderBy;  /* the ORDER BY clause */
  WhereTerm *pTerm;     /* A single term of the WHERE clause */
  Expr *pOBExpr;        /* An expression from the ORDER BY clause */
  CollSeq *pColl;       /* COLLATE function from an ORDER BY clause term */
  Index *pIndex;        /* The index associated with pLoop */
  sqlite3 *db = pWInfo->pParse->db;  /* Database connection */
  Bitmask obSat = 0;    /* Mask of ORDER BY terms satisfied so far */
  Bitmask obDone;       /* Mask of all ORDER BY terms */
................................................................................
        ** of the index and and mark that ORDER BY term off 
        */
        bOnce = 1;
        isMatch = 0;
        for(i=0; bOnce && i<nOrderBy; i++){
          if( MASKBIT(i) & obSat ) continue;
          pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
          if( (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ) bOnce = 0;
          if( pOBExpr->op!=TK_COLUMN ) continue;
          if( pOBExpr->iTable!=iCur ) continue;
          if( pOBExpr->iColumn!=iColumn ) continue;
          if( iColumn>=0 ){
            pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
            if( !pColl ) pColl = db->pDfltColl;
            if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue;
................................................................................
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        /* At this point, pWLoop is a candidate to be the next loop. 
        ** Compute its cost */
        rCost = whereCostAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
        rCost = whereCostAdd(rCost, pFrom->rCost);
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( !isOrderedValid ){
          switch( wherePathSatisfiesOrderBy(pWInfo, pFrom, iLoop, iLoop==nLoop-1,

                                            pWLoop, &revMask) ){
            case 1:  /* Yes.  pFrom+pWLoop does satisfy the ORDER BY clause */
              isOrdered = 1;
              isOrderedValid = 1;
              break;
            case 0:  /* No.  pFrom+pWLoop will require a separate sort */
              isOrdered = 0;
              isOrderedValid = 1;
................................................................................
  /* 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; /* FIXME: Omit the iFrom field */
    pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor;
  }









  if( pFrom->isOrdered ){
    pWInfo->nOBSat = pWInfo->pOrderBy->nExpr;




    pWInfo->revMask = pFrom->revLoop;

  }
  pWInfo->nRowOut = pFrom->nRow;

  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}
................................................................................
  }
  if( pLoop->wsFlags ){
    pLoop->nOut = (WhereCost)1;
    pWInfo->a[0].pWLoop = pLoop;
    pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur);
    pWInfo->a[0].iTabCur = iCur;
    pWInfo->nRowOut = 1;
    pWInfo->nOBSat =  pWInfo->pOrderBy ? pWInfo->pOrderBy->nExpr : 0;

#ifdef SQLITE_DEBUG
    pLoop->cId = '0';
#endif
    return 1;
  }
  return 0;
}
................................................................................
**    end
**
** ORDER BY CLAUSE PROCESSING
**
** pOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
** if there is one.  If there is no ORDER BY clause or if this routine
** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
**
** If an index can be used so that the natural output order of the table
** scan is correct for the ORDER BY clause, then that index is used and
** the returned WhereInfo.nOBSat field is set to pOrderBy->nExpr.  This
** is an optimization that prevents an unnecessary sort of the result set
** if an index appropriate for the ORDER BY clause already exists.
**
** If the where clause loops cannot be arranged to provide the correct
** output order, then WhereInfo.nOBSat is 0.
*/
WhereInfo *sqlite3WhereBegin(
  Parse *pParse,        /* The parser context */
  SrcList *pTabList,    /* A list of all tables to be scanned */
  Expr *pWhere,         /* The WHERE clause */
  ExprList *pOrderBy,   /* An ORDER BY clause, or NULL */
  ExprList *pDistinct,  /* The select-list for DISTINCT queries - or NULL */
................................................................................
  ** want to analyze these virtual terms, so start analyzing at the end
  ** and work forward so that the added virtual terms are never processed.
  */
  exprAnalyzeAll(pTabList, &pWInfo->sWC);
  if( db->mallocFailed ){
    goto whereBeginError;
  }















  /* Check if the DISTINCT qualifier, if there is one, is redundant. 
  ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to
  ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT.
  */

  if( pDistinct && isDistinctRedundant(pParse,pTabList,&pWInfo->sWC,pDistinct) ){
    pDistinct = 0;
    pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;




  }

  /* Construct the WhereLoop objects */
  WHERETRACE(("*** Optimizer Start ***\n"));
  if( nTabList!=1 || whereShortCut(&sWLB)==0 ){
    rc = whereLoopAddAll(&sWLB);
    if( rc ) goto whereBeginError;
................................................................................
      for(p=pWInfo->pLoops; p; p=p->pNextLoop){
        p->cId = zLabel[(i++)%sizeof(zLabel)];
        whereLoopPrint(p, pTabList);
      }
    }
#endif
  
    wherePathSolver(pWInfo, -1);
    if( db->mallocFailed ) goto whereBeginError;
    if( pWInfo->pOrderBy ){
       wherePathSolver(pWInfo, pWInfo->nRowOut);
       if( db->mallocFailed ) goto whereBeginError;
    }
  }
  if( pWInfo->pOrderBy==0 && (db->flags & SQLITE_ReverseOrder)!=0 ){
................................................................................
  }
  if( pParse->nErr || db->mallocFailed ){
    goto whereBeginError;
  }
#ifdef WHERETRACE_ENABLED
  if( sqlite3WhereTrace ){
    int ii;
    sqlite3DebugPrintf("---- Solution");
    if( pWInfo->nOBSat ){
      sqlite3DebugPrintf(" ORDER BY omitted rev=0x%llx\n", pWInfo->revMask);
    }else{



      sqlite3DebugPrintf("\n");

    }










    for(ii=0; ii<nTabList; ii++){
      whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList);
    }
  }
#endif
  WHERETRACE(("*** Optimizer Finished ***\n"));
  pWInfo->pParse->nQueryLoop += pWInfo->nRowOut;







>

<
>

>







>


<
<
<







 







|







 







>
>
|
<
<
>


|
|
|
|







 







|







 







|
>
>







 







>

>
|
|

|







 







<







 







|







 







|
>
|







 







>
>
>
>
>
>
>
>
>

<
>
>
>
>
|
>







 







|
>







 







<
<
<
<
<
<
<
<
<







 







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





>
|
|
|
>
>
>
>







 







|







 







|
|
|
<
>
>
>
|
>
|
>
>
>
>
>
>
>
>
>
>







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
...
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
....
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781


1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
....
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
3429
....
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
4504
4505
4506
....
4803
4804
4805
4806
4807
4808
4809
4810
4811
4812
4813
4814
4815
4816
4817
4818
4819
4820
4821
4822
4823
....
4824
4825
4826
4827
4828
4829
4830

4831
4832
4833
4834
4835
4836
4837
....
4960
4961
4962
4963
4964
4965
4966
4967
4968
4969
4970
4971
4972
4973
4974
....
5111
5112
5113
5114
5115
5116
5117
5118
5119
5120
5121
5122
5123
5124
5125
5126
5127
....
5250
5251
5252
5253
5254
5255
5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266

5267
5268
5269
5270
5271
5272
5273
5274
5275
5276
5277
5278
5279
....
5341
5342
5343
5344
5345
5346
5347
5348
5349
5350
5351
5352
5353
5354
5355
5356
....
5429
5430
5431
5432
5433
5434
5435









5436
5437
5438
5439
5440
5441
5442
....
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
5593
5594
5595
5596
5597
5598
5599
5600
5601
5602
5603
....
5612
5613
5614
5615
5616
5617
5618
5619
5620
5621
5622
5623
5624
5625
5626
....
5628
5629
5630
5631
5632
5633
5634
5635
5636
5637

5638
5639
5640
5641
5642
5643
5644
5645
5646
5647
5648
5649
5650
5651
5652
5653
5654
5655
5656
5657
5658
5659
5660
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;            /* Parsing and code generating context */
  SrcList *pTabList;        /* List of tables in the join */
  ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
  ExprList *pDistinct;      /* DISTINCT ON values, or NULL */
  WhereLoop *pLoops;        /* List of all WhereLoop objects */
  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 */
};

/*
** Bitmasks for the operators that indices are able to exploit.  An
** OR-ed combination of these values can be used when searching for
** terms in the where clause.
................................................................................
}

/*
** Return TRUE if the WHERE clause returns rows in ORDER BY order.
** Return FALSE if the output needs to be sorted.
*/
int sqlite3WhereIsOrdered(WhereInfo *pWInfo){
  return pWInfo->bOBSat!=0;
}

/*
** Return the VDBE address or label to jump to in order to continue
** immediately with the next row of a WHERE clause.
*/
int sqlite3WhereContinueLabel(WhereInfo *pWInfo){
................................................................................
  }

  return -1;
}

/*
** Return true if the DISTINCT expression-list passed as the third argument
** is redundant.
**
** A DISTINCT list is redundant if the database contains some set of


** columns that are unique and non-null.
*/
static int isDistinctRedundant(
  Parse *pParse,            /* Parsing context */
  SrcList *pTabList,        /* The FROM clause */
  WhereClause *pWC,         /* The WHERE clause */
  ExprList *pDistinct       /* The result set that needs to be DISTINCT */
){
  Table *pTab;
  Index *pIdx;
  int i;                          
  int iBase;

  /* If there is more than one table or sub-select in the FROM clause of
................................................................................
    ** query, then the caller will only allow the loop to run for
    ** a single iteration. This means that the first row returned
    ** should not have a NULL value stored in 'x'. If column 'x' is
    ** the first one after the nEq equality constraints in the index,
    ** this requires some special handling.
    */
    if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0
     && (pWInfo->bOBSat!=0)
     && (pIdx->nColumn>nEq)
    ){
      /* assert( pOrderBy->nExpr==1 ); */
      /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
      isMinQuery = 1;
      nExtraReg = 1;
    }
................................................................................
       && pProbe->bUnordered==0
       && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
       && sqlite3GlobalConfig.bUseCis
       && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;
        pNew->nOut = rSize;
        pNew->rRun = whereCostAdd(rSize,rLogSize);
        if( m!=0 ) pNew->rRun += rLogSize;
        if( b ) pNew->rRun--;
        rc = whereLoopInsert(pBuilder, pNew);
        if( rc ) break;
      }
    }
    rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0);

    /* If there was an INDEXED BY clause, then only that one index is
................................................................................
**    0:  ORDER BY is not satisfied.  Sorting required
**    1:  ORDER BY is satisfied.      Omit sorting
**   -1:  Unknown at this time
**
*/
static int wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  ExprList *pOrderBy,   /* ORDER BY or GROUP BY or DISTINCT clause to check */
  WherePath *pPath,     /* The WherePath to check */
  u16 wctrlFlags,       /* Might contain WHERE_GROUPBY or WHERE_DISTINCTBY */
  u16 nLoop,            /* Number of entries in pPath->aLoop[] */
  u8 isLastLoop,        /* True if pLast is the inner-most loop */
  WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  Bitmask *pRevMask     /* OUT: Mask of WhereLoops to run in reverse order */
){
  u8 revSet;            /* True if rev is known */
  u8 rev;               /* Composite sort order */
  u8 revIdx;            /* Index sort order */
  u8 isOrderDistinct;   /* All prior WhereLoops are order-distinct */
  u8 distinctColumns;   /* True if the loop has UNIQUE NOT NULL columns */
  u8 isMatch;           /* iColumn matches a term of the ORDER BY clause */
................................................................................
  u16 nColumn;          /* Number of columns in pIndex */
  u16 nOrderBy;         /* Number terms in the ORDER BY clause */
  int iLoop;            /* Index of WhereLoop in pPath being processed */
  int i, j;             /* Loop counters */
  int iCur;             /* Cursor number for current WhereLoop */
  int iColumn;          /* A column number within table iCur */
  WhereLoop *pLoop;     /* Current WhereLoop being processed. */

  WhereTerm *pTerm;     /* A single term of the WHERE clause */
  Expr *pOBExpr;        /* An expression from the ORDER BY clause */
  CollSeq *pColl;       /* COLLATE function from an ORDER BY clause term */
  Index *pIndex;        /* The index associated with pLoop */
  sqlite3 *db = pWInfo->pParse->db;  /* Database connection */
  Bitmask obSat = 0;    /* Mask of ORDER BY terms satisfied so far */
  Bitmask obDone;       /* Mask of all ORDER BY terms */
................................................................................
        ** of the index and and mark that ORDER BY term off 
        */
        bOnce = 1;
        isMatch = 0;
        for(i=0; bOnce && i<nOrderBy; i++){
          if( MASKBIT(i) & obSat ) continue;
          pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
          if( (wctrlFlags & (WHERE_GROUPBY|WHERE_DISTINCTBY))==0 ) bOnce = 0;
          if( pOBExpr->op!=TK_COLUMN ) continue;
          if( pOBExpr->iTable!=iCur ) continue;
          if( pOBExpr->iColumn!=iColumn ) continue;
          if( iColumn>=0 ){
            pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
            if( !pColl ) pColl = db->pDfltColl;
            if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue;
................................................................................
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        /* At this point, pWLoop is a candidate to be the next loop. 
        ** Compute its cost */
        rCost = whereCostAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
        rCost = whereCostAdd(rCost, pFrom->rCost);
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( !isOrderedValid ){
          switch( wherePathSatisfiesOrderBy(pWInfo,
                       pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                       iLoop, iLoop==nLoop-1, pWLoop, &revMask) ){
            case 1:  /* Yes.  pFrom+pWLoop does satisfy the ORDER BY clause */
              isOrdered = 1;
              isOrderedValid = 1;
              break;
            case 0:  /* No.  pFrom+pWLoop will require a separate sort */
              isOrdered = 0;
              isOrderedValid = 1;
................................................................................
  /* 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; /* FIXME: Omit the iFrom field */
    pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor;
  }
  if( (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0 
   && pWInfo->pDistinct
   && nRowEst
  ){
    Bitmask notUsed;
    int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pDistinct, pFrom,
                 WHERE_DISTINCTBY, nLoop-1, 1, pFrom->aLoop[nLoop-1], &notUsed);
    if( rc==1 ) pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  }
  if( pFrom->isOrdered ){

    if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
    }else{
      pWInfo->bOBSat = 1;
      pWInfo->revMask = pFrom->revLoop;
    }
  }
  pWInfo->nRowOut = pFrom->nRow;

  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}
................................................................................
  }
  if( pLoop->wsFlags ){
    pLoop->nOut = (WhereCost)1;
    pWInfo->a[0].pWLoop = pLoop;
    pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur);
    pWInfo->a[0].iTabCur = iCur;
    pWInfo->nRowOut = 1;
    if( pWInfo->pOrderBy ) pWInfo->bOBSat =  1;
    if( pWInfo->pDistinct ) pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
#ifdef SQLITE_DEBUG
    pLoop->cId = '0';
#endif
    return 1;
  }
  return 0;
}
................................................................................
**    end
**
** ORDER BY CLAUSE PROCESSING
**
** pOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
** if there is one.  If there is no ORDER BY clause or if this routine
** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.









*/
WhereInfo *sqlite3WhereBegin(
  Parse *pParse,        /* The parser context */
  SrcList *pTabList,    /* A list of all tables to be scanned */
  Expr *pWhere,         /* The WHERE clause */
  ExprList *pOrderBy,   /* An ORDER BY clause, or NULL */
  ExprList *pDistinct,  /* The select-list for DISTINCT queries - or NULL */
................................................................................
  ** want to analyze these virtual terms, so start analyzing at the end
  ** and work forward so that the added virtual terms are never processed.
  */
  exprAnalyzeAll(pTabList, &pWInfo->sWC);
  if( db->mallocFailed ){
    goto whereBeginError;
  }

  /* If the ORDER BY (or GROUP BY) clause contains references to general
  ** expressions, then we won't be able to satisfy it using indices, so
  ** go ahead and disable it now.
  */
  if( pOrderBy ){
    for(ii=0; ii<pOrderBy->nExpr; ii++){
      Expr *pExpr = sqlite3ExprSkipCollate(pOrderBy->a[ii].pExpr);
      if( pExpr->op!=TK_COLUMN ){
        pWInfo->pOrderBy = pOrderBy = 0;
        break;
      }
    }
  }

  /* Check if the DISTINCT qualifier, if there is one, is redundant. 
  ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to
  ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT.
  */
  if( pDistinct ){
    if( isDistinctRedundant(pParse,pTabList,&pWInfo->sWC,pDistinct) ){
      pDistinct = 0;
      pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
    }else if( pOrderBy==0 ){
      pWInfo->wctrlFlags |= WHERE_DISTINCTBY;
      pWInfo->pOrderBy = pDistinct;
    }
  }

  /* Construct the WhereLoop objects */
  WHERETRACE(("*** Optimizer Start ***\n"));
  if( nTabList!=1 || whereShortCut(&sWLB)==0 ){
    rc = whereLoopAddAll(&sWLB);
    if( rc ) goto whereBeginError;
................................................................................
      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;
    if( pWInfo->pOrderBy ){
       wherePathSolver(pWInfo, pWInfo->nRowOut);
       if( db->mallocFailed ) goto whereBeginError;
    }
  }
  if( pWInfo->pOrderBy==0 && (db->flags & SQLITE_ReverseOrder)!=0 ){
................................................................................
  }
  if( pParse->nErr || db->mallocFailed ){
    goto whereBeginError;
  }
#ifdef WHERETRACE_ENABLED
  if( sqlite3WhereTrace ){
    int ii;
    sqlite3DebugPrintf("---- Solution nRow=%d", pWInfo->nRowOut);
    if( pWInfo->bOBSat ){
      sqlite3DebugPrintf(" ORDERBY=0x%llx", pWInfo->revMask);

    }
    switch( pWInfo->eDistinct ){
      case WHERE_DISTINCT_UNIQUE: {
        sqlite3DebugPrintf("  DISTINCT=unique");
        break;
      }
      case WHERE_DISTINCT_ORDERED: {
        sqlite3DebugPrintf("  DISTINCT=ordered");
        break;
      }
      case WHERE_DISTINCT_UNORDERED: {
        sqlite3DebugPrintf("  DISTINCT=unordered");
        break;
      }
    }
    sqlite3DebugPrintf("\n");
    for(ii=0; ii<nTabList; ii++){
      whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList);
    }
  }
#endif
  WHERETRACE(("*** Optimizer Finished ***\n"));
  pWInfo->pParse->nQueryLoop += pWInfo->nRowOut;