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 |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
54b84a3ddba9d27814c2f613dd197f69 |
User & Date: | drh 2008-05-27 00:06:02.000 |
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: b5fd8a239d 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: 54b84a3ddb 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: 78f4ba974d user: drh tags: trunk) | |
Changes
Changes to ext/rtree/rtree.c.
︙ | ︙ | |||
8 9 10 11 12 13 14 | ** 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. ** | | | 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | ** 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 |
︙ | ︙ | |||
1076 1077 1078 1079 1080 1081 1082 | ** ** 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; | | | | | 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 | ** ** 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. */ |
︙ | ︙ | |||
1109 1110 1111 1112 1113 1114 1115 1116 | 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; | > > > > > > > > > > > > > > > > > > > > > > > > > > > | | 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 | 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 | # 2008 Feb 19 # # 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. # #*********************************************************************** # # The focus of this file is testing the r-tree extension. # | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # 2008 Feb 19 # # 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. # #*********************************************************************** # # 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 { |
︙ | ︙ | |||
40 41 42 43 44 45 46 | CREATE TABLE t2 (ii, $cols); " } {} do_test rtree2-$nDim.2 { db transaction { for {set ii 0} {$ii < $::NROW} {incr ii} { | | | | | | | | | 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 | 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} { |
︙ | ︙ | |||
96 97 98 99 100 101 102 | } 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} { | | | | | | | 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | } 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] |
︙ | ︙ | |||
137 138 139 140 141 142 143 | DROP TABLE t1; DROP TABLE t2; } } {} } finish_test | < | 137 138 139 140 141 142 143 | 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 |