SQLite

/*
** If the expression passed as the first argument is a TK_VECTOR, return
** a pointer to the i'th field of the vector. Or, if the first argument
** points to a sub-select that returns more than one column, return a 
** pointer to the i'th returned column value. Otherwise, return a copy 
** of the first argument.
*/
Expr *sqlite3ExprVectorField(Expr *pVector, int i){
  assert( i<sqlite3ExprVectorSize(pVector) );
  if( sqlite3ExprIsVector(pVector) ){
    if( pVector->op==TK_SELECT ){
      return pVector->x.pSelect->pEList->a[i].pExpr;
    }else{
      return pVector->x.pList->a[i].pExpr;
    }

      int affinity_ok = 1;
      int i;

      /* Check that the affinity that will be used to perform each 
      ** comparison is the same as the affinity of each column. If
      ** it not, it is not possible to use any index.  */
      for(i=0; i<nExpr && affinity_ok; i++){
        Expr *pLhs = sqlite3ExprVectorField(pX->pLeft, i);
        int iCol = pEList->a[i].pExpr->iColumn;
        char idxaff = pTab->aCol[iCol].affinity;
        char cmpaff = sqlite3CompareAffinity(pLhs, idxaff);
        switch( cmpaff ){
          case SQLITE_AFF_BLOB:
            break;
          case SQLITE_AFF_TEXT:

      for(pIdx=pTab->pIndex; pIdx && eType==0 && affinity_ok; pIdx=pIdx->pNext){
        if( pIdx->nKeyCol<nExpr ) continue;
        if( mustBeUnique && (pIdx->nKeyCol!=nExpr || !IsUniqueIndex(pIdx)) ){
          continue;
        }

        for(i=0; i<nExpr; i++){
          Expr *pLhs = sqlite3ExprVectorField(pX->pLeft, i);
          Expr *pRhs = pEList->a[i].pExpr;
          CollSeq *pReq = sqlite3BinaryCompareCollSeq(pParse, pLhs, pRhs);
          int j;

          for(j=0; j<nExpr; j++){
            if( pIdx->aiColumn[j]!=pRhs->iColumn ) continue;
            assert( pIdx->azColl[j] );

  char *zRet;

  assert( pExpr->op==TK_IN );
  zRet = sqlite3DbMallocZero(pParse->db, nVal+1);
  if( zRet ){
    int i;
    for(i=0; i<nVal; i++){
      Expr *pA = sqlite3ExprVectorField(pLeft, i);
      char a = sqlite3ExprAffinity(pA);
      if( pSelect ){
        zRet[i] = sqlite3CompareAffinity(pSelect->pEList->a[i].pExpr, a);
      }else{
        zRet[i] = a;
      }
    }

          }
          sqlite3DbFree(pParse->db, dest.zAffSdst);
          assert( pKeyInfo!=0 ); /* OOM will cause exit after sqlite3Select() */
          assert( pEList!=0 );
          assert( pEList->nExpr>0 );
          assert( sqlite3KeyInfoIsWriteable(pKeyInfo) );
          for(i=0; i<nVal; i++){
            Expr *p = (nVal>1) ? sqlite3ExprVectorField(pLeft, i) : pLeft;
            pKeyInfo->aColl[i] = sqlite3BinaryCompareCollSeq(
                pParse, p, pEList->a[i].pExpr
            );
          }
        }
      }else if( ALWAYS(pExpr->x.pList!=0) ){
        /* Case 2:     expr IN (exprlist)

  if( nVector>1 && (pLeft->flags & EP_xIsSelect) ){
    int regSelect = sqlite3CodeSubselect(pParse, pLeft, 0, 0);
    for(i=0; i<nVector; i++){
      sqlite3VdbeAddOp3(v, OP_Copy, regSelect+i, r1+aiMap[i], 0);
    }
  }else{
    for(i=0; i<nVector; i++){
      Expr *pLhs = sqlite3ExprVectorField(pLeft, i);
      sqlite3ExprCode(pParse, pLhs, r1+aiMap[i]);
    }
  }

  /* If sqlite3FindInIndex() did not find or create an index that is
  ** suitable for evaluating the IN operator, then evaluate using a
  ** sequence of comparisons.

    **
    ** Otherwise, if NULL and false are handled differently, and the
    ** IN(...) operation is not a vector operation, and the LHS of the
    ** operator is NULL, then the result is false if the index is 
    ** completely empty, or NULL otherwise.  */
    if( destIfNull==destIfFalse ){
      for(i=0; i<nVector; i++){
        Expr *p = sqlite3ExprVectorField(pExpr->pLeft, i);
        if( sqlite3ExprCanBeNull(p) ){
          sqlite3VdbeAddOp2(v, OP_IsNull, r1+aiMap[i], destIfNull);
        }
      }
    }else if( nVector==1 && sqlite3ExprCanBeNull(pExpr->pLeft) ){
      int addr1 = sqlite3VdbeAddOp1(v, OP_NotNull, r1); VdbeCoverage(v);
      sqlite3VdbeAddOp2(v, OP_Rewind, pExpr->iTable, destIfFalse);

        ** 0. The vdbe code generated below figures out which.  */
        addrNext = 1+sqlite3VdbeAddOp2(v, OP_Rewind, iIdx, destIfFalse);

        for(i=0; i<nVector; i++){
          Expr *p;
          CollSeq *pColl;
          int r2 = sqlite3GetTempReg(pParse);
          p = sqlite3ExprVectorField(pLeft, i);
          pColl = sqlite3ExprCollSeq(pParse, p);

          sqlite3VdbeAddOp3(v, OP_Column, iIdx, i, r2);
          sqlite3VdbeAddOp4(v, OP_Eq, r1+i, 0, r2, (void*)pColl,P4_COLLSEQ);
          sqlite3VdbeChangeP5(v, SQLITE_JUMPIFNULL);
          sqlite3VdbeAddOp2(v, OP_Next, iIdx, addrNext);
          sqlite3VdbeAddOp2(v, OP_Goto, 0, destIfFalse);
          sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-3);
          sqlite3ReleaseTempReg(pParse, r2);
        }
        sqlite3VdbeAddOp2(v, OP_Goto, 0, destIfNull);

        /* The key was found in the index. If it contains any NULL values,
        ** then the result of the IN(...) operator is NULL. Otherwise, the
        ** result is 1.  */
        sqlite3VdbeJumpHere(v, addr);
        for(i=0; i<nVector; i++){
          Expr *p = sqlite3ExprVectorField(pExpr->pLeft, i);
          if( sqlite3ExprCanBeNull(p) ){
            sqlite3VdbeAddOp2(v, OP_IsNull, r1+aiMap[i], destIfNull);
          }
        }

      }else if( rRhsHasNull==0 ){
        /* This branch runs if it is known at compile time that the RHS

int sqlite3ExprCheckIN(Parse*, Expr*);
#else
# define sqlite3ExprCheckIN(x,y) SQLITE_OK
#endif

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
void sqlite3AnalyzeFunctions(void);
int sqlite3Stat4ProbeSetValue(
    Parse*,Index*,UnpackedRecord**,Expr*,int,int,int*);
int sqlite3Stat4ValueFromExpr(Parse*, Expr*, u8, sqlite3_value**);
void sqlite3Stat4ProbeFree(UnpackedRecord*);
int sqlite3Stat4Column(sqlite3*, const void*, int, int, sqlite3_value**);
char sqlite3IndexColumnAffinity(sqlite3*, Index*, int);
#endif

/*
** The interface to the LEMON-generated parser
*/
void *sqlite3ParserAlloc(void*(*)(u64));
void sqlite3ParserFree(void*, void(*)(void*));

#if defined(SQLITE_ENABLE_DBSTAT_VTAB) || defined(SQLITE_TEST)
int sqlite3DbstatRegister(sqlite3*);
#endif

int sqlite3ExprVectorSize(Expr *pExpr);
int sqlite3ExprIsVector(Expr *pExpr);
Expr *sqlite3ExprVectorField(Expr*, int);

#endif /* SQLITEINT_H */

}

/*
** This function is used to allocate and populate UnpackedRecord 
** structures intended to be compared against sample index keys stored 
** in the sqlite_stat4 table.
**
** A single call to this function populates zero or more fields of the
** record starting with field iVal (fields are numbered from left to
** right starting with 0). A single field is populated if:
**
**  * (pExpr==0). In this case the value is assumed to be an SQL NULL,
**
**  * The expression is a bound variable, and this is a reprepare, or
**
**  * The sqlite3ValueFromExpr() function is able to extract a value 
**    from the expression (i.e. the expression is a literal value).
**
** Or, if pExpr is a TK_VECTOR, one field is populated for each of the
** vector components that match either of the two latter criteria listed
** above.
**
** Before any value is appended to the record, the affinity of the 
** corresponding column within index pIdx is applied to it. Before
** this function returns, output parameter *pnExtract is set to the
** number of values appended to the record.
**
** When this function is called, *ppRec must either point to an object
** allocated by an earlier call to this function, or must be NULL. If it
** is NULL and a value can be successfully extracted, a new UnpackedRecord
** is allocated (and *ppRec set to point to it) before returning.
**
** Unless an error is encountered, SQLITE_OK is returned. It is not an
** error if a value cannot be extracted from pExpr. If an error does
** occur, an SQLite error code is returned.
*/
int sqlite3Stat4ProbeSetValue(
  Parse *pParse,                  /* Parse context */
  Index *pIdx,                    /* Index being probed */
  UnpackedRecord **ppRec,         /* IN/OUT: Probe record */
  Expr *pExpr,                    /* The expression to extract a value from */
  int nElem,                      /* Maximum number of values to append */
  int iVal,                       /* Array element to populate */
  int *pnExtract                  /* OUT: Values appended to the record */
){
  int rc = SQLITE_OK;
  int nExtract = 0;

  if( pExpr==0 || pExpr->op!=TK_SELECT ){
    int i;
    struct ValueNewStat4Ctx alloc;

    alloc.pParse = pParse;
    alloc.pIdx = pIdx;
    alloc.ppRec = ppRec;

    for(i=0; i<nElem; i++){
      sqlite3_value *pVal = 0;
      Expr *pElem = (pExpr ? sqlite3ExprVectorField(pExpr, i) : 0);
      u8 aff = sqlite3IndexColumnAffinity(pParse->db, pIdx, iVal+i);
      alloc.iVal = iVal+i;
      rc = stat4ValueFromExpr(pParse, pElem, aff, &alloc, &pVal);
      if( !pVal ) break;
      nExtract++;
    }
  }


  *pnExtract = nExtract;
  return rc;
}

/*
** Attempt to extract a value from expression pExpr using the methods
** as described for sqlite3Stat4ProbeSetValue() above. 
**

}


#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
/*
** Return the affinity for a single column of an index.
*/
char sqlite3IndexColumnAffinity(sqlite3 *db, Index *pIdx, int iCol){
  assert( iCol>=0 && iCol<pIdx->nColumn );
  if( !pIdx->zColAff ){
    if( sqlite3IndexAffinityStr(db, pIdx)==0 ) return SQLITE_AFF_BLOB;
  }
  return pIdx->zColAff[iCol];
}
#endif

  Index *p = pLoop->u.btree.pIndex;
  int nEq = pLoop->u.btree.nEq;

  if( p->nSample>0 && nEq<p->nSampleCol ){
    if( nEq==pBuilder->nRecValid ){
      UnpackedRecord *pRec = pBuilder->pRec;
      tRowcnt a[2];
      int nBtm = pLoop->u.btree.nBtm;
      int nTop = pLoop->u.btree.nTop;

      /* Variable iLower will be set to the estimate of the number of rows in 
      ** the index that are less than the lower bound of the range query. The
      ** lower bound being the concatenation of $P and $L, where $P is the
      ** key-prefix formed by the nEq values matched against the nEq left-most
      ** columns of the index, and $L is the value in pLower.
      **

      int iLwrIdx = -2;   /* aSample[] for the lower bound */
      int iUprIdx = -1;   /* aSample[] for the upper bound */

      if( pRec ){
        testcase( pRec->nField!=pBuilder->nRecValid );
        pRec->nField = pBuilder->nRecValid;
      }


      /* Determine iLower and iUpper using ($P) only. */
      if( nEq==0 ){
        iLower = 0;
        iUpper = p->nRowEst0;
      }else{
        /* Note: this call could be optimized away - since the same values must 
        ** have been requested when testing key $P in whereEqualScanEst().  */
        whereKeyStats(pParse, p, pRec, 0, a);
        iLower = a[0];
        iUpper = a[0] + a[1];
      }

      assert( pLower==0 || (pLower->eOperator & (WO_GT|WO_GE))!=0 );
      assert( pUpper==0 || (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
      assert( p->aSortOrder!=0 );
      if( p->aSortOrder[nEq] ){
        /* The roles of pLower and pUpper are swapped for a DESC index */
        SWAP(WhereTerm*, pLower, pUpper);
        SWAP(int, nBtm, nTop);
      }

      /* If possible, improve on the iLower estimate using ($P:$L). */
      if( pLower ){
        int n;                    /* Values extracted from pExpr */
        Expr *pExpr = pLower->pExpr->pRight;
        rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, nBtm, nEq, &n);
        if( rc==SQLITE_OK && n ){
          tRowcnt iNew;
          u16 mask = WO_GT|WO_LE;
          if( sqlite3ExprVectorSize(pExpr)>n ) mask = (WO_LE|WO_LT);
          iLwrIdx = whereKeyStats(pParse, p, pRec, 0, a);
          iNew = a[0] + ((pLower->eOperator & mask) ? a[1] : 0);
          if( iNew>iLower ) iLower = iNew;
          nOut--;
          pLower = 0;
        }
      }

      /* If possible, improve on the iUpper estimate using ($P:$U). */
      if( pUpper ){
        int n;                    /* Values extracted from pExpr */
        Expr *pExpr = pUpper->pExpr->pRight;
        rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, nTop, nEq, &n);
        if( rc==SQLITE_OK && n ){
          tRowcnt iNew;
          u16 mask = WO_GT|WO_LE;
          if( sqlite3ExprVectorSize(pExpr)>n ) mask = (WO_LE|WO_LT);
          iUprIdx = whereKeyStats(pParse, p, pRec, 1, a);
          iNew = a[0] + ((pUpper->eOperator & mask) ? a[1] : 0);
          if( iNew<iUpper ) iUpper = iNew;
          nOut--;
          pUpper = 0;
        }
      }

      pBuilder->pRec = pRec;

  WhereLoopBuilder *pBuilder,
  Expr *pExpr,         /* Expression for VALUE in the x=VALUE constraint */
  tRowcnt *pnRow       /* Write the revised row estimate here */
){
  Index *p = pBuilder->pNew->u.btree.pIndex;
  int nEq = pBuilder->pNew->u.btree.nEq;
  UnpackedRecord *pRec = pBuilder->pRec;

  int rc;                   /* Subfunction return code */
  tRowcnt a[2];             /* Statistics */
  int bOk;

  assert( nEq>=1 );
  assert( nEq<=p->nColumn );
  assert( p->aSample!=0 );

  /* This is an optimization only. The call to sqlite3Stat4ProbeSetValue()
  ** below would return the same value.  */
  if( nEq>=p->nColumn ){
    *pnRow = 1;
    return SQLITE_OK;
  }


  rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, 1, nEq-1, &bOk);
  pBuilder->pRec = pRec;
  if( rc!=SQLITE_OK ) return rc;
  if( bOk==0 ) return SQLITE_NOTFOUND;
  pBuilder->nRecValid = nEq;

  whereKeyStats(pParse, p, pRec, 0, a);
  WHERETRACE(0x10,("equality scan regions %s(%d): %d\n",

    14 "(2, 1) IN (SELECT a, b FROM t2 ORDER BY d LIMIT 5 OFFSET 11)" 1
    15 "(2, 1) IN (SELECT a, b FROM t2 ORDER BY d LIMIT 5 OFFSET 12)" 0
  } {
    do_execsql_test 2.2.$nm.$tn "SELECT $e" $res
  }
}

ifcapable stat4 {
  do_execsql_test 3.0 {
    CREATE TABLE c1(a, b, c, d);
    INSERT INTO c1(a, b) VALUES(1, 'a');
    INSERT INTO c1(a, b) VALUES(1, 'b');
    INSERT INTO c1(a, b) VALUES(1, 'c');
    INSERT INTO c1(a, b) VALUES(1, 'd');
    INSERT INTO c1(a, b) VALUES(1, 'e');
    INSERT INTO c1(a, b) VALUES(1, 'f');
    INSERT INTO c1(a, b) VALUES(1, 'g');
    INSERT INTO c1(a, b) VALUES(1, 'h');
    INSERT INTO c1(a, b) VALUES(1, 'i');
    INSERT INTO c1(a, b) VALUES(1, 'j');
    INSERT INTO c1(a, b) VALUES(1, 'k');
    INSERT INTO c1(a, b) VALUES(1, 'l');
    INSERT INTO c1(a, b) VALUES(1, 'm');
    INSERT INTO c1(a, b) VALUES(1, 'n');
    INSERT INTO c1(a, b) VALUES(1, 'o');
    INSERT INTO c1(a, b) VALUES(1, 'p');
    INSERT INTO c1(a, b) VALUES(2, 'a');
    INSERT INTO c1(a, b) VALUES(2, 'b');
    INSERT INTO c1(a, b) VALUES(2, 'c');
    INSERT INTO c1(a, b) VALUES(2, 'd');
    INSERT INTO c1(a, b) VALUES(2, 'e');
    INSERT INTO c1(a, b) VALUES(2, 'f');
    INSERT INTO c1(a, b) VALUES(2, 'g');
    INSERT INTO c1(a, b) VALUES(2, 'h');

    INSERT INTO c1(c, d) SELECT a, b FROM c1;

    CREATE INDEX c1ab ON c1(a, b);
    CREATE INDEX c1cd ON c1(c, d);
    ANALYZE;
  }

  do_eqp_test 3.1.1 { SELECT * FROM c1 WHERE a=1 AND c=2 } {
    0 0 0 {SEARCH TABLE c1 USING INDEX c1cd (c=?)}
  }
  do_eqp_test 3.1.2 { SELECT * FROM c1 WHERE a=1 AND b>'d' AND c=2 } {
    0 0 0 {SEARCH TABLE c1 USING INDEX c1cd (c=?)}
  }
  do_eqp_test 3.1.3 { SELECT * FROM c1 WHERE a=1 AND b>'l' AND c=2 } {
    0 0 0 {SEARCH TABLE c1 USING INDEX c1ab (a=? AND b>?)}
  }

  do_eqp_test 3.2.1 { SELECT * FROM c1 WHERE a=1 AND c>1 } {
    0 0 0 {SEARCH TABLE c1 USING INDEX c1cd (c>?)}
  }
  do_eqp_test 3.2.2 { SELECT * FROM c1 WHERE a=1 AND c>0 } {
    0 0 0 {SEARCH TABLE c1 USING INDEX c1ab (a=?)}
  }
  do_eqp_test 3.2.3 { SELECT * FROM c1 WHERE a=1 AND c>=1 } {
    0 0 0 {SEARCH TABLE c1 USING INDEX c1ab (a=?)}
  }
  do_eqp_test 3.2.4 { SELECT * FROM c1 WHERE a=1 AND (c, d)>(1, 'c') } {
    0 0 0 {SEARCH TABLE c1 USING INDEX c1ab (a=?)}
  }
  do_eqp_test 3.2.5 { SELECT * FROM c1 WHERE a=1 AND (c, d)>(1, 'o') } {
    0 0 0 {SEARCH TABLE c1 USING INDEX c1cd (c>?)}
  }
  do_eqp_test 3.2.6 { SELECT * FROM c1 WHERE a=1 AND (c, +b)>(1, 'c') } {
    0 0 0 {SEARCH TABLE c1 USING INDEX c1ab (a=?)}
  }
}

finish_test