SQLite

      pInfo->aColl[i] = pColl;
      pInfo->aSortOrder[i] = pItem->sortOrder;
    }
  }
  return pInfo;
}

#ifndef SQLITE_OMIT_COMPOUND_SELECT
/*
** Name of the connection operator, used for error messages.
*/
static const char *selectOpName(int id){
  char *z;
  switch( id ){
    case TK_ALL:       z = "UNION ALL";   break;
    case TK_INTERSECT: z = "INTERSECT";   break;
    case TK_EXCEPT:    z = "EXCEPT";      break;
    default:           z = "UNION";       break;
  }
  return z;
}
#endif /* SQLITE_OMIT_COMPOUND_SELECT */

#ifndef SQLITE_OMIT_EXPLAIN
/*
** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
** is a no-op. Otherwise, it adds a single row of output to the EQP result,
** where the caption is of the form:
**
**   "USE TEMP B-TREE FOR xxx"
**
** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which
** is determined by the zUsage argument.
*/
static void explainTempTable(Parse *pParse, const char *zUsage){
  if( pParse->explain==2 ){
    Vdbe *v = pParse->pVdbe;
    char *zMsg = sqlite3MPrintf(pParse->db, "USE TEMP B-TREE FOR %s", zUsage);
    sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC);
  }
}

/*
** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
** is a no-op. Otherwise, it adds a single row of output to the EQP result,
** where the caption is of one of the two forms:
**
**   "COMPOSITE SUBQUERIES iSub1 and iSub2 (op)"
**   "COMPOSITE SUBQUERIES iSub1 and iSub2 USING TEMP B-TREE (op)"
**
** where iSub1 and iSub2 are the integers passed as the corresponding
** function parameters, and op is the text representation of the parameter
** of the same name. The parameter "op" must be one of TK_UNION, TK_EXCEPT,
** TK_INTERSECT or TK_ALL. The first form is used if argument bUseTmp is 
** false, or the second form if it is true.
*/
static void explainComposite(
  Parse *pParse,                  /* Parse context */
  int op,                         /* One of TK_UNION, TK_EXCEPT etc. */
  int iSub1,                      /* Subquery id 1 */
  int iSub2,                      /* Subquery id 2 */
  int bUseTmp                     /* True if a temp table was used */
){
  assert( op==TK_UNION || op==TK_EXCEPT || op==TK_INTERSECT || op==TK_ALL );
  if( pParse->explain==2 ){
    Vdbe *v = pParse->pVdbe;
    char *zMsg = sqlite3MPrintf(
        pParse->db, "COMPOSITE SUBQUERIES %d AND %d %s(%s)", iSub1, iSub2,
        bUseTmp?"USING TEMP B-TREE ":"", selectOpName(op)
    );
    sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC);
  }
}

/*
** Assign expression b to lvalue a. A second, no-op, version of this macro
** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code
** in sqlite3Select() to assign values to structure member variables that
** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the
** code with #ifndef directives.
*/
# define explainSetInteger(a, b) a = b

#else
/* No-op versions of the explainXXX() functions and macros. */
# define explainTempTable(y,z)
# define explainComposite(v,w,x,y,z)
# define explainSetInteger(y,z)
#endif

/*
** If the inner loop was generated using a non-null pOrderBy argument,
** then the results were placed in a sorter.  After the loop is terminated
** we need to run the sorter and output the results.  The following

      sqlite3VdbeSetColName(v, i, COLNAME_NAME, 
          sqlite3DbStrDup(db, pEList->a[i].zSpan), SQLITE_DYNAMIC);
    }
  }
  generateColumnTypes(pParse, pTabList, pEList);
}

#ifndef SQLITE_OMIT_COMPOUND_SELECT
/*
** Name of the connection operator, used for error messages.
*/
static const char *selectOpName(int id){
  char *z;
  switch( id ){
    case TK_ALL:       z = "UNION ALL";   break;
    case TK_INTERSECT: z = "INTERSECT";   break;
    case TK_EXCEPT:    z = "EXCEPT";      break;
    default:           z = "UNION";       break;
  }
  return z;
}
#endif /* SQLITE_OMIT_COMPOUND_SELECT */

/*
** Given a an expression list (which is really the list of expressions
** that form the result set of a SELECT statement) compute appropriate
** column names for a table that would hold the expression list.
**
** All column names will be unique.
**

){
  int rc = SQLITE_OK;   /* Success code from a subroutine */
  Select *pPrior;       /* Another SELECT immediately to our left */
  Vdbe *v;              /* Generate code to this VDBE */
  SelectDest dest;      /* Alternative data destination */
  Select *pDelete = 0;  /* Chain of simple selects to delete */
  sqlite3 *db;          /* Database connection */
#ifndef SQLITE_OMIT_EXPLAIN
  int iSub1;            /* EQP id of left-hand query */
  int iSub2;            /* EQP id of right-hand query */
#endif

  /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs.  Only
  ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
  */
  assert( p && p->pPrior );  /* Calling function guarantees this much */
  db = pParse->db;
  pPrior = p->pPrior;

  */
  switch( p->op ){
    case TK_ALL: {
      int addr = 0;
      assert( !pPrior->pLimit );
      pPrior->pLimit = p->pLimit;
      pPrior->pOffset = p->pOffset;
      explainSetInteger(iSub1, pParse->iNextSelectId);
      rc = sqlite3Select(pParse, pPrior, &dest);
      p->pLimit = 0;
      p->pOffset = 0;
      if( rc ){
        goto multi_select_end;
      }
      p->pPrior = 0;
      p->iLimit = pPrior->iLimit;
      p->iOffset = pPrior->iOffset;
      if( p->iLimit ){
        addr = sqlite3VdbeAddOp1(v, OP_IfZero, p->iLimit);
        VdbeComment((v, "Jump ahead if LIMIT reached"));
      }
      explainSetInteger(iSub2, pParse->iNextSelectId);
      rc = sqlite3Select(pParse, p, &dest);
      testcase( rc!=SQLITE_OK );
      pDelete = p->pPrior;
      p->pPrior = pPrior;
      if( addr ){
        sqlite3VdbeJumpHere(v, addr);
      }

        assert( p->pEList );
      }

      /* Code the SELECT statements to our left
      */
      assert( !pPrior->pOrderBy );
      sqlite3SelectDestInit(&uniondest, priorOp, unionTab);
      explainSetInteger(iSub1, pParse->iNextSelectId);
      rc = sqlite3Select(pParse, pPrior, &uniondest);
      if( rc ){
        goto multi_select_end;
      }

      /* Code the current SELECT statement
      */
      if( p->op==TK_EXCEPT ){
        op = SRT_Except;
      }else{
        assert( p->op==TK_UNION );
        op = SRT_Union;
      }
      p->pPrior = 0;
      pLimit = p->pLimit;
      p->pLimit = 0;
      pOffset = p->pOffset;
      p->pOffset = 0;
      uniondest.eDest = op;
      explainSetInteger(iSub2, pParse->iNextSelectId);
      rc = sqlite3Select(pParse, p, &uniondest);
      testcase( rc!=SQLITE_OK );
      /* Query flattening in sqlite3Select() might refill p->pOrderBy.
      ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */
      sqlite3ExprListDelete(db, p->pOrderBy);
      pDelete = p->pPrior;
      p->pPrior = pPrior;

      p->addrOpenEphm[0] = addr;
      p->pRightmost->selFlags |= SF_UsesEphemeral;
      assert( p->pEList );

      /* Code the SELECTs to our left into temporary table "tab1".
      */
      sqlite3SelectDestInit(&intersectdest, SRT_Union, tab1);
      explainSetInteger(iSub1, pParse->iNextSelectId);
      rc = sqlite3Select(pParse, pPrior, &intersectdest);
      if( rc ){
        goto multi_select_end;
      }

      /* Code the current SELECT into temporary table "tab2"
      */
      addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tab2, 0);
      assert( p->addrOpenEphm[1] == -1 );
      p->addrOpenEphm[1] = addr;
      p->pPrior = 0;
      pLimit = p->pLimit;
      p->pLimit = 0;
      pOffset = p->pOffset;
      p->pOffset = 0;
      intersectdest.iParm = tab2;
      explainSetInteger(iSub2, pParse->iNextSelectId);
      rc = sqlite3Select(pParse, p, &intersectdest);
      testcase( rc!=SQLITE_OK );
      pDelete = p->pPrior;
      p->pPrior = pPrior;
      sqlite3ExprDelete(db, p->pLimit);
      p->pLimit = pLimit;
      p->pOffset = pOffset;

      sqlite3VdbeAddOp2(v, OP_Next, tab1, iStart);
      sqlite3VdbeResolveLabel(v, iBreak);
      sqlite3VdbeAddOp2(v, OP_Close, tab2, 0);
      sqlite3VdbeAddOp2(v, OP_Close, tab1, 0);
      break;
    }
  }

  explainComposite(pParse, p->op, iSub1, iSub2, p->op!=TK_ALL);

  /* Compute collating sequences used by 
  ** temporary tables needed to implement the compound select.
  ** Attach the KeyInfo structure to all temporary tables.
  **
  ** This section is run by the right-most SELECT statement only.
  ** SELECT statements to the left always skip this part.  The right-most

  int op;               /* One of TK_ALL, TK_UNION, TK_EXCEPT, TK_INTERSECT */
  KeyInfo *pKeyDup = 0; /* Comparison information for duplicate removal */
  KeyInfo *pKeyMerge;   /* Comparison information for merging rows */
  sqlite3 *db;          /* Database connection */
  ExprList *pOrderBy;   /* The ORDER BY clause */
  int nOrderBy;         /* Number of terms in the ORDER BY clause */
  int *aPermute;        /* Mapping from ORDER BY terms to result set columns */
#ifndef SQLITE_OMIT_EXPLAIN
  int iSub1;            /* EQP id of left-hand query */
  int iSub2;            /* EQP id of right-hand query */
#endif

  assert( p->pOrderBy!=0 );
  assert( pKeyDup==0 ); /* "Managed" code needs this.  Ticket #3382. */
  db = pParse->db;
  v = pParse->pVdbe;
  assert( v!=0 );       /* Already thrown the error if VDBE alloc failed */
  labelEnd = sqlite3VdbeMakeLabel(v);

  /* Generate a coroutine to evaluate the SELECT statement to the
  ** left of the compound operator - the "A" select.
  */
  VdbeNoopComment((v, "Begin coroutine for left SELECT"));
  pPrior->iLimit = regLimitA;
  explainSetInteger(iSub1, pParse->iNextSelectId);
  sqlite3Select(pParse, pPrior, &destA);
  sqlite3VdbeAddOp2(v, OP_Integer, 1, regEofA);
  sqlite3VdbeAddOp1(v, OP_Yield, regAddrA);
  VdbeNoopComment((v, "End coroutine for left SELECT"));

  /* Generate a coroutine to evaluate the SELECT statement on 
  ** the right - the "B" select
  */
  addrSelectB = sqlite3VdbeCurrentAddr(v);
  VdbeNoopComment((v, "Begin coroutine for right SELECT"));
  savedLimit = p->iLimit;
  savedOffset = p->iOffset;
  p->iLimit = regLimitB;
  p->iOffset = 0;  
  explainSetInteger(iSub2, pParse->iNextSelectId);
  sqlite3Select(pParse, p, &destB);
  p->iLimit = savedLimit;
  p->iOffset = savedOffset;
  sqlite3VdbeAddOp2(v, OP_Integer, 1, regEofB);
  sqlite3VdbeAddOp1(v, OP_Yield, regAddrB);
  VdbeNoopComment((v, "End coroutine for right SELECT"));

  if( p->pPrior ){
    sqlite3SelectDelete(db, p->pPrior);
  }
  p->pPrior = pPrior;

  /*** TBD:  Insert subroutine calls to close cursors on incomplete
  **** subqueries ****/
  explainComposite(pParse, p->op, iSub1, iSub2, 0);
  return SQLITE_OK;
}
#endif

#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
/* Forward Declarations */
static void substExprList(sqlite3*, ExprList*, int, ExprList*);

      }
      mxSelect = db->aLimit[SQLITE_LIMIT_COMPOUND_SELECT];
      if( mxSelect && cnt>mxSelect ){
        sqlite3ErrorMsg(pParse, "too many terms in compound SELECT");
        goto select_end;
      }
    }
    rc = multiSelect(pParse, p, pDest);
    explainSetInteger(pParse->iSelectId, iRestoreSelectId);
    return multiSelect(pParse, p, pDest);
    return rc;
  }
#endif

  /* If possible, rewrite the query to use GROUP BY instead of DISTINCT.
  ** GROUP BY might use an index, DISTINCT never does.
  */
  assert( p->pGroupBy==0 || (p->selFlags & SF_Aggregate)!=0 );

# eqp-1.*:        Assorted tests.
# eqp-2.*:        Tests for single select statements.
# eqp-3.*:        Select statements that execute sub-selects.
# eqp-4.*:        Compound select statements.
#

proc do_eqp_test {name sql res} {
  set res [list {*}$res]
  uplevel do_execsql_test $name [list "EXPLAIN QUERY PLAN $sql"] [list $res]
}
proc det {args} { uplevel do_eqp_test $args }

do_execsql_test 1.1 {
  CREATE TABLE t1(a, b);
  CREATE INDEX i1 ON t1(a);

# Test cases eqp-4.* - tests for composite select statements.
#
do_eqp_test 4.1.1 {
  SELECT * FROM t1 UNION ALL SELECT * FROM t2
} {
  1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  2 0 0 {SCAN TABLE t2 (~1000000 rows)} 
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 2 (UNION ALL)} 
}
do_eqp_test 4.1.2 {
  SELECT * FROM t1 UNION ALL SELECT * FROM t2 ORDER BY 2
} {
  1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  1 0 0 {USE TEMP B-TREE FOR ORDER BY}
  2 0 0 {SCAN TABLE t2 (~1000000 rows)} 
  2 0 0 {USE TEMP B-TREE FOR ORDER BY}
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 2 (UNION ALL)} 
}
do_eqp_test 4.1.3 {
  SELECT * FROM t1 UNION SELECT * FROM t2 ORDER BY 2
} {
  1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  1 0 0 {USE TEMP B-TREE FOR ORDER BY}
  2 0 0 {SCAN TABLE t2 (~1000000 rows)} 
  2 0 0 {USE TEMP B-TREE FOR ORDER BY}
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 2 (UNION)} 
}
do_eqp_test 4.1.4 {
  SELECT * FROM t1 INTERSECT SELECT * FROM t2 ORDER BY 2
} {
  1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  1 0 0 {USE TEMP B-TREE FOR ORDER BY}
  2 0 0 {SCAN TABLE t2 (~1000000 rows)} 
  2 0 0 {USE TEMP B-TREE FOR ORDER BY}
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 2 (INTERSECT)} 
}
do_eqp_test 4.1.5 {
  SELECT * FROM t1 EXCEPT SELECT * FROM t2 ORDER BY 2
} {
  1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  1 0 0 {USE TEMP B-TREE FOR ORDER BY}
  2 0 0 {SCAN TABLE t2 (~1000000 rows)} 
  2 0 0 {USE TEMP B-TREE FOR ORDER BY}
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 2 (EXCEPT)} 
}

do_eqp_test 4.2.2 {
  SELECT * FROM t1 UNION ALL SELECT * FROM t2 ORDER BY 1
} {
  1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  1 0 0 {USE TEMP B-TREE FOR ORDER BY}
  2 0 0 {SCAN TABLE t2 BY INDEX t2i1 (~1000000 rows)} 
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 2 (UNION ALL)} 
}
do_eqp_test 4.2.3 {
  SELECT * FROM t1 UNION SELECT * FROM t2 ORDER BY 1
} {
  1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  1 0 0 {USE TEMP B-TREE FOR ORDER BY}
  2 0 0 {SCAN TABLE t2 (~1000000 rows)} 
  2 0 0 {USE TEMP B-TREE FOR ORDER BY}
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 2 (UNION)} 
}
do_eqp_test 4.2.4 {
  SELECT * FROM t1 INTERSECT SELECT * FROM t2 ORDER BY 1
} {
  1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  1 0 0 {USE TEMP B-TREE FOR ORDER BY}
  2 0 0 {SCAN TABLE t2 (~1000000 rows)} 
  2 0 0 {USE TEMP B-TREE FOR ORDER BY}
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 2 (INTERSECT)} 
}
do_eqp_test 4.2.5 {
  SELECT * FROM t1 EXCEPT SELECT * FROM t2 ORDER BY 1
} {
  1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  1 0 0 {USE TEMP B-TREE FOR ORDER BY}
  2 0 0 {SCAN TABLE t2 (~1000000 rows)} 
  2 0 0 {USE TEMP B-TREE FOR ORDER BY}
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 2 (EXCEPT)} 
}

do_eqp_test 4.3.1 {
  SELECT x FROM t1 UNION SELECT x FROM t2
} {
  1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  2 0 0 {SCAN TABLE t2 (~1000000 rows)} 
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 2 USING TEMP B-TREE (UNION)} 
}

do_eqp_test 4.3.2 {
  SELECT x FROM t1 UNION SELECT x FROM t2 UNION SELECT x FROM t1
} {
  2 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  3 0 0 {SCAN TABLE t2 (~1000000 rows)} 
  1 0 0 {COMPOSITE SUBQUERIES 2 AND 3 USING TEMP B-TREE (UNION)}
  4 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 4 USING TEMP B-TREE (UNION)}
}
do_eqp_test 4.3.3 {
  SELECT x FROM t1 UNION SELECT x FROM t2 UNION SELECT x FROM t1 ORDER BY 1
} {
  2 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  2 0 0 {USE TEMP B-TREE FOR ORDER BY} 
  3 0 0 {SCAN TABLE t2 BY COVERING INDEX t2i1 (~1000000 rows)} 
  1 0 0 {COMPOSITE SUBQUERIES 2 AND 3 (UNION)} 
  4 0 0 {SCAN TABLE t1 (~1000000 rows)} 
  4 0 0 {USE TEMP B-TREE FOR ORDER BY} 
  0 0 0 {COMPOSITE SUBQUERIES 1 AND 4 (UNION)}
}

finish_test