/ Check-in [7064433e]
Login

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

Overview
Comment:Basic functionality for descending indices is in place. Lots more testing needed. (CVS 2840)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:7064433e5b06a4f858f39ce57650fba99fd72ffd
User & Date: drh 2005-12-21 14:43:12
Context
2005-12-21
18:36
Bug fixes and additional testing of descending indices. (CVS 2841) check-in: 5638a11e user: drh tags: trunk
14:43
Basic functionality for descending indices is in place. Lots more testing needed. (CVS 2840) check-in: 7064433e user: drh tags: trunk
03:16
Progress toward decending indices. (CVS 2839) check-in: 112a34b8 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/alter.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
...
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
**    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 used to generate VDBE code
** that implements the ALTER TABLE command.
**
** $Id: alter.c,v 1.12 2005/12/16 01:06:17 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The code in this file only exists if we are not omitting the
** ALTER TABLE logic from the build.
................................................................................
  Table *pTab;              /* Table being altered */
  int iDb;                  /* Database number */
  const char *zDb;          /* Database name */
  const char *zTab;         /* Table name */
  char *zCol;               /* Null-terminated column definition */
  Column *pCol;             /* The new column */
  Expr *pDflt;              /* Default value for the new column */
  Vdbe *v;

  if( pParse->nErr ) return;
  pNew = pParse->pNewTable;
  assert( pNew );

  iDb = pNew->iDb;
  zDb = pParse->db->aDb[iDb].zName;
................................................................................
  ** the file format becomes 3.
  */
  sqlite3MinimumFileFormat(pParse, iDb, pDflt ? 3 : 2);

  /* Reload the schema of the modified table. */
  reloadTableSchema(pParse, pTab, pTab->zName);
}

/*
** Generate code to make sure the file format number is at least minFormat.
** The generated code will increase the file format number if necessary.
*/
void sqlite3MinimumFileFormat(Parse *pParse, int iDb, int minFormat){
  Vdbe *v;
  v = sqlite3GetVdbe(pParse);
  if( v ){
    sqlite3VdbeAddOp(v, OP_ReadCookie, iDb, 1);
    sqlite3VdbeAddOp(v, OP_Integer, minFormat, 0);
    sqlite3VdbeAddOp(v, OP_Ge, 0, sqlite3VdbeCurrentAddr(v)+3);
    sqlite3VdbeAddOp(v, OP_Integer, minFormat, 0);
    sqlite3VdbeAddOp(v, OP_SetCookie, iDb, 1);
  }
}


/*
** This function is called by the parser after the table-name in
** an "ALTER TABLE <table-name> ADD" statement is parsed. Argument 
** pSrc is the full-name of the table being altered.
**
** This routine makes a (partial) copy of the Table structure







|







 







<







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
381
382
383
384
385
386
387

388
389
390
391
392
393
394
...
462
463
464
465
466
467
468

















469
470
471
472
473
474
475
**    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 used to generate VDBE code
** that implements the ALTER TABLE command.
**
** $Id: alter.c,v 1.13 2005/12/21 14:43:12 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The code in this file only exists if we are not omitting the
** ALTER TABLE logic from the build.
................................................................................
  Table *pTab;              /* Table being altered */
  int iDb;                  /* Database number */
  const char *zDb;          /* Database name */
  const char *zTab;         /* Table name */
  char *zCol;               /* Null-terminated column definition */
  Column *pCol;             /* The new column */
  Expr *pDflt;              /* Default value for the new column */


  if( pParse->nErr ) return;
  pNew = pParse->pNewTable;
  assert( pNew );

  iDb = pNew->iDb;
  zDb = pParse->db->aDb[iDb].zName;
................................................................................
  ** the file format becomes 3.
  */
  sqlite3MinimumFileFormat(pParse, iDb, pDflt ? 3 : 2);

  /* Reload the schema of the modified table. */
  reloadTableSchema(pParse, pTab, pTab->zName);
}


















/*
** This function is called by the parser after the table-name in
** an "ALTER TABLE <table-name> ADD" statement is parsed. Argument 
** pSrc is the full-name of the table being altered.
**
** This routine makes a (partial) copy of the Table structure

Changes to src/build.c.

18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
....
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
....
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408





2409
2410
2411
2412
2413
2414
2415
....
2473
2474
2475
2476
2477
2478
2479
















2480
2481
2482
2483
2484
2485
2486
**     CREATE INDEX
**     DROP INDEX
**     creating ID lists
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**
** $Id: build.c,v 1.359 2005/12/21 03:16:43 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called when a new SQL statement is beginning to
** be parsed.  Initialize the pParse structure as needed.
................................................................................
  pIndex->nColumn = pList->nExpr;
  pIndex->onError = onError;
  pIndex->autoIndex = pName==0;
  pIndex->iDb = iDb;

  /* Check to see if we should honor DESC requests on index columns
  */
  if( pDb->file_format>=4 || (pDb->descIndex && db->init.busy) ){
#if 0
    sortOrderMask = -1;   /* Honor DESC */
#else
    sortOrderMask = 0;
#endif
  }else{
    sortOrderMask = 0;    /* Ignore DESC */
  }

  /* Scan the names of the columns of the table to be indexed and
  ** load the column indices into the Index structure.  Report an error
  ** if any column is not found.
................................................................................
    Vdbe *v;
    char *zStmt;
    int iMem = pParse->nMem++;

    v = sqlite3GetVdbe(pParse);
    if( v==0 ) goto exit_create_index;

    /* Make sure the file_format is at least 4 if we have DESC indices. */
    if( descSeen ){
      sqlite3MinimumFileFormat(pParse, iDb, 4);
    }

    /* Create the rootpage for the index
    */
    sqlite3BeginWriteOperation(pParse, 1, iDb);
    sqlite3VdbeAddOp(v, OP_CreateIndex, iDb, 0);
    sqlite3VdbeAddOp(v, OP_MemStore, iMem, 0);






    /* Gather the complete text of the CREATE INDEX statement into
    ** the zStmt variable
    */
    if( pStart && pEnd ){
      /* A named index with an explicit CREATE INDEX statement */
      zStmt = sqlite3MPrintf("CREATE%s INDEX %.*s",
................................................................................
    freeIndex(pIndex);
  }
  sqlite3ExprListDelete(pList);
  sqlite3SrcListDelete(pTblName);
  sqliteFree(zName);
  return;
}

















/*
** Fill the Index.aiRowEst[] array with default information - information
** to be used when we have not run the ANALYZE command.
**
** aiRowEst[0] is suppose to contain the number of elements in the index.
** Since we do not know, guess 1 million.  aiRowEst[1] is an estimate of the







|







 







|
<

<
<
<







 







<
<
<
<






>
>
>
>
>







 







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







18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
....
2255
2256
2257
2258
2259
2260
2261
2262

2263



2264
2265
2266
2267
2268
2269
2270
....
2388
2389
2390
2391
2392
2393
2394




2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
....
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
**     CREATE INDEX
**     DROP INDEX
**     creating ID lists
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**
** $Id: build.c,v 1.360 2005/12/21 14:43:12 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called when a new SQL statement is beginning to
** be parsed.  Initialize the pParse structure as needed.
................................................................................
  pIndex->nColumn = pList->nExpr;
  pIndex->onError = onError;
  pIndex->autoIndex = pName==0;
  pIndex->iDb = iDb;

  /* Check to see if we should honor DESC requests on index columns
  */
  if( pDb->file_format>=4 || (!pDb->descIndex && !db->init.busy) ){

    sortOrderMask = -1;   /* Honor DESC */



  }else{
    sortOrderMask = 0;    /* Ignore DESC */
  }

  /* Scan the names of the columns of the table to be indexed and
  ** load the column indices into the Index structure.  Report an error
  ** if any column is not found.
................................................................................
    Vdbe *v;
    char *zStmt;
    int iMem = pParse->nMem++;

    v = sqlite3GetVdbe(pParse);
    if( v==0 ) goto exit_create_index;






    /* Create the rootpage for the index
    */
    sqlite3BeginWriteOperation(pParse, 1, iDb);
    sqlite3VdbeAddOp(v, OP_CreateIndex, iDb, 0);
    sqlite3VdbeAddOp(v, OP_MemStore, iMem, 0);

    /* Make sure the file_format is at least 4 if we have DESC indices. */
    if( descSeen ){
      sqlite3MinimumFileFormat(pParse, iDb, 4);
    }

    /* Gather the complete text of the CREATE INDEX statement into
    ** the zStmt variable
    */
    if( pStart && pEnd ){
      /* A named index with an explicit CREATE INDEX statement */
      zStmt = sqlite3MPrintf("CREATE%s INDEX %.*s",
................................................................................
    freeIndex(pIndex);
  }
  sqlite3ExprListDelete(pList);
  sqlite3SrcListDelete(pTblName);
  sqliteFree(zName);
  return;
}

/*
** Generate code to make sure the file format number is at least minFormat.
** The generated code will increase the file format number if necessary.
*/
void sqlite3MinimumFileFormat(Parse *pParse, int iDb, int minFormat){
  Vdbe *v;
  v = sqlite3GetVdbe(pParse);
  if( v ){
    sqlite3VdbeAddOp(v, OP_ReadCookie, iDb, 1);
    sqlite3VdbeAddOp(v, OP_Integer, minFormat, 0);
    sqlite3VdbeAddOp(v, OP_Ge, 0, sqlite3VdbeCurrentAddr(v)+3);
    sqlite3VdbeAddOp(v, OP_Integer, minFormat, 0);
    sqlite3VdbeAddOp(v, OP_SetCookie, iDb, 1);
  }
}

/*
** Fill the Index.aiRowEst[] array with default information - information
** to be used when we have not run the ANALYZE command.
**
** aiRowEst[0] is suppose to contain the number of elements in the index.
** Since we do not know, guess 1 million.  aiRowEst[1] is an estimate of the

Changes to src/vdbe.c.

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
2418
2419
2420
2421
2422
2423
2424



2425
2426
2427
2428
2429
2430
2431
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.506 2005/12/16 15:24:29 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
  sqlite3VdbeMemIntegerify(pTos);
  /* See note about index shifting on OP_ReadCookie */
  rc = sqlite3BtreeUpdateMeta(pDb->pBt, 1+pOp->p2, (int)pTos->i);
  if( pOp->p2==0 ){
    /* When the schema cookie changes, record the new cookie internally */
    pDb->schema_cookie = pTos->i;
    db->flags |= SQLITE_InternChanges;



  }
  assert( (pTos->flags & MEM_Dyn)==0 );
  pTos--;
  break;
}

/* Opcode: VerifyCookie P1 P2 *







|







 







>
>
>







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.507 2005/12/21 14:43:12 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
  sqlite3VdbeMemIntegerify(pTos);
  /* See note about index shifting on OP_ReadCookie */
  rc = sqlite3BtreeUpdateMeta(pDb->pBt, 1+pOp->p2, (int)pTos->i);
  if( pOp->p2==0 ){
    /* When the schema cookie changes, record the new cookie internally */
    pDb->schema_cookie = pTos->i;
    db->flags |= SQLITE_InternChanges;
  }else if( pOp->p2==1 ){
    /* Record changes in the file format */
    pDb->file_format = pTos->i;
  }
  assert( (pTos->flags & MEM_Dyn)==0 );
  pTos--;
  break;
}

/* Opcode: VerifyCookie P1 P2 *

Added test/descidx1.test.























































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
# 2005 December 21
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    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.
#
#*************************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is descending indices.
#
# $Id: descidx1.test,v 1.1 2005/12/21 14:43:12 drh Exp $
#

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

# This procedure sets the value of the file-format in file 'test.db'
# to $newval. Also, the schema cookie is incremented.
# 
proc set_file_format {newval} {
  set bt [btree_open test.db 10 0]
  btree_begin_transaction $bt
  set meta [btree_get_meta $bt]
  lset meta 2 $newval                    ;# File format
  lset meta 1 [expr [lindex $meta 1]+1]  ;# Schema cookie
  eval "btree_update_meta $bt $meta"
  btree_commit $bt
  btree_close $bt
}

# This procedure returns the value of the file-format in file 'test.db'.
# 
proc get_file_format {{fname test.db}} {
  set bt [btree_open $fname 10 0]
  set meta [btree_get_meta $bt]
  btree_close $bt
  lindex $meta 2
}

# Verify that the file format jumps to (at least) 4 as soon as a
# descending index is created.
#
do_test descidx1-1.1 {
  execsql {
    CREATE TABLE t1(a,b);
    CREATE INDEX i1 ON t1(b ASC);
  }
  get_file_format
} {1}
do_test descidx1-1.2 {
  execsql {
    CREATE INDEX i2 ON t1(a DESC);
  }
  get_file_format
} {4}

# Put some information in the table and verify that the descending
# index actually works.
#
do_test descidx1-2.1 {
  execsql {
    INSERT INTO t1 VALUES(1,1);
    INSERT INTO t1 VALUES(2,2);
    INSERT INTO t1 SELECT a+2, a+2 FROM t1;
    INSERT INTO t1 SELECT a+4, a+4 FROM t1;
    SELECT b FROM t1 WHERE a>3 AND a<7;
  }
} {6 5 4}
do_test descidx1-2.2 {
  execsql {
    SELECT a FROM t1 WHERE b>3 AND b<7;
  }
} {4 5 6}
do_test descidx1-2.3 {
  execsql {
    SELECT b FROM t1 WHERE a>=3 AND a<7;
  }
} {6 5 4 3}
do_test descidx1-2.4 {
  execsql {
    SELECT b FROM t1 WHERE a>3 AND a<=7;
  }
} {7 6 5 4}
do_test descidx1-2.5 {
  execsql {
    SELECT b FROM t1 WHERE a>=3 AND a<=7;
  }
} {7 6 5 4 3}
do_test descidx1-2.6 {
  execsql {
    SELECT a FROM t1 WHERE b>=3 AND b<=7;
  }
} {3 4 5 6 7}

# This procedure executes the SQL.  Then it checks to see if the OP_Sort
# opcode was executed.  If an OP_Sort did occur, then "sort" is appended
# to the result.  If no OP_Sort happened, then "nosort" is appended.
#
# This procedure is used to check to make sure sorting is or is not
# occurring as expected.
#
proc cksort {sql} {
  set ::sqlite_sort_count 0
  set data [execsql $sql]
  if {$::sqlite_sort_count} {set x sort} {set x nosort}
  lappend data $x
  return $data
}

# Test sorting using a descending index.
#
do_test descidx1-3.1 {
  cksort {SELECT a FROM t1 ORDER BY a}
} {1 2 3 4 5 6 7 8 nosort}
do_test descidx1-3.2 {
  cksort {SELECT a FROM t1 ORDER BY a ASC}
} {1 2 3 4 5 6 7 8 nosort}
do_test descidx1-3.3 {
  cksort {SELECT a FROM t1 ORDER BY a DESC}
} {8 7 6 5 4 3 2 1 nosort}
do_test descidx1-3.4 {
  cksort {SELECT b FROM t1 ORDER BY a}
} {1 2 3 4 5 6 7 8 nosort}
do_test descidx1-3.5 {
  cksort {SELECT b FROM t1 ORDER BY a ASC}
} {1 2 3 4 5 6 7 8 nosort}
do_test descidx1-3.6 {
  cksort {SELECT b FROM t1 ORDER BY a DESC}
} {8 7 6 5 4 3 2 1 nosort}
do_test descidx1-3.7 {
  cksort {SELECT a FROM t1 ORDER BY b}
} {1 2 3 4 5 6 7 8 nosort}
do_test descidx1-3.8 {
  cksort {SELECT a FROM t1 ORDER BY b ASC}
} {1 2 3 4 5 6 7 8 nosort}
do_test descidx1-3.9 {
  cksort {SELECT a FROM t1 ORDER BY b DESC}
} {8 7 6 5 4 3 2 1 nosort}
do_test descidx1-3.10 {
  cksort {SELECT b FROM t1 ORDER BY b}
} {1 2 3 4 5 6 7 8 nosort}
do_test descidx1-3.11 {
  cksort {SELECT b FROM t1 ORDER BY b ASC}
} {1 2 3 4 5 6 7 8 nosort}
do_test descidx1-3.12 {
  cksort {SELECT b FROM t1 ORDER BY b DESC}
} {8 7 6 5 4 3 2 1 nosort}

do_test descidx1-3.21 {
  cksort {SELECT a FROM t1 WHERE a>3 AND a<8 ORDER BY a}
} {4 5 6 7 nosort}
do_test descidx1-3.22 {
  cksort {SELECT a FROM t1 WHERE a>3 AND a<8 ORDER BY a ASC}
} {4 5 6 7 nosort}
do_test descidx1-3.23 {
  cksort {SELECT a FROM t1 WHERE a>3 AND a<8 ORDER BY a DESC}
} {7 6 5 4 nosort}
do_test descidx1-3.24 {
  cksort {SELECT b FROM t1 WHERE a>3 AND a<8 ORDER BY a}
} {4 5 6 7 nosort}
do_test descidx1-3.25 {
  cksort {SELECT b FROM t1 WHERE a>3 AND a<8 ORDER BY a ASC}
} {4 5 6 7 nosort}
do_test descidx1-3.26 {
  cksort {SELECT b FROM t1 WHERE a>3 AND a<8 ORDER BY a DESC}
} {7 6 5 4 nosort}

finish_test