SQLite

Check-in [22132ce18c]
Login

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

Overview
Comment:Fix a problem in GROUP BY with multiple columns. (CVS 255)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 22132ce18cad31482cdb9b380cedc3f53bc532b8
User & Date: drh 2001-09-18 22:17:44.000
Context
2001-09-19
13:22
Trying to get the OS abstraction layer to work. (CVS 256) (check-in: abff526d00 user: drh tags: trunk)
2001-09-18
22:17
Fix a problem in GROUP BY with multiple columns. (CVS 255) (check-in: 22132ce18c user: drh tags: trunk)
02:02
Bug fixes. Trying to make it go faster. (CVS 254) (check-in: 8f28a83aba user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/util.c.
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.25 2001/09/16 00:13:27 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

/*
** If malloc() ever fails, this global variable gets set to 1.







|







10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.26 2001/09/18 22:17:44 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

/*
** If malloc() ever fails, this global variable gets set to 1.
386
387
388
389
390
391
392
393
394
395
396

397
398
399
400
401
402
403

/*
** This function computes a hash on the name of a keyword.
** Case is not significant.
*/
int sqliteHashNoCase(const char *z, int n){
  int h = 0;
  int c;
  if( n<=0 ) n = strlen(z);
  while( n-- > 0 && (c = *z++)!=0 ){
    h = (h<<3) ^ h ^ UpperToLower[c];

  }
  if( h<0 ) h = -h;
  return h;
}

/*
** Some systems have stricmp().  Others have strcasecmp().  Because







<

|
|
>







386
387
388
389
390
391
392

393
394
395
396
397
398
399
400
401
402
403

/*
** This function computes a hash on the name of a keyword.
** Case is not significant.
*/
int sqliteHashNoCase(const char *z, int n){
  int h = 0;

  if( n<=0 ) n = strlen(z);
  while( n > 0  ){
    h = (h<<3) ^ h ^ UpperToLower[*z++];
    n--;
  }
  if( h<0 ) h = -h;
  return h;
}

/*
** Some systems have stricmp().  Others have strcasecmp().  Because
Changes to src/vdbe.c.
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
** type to the other occurs as necessary.
** 
** Most of the code in this file is taken up by the sqliteVdbeExec()
** function which does the work of interpreting a VDBE program.
** But other routines are also provided to help in building up
** a program instruction by instruction.
**
** $Id: vdbe.c,v 1.71 2001/09/18 02:02:23 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include <unistd.h>

/*
** SQL is translated into a sequence of instructions to be







|







26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
** type to the other occurs as necessary.
** 
** Most of the code in this file is taken up by the sqliteVdbeExec()
** function which does the work of interpreting a VDBE program.
** But other routines are also provided to help in building up
** a program instruction by instruction.
**
** $Id: vdbe.c,v 1.72 2001/09/18 22:17:44 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include <unistd.h>

/*
** SQL is translated into a sequence of instructions to be
138
139
140
141
142
143
144

145
146
147
148
149
150
151
  int nElem;             /* The number of AggElems */
  int nHash;             /* Number of slots in apHash[] */
  AggElem **apHash;      /* A hash array for looking up AggElems by zKey */
  AggElem *pFirst;       /* A list of all AggElems */
};
struct AggElem {
  char *zKey;            /* The key to this AggElem */

  AggElem *pHash;        /* Next AggElem with the same hash on zKey */
  AggElem *pNext;        /* Next AggElem in a list of them all */
  Mem aMem[1];           /* The values for this AggElem */
};

/*
** A Set structure is used for quick testing to see if a value







>







138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
  int nElem;             /* The number of AggElems */
  int nHash;             /* Number of slots in apHash[] */
  AggElem **apHash;      /* A hash array for looking up AggElems by zKey */
  AggElem *pFirst;       /* A list of all AggElems */
};
struct AggElem {
  char *zKey;            /* The key to this AggElem */
  int nKey;              /* Number of bytes in the key, including '\0' at end */
  AggElem *pHash;        /* Next AggElem with the same hash on zKey */
  AggElem *pNext;        /* Next AggElem in a list of them all */
  Mem aMem[1];           /* The values for this AggElem */
};

/*
** A Set structure is used for quick testing to see if a value
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
  memset(p, 0, sizeof(*p));
}

/*
** Add the given AggElem to the hash array
*/
static void AggEnhash(Agg *p, AggElem *pElem){
  int h = sqliteHashNoCase(pElem->zKey, 0) % p->nHash;
  pElem->pHash = p->apHash[h];
  p->apHash[h] = pElem;
}

/*
** Change the size of the hash array to the amount given.
*/







|







476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
  memset(p, 0, sizeof(*p));
}

/*
** Add the given AggElem to the hash array
*/
static void AggEnhash(Agg *p, AggElem *pElem){
  int h = sqliteHashNoCase(pElem->zKey, pElem->nKey) % p->nHash;
  pElem->pHash = p->apHash[h];
  p->apHash[h] = pElem;
}

/*
** Change the size of the hash array to the amount given.
*/
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523

524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
}

/*
** Insert a new element and make it the current element.  
**
** Return 0 on success and 1 if memory is exhausted.
*/
static int AggInsert(Agg *p, char *zKey){
  AggElem *pElem;
  int i;
  if( p->nHash <= p->nElem*2 ){
    AggRehash(p, p->nElem*2 + 19);
  }
  if( p->nHash==0 ) return 1;
  pElem = sqliteMalloc( sizeof(AggElem) + strlen(zKey) + 1 +
                        (p->nMem-1)*sizeof(pElem->aMem[0]) );
  if( pElem==0 ) return 1;
  pElem->zKey = (char*)&pElem->aMem[p->nMem];
  strcpy(pElem->zKey, zKey);

  AggEnhash(p, pElem);
  pElem->pNext = p->pFirst;
  p->pFirst = pElem;
  p->nElem++;
  p->pCurrent = pElem;
  for(i=0; i<p->nMem; i++){
    pElem->aMem[i].s.flags = STK_Null;
  }
  return 0;
}

/*
** Get the AggElem currently in focus
*/
#define AggInFocus(P)   ((P).pCurrent ? (P).pCurrent : _AggInFocus(&(P)))
static AggElem *_AggInFocus(Agg *p){
  AggElem *pFocus = p->pFirst;
  if( pFocus ){
    p->pCurrent = pFocus;
  }else{
    AggInsert(p,"");
    pFocus = p->pCurrent = p->pFirst;
  }
  return pFocus;
}

/*
** Erase all information from a Set







|






|



|
>




















|







506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
}

/*
** Insert a new element and make it the current element.  
**
** Return 0 on success and 1 if memory is exhausted.
*/
static int AggInsert(Agg *p, char *zKey, int nKey){
  AggElem *pElem;
  int i;
  if( p->nHash <= p->nElem*2 ){
    AggRehash(p, p->nElem*2 + 19);
  }
  if( p->nHash==0 ) return 1;
  pElem = sqliteMalloc( sizeof(AggElem) + nKey +
                        (p->nMem-1)*sizeof(pElem->aMem[0]) );
  if( pElem==0 ) return 1;
  pElem->zKey = (char*)&pElem->aMem[p->nMem];
  memcpy(pElem->zKey, zKey, nKey);
  pElem->nKey = nKey;
  AggEnhash(p, pElem);
  pElem->pNext = p->pFirst;
  p->pFirst = pElem;
  p->nElem++;
  p->pCurrent = pElem;
  for(i=0; i<p->nMem; i++){
    pElem->aMem[i].s.flags = STK_Null;
  }
  return 0;
}

/*
** Get the AggElem currently in focus
*/
#define AggInFocus(P)   ((P).pCurrent ? (P).pCurrent : _AggInFocus(&(P)))
static AggElem *_AggInFocus(Agg *p){
  AggElem *pFocus = p->pFirst;
  if( pFocus ){
    p->pCurrent = pFocus;
  }else{
    AggInsert(p,"",1);
    pFocus = p->pCurrent = p->pFirst;
  }
  return pFocus;
}

/*
** Erase all information from a Set
2307
2308
2309
2310
2311
2312
2313
















2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
*/
case OP_NewRecno: {
  int i = pOp->p1;
  int v = 0;
  if( VERIFY( i<0 || i>=p->nCursor || ) p->aCsr[i].pCursor==0 ){
    v = 0;
  }else{
















    int res, rx, cnt;
    static int x = 0;
    union {
       char zBuf[sizeof(int)];
       int i;
    } ux;
    cnt = 0;
    do{
      if( x==0 || cnt>5 ){
        x = sqliteRandomInteger();
      }else{
        x += sqliteRandomByte() + 1;
      }
      if( x==0 ) continue;
      ux.zBuf[3] = x&0xff;
      ux.zBuf[2] = (x>>8)&0xff;
      ux.zBuf[1] = (x>>16)&0xff;
      ux.zBuf[0] = (x>>24)&0xff;
      v = ux.i;
      rx = sqliteBtreeMoveto(p->aCsr[i].pCursor, &v, sizeof(v), &res);
      cnt++;
    }while( cnt<200 && rx==SQLITE_OK && res==0 );
    if( rx==SQLITE_OK && res==0 ){
      rc = SQLITE_FULL;
      goto abort_due_to_error;
    }
  }
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;







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








|












|







2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
*/
case OP_NewRecno: {
  int i = pOp->p1;
  int v = 0;
  if( VERIFY( i<0 || i>=p->nCursor || ) p->aCsr[i].pCursor==0 ){
    v = 0;
  }else{
    /* A probablistic algorithm is used to locate an unused rowid.
    ** We select a rowid at random and see if it exists in the table.
    ** If it does not exist, we have succeeded.  If the random rowid
    ** does exist, we select a new one and try again, up to 1000 times.
    **
    ** For a table with less than 2 billion entries, the probability
    ** of not finding a unused rowid is about 1.0e-300.  This is a 
    ** non-zero probability, but it is still vanishingly small and should
    ** never cause a problem.  You are much, much more likely to have a
    ** hardware failure than for this algorithm to fail.
    **
    ** To promote locality of reference for repetitive inserts, the
    ** first few attempts at chosing a rowid pick values just a little
    ** larger than the previous rowid.  This has been shown experimentally
    ** to double the speed of the COPY operation.
    */
    int res, rx, cnt;
    static int x = 0;
    union {
       char zBuf[sizeof(int)];
       int i;
    } ux;
    cnt = 0;
    do{
      if( cnt>5 ){
        x = sqliteRandomInteger();
      }else{
        x += sqliteRandomByte() + 1;
      }
      if( x==0 ) continue;
      ux.zBuf[3] = x&0xff;
      ux.zBuf[2] = (x>>8)&0xff;
      ux.zBuf[1] = (x>>16)&0xff;
      ux.zBuf[0] = (x>>24)&0xff;
      v = ux.i;
      rx = sqliteBtreeMoveto(p->aCsr[i].pCursor, &v, sizeof(v), &res);
      cnt++;
    }while( cnt<1000 && rx==SQLITE_OK && res==0 );
    if( rx==SQLITE_OK && res==0 ){
      rc = SQLITE_FULL;
      goto abort_due_to_error;
    }
  }
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
3453
3454
3455
3456
3457
3458
3459
3460
3461
3462
3463
3464
3465
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
3476
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( Stringify(p, tos) ) goto no_mem;
  zKey = zStack[tos]; 
  nKey = aStack[tos].n;
  if( p->agg.nHash<=0 ){
    pElem = 0;
  }else{
    int h = sqliteHashNoCase(zKey, nKey-1) % p->agg.nHash;
    for(pElem=p->agg.apHash[h]; pElem; pElem=pElem->pHash){
      if( strcmp(pElem->zKey, zKey)==0 ) break;
    }
  }
  if( pElem ){
    p->agg.pCurrent = pElem;
    pc = pOp->p2 - 1;
  }else{
    AggInsert(&p->agg, zKey);
    if( sqlite_malloc_failed ) goto no_mem;
  }
  POPSTACK;
  break; 
}

/* Opcode: AggIncr P1 P2 *







|

|






|







3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( Stringify(p, tos) ) goto no_mem;
  zKey = zStack[tos]; 
  nKey = aStack[tos].n;
  if( p->agg.nHash<=0 ){
    pElem = 0;
  }else{
    int h = sqliteHashNoCase(zKey, nKey) % p->agg.nHash;
    for(pElem=p->agg.apHash[h]; pElem; pElem=pElem->pHash){
      if( pElem->nKey==nKey && memcmp(pElem->zKey, zKey, nKey)==0 ) break;
    }
  }
  if( pElem ){
    p->agg.pCurrent = pElem;
    pc = pOp->p2 - 1;
  }else{
    AggInsert(&p->agg, zKey, nKey);
    if( sqlite_malloc_failed ) goto no_mem;
  }
  POPSTACK;
  break; 
}

/* Opcode: AggIncr P1 P2 *
Added test/misc1.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
# 2001 September 15
#
# 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.
#
# This file implements tests for miscellanous features that were
# left out of other test files.
#
# $Id: misc1.test,v 1.1 2001/09/18 22:17:45 drh Exp $

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

# Test the creation and use of tables that have a large number
# of columns.
#
do_test misc1-1.1 {
  set cmd "CREATE TABLE manycol(x0 text"
  for {set i 1} {$i<=99} {incr i} {
    append cmd ",x$i text"
  }
  append cmd ")";
  execsql $cmd
  set cmd "INSERT INTO manycol VALUES(0"
  for {set i 1} {$i<=99} {incr i} {
    append cmd ",$i"
  }
  append cmd ")";
  execsql $cmd
  execsql "SELECT x99 FROM manycol"
} 99
do_test misc1-1.2 {
  execsql {SELECT x0, x10, x25, x50, x75 FROM manycol}
} {0 10 25 50 75}
do_test misc1-1.3 {
  for {set j 100} {$j<=1000} {incr j 100} {
    set cmd "INSERT INTO manycol VALUES($j"
    for {set i 1} {$i<=99} {incr i} {
      append cmd ",[expr {$i+$j}]"
    }
    append cmd ")"
    execsql $cmd
  }
  execsql {SELECT x50 FROM manycol ORDER BY x80}
} {50 150 250 350 450 550 650 750 850 950 1050}
do_test misc1-1.4 {
  execsql {SELECT x75 FROM manycol WHERE x50=350}
} 375
do_test misc1-1.5 {
  execsql {SELECT x50 FROM manycol WHERE x99=599}
} 550
do_test misc1-1.6 {
  execsql {CREATE INDEX manycol_idx1 ON manycol(x99)}
  execsql {SELECT x50 FROM manycol WHERE x99=899}
} 850
do_test misc1-1.7 {
  execsql {SELECT count(*) FROM manycol}
} 11
do_test misc1-1.8 {
  execsql {DELETE FROM manycol WHERE x98=1234}
  execsql {SELECT count(*) FROM manycol}
} 11
do_test misc1-1.9 {
  execsql {DELETE FROM manycol WHERE x98=998}
  execsql {SELECT count(*) FROM manycol}
} 10
do_test misc1-1.10 {
  execsql {DELETE FROM manycol WHERE x99=500}
  execsql {SELECT count(*) FROM manycol}
} 10
do_test misc1-1.11 {
  execsql {DELETE FROM manycol WHERE x99=599}
  execsql {SELECT count(*) FROM manycol}
} 9

# Check GROUP BY expressions that name two or more columns.
#
do_test misc1-2.1 {
  execsql {
    BEGIN TRANSACTION;
    CREATE TABLE agger(one text, two text, three text, four text);
    INSERT INTO agger VALUES(1, 'one', 'hello', 'yes');
    INSERT INTO agger VALUES(2, 'two', 'howdy', 'no');
    INSERT INTO agger VALUES(3, 'thr', 'howareya', 'yes');
    INSERT INTO agger VALUES(4, 'two', 'lothere', 'yes');
    INSERT INTO agger VALUES(5, 'one', 'atcha', 'yes');
    INSERT INTO agger VALUES(6, 'two', 'hello', 'no');
    COMMIT
  }
  execsql {SELECT count(*) FROM agger}
} 6
do_test misc1-2.2 {
  execsql {SELECT sum(one), two, four FROM agger
           GROUP BY two, four ORDER BY sum(one) desc}
} {8 two no 6 one yes 4 two yes 3 thr yes}

finish_test