/ Check-in [54b84a3d]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Fix a bug in rtree that occurs when too many constraints are passed in on a query. (CVS 5162)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 54b84a3ddba9d27814c2f613dd197f691ac549a4
User & Date: drh 2008-05-27 00:06:02
Context
2008-05-27
18:11
Explicitly typedef Pgno as 'u32' instead of 'unsigned int' to remove a few warnings/errors from native x86_64 compile. (CVS 5163) check-in: b5fd8a23 user: shane tags: trunk
00:06
Fix a bug in rtree that occurs when too many constraints are passed in on a query. (CVS 5162) check-in: 54b84a3d user: drh tags: trunk
2008-05-26
20:49
Use %w instead of %q when constructing shadow table names for rtree. (CVS 5161) check-in: 78f4ba97 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
....
1109
1110
1111
1112
1113
1114
1115



























1116
1117
1118
1119
1120
1121
1122
1123
1124
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains code for implementations of the r-tree and r*-tree
** algorithms packaged as an SQLite virtual table module.
**
** $Id: rtree.c,v 1.3 2008/05/26 20:49:03 drh Exp $
*/

#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)

/*
** This file contains an implementation of a couple of different variants
** of the r-tree algorithm. See the README file for further details. The 
................................................................................
**
** The second of each pair of bytes identifies the coordinate column
** to which the constraint applies. The leftmost coordinate column
** is 'a', the second from the left 'b' etc.
*/
static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
  int rc = SQLITE_OK;
  int ii;

  int iIdx = 0;
  char zIdxStr[RTREE_MAX_DIMENSIONS*2+1];
  memset(zIdxStr, 0, RTREE_MAX_DIMENSIONS*2+1);

  assert( pIdxInfo->idxStr==0 );
  for(ii=0; ii<pIdxInfo->nConstraint; ii++){
    struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];

    if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
      /* We have an equality constraint on the rowid. Use strategy 1. */
................................................................................
        case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
        case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
        case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
        case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
        case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
      }
      if( op ){



























        zIdxStr[iIdx++] = op;
        zIdxStr[iIdx++] = (char)(p->iColumn-1) + 'a';
        pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
        pIdxInfo->aConstraintUsage[ii].omit = 1;
      }
    }
  }

  pIdxInfo->idxNum = 2;







|







 







|


|
|







 







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

|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
....
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains code for implementations of the r-tree and r*-tree
** algorithms packaged as an SQLite virtual table module.
**
** $Id: rtree.c,v 1.4 2008/05/27 00:06:02 drh Exp $
*/

#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)

/*
** This file contains an implementation of a couple of different variants
** of the r-tree algorithm. See the README file for further details. The 
................................................................................
**
** The second of each pair of bytes identifies the coordinate column
** to which the constraint applies. The leftmost coordinate column
** is 'a', the second from the left 'b' etc.
*/
static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
  int rc = SQLITE_OK;
  int ii, cCol;

  int iIdx = 0;
  char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
  memset(zIdxStr, 0, sizeof(zIdxStr));

  assert( pIdxInfo->idxStr==0 );
  for(ii=0; ii<pIdxInfo->nConstraint; ii++){
    struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];

    if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
      /* We have an equality constraint on the rowid. Use strategy 1. */
................................................................................
        case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
        case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
        case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
        case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
        case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
      }
      if( op ){
        /* Make sure this particular constraint has not been used before.
        ** If it has been used before, ignore it.
        **
        ** A <= or < can be used if there is a prior >= or >.
        ** A >= or > can be used if there is a prior < or <=.
        ** A <= or < is disqualified if there is a prior <=, <, or ==.
        ** A >= or > is disqualified if there is a prior >=, >, or ==.
        ** A == is disqualifed if there is any prior constraint.
        */
        int j, opmsk;
        static const unsigned char compatible[] = { 0, 0, 1, 1, 2, 2 };
        assert( compatible[RTREE_EQ & 7]==0 );
        assert( compatible[RTREE_LT & 7]==1 );
        assert( compatible[RTREE_LE & 7]==1 );
        assert( compatible[RTREE_GT & 7]==2 );
        assert( compatible[RTREE_GE & 7]==2 );
        cCol = p->iColumn - 1 + 'a';
        opmsk = compatible[op & 7];
        for(j=0; j<iIdx; j+=2){
          if( zIdxStr[j+1]==cCol && (compatible[zIdxStr[j] & 7] & opmsk)!=0 ){
            op = 0;
            break;
          }
        }
      }
      if( op ){
        assert( iIdx<sizeof(zIdxStr)-1 );
        zIdxStr[iIdx++] = op;
        zIdxStr[iIdx++] = cCol;
        pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
        pIdxInfo->aConstraintUsage[ii].omit = 1;
      }
    }
  }

  pIdxInfo->idxNum = 2;

Changes to ext/rtree/rtree2.test.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
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
..
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
...
137
138
139
140
141
142
143
144
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# The focus of this file is testing the r-tree extension.
#
# $Id: rtree2.test,v 1.1 2008/05/26 18:41:54 danielk1977 Exp $
#

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

ifcapable !rtree {
................................................................................
      CREATE TABLE t2 (ii, $cols);
    "
  } {}

  do_test rtree2-$nDim.2 {
    db transaction {
      for {set ii 0} {$ii < $::NROW} {incr ii} {
#puts "Row $ii"
        set values [list]
        for {set jj 0} {$jj<$nDim*2} {incr jj} {
          lappend values [expr int(rand()*1000)]
        }
        set values [join $values ,]
#puts [rtree_treedump db t1]
#puts "INSERT INTO t2 VALUES($ii, $values)"
        set rc [catch {db eval "INSERT INTO t1 VALUES($ii, $values)"}]
        if {$rc} {
          incr ii -1
        } else {
          db eval "INSERT INTO t2 VALUES($ii, $values)"
        }
#if {[rtree_check db t1]} {
#puts [rtree_treedump db t1]
#exit
#}
      }
    }

    set t1 [execsql {SELECT * FROM t1 ORDER BY ii}]
    set t2 [execsql {SELECT * FROM t2 ORDER BY ii}]
    set rc [expr {$t1 eq $t2}]
    if {$rc != 1} {
................................................................................
      }
      set where [join $where " AND "]

      set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"]
      set t2 [execsql "SELECT * FROM t2 WHERE $where ORDER BY ii"]
      set rc [expr {$t1 eq $t2}]
      if {$rc != 1} {
puts $where
        puts $t1
        puts $t2
puts [rtree_treedump db t1]
breakpoint
set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"]
exit
      }
      set rc
    } {1}
  }

  for {set ii 0} {$ii < $::NROW} {incr ii $::NDEL} {
    #puts [rtree_treedump db t1]
................................................................................
      DROP TABLE t1;
      DROP TABLE t2;
    }
  } {}
}

finish_test








|







 







|





|
|






|
|
|
|







 







|


|
|
|
|







 







<
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
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
..
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
...
137
138
139
140
141
142
143

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# The focus of this file is testing the r-tree extension.
#
# $Id: rtree2.test,v 1.2 2008/05/27 00:06:02 drh Exp $
#

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

ifcapable !rtree {
................................................................................
      CREATE TABLE t2 (ii, $cols);
    "
  } {}

  do_test rtree2-$nDim.2 {
    db transaction {
      for {set ii 0} {$ii < $::NROW} {incr ii} {
        #puts "Row $ii"
        set values [list]
        for {set jj 0} {$jj<$nDim*2} {incr jj} {
          lappend values [expr int(rand()*1000)]
        }
        set values [join $values ,]
        #puts [rtree_treedump db t1]
        #puts "INSERT INTO t2 VALUES($ii, $values)"
        set rc [catch {db eval "INSERT INTO t1 VALUES($ii, $values)"}]
        if {$rc} {
          incr ii -1
        } else {
          db eval "INSERT INTO t2 VALUES($ii, $values)"
        }
        #if {[rtree_check db t1]} {
          #puts [rtree_treedump db t1]
          #exit
        #}
      }
    }

    set t1 [execsql {SELECT * FROM t1 ORDER BY ii}]
    set t2 [execsql {SELECT * FROM t2 ORDER BY ii}]
    set rc [expr {$t1 eq $t2}]
    if {$rc != 1} {
................................................................................
      }
      set where [join $where " AND "]

      set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"]
      set t2 [execsql "SELECT * FROM t2 WHERE $where ORDER BY ii"]
      set rc [expr {$t1 eq $t2}]
      if {$rc != 1} {
        #puts $where
        puts $t1
        puts $t2
        #puts [rtree_treedump db t1]
        #breakpoint
        #set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"]
        #exit
      }
      set rc
    } {1}
  }

  for {set ii 0} {$ii < $::NROW} {incr ii $::NDEL} {
    #puts [rtree_treedump db t1]
................................................................................
      DROP TABLE t1;
      DROP TABLE t2;
    }
  } {}
}

finish_test

Added ext/rtree/rtree4.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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
# 2008 May 23
#
# 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.
#
#***********************************************************************
#
# Randomized test cases for the rtree extension.
#
# $Id: rtree4.test,v 1.1 2008/05/27 00:06:02 drh Exp $
#

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

ifcapable !rtree {
  finish_test
  return
}

# Return a floating point number between -X and X.
# 
proc rand {X} {
  return [expr {int((rand()-0.5)*1024.0*$X)/512.0}]
}

# Return a positive floating point number less than or equal to X
#
proc randincr {X} {
  while 1 {
    set r [expr {int(rand()*$X*32.0)/32.0}]
    if {$r>0.0} {return $r}
  }
}

# Scramble the $inlist into a random order.
#
proc scramble {inlist} {
  set y {}
  foreach x $inlist {
    lappend y [list [expr {rand()}] $x]
  }
  set y [lsort $y]
  set outlist {}
  foreach x $y {
    lappend outlist [lindex $x 1]
  }
  return $outlist
}

# Always use the same random seed so that the sequence of tests
# is repeatable.
#
expr {srand(1234)}

# Run these tests for all number of dimensions between 1 and 5.
#
for {set nDim 1} {$nDim<=5} {incr nDim} {

  # Construct an rtree virtual table and an ordinary btree table
  # to mirror it.  The ordinary table should be much slower (since
  # it has to do a full table scan) but should give the exact same
  # answers.
  #
  do_test rtree4-$nDim.1 {
    set clist {}
    set cklist {}
    for {set i 0} {$i<$nDim} {incr i} {
      lappend clist mn$i mx$i
      lappend cklist "mn$i<mx$i"
    }
    db eval "DROP TABLE IF EXISTS rx"
    db eval "DROP TABLE IF EXISTS bx"
    db eval "CREATE VIRTUAL TABLE rx USING rtree(id, [join $clist ,])"
    db eval "CREATE TABLE bx(id INTEGER PRIMARY KEY,\
                [join $clist ,], CHECK( [join $cklist { AND }] ))"
  } {}

  # Do many insertions of small objects.  Do both overlapping and
  # contained-within queries after each insert to verify that all
  # is well.
  #
  unset -nocomplain where
  for {set i 1} {$i<2500} {incr i} {
    # Do a random insert
    #
    do_test rtree-$nDim.2.$i.1 {
      set vlist {}
      for {set j 0} {$j<$nDim} {incr j} {
        set mn [rand 10000]
        set mx [expr {$mn+[randincr 50]}]
        lappend vlist $mn $mx
      }
      db eval "INSERT INTO rx VALUES(NULL, [join $vlist ,])"
      db eval "INSERT INTO bx VALUES(NULL, [join $vlist ,])"
    } {}

    # Do a contained-in query on all dimensions
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mn$j>=$mn mx$j<=$mx
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.2 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do an overlaps query on all dimensions
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mx$j>=$mn mn$j<=$mx
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.3 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do a contained-in query with surplus contraints at the beginning.
    # This should force a full-table scan on the rtree.
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      lappend where mn$j>-10000 mx$j<10000
    }
    for {set j 0} {$j<$nDim} {incr j} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mn$j>=$mn mx$j<=$mx
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.3 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do an overlaps query with surplus contraints at the beginning.
    # This should force a full-table scan on the rtree.
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      lappend where mn$j>=-10000 mx$j<=10000
    }
    for {set j 0} {$j<$nDim} {incr j} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mx$j>$mn mn$j<$mx
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.4 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do a contained-in query with surplus contraints at the end
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mn$j>=$mn mx$j<$mx
    }
    for {set j [expr {$nDim-1}]} {$j>=0} {incr j -1} {
      lappend where mn$j>=-10000 mx$j<10000
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.5 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do an overlaps query with surplus contraints at the end
    #
    set where {}
    for {set j [expr {$nDim-1}]} {$j>=0} {incr j -1} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mx$j>$mn mn$j<=$mx
    }
    for {set j 0} {$j<$nDim} {incr j} {
      lappend where mx$j>-10000 mn$j<=10000
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.6 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do a contained-in query with surplus contraints where the 
    # constraints appear in a random order.
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      set mn1 [rand 10000]
      set mn2 [expr {$mn1+[randincr 100]}]
      set mx1 [expr {$mn2+[randincr 400]}]
      set mx2 [expr {$mx1+[randincr 100]}]
      lappend where mn$j>=$mn1 mn$j>$mn2 mx$j<$mx1 mx$j<=$mx2
    }
    set where "WHERE [join [scramble $where] { AND }]"
    do_test rtree-$nDim.2.$i.7 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do an overlaps query with surplus contraints where the
    # constraints appear in a random order.
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      set mn1 [rand 10000]
      set mn2 [expr {$mn1+[randincr 100]}]
      set mx1 [expr {$mn2+[randincr 400]}]
      set mx2 [expr {$mx1+[randincr 100]}]
      lappend where mx$j>=$mn1 mx$j>$mn2 mn$j<$mx1 mn$j<=$mx2
    }
    set where "WHERE [join [scramble $where] { AND }]"
    do_test rtree-$nDim.2.$i.8 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

  }

}

finish_test