SQLite4
Check-in [4c1dca78b3]
Not logged in

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

Overview
Comment:Changes to where.c to use the PK columns appended to each auxiliary index entry.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | primary-keys
Files: files | file ages | folders
SHA1: 4c1dca78b37403666c9b23f9d6ccc054907af64e
User & Date: dan 2012-04-20 18:35:48
Context
2012-04-20
20:15
Fix the sqlite4RefillIndex() function. This removes the broken (and disabled) merge-sort code. check-in: 9ac54fff5f user: dan tags: primary-keys
18:35
Changes to where.c to use the PK columns appended to each auxiliary index entry. check-in: 4c1dca78b3 user: dan tags: primary-keys
14:21
A fix to sqlite4VdbeDecodeIntKey(). check-in: b05e622090 user: drh tags: primary-keys
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/select.c.

938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
    codeOffset(v, p, addrContinue);
    sqlite4VdbeAddOp2(v, OP_SorterData, iTab, regSortOut);
    sqlite4VdbeAddOp3(v, OP_Column, ptab2, pOrderBy->nExpr+1, regRow);
    sqlite4VdbeChangeP5(v, OPFLAG_CLEARCACHE);
  }else{
    addr = 1 + sqlite4VdbeAddOp2(v, OP_Sort, iTab, addrBreak);
    codeOffset(v, p, addrContinue);
    sqlite4VdbeAddOp3(v, OP_Column, iTab, pOrderBy->nExpr+1, regRow);
  }
  switch( eDest ){
    case SRT_Table:
    case SRT_EphemTab: {
      testcase( eDest==SRT_Table );
      testcase( eDest==SRT_EphemTab );
      sqlite4VdbeAddOp2(v, OP_NewRowid, iParm, regRowid);







|







938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
    codeOffset(v, p, addrContinue);
    sqlite4VdbeAddOp2(v, OP_SorterData, iTab, regSortOut);
    sqlite4VdbeAddOp3(v, OP_Column, ptab2, pOrderBy->nExpr+1, regRow);
    sqlite4VdbeChangeP5(v, OPFLAG_CLEARCACHE);
  }else{
    addr = 1 + sqlite4VdbeAddOp2(v, OP_Sort, iTab, addrBreak);
    codeOffset(v, p, addrContinue);
    /* sqlite4VdbeAddOp3(v, OP_Column, iTab, pOrderBy->nExpr+1, regRow); */
  }
  switch( eDest ){
    case SRT_Table:
    case SRT_EphemTab: {
      testcase( eDest==SRT_Table );
      testcase( eDest==SRT_EphemTab );
      sqlite4VdbeAddOp2(v, OP_NewRowid, iParm, regRowid);

Changes to src/vdbecursor.c.

37
38
39
40
41
42
43
44

45
46
47
48
49
50
51
52
53
54

55
56
57
58
59
60
61
  KVSize nKey;
  KVSize nProbe;
  int rc;
  KVByteArray aProbe[16];

  assert( iEnd==(+1) || iEnd==(-1) );  
  nProbe = sqlite4PutVarint64(aProbe, pC->iRoot);
  aProbe[nProbe++] = 16 - iEnd*12;

  rc = sqlite4KVCursorSeek(pCur, aProbe, nProbe, iEnd);
  if( rc==SQLITE_OK ){
    return SQLITE_CORRUPT;
  }
  if( rc==SQLITE_INEXACT ){
    rc = sqlite4KVCursorKey(pCur, &aKey, &nKey);
    if( rc==SQLITE_OK && (nKey<nProbe-1 || memcmp(aKey, aProbe, nProbe-1)!=0) ){
      rc = SQLITE_NOTFOUND;
    }
  }

  return rc;
}

/*
** Move a VDBE cursor to the next element in its table.
** Return SQLITE_NOTFOUND if the seek falls of the end of the table.
*/







|
>
|

|
<
|

|



>







37
38
39
40
41
42
43
44
45
46
47
48

49
50
51
52
53
54
55
56
57
58
59
60
61
62
  KVSize nKey;
  KVSize nProbe;
  int rc;
  KVByteArray aProbe[16];

  assert( iEnd==(+1) || iEnd==(-1) );  
  nProbe = sqlite4PutVarint64(aProbe, pC->iRoot);
  aProbe[nProbe] = 0xFF;

  rc = sqlite4KVCursorSeek(pCur, aProbe, nProbe+(iEnd==-1), iEnd);
  if( rc==SQLITE_OK ){
    rc = SQLITE_CORRUPT_BKPT;

  }else if( rc==SQLITE_INEXACT ){
    rc = sqlite4KVCursorKey(pCur, &aKey, &nKey);
    if( rc==SQLITE_OK && (nKey<nProbe || memcmp(aKey, aProbe, nProbe)!=0) ){
      rc = SQLITE_NOTFOUND;
    }
  }

  return rc;
}

/*
** Move a VDBE cursor to the next element in its table.
** Return SQLITE_NOTFOUND if the seek falls of the end of the table.
*/

Changes to src/where.c.

587
588
589
590
591
592
593


594
595

596
597
598
599
600
601
602
603
604
605


606
607
608
609
610
611
612
613
614

615
616
617
618
619
620
621
622
623
624



625
626




627
628
629
630
631
632
633
....
1576
1577
1578
1579
1580
1581
1582

























1583
1584
1585
1586
1587
1588
1589
....
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616



1617
1618
1619
1620
1621


1622


1623

1624
1625
1626
1627
1628



1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645




1646
1647
1648
1649
1650

1651













1652
1653
1654
1655
1656
1657
1658
1659
1660
1661





1662
1663



1664
1665
1666

1667
1668
1669
1670
1671
1672
1673


1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696

1697
1698
1699
1700
1701
1702
1703
1704
1705

1706
1707
1708

1709
1710
1711
1712
1713

1714

1715
1716




1717
1718
1719
1720
1721
1722



1723





1724











1725
1726
1727
1728
1729
1730
1731
....
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
....
2878
2879
2880
2881
2882
2883
2884

2885
2886
2887
2888
2889
2890
2891
....
2921
2922
2923
2924
2925
2926
2927

2928
2929
2930
2931
2932
2933
2934
....
3006
3007
3008
3009
3010
3011
3012

3013






3014
3015
3016


3017
3018
3019
3020
3021
3022
3023
3024
....
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
....
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
....
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
....
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
....
3931
3932
3933
3934
3935
3936
3937


3938
3939

3940
3941

3942
3943
3944
3945
3946
3947
3948
....
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
3969
3970
3971
3972
3973
3974
3975
....
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
  WhereClause *pWC,     /* The WHERE clause to be searched */
  int iCur,             /* Cursor number of LHS */
  int iColumn,          /* Column number of LHS */
  Bitmask notReady,     /* RHS must not overlap with this mask */
  u32 op,               /* Mask of WO_xx values describing operator */
  Index *pIdx           /* Must be compatible with this index, if not NULL */
){


  WhereTerm *pTerm;
  int k;

  assert( iCur>=0 );
  op &= WO_ALL;
  for(; pWC; pWC=pWC->pOuter){
    for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
      if( pTerm->leftCursor==iCur
         && (pTerm->prereqRight & notReady)==0
         && pTerm->u.leftColumn==iColumn
         && (pTerm->eOperator & op)!=0
      ){
        if( iColumn>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){


          Expr *pX = pTerm->pExpr;
          CollSeq *pColl;
          char idxaff;
          int j;
          Parse *pParse = pWC->pParse;
  
          idxaff = pIdx->pTable->aCol[iColumn].affinity;
          if( !sqlite4IndexAffinityOk(pX, idxaff) ) continue;
  

          /* Figure out the collation sequence required from an index for
          ** it to be useful for optimising expression pX. Store this
          ** value in variable pColl.
          */
          assert(pX->pLeft);
          pColl = sqlite4BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
          assert(pColl || pParse->nErr);
  
          for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
            if( NEVER(j>=pIdx->nColumn) ) return 0;



          }
          if( pColl && sqlite4StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;




        }
        return pTerm;
      }
    }
  }
  return 0;
}
................................................................................
      return 1;
    }
  }

  return 0;
}


























/*
** This routine decides if pIdx can be used to satisfy the ORDER BY
** clause.  If it can, it returns 1.  If pIdx cannot satisfy the
** ORDER BY clause, this routine returns 0.
**
** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
** left-most table in the FROM clause of that same SELECT statement and
................................................................................
  Index *pIdx,            /* The index we are testing */
  int base,               /* Cursor number for the table to be sorted */
  ExprList *pOrderBy,     /* The ORDER BY clause */
  int nEqCol,             /* Number of index columns with == constraints */
  int wsFlags,            /* Index usages flags */
  int *pbRev              /* Set to 1 if ORDER BY is DESC */
){
  int i, j;                       /* Loop counters */
  int sortOrder = 0;              /* XOR of index and ORDER BY sort direction */
  int nTerm;                      /* Number of ORDER BY terms */
  struct ExprList_item *pTerm;    /* A term of the ORDER BY clause */
  sqlite4 *db = pParse->db;




  if( !pOrderBy ) return 0;
  if( wsFlags & WHERE_COLUMN_IN ) return 0;
  if( pIdx->bUnordered ) return 0;



  nTerm = pOrderBy->nExpr;


  assert( nTerm>0 );


  /* Argument pIdx must either point to a 'real' named index structure, 
  ** or an index structure allocated on the stack by bestKVIndex() to
  ** represent the rowid index that is part of every table.  */
  assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) );




  /* Match terms of the ORDER BY clause against columns of
  ** the index.
  **
  ** Note that indices have pIdx->nColumn regular columns plus
  ** one additional column containing the rowid.  The rowid column
  ** of the index is also allowed to match against the ORDER BY
  ** clause.
  */
  for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){
    Expr *pExpr;       /* The expression of the ORDER BY pTerm */
    CollSeq *pColl;    /* The collating sequence of pExpr */
    int termSortOrder; /* Sort order for this term */
    int iColumn;       /* The i-th column of the index.  -1 for rowid */
    int iSortOrder;    /* 1 for DESC, 0 for ASC on the i-th index term */
    const char *zColl; /* Name of the collating sequence for i-th index term */





    pExpr = pTerm->pExpr;
    if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
      /* Can not use an index sort on anything that is not a column in the
      ** left-most table of the FROM clause */
      break;

    }













    pColl = sqlite4ExprCollSeq(pParse, pExpr);
    if( !pColl ){
      pColl = db->pDfltColl;
    }
    if( pIdx->zName && i<pIdx->nColumn ){
      iColumn = pIdx->aiColumn[i];
      iSortOrder = pIdx->aSortOrder[i];
      zColl = pIdx->azColl[i];
    }else{
      iColumn = -1;





      iSortOrder = 0;
      zColl = pColl->zName;



    }
    if( pExpr->iColumn!=iColumn || sqlite4StrICmp(pColl->zName, zColl) ){
      /* Term j of the ORDER BY clause does not match column i of the index */

      if( i<nEqCol ){
        /* If an index column that is constrained by == fails to match an
        ** ORDER BY term, that is OK.  Just ignore that column of the index
        */
        continue;
      }else if( i==pIdx->nColumn ){
        /* Index column i is the rowid.  All other terms match. */


        break;
      }else{
        /* If an index column fails to match and is not constrained by ==
        ** then the index cannot satisfy the ORDER BY constraint.
        */
        return 0;
      }
    }
    assert( pIdx->aSortOrder!=0 || iColumn==-1 );
    assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
    assert( iSortOrder==0 || iSortOrder==1 );
    termSortOrder = iSortOrder ^ pTerm->sortOrder;
    if( i>nEqCol ){
      if( termSortOrder!=sortOrder ){
        /* Indices can only be used if all ORDER BY terms past the
        ** equality constraints are all either DESC or ASC. */
        return 0;
      }
    }else{
      sortOrder = termSortOrder;
    }
    j++;
    pTerm++;

    if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
      /* If the indexed column is the primary key and everything matches
      ** so far and none of the ORDER BY terms to the right reference other
      ** tables in the join, then we are assured that the index can be used 
      ** to sort because the primary key is unique and so none of the other
      ** columns will make any difference
      */
      j = nTerm;
    }

  }

  *pbRev = sortOrder!=0;

  if( j>=nTerm ){
    /* All terms of the ORDER BY clause are covered by this index so
    ** this index can be used for sorting. */
    return 1;
  }

  if( pIdx->onError!=OE_None && i==pIdx->nColumn

      && (wsFlags & WHERE_COLUMN_NULL)==0
      && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){




    /* All terms of this index match some prefix of the ORDER BY clause
    ** and the index is UNIQUE and no terms on the tail of the ORDER BY
    ** clause reference other tables in a join.  If this is all true then
    ** the order by clause is superfluous.  Not that if the matching
    ** condition is IS NULL then the result is not necessarily unique
    ** even on a UNIQUE index, so disallow those cases. */



    return 1;





  }











  return 0;
}

/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operations with O(logN) or O(NlogN)
................................................................................
    *pnRow = nRowEst;
    WHERETRACE(("IN row estimate: est=%g\n", nRowEst));
  }
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT3) */


/*
** Find the best query plan for accessing a particular table.  Write the
** best query plan and its cost into the WhereCost object supplied as the
** last parameter.
**
** The lowest cost plan wins.  The cost is an estimate of the amount of
** CPU and disk I/O needed to process the requested result.
................................................................................
  ExprList *pOrderBy,         /* The ORDER BY clause */
  ExprList *pDistinct,        /* The select-list if query is DISTINCT */
  WhereCost *pCost            /* Lowest cost query plan */
){
  int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  Index *pProbe;              /* An index we are evaluating */
  Index *pFirst;              /* First index to evaluate */

  int eqTermMask;             /* Current mask of valid equality operators */
  int idxEqTermMask;          /* Index mask of valid equality operators */

  /* Initialize the cost to a worst-case value */
  memset(pCost, 0, sizeof(*pCost));
  pCost->rCost = SQLITE_BIG_DBL;

................................................................................
    eqTermMask = WO_EQ|WO_IN;
    pFirst = pSrc->pTab->pIndex;
  }
#else
  eqTermMask = idxEqTermMask;
  pFirst = pSrc->pTab->pIndex;
#endif


  /* Loop over all indices looking for the best one to use */
  for(pProbe=pFirst; pProbe; pProbe=pProbe->pNext){
    const tRowcnt * const aiRowEst = pProbe->aiRowEst;
    double cost;                /* Cost of using pProbe */
    double nRow;                /* Estimated number of rows in result set */
    double log10N = (double)1;  /* base-10 logarithm of nRow (inexact) */
................................................................................
    int bSort = !!pOrderBy;       /* True if external sort required */
    int bDist = !!pDistinct;      /* True if index cannot help with DISTINCT */
    int bLookup = 0;              /* True if not the PK index */
    WhereTerm *pTerm;             /* A single term of the WHERE clause */
#ifdef SQLITE_ENABLE_STAT3
    WhereTerm *pFirstTerm = 0;    /* First term matching the index */
#endif








    /* Determine the values of nEq and nInMul */
    for(nEq=0; nEq<pProbe->nColumn; nEq++){
      int j = pProbe->aiColumn[nEq];


      pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
      if( pTerm==0 ) break;
      wsFlags |= WHERE_COLUMN_EQ;
      testcase( pTerm->pWC!=pWC );
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        wsFlags |= WHERE_COLUMN_IN;
        if( ExprHasProperty(pExpr, EP_xIsSelect) ){
................................................................................
    ** at most a single row. In this case set the WHERE_UNIQUE flag to 
    ** indicate this to the caller.
    **
    ** Otherwise, if the search may find more than one row, test to see if
    ** there is a range constraint on indexed column (nEq+1) that can be 
    ** optimized using the index. 
    */
    if( nEq==pProbe->nColumn && pProbe->onError!=OE_None ){
      testcase( wsFlags & WHERE_COLUMN_IN );
      testcase( wsFlags & WHERE_COLUMN_NULL );
      if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
        wsFlags |= WHERE_UNIQUE;
      }
    }else if( pProbe->bUnordered==0 ){
      int j = (nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[nEq]);
      if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe) ){
        WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe);
        WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe);
        whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv);
        if( pTop ){
          nBound = 1;
          wsFlags |= WHERE_TOP_LIMIT;
................................................................................
    sqlite4VdbeAddOp4(v, OP_Explain, iId, iLevel, iFrom, zMsg, P4_DYNAMIC);
  }
}
#else
# define explainOneScan(u,v,w,x,y,z)
#endif /* SQLITE_OMIT_EXPLAIN */


/*
** Generate code for the start of the iLevel-th loop in the WHERE clause
** implementation described by pWInfo.
*/
static Bitmask codeOneLoopStart(
  WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
  int iLevel,          /* Which level of pWInfo->a[] should be coded */
................................................................................
  u16 wctrlFlags,      /* One of the WHERE_* flags defined in sqliteInt.h */
  Bitmask notReady,    /* Which tables are currently available */
  Expr *pWhere         /* Complete WHERE clause */
){
  int j, k;            /* Loop counters */
  int iCur;            /* The VDBE cursor for the table */
  int addrNxt;         /* Where to jump to continue with the next IN case */
  int omitTable;       /* True if we use the index only */
  int bRev;            /* True if we need to scan in reverse order */
  WhereLevel *pLevel;  /* The where level to be coded */
  WhereClause *pWC;    /* Decomposition of the entire WHERE clause */
  WhereTerm *pTerm;               /* A WHERE clause term */
  Parse *pParse;                  /* Parsing context */
  Vdbe *v;                        /* The prepared stmt under constructions */
  struct SrcList_item *pTabItem;  /* FROM clause term being coded */
................................................................................
  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = pWInfo->pWC;
  pLevel = &pWInfo->a[iLevel];
  pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
  iCur = pTabItem->iCursor;
  bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
  omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0 
           && (wctrlFlags & WHERE_FORCE_TABLE)==0;

  /* Create labels for the "break" and "continue" instructions
  ** for the current loop.  Jump to addrBrk to break out of a loop.
  ** Jump to cont to go immediately to the next iteration of the
  ** loop.
  **
  ** When there is an IN operator, we also have a "addrNxt" label that
................................................................................
    Index *pIdx;                 /* The index we will be using */
    int iIdxCur;                 /* The VDBE cursor for the index */
    int nExtraReg = 0;           /* Number of extra registers needed */
    int op;                      /* Instruction opcode */
    char *zStartAff;             /* Affinity for start of range constraint */
    char *zEndAff;               /* Affinity for end of range constraint */
    int regEndKey;               /* Register for end-key */



    pIdx = pLevel->plan.u.pIdx;

    iIdxCur = pLevel->iIdxCur;
    k = (nEq==pIdx->nColumn ? -1 : pIdx->aiColumn[nEq]);


    /* If this loop satisfies a sort order (pOrderBy) request that 
    ** was passed to this function to implement a "SELECT min(x) ..." 
    ** 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,
................................................................................
      isMinQuery = 1;
      nExtraReg = 1;
    }

    /* Find any inequality constraint terms for the start and end 
    ** of the range.  */
    if( pLevel->plan.wsFlags & WHERE_TOP_LIMIT ){
      pRangeEnd = findTerm(pWC, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
      nExtraReg = 1;
    }
    if( pLevel->plan.wsFlags & WHERE_BTM_LIMIT ){
      pRangeStart = findTerm(pWC, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
      nExtraReg = 1;
    }

    /* Generate code to evaluate all constraint terms using == or IN
    ** and store the values of those terms in an array of registers
    ** starting at regBase. Ensure that nExtraReg registers are allocated
    ** immediately following the array.
................................................................................
  {
    /* Case 5:  There is no usable index.  We must do a complete
    **          scan of the entire table.
    */
    static const u8 aStep[] = { OP_Next, OP_Prev };
    static const u8 aStart[] = { OP_Rewind, OP_Last };
    assert( bRev==0 || bRev==1 );
    assert( omitTable==0 );
    pLevel->op = aStep[bRev];
    pLevel->p1 = iCur;
    pLevel->p2 = 1 + sqlite4VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
    pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
  }
  notReady &= ~getMask(pWC->pMaskSet, iCur);








>
>


>










>
>

<
<



|
|
|
>
|
<
|
|


|
<
|
|
>
>
>

<
>
>
>
>







 







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







 







|


|
|
>
>
>





>
>

>
>

>

<
<
<
<
>
>
>

<
<
<
<
<
<
<
<
<




<


>
>
>
>

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

<
|
<
|
<
<
|

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

<
<
<
<
<

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









>



>
|
|
|


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







 







<







 







>







 







>







 







>

>
>
>
>
>
>

|
<
>
>
|







 







|






|







 







<







 







<







 







<
<







 







>
>


>

<
>







 







|



|







 







<







587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611


612
613
614
615
616
617
618
619

620
621
622
623
624

625
626
627
628
629
630

631
632
633
634
635
636
637
638
639
640
641
....
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
....
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665




1666
1667
1668
1669









1670
1671
1672
1673

1674
1675
1676
1677
1678
1679
1680
1681



1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697

1698

1699


1700
1701

1702
1703
1704
1705
1706
1707

1708
1709
1710
1711


1712
1713






1714
1715
1716





1717






1718



1719


1720


1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750





1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
....
2883
2884
2885
2886
2887
2888
2889

2890
2891
2892
2893
2894
2895
2896
....
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
....
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
....
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070

3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
....
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
....
3815
3816
3817
3818
3819
3820
3821

3822
3823
3824
3825
3826
3827
3828
....
3829
3830
3831
3832
3833
3834
3835

3836
3837
3838
3839
3840
3841
3842
....
3848
3849
3850
3851
3852
3853
3854


3855
3856
3857
3858
3859
3860
3861
....
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995

3996
3997
3998
3999
4000
4001
4002
4003
....
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
....
4342
4343
4344
4345
4346
4347
4348

4349
4350
4351
4352
4353
4354
4355
  WhereClause *pWC,     /* The WHERE clause to be searched */
  int iCur,             /* Cursor number of LHS */
  int iColumn,          /* Column number of LHS */
  Bitmask notReady,     /* RHS must not overlap with this mask */
  u32 op,               /* Mask of WO_xx values describing operator */
  Index *pIdx           /* Must be compatible with this index, if not NULL */
){
  sqlite4 *db = pWC->pParse->db;  /* Database handle */
  Table *pTab = pIdx->pTable;     /* Table object for cursor iCur */
  WhereTerm *pTerm;
  int k;

  assert( iCur>=0 );
  op &= WO_ALL;
  for(; pWC; pWC=pWC->pOuter){
    for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
      if( pTerm->leftCursor==iCur
         && (pTerm->prereqRight & notReady)==0
         && pTerm->u.leftColumn==iColumn
         && (pTerm->eOperator & op)!=0
      ){
        if( iColumn>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){
          const char *zColl;      /* Collation sequence used by index */
          CollSeq *pColl;         /* Collation sequence used by expression */
          Expr *pX = pTerm->pExpr;


          int j;
          Parse *pParse = pWC->pParse;
  
          if( !sqlite4IndexAffinityOk(pX, pTab->aCol[iColumn].affinity) ){
            continue;
          }
  
          /* Figure out the collation sequence used by expression pX. Store

          ** this in pColl. Also the collation sequence used by the index.
          ** Store this one in zColl.  */
          assert(pX->pLeft);
          pColl = sqlite4BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
          assert( pParse->nErr || (pColl && pColl->enc==pIdx->pSchema->enc)  );

          for(j=0; pIdx->aiColumn[j]!=iColumn && j<pIdx->nColumn; j++);
          if( j>=pIdx->nColumn ){
            zColl = pTab->aCol[iColumn].zColl;
          }else{
            zColl = pIdx->azColl[j];
          }


          /* If the collation sequence used by the index is not the same as
          ** that used by the expression, then this term is not a match.  */
          if( pColl!=sqlite4FindCollSeq(db, ENC(db), zColl, 0) ) continue;
        }
        return pTerm;
      }
    }
  }
  return 0;
}
................................................................................
      return 1;
    }
  }

  return 0;
}


/*
** Return the table column number of the iIdxCol'th field in the index
** keys used by index pIdx, including any appended PRIMARY KEY fields.
** If there is no iIdxCol'th field in index pIdx, return -2.
**
** Example:
**
**   CREATE TABLE t1(a, b, c, PRIMARY KEY(a, b));
**   CREATE INDEX i1 ON t1(c);
**
** Index i1 in the example above consists of three fields - the indexed
** field "c" followed by the two primary key fields. The automatic PRIMARY
** KEY index consists of two fields only.
*/
static int idxColumnNumber(Index *pIdx, Index *pPk, int iIdxCol){
  int iRet = -2;
  if( iIdxCol<pIdx->nColumn ){
    iRet = pIdx->aiColumn[iIdxCol];
  }else if( iIdxCol<(pIdx->nColumn + pPk->nColumn) ){
    iRet = pPk->aiColumn[iIdxCol - pIdx->nColumn];
  }
  return iRet;
}

/*
** This routine decides if pIdx can be used to satisfy the ORDER BY
** clause.  If it can, it returns 1.  If pIdx cannot satisfy the
** ORDER BY clause, this routine returns 0.
**
** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
** left-most table in the FROM clause of that same SELECT statement and
................................................................................
  Index *pIdx,            /* The index we are testing */
  int base,               /* Cursor number for the table to be sorted */
  ExprList *pOrderBy,     /* The ORDER BY clause */
  int nEqCol,             /* Number of index columns with == constraints */
  int wsFlags,            /* Index usages flags */
  int *pbRev              /* Set to 1 if ORDER BY is DESC */
){
  sqlite4 *db = pParse->db;       /* Database handle */
  int sortOrder = 0;              /* XOR of index and ORDER BY sort direction */
  int nTerm;                      /* Number of ORDER BY terms */
  int iTerm;                      /* Used to iterate through nTerm terms */
  int iNext = nEqCol;             /* Index of next unmatched column in index */
  int nIdxCol;                    /* Number of columns in index, incl. PK */
  Index *pPk;
  Table *pTab;

  if( !pOrderBy ) return 0;
  if( wsFlags & WHERE_COLUMN_IN ) return 0;
  if( pIdx->bUnordered ) return 0;

  pTab = pIdx->pTable;
  pPk = sqlite4FindPrimaryKey(pTab, 0);
  nTerm = pOrderBy->nExpr;
  nIdxCol = pIdx->nColumn + (pIdx==pPk ? 0 : pPk->nColumn);

  assert( nTerm>0 );
  assert( pIdx && pIdx->zName );





  for(iTerm=0; iTerm<nTerm; iTerm++){
    struct ExprList_item *pTerm;  /* iTerm'th term of ORDER BY clause */
    int iIdxCol;                  /* Index of column in index records */










    Expr *pExpr;       /* The expression of the ORDER BY pTerm */
    CollSeq *pColl;    /* The collating sequence of pExpr */
    int termSortOrder; /* Sort order for this term */
    int iColumn;       /* The i-th column of the index.  -1 for rowid */

    const char *zColl; /* Name of the collating sequence for i-th index term */

    /* Can not use an index sort on anything that is not a column in the
    ** left-most table of the FROM clause. Break out of the loop if this
    ** expression is anything other than that. */
    pTerm = &pOrderBy->a[iTerm];
    pExpr = pTerm->pExpr;
    if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ) break;



    iColumn = pExpr->iColumn;

    /* Check that column iColumn is a part of the index. If it is not, then
    ** this index may not be used as a sorting index. This block also checks
    ** that column iColumn is either the iNext'th column of the index, or
    ** else one of the nEqCol columns that the index guarantees will be 
    ** constant.  */
    for(iIdxCol=0; iIdxCol<nIdxCol; iIdxCol++){
      if( idxColumnNumber(pIdx, pPk, iIdxCol)==iColumn ) break;
    }
    if( iIdxCol==nIdxCol || (iIdxCol>=nEqCol && iIdxCol!=iNext) ) break;

    /* Check that the collation sequence used by the expression is the same
    ** as the collation sequence used by the index. If not, this is not a
    ** sorting index.  */
    pColl = sqlite4ExprCollSeq(pParse, pExpr);

    if( !pColl ) pColl = db->pDfltColl;

    if( iIdxCol<pIdx->nColumn ){


      zColl = pIdx->azColl[iIdxCol];
    }else{

      zColl = pTab->aCol[iColumn].zColl;
    }
    if( pColl!=sqlite4FindCollSeq(db, ENC(db), zColl, 0) ) break;

    if( iIdxCol==iNext ){
      u8 reqSortOrder;

      u8 idxSortOrder = SQLITE_SO_ASC;
      if( iIdxCol<pIdx->nColumn ) idxSortOrder = pIdx->aSortOrder[iIdxCol];
      assert( idxSortOrder==SQLITE_SO_ASC || idxSortOrder==SQLITE_SO_DESC );



      reqSortOrder = (idxSortOrder ^ pTerm->sortOrder);
      if( iNext==nEqCol ){






        sortOrder = reqSortOrder;
      }else if( sortOrder!=reqSortOrder ){
        break;





      }






      iNext++;



    }





#if 0
    if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
      /* If the indexed column is the primary key and everything matches
      ** so far and none of the ORDER BY terms to the right reference other
      ** tables in the join, then we are assured that the index can be used 
      ** to sort because the primary key is unique and so none of the other
      ** columns will make any difference
      */
      j = nTerm;
    }
#endif
  }

  *pbRev = sortOrder!=0;

  if( iTerm>=nTerm ){
    /* All terms of the ORDER BY clause are covered by this index. The
    ** index can therefore be used for sorting.  */
    return 1;
  }

  if( pIdx->onError!=OE_None
   && iNext>=pIdx->nColumn 
   && (wsFlags & WHERE_COLUMN_NULL)==0
   && !referencesOtherTables(pOrderBy, pMaskSet, iTerm, base) 
  ){

    if( iNext==nIdxCol ){
      /* All columns indexed by this UNIQUE index, and all PK columns are
      ** are matched by a prefix of the ORDER BY clause. And since the PK





      ** columns are guaranteed to be unique and NOT NULL, there is no way
      ** for the trailing ORDER BY terms to affect the sort order. Therefore,
      ** we have a sorting index.  */
      return 1;
    }else{
      int i;
      for(i=nEqCol; i<pIdx->nColumn; i++){
        int iCol = pIdx->aiColumn[i];
        if( iCol>=0 && pTab->aCol[iCol].notNull==0 ) break;
      }

      /* All columns indexed by this UNIQUE index are matched by a prefix
      ** of the ORDER BY clause. And there is reason to believe that none
      ** of the expressions in the ORDER BY prefix will evalulate to NULL.
      ** The index may be used for sorting in this case too since it is
      ** guaranteed that none of the trailing, unmatched ORDER BY terms 
      ** affect the sort order.  */
      return (i>=pIdx->nColumn);
    }
  }

  return 0;
}

/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operations with O(logN) or O(NlogN)
................................................................................
    *pnRow = nRowEst;
    WHERETRACE(("IN row estimate: est=%g\n", nRowEst));
  }
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT3) */


/*
** Find the best query plan for accessing a particular table.  Write the
** best query plan and its cost into the WhereCost object supplied as the
** last parameter.
**
** The lowest cost plan wins.  The cost is an estimate of the amount of
** CPU and disk I/O needed to process the requested result.
................................................................................
  ExprList *pOrderBy,         /* The ORDER BY clause */
  ExprList *pDistinct,        /* The select-list if query is DISTINCT */
  WhereCost *pCost            /* Lowest cost query plan */
){
  int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  Index *pProbe;              /* An index we are evaluating */
  Index *pFirst;              /* First index to evaluate */
  Index *pPk;                 /* Primary Key index */
  int eqTermMask;             /* Current mask of valid equality operators */
  int idxEqTermMask;          /* Index mask of valid equality operators */

  /* Initialize the cost to a worst-case value */
  memset(pCost, 0, sizeof(*pCost));
  pCost->rCost = SQLITE_BIG_DBL;

................................................................................
    eqTermMask = WO_EQ|WO_IN;
    pFirst = pSrc->pTab->pIndex;
  }
#else
  eqTermMask = idxEqTermMask;
  pFirst = pSrc->pTab->pIndex;
#endif
  pPk = sqlite4FindPrimaryKey(pSrc->pTab, 0);

  /* Loop over all indices looking for the best one to use */
  for(pProbe=pFirst; pProbe; pProbe=pProbe->pNext){
    const tRowcnt * const aiRowEst = pProbe->aiRowEst;
    double cost;                /* Cost of using pProbe */
    double nRow;                /* Estimated number of rows in result set */
    double log10N = (double)1;  /* base-10 logarithm of nRow (inexact) */
................................................................................
    int bSort = !!pOrderBy;       /* True if external sort required */
    int bDist = !!pDistinct;      /* True if index cannot help with DISTINCT */
    int bLookup = 0;              /* True if not the PK index */
    WhereTerm *pTerm;             /* A single term of the WHERE clause */
#ifdef SQLITE_ENABLE_STAT3
    WhereTerm *pFirstTerm = 0;    /* First term matching the index */
#endif
    int nCol = pProbe->nColumn;   /* Total columns in index record */

    /* Unless pProbe is the primary key index, then the encoded PK column 
    ** values are at the end of each record. Set variable nCol to the total
    ** number of columns encoded into each index record, including the PK  
    ** columns.  */
    if( pProbe!=pPk ) nCol += pPk->nColumn;

    /* Determine the values of nEq and nInMul */
    for(nEq=0; nEq<nCol; nEq++){

      int iCol;                   /* Table column of nEq'th index field */
      iCol = idxColumnNumber(pProbe, pPk, nEq);
      pTerm = findTerm(pWC, iCur, iCol, notReady, eqTermMask, pProbe);
      if( pTerm==0 ) break;
      wsFlags |= WHERE_COLUMN_EQ;
      testcase( pTerm->pWC!=pWC );
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        wsFlags |= WHERE_COLUMN_IN;
        if( ExprHasProperty(pExpr, EP_xIsSelect) ){
................................................................................
    ** at most a single row. In this case set the WHERE_UNIQUE flag to 
    ** indicate this to the caller.
    **
    ** Otherwise, if the search may find more than one row, test to see if
    ** there is a range constraint on indexed column (nEq+1) that can be 
    ** optimized using the index. 
    */
    if( nEq>=pProbe->nColumn && pProbe->onError!=OE_None ){
      testcase( wsFlags & WHERE_COLUMN_IN );
      testcase( wsFlags & WHERE_COLUMN_NULL );
      if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
        wsFlags |= WHERE_UNIQUE;
      }
    }else if( pProbe->bUnordered==0 ){
      int j = idxColumnNumber(pProbe, pPk, nEq);
      if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe) ){
        WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe);
        WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe);
        whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv);
        if( pTop ){
          nBound = 1;
          wsFlags |= WHERE_TOP_LIMIT;
................................................................................
    sqlite4VdbeAddOp4(v, OP_Explain, iId, iLevel, iFrom, zMsg, P4_DYNAMIC);
  }
}
#else
# define explainOneScan(u,v,w,x,y,z)
#endif /* SQLITE_OMIT_EXPLAIN */


/*
** Generate code for the start of the iLevel-th loop in the WHERE clause
** implementation described by pWInfo.
*/
static Bitmask codeOneLoopStart(
  WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
  int iLevel,          /* Which level of pWInfo->a[] should be coded */
................................................................................
  u16 wctrlFlags,      /* One of the WHERE_* flags defined in sqliteInt.h */
  Bitmask notReady,    /* Which tables are currently available */
  Expr *pWhere         /* Complete WHERE clause */
){
  int j, k;            /* Loop counters */
  int iCur;            /* The VDBE cursor for the table */
  int addrNxt;         /* Where to jump to continue with the next IN case */

  int bRev;            /* True if we need to scan in reverse order */
  WhereLevel *pLevel;  /* The where level to be coded */
  WhereClause *pWC;    /* Decomposition of the entire WHERE clause */
  WhereTerm *pTerm;               /* A WHERE clause term */
  Parse *pParse;                  /* Parsing context */
  Vdbe *v;                        /* The prepared stmt under constructions */
  struct SrcList_item *pTabItem;  /* FROM clause term being coded */
................................................................................
  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = pWInfo->pWC;
  pLevel = &pWInfo->a[iLevel];
  pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
  iCur = pTabItem->iCursor;
  bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;



  /* Create labels for the "break" and "continue" instructions
  ** for the current loop.  Jump to addrBrk to break out of a loop.
  ** Jump to cont to go immediately to the next iteration of the
  ** loop.
  **
  ** When there is an IN operator, we also have a "addrNxt" label that
................................................................................
    Index *pIdx;                 /* The index we will be using */
    int iIdxCur;                 /* The VDBE cursor for the index */
    int nExtraReg = 0;           /* Number of extra registers needed */
    int op;                      /* Instruction opcode */
    char *zStartAff;             /* Affinity for start of range constraint */
    char *zEndAff;               /* Affinity for end of range constraint */
    int regEndKey;               /* Register for end-key */
    int iIneq;                   /* The table column subject to inequality */
    Index *pPk;                  /* Primary key index on same table as pIdx */

    pIdx = pLevel->plan.u.pIdx;
    pPk = sqlite4FindPrimaryKey(pIdx->pTable, 0);
    iIdxCur = pLevel->iIdxCur;

    iIneq = idxColumnNumber(pIdx, pPk, nEq);

    /* If this loop satisfies a sort order (pOrderBy) request that 
    ** was passed to this function to implement a "SELECT min(x) ..." 
    ** 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,
................................................................................
      isMinQuery = 1;
      nExtraReg = 1;
    }

    /* Find any inequality constraint terms for the start and end 
    ** of the range.  */
    if( pLevel->plan.wsFlags & WHERE_TOP_LIMIT ){
      pRangeEnd = findTerm(pWC, iCur, iIneq, notReady, (WO_LT|WO_LE), pIdx);
      nExtraReg = 1;
    }
    if( pLevel->plan.wsFlags & WHERE_BTM_LIMIT ){
      pRangeStart = findTerm(pWC, iCur, iIneq, notReady, (WO_GT|WO_GE), pIdx);
      nExtraReg = 1;
    }

    /* Generate code to evaluate all constraint terms using == or IN
    ** and store the values of those terms in an array of registers
    ** starting at regBase. Ensure that nExtraReg registers are allocated
    ** immediately following the array.
................................................................................
  {
    /* Case 5:  There is no usable index.  We must do a complete
    **          scan of the entire table.
    */
    static const u8 aStep[] = { OP_Next, OP_Prev };
    static const u8 aStart[] = { OP_Rewind, OP_Last };
    assert( bRev==0 || bRev==1 );

    pLevel->op = aStep[bRev];
    pLevel->p1 = iCur;
    pLevel->p2 = 1 + sqlite4VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
    pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
  }
  notReady &= ~getMask(pWC->pMaskSet, iCur);

Changes to test/permutations.test.

128
129
130
131
132
133
134
135
136
137


138
139
140
141
142
143
144
#   veryquick
#   quick
#   full
#
lappend ::testsuitelist xxx

test_suite "src4" -prefix "" -description {
} -files [
  test_set simple.test fkey1.test conflict.test trigger2.test select1.test
]



test_suite "veryquick" -prefix "" -description {
  "Very" quick test suite. Runs in less than 5 minutes on a workstation. 
  This test suite is the same as the "quick" tests, except that some files
  that test malloc and IO errors are omitted.
} -files [
  test_set $allquicktests -exclude *malloc* *ioerr* *fault*







|
|
<
>
>







128
129
130
131
132
133
134
135
136

137
138
139
140
141
142
143
144
145
#   veryquick
#   quick
#   full
#
lappend ::testsuitelist xxx

test_suite "src4" -prefix "" -description {
} -files {
  simple.test fkey1.test conflict.test trigger2.test select1.test

  where.test
}

test_suite "veryquick" -prefix "" -description {
  "Very" quick test suite. Runs in less than 5 minutes on a workstation. 
  This test suite is the same as the "quick" tests, except that some files
  that test malloc and IO errors are omitted.
} -files [
  test_set $allquicktests -exclude *malloc* *ioerr* *fault*

Changes to test/where.test.

197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
...
310
311
312
313
314
315
316
317
318
319
320
321
322
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
...
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
...
493
494
495
496
497
498
499

500
501
502
503
504
505
506
507
508
509

510


511
512
513
514

515
516
517
518
519
520
521
...
556
557
558
559
560
561
562

563
564
565
566
567
568
569
570
571
572
573
...
620
621
622
623
624
625
626

627
628
629
630
631

632
633
634
635
636
637
638
....
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128

1129
1130
1131
1132
1133

1134
1135
1136
1137
1138
1139
1140
#
# do_test where-1.26 {
#   count {SELECT w FROM t1 WHERE x=3 AND y BETWEEN 121 AND 196}
# } {10 11 12 13 9}

do_test where-1.27 {
  count {SELECT w FROM t1 WHERE x=3 AND y+1==122}
} {10 10}

do_test where-1.28 {
  count {SELECT w FROM t1 WHERE x+1=4 AND y+1==122}
} {10 99}
do_test where-1.29 {
  count {SELECT w FROM t1 WHERE y==121}
} {10 99}


do_test where-1.30 {
  count {SELECT w FROM t1 WHERE w>97}
} {98 99 100 3}
do_test where-1.31 {
  count {SELECT w FROM t1 WHERE w>=97}
} {97 98 99 100 4}
do_test where-1.33 {
  count {SELECT w FROM t1 WHERE w==97}
} {97 2}
do_test where-1.33.1  {
  count {SELECT w FROM t1 WHERE w<=97 AND w==97}
} {97 2}
do_test where-1.33.2  {
  count {SELECT w FROM t1 WHERE w<98 AND w==97}
} {97 2}
do_test where-1.33.3  {
  count {SELECT w FROM t1 WHERE w>=97 AND w==97}
} {97 2}
do_test where-1.33.4  {
  count {SELECT w FROM t1 WHERE w>96 AND w==97}
} {97 2}
do_test where-1.33.5  {
  count {SELECT w FROM t1 WHERE w==97 AND w==97}
} {97 2}
do_test where-1.34 {
  count {SELECT w FROM t1 WHERE w+1==98}
} {97 99}
do_test where-1.35 {
  count {SELECT w FROM t1 WHERE w<3}
} {1 2 2}
do_test where-1.36 {
  count {SELECT w FROM t1 WHERE w<=3}
} {1 2 3 3}
do_test where-1.37 {
  count {SELECT w FROM t1 WHERE w+1<=4 ORDER BY w}
} {1 2 3 99}

do_test where-1.38 {
  count {SELECT (w) FROM t1 WHERE (w)>(97)}
} {98 99 100 3}
do_test where-1.39 {
  count {SELECT (w) FROM t1 WHERE (w)>=(97)}
} {97 98 99 100 4}
do_test where-1.40 {
  count {SELECT (w) FROM t1 WHERE (w)==(97)}
} {97 2}
do_test where-1.41 {
  count {SELECT (w) FROM t1 WHERE ((w)+(1))==(98)}
} {97 99}


# Do the same kind of thing except use a join as the data source.
#
do_test where-2.1 {
  count {
    SELECT w, p FROM t2, t1
................................................................................
# Lets do a 3-way join.
#
do_test where-3.1 {
  count {
    SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C
    WHERE C.w=101-B.p AND B.r=10202-A.y AND A.w=11
  }
} {11 90 11 8}
do_test where-3.2 {
  count {
    SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C
    WHERE C.w=101-B.p AND B.r=10202-A.y AND A.w=12
  }
} {12 89 12 8}
do_test where-3.3 {
  count {
    SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C
    WHERE A.w=15 AND B.p=C.w AND B.r=10202-A.y
  }
} {15 86 86 8}

# Test to see that the special case of a constant WHERE clause is
# handled.
#
do_test where-4.1 {
  count {
    SELECT * FROM t1 WHERE 0
  }
} {0}
do_test where-4.2 {
  count {
    SELECT * FROM t1 WHERE 1 LIMIT 1
  }
} {1 0 4 0}
do_test where-4.3 {
  execsql {
    SELECT 99 WHERE 0
  }
} {}
do_test where-4.4 {
  execsql {
................................................................................
# Omit these tests if the build is not capable of sub-queries.
#
ifcapable subquery {
  do_test where-5.1 {
    count {
      SELECT * FROM t1 WHERE rowid IN (1,2,3,1234) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 4}
  do_test where-5.2 {
    count {
      SELECT * FROM t1 WHERE rowid+0 IN (1,2,3,1234) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 102}
  do_test where-5.3 {
    count {
      SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 14}
  do_test where-5.4 {
    count {
      SELECT * FROM t1 WHERE w+0 IN (-1,1,2,3) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 102}
  do_test where-5.5 {
    count {
      SELECT * FROM t1 WHERE rowid IN 
         (select rowid from t1 where rowid IN (-1,2,4))
      ORDER BY 1;
    }
  } {2 1 9 4 2 25 3}
  do_test where-5.6 {
    count {
      SELECT * FROM t1 WHERE rowid+0 IN 
         (select rowid from t1 where rowid IN (-1,2,4))
      ORDER BY 1;
    }
  } {2 1 9 4 2 25 103}
  do_test where-5.7 {
    count {
      SELECT * FROM t1 WHERE w IN 
         (select rowid from t1 where rowid IN (-1,2,4))
      ORDER BY 1;
    }
  } {2 1 9 4 2 25 9}
  do_test where-5.8 {
    count {
      SELECT * FROM t1 WHERE w+0 IN 
         (select rowid from t1 where rowid IN (-1,2,4))
      ORDER BY 1;
    }
  } {2 1 9 4 2 25 103}
  do_test where-5.9 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) ORDER BY 1;
    }
  } {2 1 9 3 1 16 7}
  do_test where-5.10 {
    count {
      SELECT * FROM t1 WHERE x+0 IN (1,7) ORDER BY 1;
    }
  } {2 1 9 3 1 16 199}
  do_test where-5.11 {
    count {
      SELECT * FROM t1 WHERE y IN (6400,8100) ORDER BY 1;
    }
  } {79 6 6400 89 6 8100 199}
  do_test where-5.12 {
    count {
      SELECT * FROM t1 WHERE x=6 AND y IN (6400,8100) ORDER BY 1;
    }
  } {79 6 6400 89 6 8100 7}
  do_test where-5.13 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y NOT IN (6400,8100) ORDER BY 1;
    }
  } {2 1 9 3 1 16 7}
  do_test where-5.14 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,10) ORDER BY 1;
    }
  } {2 1 9 8}
  do_test where-5.15 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,16) ORDER BY 1;
    }
  } {2 1 9 3 1 16 11}
}

# This procedure executes the SQL.  Then it checks to see if the OP_Sort
# opcode was executed.  If an OP_Sort did occur, then "sort" is appended
# to the result.  If no OP_Sort happened, then "nosort" is appended.
#
# This procedure is used to check to make sure sorting is or is not
................................................................................
  }
} {1 100 4 2 99 9 3 98 16 sort}
do_test where-6.4 {
  cksort {
    SELECT * FROM t3 WHERE a<10 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}

do_test where-6.5 {
  cksort {
    SELECT * FROM t3 WHERE a>0 AND a<10 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}
do_test where-6.6 {
  cksort {
    SELECT * FROM t3 WHERE a>0 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}

do_test where-6.7 {


  cksort {
    SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}

ifcapable subquery {
  do_test where-6.8 {
    cksort {
      SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3
    }
  } {1 100 4 2 99 9 3 98 16 sort}
}
................................................................................
} {1 100 4 nosort}
do_test where-6.9.6 {
  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY c DESC LIMIT 3
  }
} {1 100 4 nosort}
do_test where-6.9.7 {

  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY c,a LIMIT 3
  }
} {1 100 4 sort}
do_test where-6.9.8 {
  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a DESC, c ASC LIMIT 3
  }
} {1 100 4 nosort}
do_test where-6.9.9 {
  cksort {
................................................................................
  }
} {4 9 16 nosort}
do_test where-6.20 {
  cksort {
    SELECT y FROM t1 ORDER BY rowid LIMIT 3;
  }
} {4 9 16 nosort}

do_test where-6.21 {
  cksort {
    SELECT y FROM t1 ORDER BY rowid, y LIMIT 3;
  }
} {4 9 16 nosort}

do_test where-6.22 {
  cksort {
    SELECT y FROM t1 ORDER BY rowid, y DESC LIMIT 3;
  }
} {4 9 16 nosort}
do_test where-6.23 {
  cksort {
................................................................................
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, x.b DESC
  } 
} {1/1 1/4 4/1 4/4 nosort}
do_test where-14.5 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b
  } 
} {4/1 4/4 1/1 1/4 nosort}
do_test where-14.6 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b DESC
  } 
} {4/1 4/4 1/1 1/4 nosort}
do_test where-14.7 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.7.1 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a, y.a||y.b
  } 
} {4/1 4/4 1/1 1/4 sort}

do_test where-14.7.2 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a, x.a||x.b
  } 
} {4/1 4/4 1/1 1/4 nosort}

do_test where-14.8 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b DESC
  } 
} {4/4 4/1 1/4 1/1 sort}
do_test where-14.9 {
  cksort {







|



|


|




|


|


|


|


|


|


|


|


|


|


|


|



|


|


|


|







 







|





|





|













|







 







|




|




|




|






|






|






|






|




|




|




|




|




|




|




|







 







>










>

>
>



|
>







 







>



|







 







>





>







 







|




|










>





>







197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
...
310
311
312
313
314
315
316
317
318
319
320
321
322
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
...
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
...
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
...
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
...
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
....
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
#
# do_test where-1.26 {
#   count {SELECT w FROM t1 WHERE x=3 AND y BETWEEN 121 AND 196}
# } {10 11 12 13 9}

do_test where-1.27 {
  count {SELECT w FROM t1 WHERE x=3 AND y+1==122}
} {10 17}

do_test where-1.28 {
  count {SELECT w FROM t1 WHERE x+1=4 AND y+1==122}
} {10 101}
do_test where-1.29 {
  count {SELECT w FROM t1 WHERE y==121}
} {10 101}


do_test where-1.30 {
  count {SELECT w FROM t1 WHERE w>97}
} {98 99 100 7}
do_test where-1.31 {
  count {SELECT w FROM t1 WHERE w>=97}
} {97 98 99 100 9}
do_test where-1.33 {
  count {SELECT w FROM t1 WHERE w==97}
} {97 3}
do_test where-1.33.1  {
  count {SELECT w FROM t1 WHERE w<=97 AND w==97}
} {97 3}
do_test where-1.33.2  {
  count {SELECT w FROM t1 WHERE w<98 AND w==97}
} {97 3}
do_test where-1.33.3  {
  count {SELECT w FROM t1 WHERE w>=97 AND w==97}
} {97 3}
do_test where-1.33.4  {
  count {SELECT w FROM t1 WHERE w>96 AND w==97}
} {97 3}
do_test where-1.33.5  {
  count {SELECT w FROM t1 WHERE w==97 AND w==97}
} {97 3}
do_test where-1.34 {
  count {SELECT w FROM t1 WHERE w+1==98}
} {97 101}
do_test where-1.35 {
  count {SELECT w FROM t1 WHERE w<3}
} {1 2 5}
do_test where-1.36 {
  count {SELECT w FROM t1 WHERE w<=3}
} {1 2 3 7}
do_test where-1.37 {
  count {SELECT w FROM t1 WHERE w+1<=4 ORDER BY w}
} {1 2 3 201}

do_test where-1.38 {
  count {SELECT (w) FROM t1 WHERE (w)>(97)}
} {98 99 100 7}
do_test where-1.39 {
  count {SELECT (w) FROM t1 WHERE (w)>=(97)}
} {97 98 99 100 9}
do_test where-1.40 {
  count {SELECT (w) FROM t1 WHERE (w)==(97)}
} {97 3}
do_test where-1.41 {
  count {SELECT (w) FROM t1 WHERE ((w)+(1))==(98)}
} {97 101}


# Do the same kind of thing except use a join as the data source.
#
do_test where-2.1 {
  count {
    SELECT w, p FROM t2, t1
................................................................................
# Lets do a 3-way join.
#
do_test where-3.1 {
  count {
    SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C
    WHERE C.w=101-B.p AND B.r=10202-A.y AND A.w=11
  }
} {11 90 11 9}
do_test where-3.2 {
  count {
    SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C
    WHERE C.w=101-B.p AND B.r=10202-A.y AND A.w=12
  }
} {12 89 12 9}
do_test where-3.3 {
  count {
    SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C
    WHERE A.w=15 AND B.p=C.w AND B.r=10202-A.y
  }
} {15 86 86 9}

# Test to see that the special case of a constant WHERE clause is
# handled.
#
do_test where-4.1 {
  count {
    SELECT * FROM t1 WHERE 0
  }
} {0}
do_test where-4.2 {
  count {
    SELECT * FROM t1 WHERE 1 LIMIT 1
  }
} {1 0 4 1}
do_test where-4.3 {
  execsql {
    SELECT 99 WHERE 0
  }
} {}
do_test where-4.4 {
  execsql {
................................................................................
# Omit these tests if the build is not capable of sub-queries.
#
ifcapable subquery {
  do_test where-5.1 {
    count {
      SELECT * FROM t1 WHERE rowid IN (1,2,3,1234) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 7}
  do_test where-5.2 {
    count {
      SELECT * FROM t1 WHERE rowid+0 IN (1,2,3,1234) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 201}
  do_test where-5.3 {
    count {
      SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 10}
  do_test where-5.4 {
    count {
      SELECT * FROM t1 WHERE w+0 IN (-1,1,2,3) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 201}
  do_test where-5.5 {
    count {
      SELECT * FROM t1 WHERE rowid IN 
         (select rowid from t1 where rowid IN (-1,2,4))
      ORDER BY 1;
    }
  } {2 1 9 4 2 25 9}
  do_test where-5.6 {
    count {
      SELECT * FROM t1 WHERE rowid+0 IN 
         (select rowid from t1 where rowid IN (-1,2,4))
      ORDER BY 1;
    }
  } {2 1 9 4 2 25 206}
  do_test where-5.7 {
    count {
      SELECT * FROM t1 WHERE w IN 
         (select rowid from t1 where rowid IN (-1,2,4))
      ORDER BY 1;
    }
  } {2 1 9 4 2 25 11}
  do_test where-5.8 {
    count {
      SELECT * FROM t1 WHERE w+0 IN 
         (select rowid from t1 where rowid IN (-1,2,4))
      ORDER BY 1;
    }
  } {2 1 9 4 2 25 206}
  do_test where-5.9 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) ORDER BY 1;
    }
  } {2 1 9 3 1 16 6}
  do_test where-5.10 {
    count {
      SELECT * FROM t1 WHERE x+0 IN (1,7) ORDER BY 1;
    }
  } {2 1 9 3 1 16 201}
  do_test where-5.11 {
    count {
      SELECT * FROM t1 WHERE y IN (6400,8100) ORDER BY 1;
    }
  } {79 6 6400 89 6 8100 201}
  do_test where-5.12 {
    count {
      SELECT * FROM t1 WHERE x=6 AND y IN (6400,8100) ORDER BY 1;
    }
  } {79 6 6400 89 6 8100 6}
  do_test where-5.13 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y NOT IN (6400,8100) ORDER BY 1;
    }
  } {2 1 9 3 1 16 6}
  do_test where-5.14 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,10) ORDER BY 1;
    }
  } {2 1 9 6}
  do_test where-5.15 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,16) ORDER BY 1;
    }
  } {2 1 9 3 1 16 8}
}

# This procedure executes the SQL.  Then it checks to see if the OP_Sort
# opcode was executed.  If an OP_Sort did occur, then "sort" is appended
# to the result.  If no OP_Sort happened, then "nosort" is appended.
#
# This procedure is used to check to make sure sorting is or is not
................................................................................
  }
} {1 100 4 2 99 9 3 98 16 sort}
do_test where-6.4 {
  cksort {
    SELECT * FROM t3 WHERE a<10 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}

do_test where-6.5 {
  cksort {
    SELECT * FROM t3 WHERE a>0 AND a<10 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}
do_test where-6.6 {
  cksort {
    SELECT * FROM t3 WHERE a>0 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}

do_test where-6.7 {
  # UPDATE: src4 does a sort here. It picks a different index because it
  # does not support the covering index optimization.
  cksort {
    SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 sort}

ifcapable subquery {
  do_test where-6.8 {
    cksort {
      SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3
    }
  } {1 100 4 2 99 9 3 98 16 sort}
}
................................................................................
} {1 100 4 nosort}
do_test where-6.9.6 {
  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY c DESC LIMIT 3
  }
} {1 100 4 nosort}
do_test where-6.9.7 {
  # UPDATE: src4 uses t3acb here. So does not require an external sort.
  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY c,a LIMIT 3
  }
} {1 100 4 nosort}
do_test where-6.9.8 {
  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a DESC, c ASC LIMIT 3
  }
} {1 100 4 nosort}
do_test where-6.9.9 {
  cksort {
................................................................................
  }
} {4 9 16 nosort}
do_test where-6.20 {
  cksort {
    SELECT y FROM t1 ORDER BY rowid LIMIT 3;
  }
} {4 9 16 nosort}

do_test where-6.21 {
  cksort {
    SELECT y FROM t1 ORDER BY rowid, y LIMIT 3;
  }
} {4 9 16 nosort}

do_test where-6.22 {
  cksort {
    SELECT y FROM t1 ORDER BY rowid, y DESC LIMIT 3;
  }
} {4 9 16 nosort}
do_test where-6.23 {
  cksort {
................................................................................
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, x.b DESC
  } 
} {1/1 1/4 4/1 4/4 nosort}
do_test where-14.5 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.6 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b DESC
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.7 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.7.1 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a, y.a||y.b
  } 
} {4/1 4/4 1/1 1/4 sort}

do_test where-14.7.2 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a, x.a||x.b
  } 
} {4/1 4/4 1/1 1/4 nosort}

do_test where-14.8 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b DESC
  } 
} {4/4 4/1 1/4 1/1 sort}
do_test where-14.9 {
  cksort {