SQLite

Check-in [260338c4b2]
Login

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

Overview
Comment:Fix another variant of the "IN (...)" b-tree problem. (CVS 3988)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 260338c4b2b18c9f4da8bc7fe3eda306dcaa4e38
User & Date: danielk1977 2007-05-12 10:41:48.000
Context
2007-05-12
12:08
Make the ANALYZE command robust in the face of malloc() failures. (CVS 3989) (check-in: c08658e1f8 user: drh tags: trunk)
10:41
Fix another variant of the "IN (...)" b-tree problem. (CVS 3988) (check-in: 260338c4b2 user: danielk1977 tags: trunk)
09:30
Fix an obscure b-tree bug that applied to transient trees used for IN(...) expressions. (CVS 3987) (check-in: 96c7232f8b user: danielk1977 tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/btree.c.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
** 2004 April 6
**
** 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.
**
*************************************************************************
** $Id: btree.c,v 1.380 2007/05/12 09:30:47 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"












|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
** 2004 April 6
**
** 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.
**
*************************************************************************
** $Id: btree.c,v 1.381 2007/05/12 10:41:48 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

4506
4507
4508
4509
4510
4511
4512




4513
4514
4515
4516
4517
4518
4519
        if( !pOld->leaf ){
          assert( leafCorrection==0 );
          /* The right pointer of the child page pOld becomes the left
          ** pointer of the divider cell */
          memcpy(apCell[nCell], &pOld->aData[pOld->hdrOffset+8], 4);
        }else{
          assert( leafCorrection==4 );




        }
        nCell++;
      }
    }
  }

  /*







>
>
>
>







4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
        if( !pOld->leaf ){
          assert( leafCorrection==0 );
          /* The right pointer of the child page pOld becomes the left
          ** pointer of the divider cell */
          memcpy(apCell[nCell], &pOld->aData[pOld->hdrOffset+8], 4);
        }else{
          assert( leafCorrection==4 );
          if( szCell[nCell]<4 ){
            /* Do not allow any cells smaller than 4 bytes. */
            szCell[nCell] = 4;
          }
        }
        nCell++;
      }
    }
  }

  /*
Changes to test/in2.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
# 2007 May 12
#
# 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 tests a special case in the b-tree code that can be
# hit by the "IN" operator (or EXISTS, NOT IN, etc.).
#
# $Id: in2.test,v 1.1 2007/05/12 09:30:47 danielk1977 Exp $

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

do_test in2-1 {
  execsql {
    CREATE TABLE a(i INTEGER PRIMARY KEY, a);
  }
} {}



do_test in2-2 {
  db transaction {
    for {set ::ii 0} {$::ii < 1000} {incr ::ii} {
      execsql {INSERT INTO a VALUES($::ii, $::ii)}
    }
    execsql {INSERT INTO a VALUES(1000, '')}

    for {set ::ii 0} {$::ii < 1000} {incr ::ii} {

      execsql {INSERT INTO a VALUES(NULL, 'x' || $::ii)}
    }
  }
} {}

# Each iteration of this loop builds a slightly different b-tree to
# evaluate the "IN (...)" operator in the SQL statement. The contents
# of the b-tree are (in sorted order):
#
#     $::ii integers.
#     a string of zero length.
#     1000 short strings.
#
# Records are inserted in sorted order.
#
# The string of zero-length is stored in a b-tree cell with 3 bytes
# of payload. Moving this cell from a leaf node to a internal node 
# during b-tree balancing was causing an assertion failure. 
#
# This bug only applied to b-trees generated to evaluate IN (..) 
# clauses, as it is impossible for persistent b-trees (SQL tables + 
# indices) to contain cells smaller than 4 bytes.
#
for {set ::ii 3} {$::ii < 1000} {incr ::ii} {
  do_test in2-$::ii {
    execsql {
      SELECT 1 IN (SELECT a FROM a WHERE (i < $::ii) OR (i >= 1000))
    }
  } {1}
}

finish_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
# 2007 May 12
#
# 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 tests a special case in the b-tree code that can be
# hit by the "IN" operator (or EXISTS, NOT IN, etc.).
#
# $Id: in2.test,v 1.2 2007/05/12 10:41:48 danielk1977 Exp $

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

do_test in2-1 {
  execsql {
    CREATE TABLE a(i INTEGER PRIMARY KEY, a);
  }
} {}

set ::N 2000

do_test in2-2 {
  db transaction {
    for {set ::ii 0} {$::ii < $::N} {incr ::ii} {
      execsql {INSERT INTO a VALUES($::ii, $::ii)}
    }
    execsql {INSERT INTO a VALUES(4000, '')}

    for {set ::ii 0} {$::ii < $::N} {incr ::ii} {
      set ::t [format "x%04d" $ii]
      execsql {INSERT INTO a VALUES(NULL, $::t)}
    }
  }
} {}

# Each iteration of this loop builds a slightly different b-tree to
# evaluate the "IN (...)" operator in the SQL statement. The contents
# of the b-tree are (in sorted order):
#
#     $::ii integers.
#     a string of zero length.
#     $::N short strings.
#
# Records are inserted in sorted order.
#
# The string of zero-length is stored in a b-tree cell with 3 bytes
# of payload. Moving this cell from a leaf node to a internal node 
# during b-tree balancing was causing an assertion failure. 
#
# This bug only applied to b-trees generated to evaluate IN (..) 
# clauses, as it is impossible for persistent b-trees (SQL tables + 
# indices) to contain cells smaller than 4 bytes.
#
for {set ::ii 3} {$::ii < $::N} {incr ::ii} {
  do_test in2-$::ii {
    execsql {
      SELECT 1 IN (SELECT a FROM a WHERE (i < $::ii) OR (i >= $::N))
    }
  } {1}
}

finish_test