/ Check-in [8aa73ce6]
Login

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

Overview
Comment:An optimization: avoid the use of an intermediate table on UNION ALL if there is no ORDER BY clause. (CVS 637)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:8aa73ce61268a50d353d9a5c878461290195525f
User & Date: drh 2002-06-22 02:33:38
Context
2002-06-24
12:20
Fix a VDBE stack leak in LEFT OUTER JOIN. Fix a bug in the code generator for JOIN ... USING(...). (CVS 638) check-in: d861489e user: drh tags: trunk
2002-06-22
02:33
An optimization: avoid the use of an intermediate table on UNION ALL if there is no ORDER BY clause. (CVS 637) check-in: 8aa73ce6 user: drh tags: trunk
2002-06-21
23:01
Fix for bugs #77 and #80: Rework the LIMIT mechanism to be reentrant and to clean up the VDBE stack properly. (CVS 636) check-in: 9d552310 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/main.c.

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
839
840
841
842
843
844
845

846
**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.82 2002/06/21 11:55:49 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>

/*
** This is the callback routine for the code that initializes the
................................................................................
*/
int sqlite_function_type(sqlite *db, const char *zName, int dataType){
  FuncDef *p = (FuncDef*)sqliteHashFind(&db->aFunc, zName, strlen(zName));
  while( p ){
    p->dataType = dataType; 
    p = p->pNext;
  }

}







|







 







>

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
839
840
841
842
843
844
845
846
847
**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.83 2002/06/22 02:33:38 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>

/*
** This is the callback routine for the code that initializes the
................................................................................
*/
int sqlite_function_type(sqlite *db, const char *zName, int dataType){
  FuncDef *p = (FuncDef*)sqliteHashFind(&db->aFunc, zName, strlen(zName));
  while( p ){
    p->dataType = dataType; 
    p = p->pNext;
  }
  return SQLITE_OK;
}

Changes to src/select.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
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
464
465
466
467
468
469
470
...
478
479
480
481
482
483
484

485
486
487
488
489
490
491
...
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
...
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005











1006
1007
1008
1009
1010
1011
1012
**    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.96 2002/06/21 23:01:50 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/
................................................................................
        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;
}

/*
................................................................................
  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_MemIncr, p->nOffset, addr+4);
    sqliteVdbeAddOp(v, OP_Pop, 1, 0);
    sqliteVdbeAddOp(v, OP_Goto, 0, addr);
  }
................................................................................
    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);
}
................................................................................
  /* Create the destination temporary table if necessary
  */
  if( eDest==SRT_TempTable ){
    sqliteVdbeAddOp(v, OP_OpenTemp, iParm, 0);
    eDest = SRT_Table;
  }

  /* Process the UNION or INTERSECTION
  */
  base = 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 */








|







 







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






<
<
<
<
<
<
<

|
<
<
<
<
|
<







 







>







 







|







 







|



|
>
>
>
>
>
>
>
>
>
>
>







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
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
464




465

466
467
468
469
470
471
472
...
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
...
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
...
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
**    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.97 2002/06/22 02:33:38 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/
................................................................................
        pushOntoSorter(pParse, v, pOrderBy);
      }else{
        sqliteVdbeAddOp(v, OP_MemStore, iParm, 1);
        sqliteVdbeAddOp(v, OP_Goto, 0, iBreak);
      }
      break;
    }

    /* Send the data to the callback function.
    */
    case SRT_Callback:
    case SRT_Sorter: {
      if( pOrderBy ){
        sqliteVdbeAddOp(v, OP_SortMakeRec, nColumn, 0);
        pushOntoSorter(pParse, v, pOrderBy);
      }else{
        assert( eDest==SRT_Callback );
        sqliteVdbeAddOp(v, OP_Callback, nColumn, 0);
      }
      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.
    */







    default: {
      assert( eDest==SRT_Discard );




      sqliteVdbeAddOp(v, OP_Pop, nColumn, 0);

      break;
    }
  }
  return 0;
}

/*
................................................................................
  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;
  if( eDest==SRT_Sorter ) return;
  sqliteVdbeAddOp(v, OP_Sort, 0, 0);
  addr = sqliteVdbeAddOp(v, OP_SortNext, 0, end);
  if( p->nOffset>0 ){
    sqliteVdbeAddOp(v, OP_MemIncr, p->nOffset, addr+4);
    sqliteVdbeAddOp(v, OP_Pop, 1, 0);
    sqliteVdbeAddOp(v, OP_Goto, 0, addr);
  }
................................................................................
    case SRT_Mem: {
      assert( nColumn==1 );
      sqliteVdbeAddOp(v, OP_MemStore, iParm, 1);
      sqliteVdbeAddOp(v, OP_Goto, 0, end);
      break;
    }
    default: {
      /* Do nothing */
      break;
    }
  }
  sqliteVdbeAddOp(v, OP_Goto, 0, addr);
  sqliteVdbeResolveLabel(v, end);
  sqliteVdbeAddOp(v, OP_SortReset, 0, 0);
}
................................................................................
  /* Create the destination temporary table if necessary
  */
  if( eDest==SRT_TempTable ){
    sqliteVdbeAddOp(v, OP_OpenTemp, iParm, 0);
    eDest = SRT_Table;
  }

  /* Generate code for the left and right SELECT statements.
  */
  base = pParse->nTab;
  switch( p->op ){
    case TK_ALL: {
      if( p->pOrderBy==0 ){
        rc = sqliteSelect(pParse, pPrior, eDest, iParm, 0, 0, 0);
        if( rc ) return rc;
        p->pPrior = 0;
        rc = sqliteSelect(pParse, p, eDest, iParm, 0, 0, 0);
        p->pPrior = pPrior;
        if( rc ) return rc;
        break;
      }
      /* For UNION ALL ... ORDER BY fall through to the next case */
    }
    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 */

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
599
600
601
602
603
604
605

606
607
608
609
610
611
612
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.128 2002/06/21 23:01:50 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>
................................................................................
#define SRT_Mem          2  /* Store result in a memory cell */
#define SRT_Set          3  /* Store result as unique keys in a table */
#define SRT_Union        5  /* Store result as keys in a table */
#define SRT_Except       6  /* Remove result from a UNION table */
#define SRT_Table        7  /* Store result as data with a unique key */
#define SRT_TempTable    8  /* Store result in a trasient table */
#define SRT_Discard      9  /* Do not save the results anywhere */


/*
** When a SELECT uses aggregate functions (like "count(*)" or "avg(f1)")
** we have to do some additional analysis of expressions.  An instance
** of the following structure holds information about a single subexpression
** somewhere in the SELECT statement.  An array of these structures holds
** all the information we need to generate code for aggregate







|







 







>







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.129 2002/06/22 02:33:39 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>
................................................................................
#define SRT_Mem          2  /* Store result in a memory cell */
#define SRT_Set          3  /* Store result as unique keys in a table */
#define SRT_Union        5  /* Store result as keys in a table */
#define SRT_Except       6  /* Remove result from a UNION table */
#define SRT_Table        7  /* Store result as data with a unique key */
#define SRT_TempTable    8  /* Store result in a trasient table */
#define SRT_Discard      9  /* Do not save the results anywhere */
#define SRT_Sorter      10  /* Store results in the sorter */

/*
** When a SELECT uses aggregate functions (like "count(*)" or "avg(f1)")
** we have to do some additional analysis of expressions.  An instance
** of the following structure holds information about a single subexpression
** somewhere in the SELECT statement.  An array of these structures holds
** all the information we need to generate code for aggregate

Changes to test/select4.test.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
68
69
70
71
72
73
74

















75
76
77
78
79
80
81
#    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]
................................................................................
      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;







|







 







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







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#    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.12 2002/06/22 02:33:39 drh Exp $

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

# Build some test data
#
set fd [open data1.txt w]
................................................................................
      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.1f {
  execsql {
    SELECT DISTINCT log FROM t1
    UNION ALL
    SELECT n FROM t1 WHERE log=2
  }
} {0 1 2 3 4 5 3 4}
do_test select4-1.1g {
  execsql {
    CREATE TABLE t2 AS 
      SELECT DISTINCT log FROM t1
      UNION ALL
      SELECT n FROM t1 WHERE log=2;
    SELECT * FROM t2;
  }
} {0 1 2 3 4 5 3 4}
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;