SQLite

  /* Compute the comparison permutation and keyinfo that is used with
  ** the permutation used to determine if the next
  ** row of results comes from selectA or selectB.  Also add explicit
  ** collations to the ORDER BY clause terms so that when the subqueries
  ** to the right and the left are evaluated, they use the correct
  ** collation.
  */
  aPermute = sqlite3DbMallocRaw(db, sizeof(int)*(nOrderBy + 1));
  if( aPermute ){
    struct ExprList_item *pItem;
    aPermute[0] = nOrderBy;
    for(i=1, pItem=pOrderBy->a; i<=nOrderBy; i++, pItem++){
      assert( pItem->u.x.iOrderByCol>0
          && pItem->u.x.iOrderByCol<=p->pEList->nExpr );
      aPermute[i] = pItem->u.x.iOrderByCol - 1;
    }
    pKeyMerge = multiSelectOrderByKeyInfo(pParse, p, 1);
  }else{
    pKeyMerge = 0;

**
** Set the permutation used by the OP_Compare operator to be the array
** of integers in P4.
**
** The permutation is only valid until the next OP_Compare that has
** the OPFLAG_PERMUTE bit set in P5. Typically the OP_Permutation should 
** occur immediately prior to the OP_Compare.
**
** The first integer in the P4 integer array is the length of the array
** and does not become part of the permutation.
*/
case OP_Permutation: {
  assert( pOp->p4type==P4_INTARRAY );
  assert( pOp->p4.ai );
  aPermute = pOp->p4.ai + 1;
  break;
}

/* Opcode: Compare P1 P2 P3 P4 P5
** Synopsis: r[P1@P3] <-> r[P2@P3]
**
** Compare two vectors of registers in reg(P1)..reg(P1+P3-1) (call this

  u32 offset;        /* Offset into the data */
  u32 szField;       /* Number of bytes in the content of a field */
  u32 avail;         /* Number of bytes of available data */
  u32 t;             /* A type code from the record header */
  u16 fx;            /* pDest->flags value */
  Mem *pReg;         /* PseudoTable input register */

  pC = p->apCsr[pOp->p1];
  p2 = pOp->p2;

  /* If the cursor cache is stale, bring it up-to-date */
  rc = sqlite3VdbeCursorMoveto(&pC, &p2);

  assert( pOp->p3>0 && pOp->p3<=(p->nMem-p->nCursor) );
  pDest = &aMem[pOp->p3];
  memAboutToChange(p, pDest);
  assert( pOp->p1>=0 && pOp->p1<p->nCursor );

  assert( pC!=0 );
  assert( p2<pC->nField );
  aOffset = pC->aOffset;
#ifndef SQLITE_OMIT_VIRTUALTABLE
  assert( pC->pVtabCursor==0 ); /* OP_Column never called on virtual table */
#endif
  pCrsr = pC->pCursor;
  assert( pCrsr!=0 || pC->pseudoTableReg>0 ); /* pCrsr NULL on PseudoTables */
  assert( pCrsr!=0 || pC->nullRow );          /* pC->nullRow on PseudoTables */



  if( rc ) goto abort_due_to_error;
  if( pC->cacheStatus!=p->cacheCtr ){
    if( pC->nullRow ){
      if( pCrsr==0 ){
        assert( pC->pseudoTableReg>0 );
        pReg = &aMem[pC->pseudoTableReg];
        assert( pReg->flags & MEM_Blob );

  VdbeBranchTaken(res!=0,2);
  if( res ){
    pc = pOp->p2 - 1;
  }
  break;
}

/* Opcode: Seek P1 P2 P3 P4 *
** Synopsis:  intkey=r[P2]
**
** P1 is an open table cursor and P2 is a rowid integer.  Arrange
** for P1 to move so that it points to the rowid given by P2.
**
** This is actually a deferred seek.  Nothing actually happens until
** the cursor is used to read a record.  That way, if no reads
** occur, no unnecessary I/O happens.
**
** P4 may contain an array of integers (type P4_INTARRAY) containing
** one entry for each column in the table P1 is open on. If so, then
** parameter P3 is a cursor open on a database index. If array entry
** a[i] is non-zero, then reading column (a[i]-1) from cursor P3 is 
** equivalent to performing the deferred seek and then reading column i 
** from P1.
*/
case OP_Seek: {    /* in2 */
  VdbeCursor *pC;

  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
  assert( pC->pCursor!=0 );
  assert( pC->isTable );
  pC->nullRow = 0;
  pIn2 = &aMem[pOp->p2];
  pC->movetoTarget = sqlite3VdbeIntValue(pIn2);
  pC->deferredMoveto = 1;
  assert( pOp->p4type==P4_INTARRAY || pOp->p4.ai==0 );
  pC->aAltMap = pOp->p4.ai;
  pC->pAltCursor = p->apCsr[pOp->p3];
  break;
}
  

/* Opcode: Found P1 P2 P3 P4 *
** Synopsis: key=r[P3@P4]
**

**
** Cursors can also point to virtual tables, sorters, or "pseudo-tables".
** A pseudo-table is a single-row table implemented by registers.
** 
** Every cursor that the virtual machine has open is represented by an
** instance of the following structure.
*/
typedef struct VdbeCursor VdbeCursor;
struct VdbeCursor {
  BtCursor *pCursor;    /* The cursor structure of the backend */
  Btree *pBt;           /* Separate file holding temporary table */
  KeyInfo *pKeyInfo;    /* Info about index keys needed by index cursors */
  int seekResult;       /* Result of previous sqlite3BtreeMoveto() */
  int pseudoTableReg;   /* Register holding pseudotable content. */
  i16 nField;           /* Number of fields in the header */

  Bool isTable:1;       /* True if a table requiring integer keys */
  Bool isOrdered:1;     /* True if the underlying table is BTREE_UNORDERED */
  Pgno pgnoRoot;        /* Root page of the open btree cursor */
  sqlite3_vtab_cursor *pVtabCursor;  /* The cursor for a virtual table */
  i64 seqCount;         /* Sequence counter */
  i64 movetoTarget;     /* Argument to the deferred sqlite3BtreeMoveto() */
  VdbeSorter *pSorter;  /* Sorter object for OP_SorterOpen cursors */
  VdbeCursor *pAltCursor; /* Associated index cursor from which to read */
  int *aAltMap;           /* Mapping from table to index column numbers */
#ifdef SQLITE_ENABLE_COLUMN_USED_MASK
  u64 maskUsed;         /* Mask of columns used by this cursor */
#endif

  /* Cached information about the header for the data record that the
  ** cursor is currently pointing to.  Only valid if cacheStatus matches
  ** Vdbe.cacheCtr.  Vdbe.cacheCtr will never take on the value of
  ** CACHE_STALE and so setting cacheStatus=CACHE_STALE guarantees that
  ** the cache is out of date.
  **

  const u8 *aRow;       /* Data for the current row, if all on one page */
  u32 *aOffset;         /* Pointer to aType[nField] */
  u32 aType[1];         /* Type values for all entries in the record */
  /* 2*nField extra array elements allocated for aType[], beyond the one
  ** static element declared in the structure.  nField total array slots for
  ** aType[] and nField+1 array slots for aOffset[] */
};


/*
** When a sub-program is executed (OP_Program), a structure of this type
** is allocated to store the current value of the program counter, as
** well as the current memory cell array and various other frame specific
** values stored in the Vdbe struct. When the sub-program is finished, 
** these values are copied back to the Vdbe from the VdbeFrame structure,

#define VDBE_MAGIC_DEAD     0xb606c3c8    /* The VDBE has been deallocated */

/*
** Function prototypes
*/
void sqlite3VdbeFreeCursor(Vdbe *, VdbeCursor*);
void sqliteVdbePopStack(Vdbe*,int);
int sqlite3VdbeCursorMoveto(VdbeCursor**, int*);
int sqlite3VdbeCursorRestore(VdbeCursor*);
#if defined(SQLITE_DEBUG) || defined(VDBE_PROFILE)
void sqlite3VdbePrintOp(FILE*, int, Op*);
#endif
u32 sqlite3VdbeSerialTypeLen(u32);
u32 sqlite3VdbeSerialType(Mem*, int);
u32 sqlite3VdbeSerialPut(unsigned char*, Mem*, u32);

    case P4_VTAB: {
      sqlite3_vtab *pVtab = pOp->p4.pVtab->pVtab;
      sqlite3_snprintf(nTemp, zTemp, "vtab:%p", pVtab);
      break;
    }
#endif
    case P4_INTARRAY: {
      int i, j;
      int *ai = pOp->p4.ai;
      int n = ai[0];   /* The first element of an INTARRAY is always the
                       ** count of the number of elements to follow */
      zTemp[0] = '[';
      for(i=j=1; i<n && j<nTemp-7; i++){
        if( j>1 ) zTemp[j++] = ',';
        sqlite3_snprintf(nTemp-j, zTemp+j, "%d", ai[i]);
        j += sqlite3Strlen30(zTemp+j);
      }
      if( i<n ){
        memcpy(zTemp+j, ",...]", 6);
      }else{
        memcpy(zTemp+j, "]", 2);
      }
      break;
    }
    case P4_SUBPROGRAM: {
      sqlite3_snprintf(nTemp, zTemp, "program");
      break;
    }
    case P4_ADVANCE: {

** MoveTo now.  If no move is pending, check to see if the row has been
** deleted out from under the cursor and if it has, mark the row as
** a NULL row.
**
** If the cursor is already pointing to the correct row and that row has
** not been deleted out from under the cursor, then this routine is a no-op.
*/
int sqlite3VdbeCursorMoveto(VdbeCursor **pp, int *piCol){
  VdbeCursor *p = *pp;
  if( p->deferredMoveto ){
    int iMap;
    if( p->aAltMap && (iMap = p->aAltMap[1+*piCol])>0 ){
      *pp = p->pAltCursor;
      *piCol = iMap - 1;
      return SQLITE_OK;
    }
    return handleDeferredMoveto(p);
  }
  if( p->pCursor && sqlite3BtreeCursorHasMoved(p->pCursor) ){
    return handleMovedCursor(p);
  }
  return SQLITE_OK;
}

    assert( pOp!=0 );
    assert( pOp->opcode==OP_String8 
            || pTerm->pWC->pWInfo->pParse->db->mallocFailed );
    pOp->p3 = pLevel->iLikeRepCntr;
    pOp->p5 = 1;
  }
}

/*
** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains
** a rowid value just read from cursor iIdxCur, open on index pIdx. This
** function generates code to do a deferred seek of cursor iCur to the 
** rowid stored in register iRowid.
**
** Normally, this is just:
**
**   OP_Seek $iCur $iRowid
**
** However, if the scan currently being coded is a branch of an OR-loop and
** the statement currently being coded is a SELECT, then P3 of the OP_Seek
** is set to iIdxCur and P4 is set to point to an array of integers
** containing one entry for each column of the table cursor iCur is open 
** on. For each table column, if the column is the i'th column of the 
** index, then the corresponding array entry is set to (i+1). If the column
** does not appear in the index at all, the array entry is set to 0.
*/
static void codeDeferredSeek(
  WhereInfo *pWInfo,              /* Where clause context */
  Index *pIdx,                    /* Index scan is using */
  int iCur,                       /* Cursor for IPK b-tree */
  int iRowid,                     /* Register containing rowid to seek to */
  int iIdxCur                     /* Index cursor */
){
  Parse *pParse = pWInfo->pParse; /* Parse context */
  Vdbe *v = pParse->pVdbe;        /* Vdbe to generate code within */

  assert( iIdxCur>0 );
  assert( pIdx->aiColumn[pIdx->nColumn-1]==-1 );
  
  sqlite3VdbeAddOp3(v, OP_Seek, iCur, iRowid, iIdxCur);
  if( (pWInfo->wctrlFlags & WHERE_FORCE_TABLE)
   && sqlite3ParseToplevel(pParse)->writeMask==0 
  ){
    int i;
    Table *pTab = pIdx->pTable;
    int *ai = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*(pTab->nCol+1));
    if( ai ){
      ai[0] = pTab->nCol;
      for(i=0; i<pIdx->nColumn-1; i++){
        assert( pIdx->aiColumn[i]<pTab->nCol );
        if( pIdx->aiColumn[i]>=0 ) ai[pIdx->aiColumn[i]+1] = i+1;
      }
      sqlite3VdbeChangeP4(v, -1, (char*)ai, P4_INTARRAY);
    }
  }
}

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

    disableTerm(pLevel, pRangeEnd);
    if( omitTable ){
      /* pIdx is a covering index.  No need to access the main table. */
    }else if( HasRowid(pIdx->pTable) ){
      iRowidReg = ++pParse->nMem;
      sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg);
      sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
      codeDeferredSeek(pWInfo, pIdx, iCur, iRowidReg, iIdxCur);
    }else if( iCur!=iIdxCur ){
      Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable);
      iRowidReg = sqlite3GetTempRange(pParse, pPk->nKeyCol);
      for(j=0; j<pPk->nKeyCol; j++){
        k = sqlite3ColumnOfIndex(pIdx, pPk->aiColumn[j]);
        sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, k, iRowidReg+j);
      }

  SELECT a, b FROM t3 WHERE 
        (a=2 AND b=(SELECT y FROM t4 WHERE x='b')) 
     OR (a=1 AND b=(SELECT y FROM t4 WHERE x='a')) 
} {2 two 1 one search 6}

do_searchcount_test 3.5.1 {
  SELECT a, b FROM t3 WHERE (a=1 AND b='one') OR rowid=4
} {1 one 2 two search 1}
do_searchcount_test 3.5.2 {
  SELECT a, c FROM t3 WHERE (a=1 AND b='one') OR rowid=4
} {1 i 2 ii search 2}

# Ticket [d02e1406a58ea02d] (2012-10-04)
# LEFT JOIN with an OR in the ON clause causes segfault 
#

    c0=1 or  c1=1 or  c2=1 or  c3=1 or
    c4=1 or  c5=1 or  c6=1 or  c7=1 or
    c8=1 or  c9=1 or c10=1 or c11=1 or
    c12=1 or c13=1 or c14=1 or c15=1 or
    c16=1 or c17=1;
} {1 {} {} {} {} {} {} {} {} {} {} {} {} {} {} 1 {} {}}

#-------------------------------------------------------------------------
#-------------------------------------------------------------------------
do_execsql_test 6.1 {
  CREATE TABLE x1(a, b, c, d, e);
  CREATE INDEX x1a  ON x1(a);
  CREATE INDEX x1bc ON x1(b, c);
  CREATE INDEX x1cd ON x1(c, d);

  INSERT INTO x1 VALUES(1, 2, 3, 4, 'A');
  INSERT INTO x1 VALUES(5, 6, 7, 8, 'B');
  INSERT INTO x1 VALUES(9, 10, 11, 12, 'C');
  INSERT INTO x1 VALUES(13, 14, 15, 16, 'D');
}

do_searchcount_test 6.2.1 {
  SELECT e FROM x1 WHERE b=2 OR c=7;
} {A B search 6}
do_searchcount_test 6.2.2 {
  SELECT c FROM x1 WHERE b=2 OR c=7;
} {3 7 search 4}

do_searchcount_test 6.3.1 {
  SELECT e FROM x1 WHERE a=1 OR b=10;
} {A C search 6}
do_searchcount_test 6.3.2 {
  SELECT c FROM x1 WHERE a=1 OR b=10;
} {3 11 search 5}
do_searchcount_test 6.3.3 {
  SELECT rowid FROM x1 WHERE a=1 OR b=10;
} {1 3 search 4}

do_searchcount_test 6.4.1 {
  SELECT a FROM x1 WHERE b BETWEEN 1 AND 4 OR c BETWEEN 8 AND 12
} {1 9 search 6}
do_searchcount_test 6.4.2 {
  SELECT b, c FROM x1 WHERE b BETWEEN 1 AND 4 OR c BETWEEN 8 AND 12
} {2 3 10 11 search 5}
do_searchcount_test 6.4.3 {
  SELECT rowid, c FROM x1 WHERE b BETWEEN 1 AND 4 OR c BETWEEN 8 AND 12
} {1 3 3 11 search 4}

db eval {
  WITH RECURSIVE c(x) AS (VALUES(1000) UNION ALL SELECT x+1 FROM c WHERE x<2000)
  INSERT INTO x1(rowid,a,b,c,d,e) SELECT x,x,x,x,x,x FROM c;
}

do_searchcount_test 6.5.1 {
  SELECT a FROM x1 WHERE rowid = 2 OR c=11
} {5 9 search 3}
do_searchcount_test 6.5.2 {
  SELECT d FROM x1 WHERE rowid = 2 OR c=11
} {8 12 search 2}
do_searchcount_test 6.5.3 {
  SELECT d FROM x1 WHERE c=11 OR rowid = 2
} {12 8 search 2}
do_searchcount_test 6.5.4 {
  SELECT a FROM x1 WHERE c=11 OR rowid = 2 
} {9 5 search 3}

do_searchcount_test 6.6.1 {
  SELECT rowid FROM x1 WHERE a=1 OR b=6 OR c=11
} {1 2 3 search 6}
do_searchcount_test 6.6.2 {
  SELECT c FROM x1 WHERE a=1 OR b=6 OR c=11
} {3 7 11 search 7}
do_searchcount_test 6.6.3 {
  SELECT c FROM x1 WHERE c=11 OR a=1 OR b=6 
} {11 3 7 search 7}
do_searchcount_test 6.6.4 {
  SELECT c FROM x1 WHERE b=6 OR c=11 OR a=1
} {7 11 3 search 7}

finish_test