SQLite

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.95 2002/06/20 03:38:26 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/

*/
static void sqliteAggregateInfoReset(Parse *pParse){
  sqliteFree(pParse->aAgg);
  pParse->aAgg = 0;
  pParse->nAgg = 0;
  pParse->useAgg = 0;
}

/*
** Insert code into "v" that will push the record on the top of the
** stack into the sorter.
*/
static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){
  char *zSortOrder;
  int i;
  zSortOrder = sqliteMalloc( pOrderBy->nExpr + 1 );
  if( zSortOrder==0 ) return;
  for(i=0; i<pOrderBy->nExpr; i++){
    zSortOrder[i] = pOrderBy->a[i].sortOrder ? '-' : '+';
    sqliteExprCode(pParse, pOrderBy->a[i].pExpr);
  }
  zSortOrder[pOrderBy->nExpr] = 0;
  sqliteVdbeAddOp(v, OP_SortMakeKey, pOrderBy->nExpr, 0);
  sqliteVdbeChangeP3(v, -1, zSortOrder, strlen(zSortOrder));
  sqliteFree(zSortOrder);
  sqliteVdbeAddOp(v, OP_SortPut, 0, 0);
}

/*
** This routine generates the code for the inside of the inner loop
** of a SELECT.
**
** The pEList is used to determine the values for each column in the
** result row.  Except  if pEList==NULL, then we just read nColumn

    sqliteVdbeAddOp(v, OP_Distinct, distinct, sqliteVdbeCurrentAddr(v)+3);
    sqliteVdbeAddOp(v, OP_Pop, pEList->nExpr+1, 0);
    sqliteVdbeAddOp(v, OP_Goto, 0, iContinue);
    sqliteVdbeAddOp(v, OP_String, 0, 0);
    sqliteVdbeAddOp(v, OP_PutStrKey, distinct, 0);
  }



















  switch( eDest ){
    /* In this mode, write each query result to the key of the temporary
    ** table iParm.
    */
    case SRT_Union: {
      sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, NULL_ALWAYS_DISTINCT);
      sqliteVdbeAddOp(v, OP_String, 0, 0);
      sqliteVdbeAddOp(v, OP_PutStrKey, iParm, 0);
      break;
    }

    /* Store the result as data using a unique key.
    */
    case SRT_Table:
    case SRT_TempTable: {
      sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, 0);
      if( pOrderBy ){
        pushOntoSorter(pParse, v, pOrderBy);
      }else{
        sqliteVdbeAddOp(v, OP_NewRecno, iParm, 0);
        sqliteVdbeAddOp(v, OP_Pull, 1, 0);
        sqliteVdbeAddOp(v, OP_PutIntKey, iParm, 0);
      }
      break;
    }

    /* Construct a record from the query result, but instead of
    ** saving that record, use it as a key to delete elements from
    ** the temporary table iParm.
    */
    case SRT_Except: {
      int addr;
      addr = sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, NULL_ALWAYS_DISTINCT);
      sqliteVdbeAddOp(v, OP_NotFound, iParm, addr+3);
      sqliteVdbeAddOp(v, OP_Delete, iParm, 0);
      break;
    }

    /* If we are creating a set for an "expr IN (SELECT ...)" construct,
    ** then there should be a single item on the stack.  Write this
    ** item into the set table with bogus data.
    */
    case SRT_Set: {
      assert( nColumn==1 );
      sqliteVdbeAddOp(v, OP_IsNull, -1, sqliteVdbeCurrentAddr(v)+3);
      sqliteVdbeAddOp(v, OP_String, 0, 0);
      if( pOrderBy ){
        pushOntoSorter(pParse, v, pOrderBy);
      }else{
        sqliteVdbeAddOp(v, OP_PutStrKey, iParm, 0);
      }
      break;
    }

    /* If this is a scalar select that is part of an expression, then
    ** store the results in the appropriate memory cell and break out
    ** of the scan loop.
    */
    case SRT_Mem: {
      assert( nColumn==1 );
      if( pOrderBy ){
        pushOntoSorter(pParse, v, pOrderBy);
      }else{
        sqliteVdbeAddOp(v, OP_MemStore, iParm, 1);
        sqliteVdbeAddOp(v, OP_Goto, 0, iBreak);
      }
      break;
    }

    /* Discard the results.  This is used for SELECT statements inside
    ** the body of a TRIGGER.  The purpose of such selects is to call
    ** user-defined functions that have side effects.  We do not care
    ** about the actual results of the select.
    */
    case SRT_Discard: {
      sqliteVdbeAddOp(v, OP_Pop, nColumn, 0);
      break;
    }

    /* Send the data to the callback function.
    */

    default: {
      assert( eDest==SRT_Callback );
      if( pOrderBy ){
        sqliteVdbeAddOp(v, OP_SortMakeRec, nColumn, 0);
        pushOntoSorter(pParse, v, pOrderBy);
      }else{
        sqliteVdbeAddOp(v, OP_Callback, nColumn, 0);
      }
      break;
    }
  }
  return 0;
}

/*
** 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
** routine generates the code needed to do that.
*/
static void generateSortTail(
  Select *p,       /* The SELECT statement */
  Vdbe *v,         /* Generate code into this VDBE */
  int nColumn,     /* Number of columns of data */
  int eDest,       /* Write the sorted results here */
  int iParm        /* Optional parameter associated with eDest */
){
  int end = sqliteVdbeMakeLabel(v);
  int addr;
  sqliteVdbeAddOp(v, OP_Sort, 0, 0);
  addr = sqliteVdbeAddOp(v, OP_SortNext, 0, end);
  if( p->nOffset>0 ){
    sqliteVdbeAddOp(v, OP_LimitCk, 1, addr);
  }
  if( p->nLimit>0 ){
    sqliteVdbeAddOp(v, OP_LimitCk, 0, end);
  }
  switch( eDest ){
    case SRT_Callback: {
      sqliteVdbeAddOp(v, OP_SortCallback, nColumn, 0);
      break;
    }
    case SRT_Table:
    case SRT_TempTable: {
      sqliteVdbeAddOp(v, OP_NewRecno, iParm, 0);
      sqliteVdbeAddOp(v, OP_Pull, 1, 0);
      sqliteVdbeAddOp(v, OP_PutIntKey, iParm, 0);
      break;
    }
    case SRT_Set: {
      assert( nColumn==1 );
      sqliteVdbeAddOp(v, OP_IsNull, -1, sqliteVdbeCurrentAddr(v)+3);
      sqliteVdbeAddOp(v, OP_String, 0, 0);
      sqliteVdbeAddOp(v, OP_PutStrKey, iParm, 0);
      break;
    }
    case SRT_Mem: {
      assert( nColumn==1 );
      sqliteVdbeAddOp(v, OP_MemStore, iParm, 1);
      sqliteVdbeAddOp(v, OP_Goto, 0, end);
      break;
    }
    default: {
      assert( end==0 ); /* Cannot happen */
      break;
    }
  }
  sqliteVdbeAddOp(v, OP_Goto, 0, addr);
  sqliteVdbeResolveLabel(v, end);
  sqliteVdbeAddOp(v, OP_SortReset, 0, 0);
}

/*
** Generate code that will tell the VDBE how many columns there

  return v;
}
    

/*
** This routine is called to process a query that is really the union
** or intersection of two or more separate queries.
**
** "p" points to the right-most of the two queries.  The results should
** be stored in eDest with parameter iParm.
*/
static int multiSelect(Parse *pParse, Select *p, int eDest, int iParm){
  int rc;             /* Success code from a subroutine */
  Select *pPrior;     /* Another SELECT immediately to our left */
  Vdbe *v;            /* Generate code to this VDBE */
  int base;           /* Baseline value for pParse->nTab */

  switch( p->op ){
    case TK_ALL:
    case TK_EXCEPT:
    case TK_UNION: {
      int unionTab;    /* Cursor number of the temporary table holding result */
      int op;          /* One of the SRT_ operations to apply to self */
      int priorOp;     /* The SRT_ operation to apply to prior selects */
      ExprList *pOrderBy;  /* The ORDER BY clause for the right SELECT */

      priorOp = p->op==TK_ALL ? SRT_Table : SRT_Union;
      if( eDest==priorOp && p->pOrderBy==0 ){
        /* We can reuse a temporary table generated by a SELECT to our
        ** right.

        */
        unionTab = iParm;

      }else{
        /* We will need to create our own temporary table to hold the
        ** intermediate results.
        */
        unionTab = pParse->nTab++;
        if( p->pOrderBy 
        && matchOrderbyToColumn(pParse, p, p->pOrderBy, unionTab, 1) ){

      */
      switch( p->op ){
         case TK_EXCEPT:  op = SRT_Except;   break;
         case TK_UNION:   op = SRT_Union;    break;
         case TK_ALL:     op = SRT_Table;    break;
      }
      p->pPrior = 0;
      pOrderBy = p->pOrderBy;
      p->pOrderBy = 0;
      rc = sqliteSelect(pParse, p, op, unionTab, 0, 0, 0);
      p->pPrior = pPrior;
      p->pOrderBy = pOrderBy;
      if( rc ) return rc;

      /* Convert the data in the temporary table into whatever form
      ** it is that we currently need.
      */      
      if( eDest!=priorOp || unionTab!=iParm ){
        int iCont, iBreak, iStart;
        assert( p->pEList );
        if( eDest==SRT_Callback ){
          generateColumnNames(pParse, p->base, 0, p->pEList);
        }
        iBreak = sqliteVdbeMakeLabel(v);
        iCont = sqliteVdbeMakeLabel(v);
        sqliteVdbeAddOp(v, OP_Rewind, unionTab, iBreak);
        iStart = sqliteVdbeCurrentAddr(v);
        rc = selectInnerLoop(pParse, p, 0, unionTab, p->pEList->nExpr,
                             p->pOrderBy, -1, eDest, iParm, 
                             iCont, iBreak);
        if( rc ) return 1;
        sqliteVdbeResolveLabel(v, iCont);
        sqliteVdbeAddOp(v, OP_Next, unionTab, iStart);
        sqliteVdbeResolveLabel(v, iBreak);
        sqliteVdbeAddOp(v, OP_Close, unionTab, 0);
        if( p->pOrderBy ){
          generateSortTail(p, v, p->pEList->nExpr, eDest, iParm);
        }
      }
      break;
    }
    case TK_INTERSECT: {
      int tab1, tab2;
      int iCont, iBreak, iStart;

      if( rc ) return 1;
      sqliteVdbeResolveLabel(v, iCont);
      sqliteVdbeAddOp(v, OP_Next, tab1, iStart);
      sqliteVdbeResolveLabel(v, iBreak);
      sqliteVdbeAddOp(v, OP_Close, tab2, 0);
      sqliteVdbeAddOp(v, OP_Close, tab1, 0);
      if( p->pOrderBy ){
        generateSortTail(p, v, p->pEList->nExpr, eDest, iParm);
      }
      break;
    }
  }
  assert( p->pEList && pPrior->pEList );
  if( p->pEList->nExpr!=pPrior->pEList->nExpr ){
    sqliteSetString(&pParse->zErrMsg, "SELECTs to the left and right of ",

  if( (eDest==SRT_Mem || eDest==SRT_Set) && pEList->nExpr>1 ){
    sqliteSetString(&pParse->zErrMsg, "only a single result allowed for "
       "a SELECT that is part of an expression", 0);
    pParse->nErr++;
    goto select_end;
  }

  /* ORDER BY is ignored for some destinations.
  */
  switch( eDest ){
    case SRT_Union:
    case SRT_Except:
    case SRT_Discard:
      pOrderBy = 0;
      break;
    default:
      break;
  }

  /* At this point, we should have allocated all the cursors that we
  ** need to handle subquerys and temporary tables.  
  **
  ** Resolve the column names and do a semantics check on all the expressions.
  */

    pParse->useAgg = 0;
  }

  /* If there is an ORDER BY clause, then we need to sort the results
  ** and send them to the callback one by one.
  */
  if( pOrderBy ){
    generateSortTail(p, v, pEList->nExpr, eDest, iParm);
  }


  /* Issue a null callback if that is what the user wants.
  */
  if( (pParse->db->flags & SQLITE_NullCallback)!=0 && eDest==SRT_Callback ){
    sqliteVdbeAddOp(v, OP_NullCallback, pEList->nExpr, 0);

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing UNION, INTERSECT and EXCEPT operators
# in SELECT statements.
#
# $Id: select4.test,v 1.11 2002/06/20 03:38:26 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Build some test data
#
set fd [open data1.txt w]

  execsql {
    SELECT DISTINCT log FROM t1
    UNION ALL
    SELECT n FROM t1 WHERE log=3
    ORDER BY log;
  }
} {0 1 2 3 4 5 5 6 7 8}
do_test select4-1.1d {
  execsql {
    CREATE TABLE t2 AS
      SELECT DISTINCT log FROM t1
      UNION ALL
      SELECT n FROM t1 WHERE log=3
      ORDER BY log;
    SELECT * FROM t2;
  }
} {0 1 2 3 4 5 5 6 7 8}
execsql {DROP TABLE t2}
do_test select4-1.1e {
  execsql {
    CREATE TABLE t2 AS
      SELECT DISTINCT log FROM t1
      UNION ALL
      SELECT n FROM t1 WHERE log=3
      ORDER BY log DESC;
    SELECT * FROM t2;
  }
} {8 7 6 5 5 4 3 2 1 0}
execsql {DROP TABLE t2}
do_test select4-1.2 {
  execsql {
    SELECT log FROM t1 WHERE n IN 
      (SELECT DISTINCT log FROM t1 UNION ALL
       SELECT n FROM t1 WHERE log=3)
    ORDER BY log;
  }

    ORDER BY log;
  }} msg]
  lappend v $msg
} {1 {ORDER BY clause should come after UNION not before}}

# Except operator
#
do_test select4-3.1.1 {
  execsql {
    SELECT DISTINCT log FROM t1
    EXCEPT
    SELECT n FROM t1 WHERE log=3
    ORDER BY log;
  }
} {0 1 2 3 4}
do_test select4-3.1.2 {
  execsql {
    CREATE TABLE t2 AS 
      SELECT DISTINCT log FROM t1
      EXCEPT
      SELECT n FROM t1 WHERE log=3
      ORDER BY log;
    SELECT * FROM t2;
  }
} {0 1 2 3 4}
execsql {DROP TABLE t2}
do_test select4-3.1.3 {
  execsql {
    CREATE TABLE t2 AS 
      SELECT DISTINCT log FROM t1
      EXCEPT
      SELECT n FROM t1 WHERE log=3
      ORDER BY log DESC;
    SELECT * FROM t2;
  }
} {4 3 2 1 0}
execsql {DROP TABLE t2}
do_test select4-3.2 {
  execsql {
    SELECT log FROM t1 WHERE n IN 
      (SELECT DISTINCT log FROM t1 EXCEPT
       SELECT n FROM t1 WHERE log=3)
    ORDER BY log;
  }
} {0 1 2 2}
do_test select4-3.3 {
  set v [catch {execsql {
    SELECT DISTINCT log FROM t1 ORDER BY log
    EXCEPT
    SELECT n FROM t1 WHERE log=3
    ORDER BY log;
  }} msg]
  lappend v $msg
} {1 {ORDER BY clause should come after EXCEPT not before}}

# Intersect operator
#
do_test select4-4.1.1 {
  execsql {
    SELECT DISTINCT log FROM t1
    INTERSECT
    SELECT n FROM t1 WHERE log=3
    ORDER BY log;
  }
} {5}
do_test select4-4.1.2 {
  execsql {
    SELECT DISTINCT log FROM t1 UNION ALL SELECT 6
    INTERSECT
    SELECT n FROM t1 WHERE log=3
    ORDER BY log;
  }
} {5 6}
do_test select4-4.1.3 {
  execsql {
    CREATE TABLE t2 AS
      SELECT DISTINCT log FROM t1 UNION ALL SELECT 6
      INTERSECT
      SELECT n FROM t1 WHERE log=3
      ORDER BY log;
    SELECT * FROM t2;
  }
} {5 6}
execsql {DROP TABLE t2}
do_test select4-4.1.4 {
  execsql {
    CREATE TABLE t2 AS
      SELECT DISTINCT log FROM t1 UNION ALL SELECT 6
      INTERSECT
      SELECT n FROM t1 WHERE log=3
      ORDER BY log DESC;
    SELECT * FROM t2;
  }
} {6 5}
execsql {DROP TABLE t2}
do_test select4-4.2 {
  execsql {
    SELECT log FROM t1 WHERE n IN 
      (SELECT DISTINCT log FROM t1 INTERSECT
       SELECT n FROM t1 WHERE log=3)
    ORDER BY log;
  }