/ Hex Artifact Content
Login

Artifact 11724f766a74f48710998cdd7552cec140c55bf9:


0000: 23 20 32 30 30 38 20 4d 61 79 20 32 33 0a 23 0a  # 2008 May 23.#.
0010: 23 20 54 68 65 20 61 75 74 68 6f 72 20 64 69 73  # The author dis
0020: 63 6c 61 69 6d 73 20 63 6f 70 79 72 69 67 68 74  claims copyright
0030: 20 74 6f 20 74 68 69 73 20 73 6f 75 72 63 65 20   to this source 
0040: 63 6f 64 65 2e 20 20 49 6e 20 70 6c 61 63 65 20  code.  In place 
0050: 6f 66 0a 23 20 61 20 6c 65 67 61 6c 20 6e 6f 74  of.# a legal not
0060: 69 63 65 2c 20 68 65 72 65 20 69 73 20 61 20 62  ice, here is a b
0070: 6c 65 73 73 69 6e 67 3a 0a 23 0a 23 20 20 20 20  lessing:.#.#    
0080: 4d 61 79 20 79 6f 75 20 64 6f 20 67 6f 6f 64 20  May you do good 
0090: 61 6e 64 20 6e 6f 74 20 65 76 69 6c 2e 0a 23 20  and not evil..# 
00a0: 20 20 20 4d 61 79 20 79 6f 75 20 66 69 6e 64 20     May you find 
00b0: 66 6f 72 67 69 76 65 6e 65 73 73 20 66 6f 72 20  forgiveness for 
00c0: 79 6f 75 72 73 65 6c 66 20 61 6e 64 20 66 6f 72  yourself and for
00d0: 67 69 76 65 20 6f 74 68 65 72 73 2e 0a 23 20 20  give others..#  
00e0: 20 20 4d 61 79 20 79 6f 75 20 73 68 61 72 65 20    May you share 
00f0: 66 72 65 65 6c 79 2c 20 6e 65 76 65 72 20 74 61  freely, never ta
0100: 6b 69 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20 79  king more than y
0110: 6f 75 20 67 69 76 65 2e 0a 23 0a 23 2a 2a 2a 2a  ou give..#.#****
0120: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 0a 23 0a 23 20 52 61 6e 64 6f 6d 69 7a  ***.#.# Randomiz
0170: 65 64 20 74 65 73 74 20 63 61 73 65 73 20 66 6f  ed test cases fo
0180: 72 20 74 68 65 20 72 74 72 65 65 20 65 78 74 65  r the rtree exte
0190: 6e 73 69 6f 6e 2e 0a 23 0a 23 20 24 49 64 3a 20  nsion..#.# $Id: 
01a0: 72 74 72 65 65 34 2e 74 65 73 74 2c 76 20 31 2e  rtree4.test,v 1.
01b0: 33 20 32 30 30 38 2f 30 36 2f 32 33 20 31 35 3a  3 2008/06/23 15:
01c0: 35 35 3a 35 32 20 64 61 6e 69 65 6c 6b 31 39 37  55:52 danielk197
01d0: 37 20 45 78 70 20 24 0a 23 0a 0a 69 66 20 7b 21  7 Exp $.#..if {!
01e0: 5b 69 6e 66 6f 20 65 78 69 73 74 73 20 74 65 73  [info exists tes
01f0: 74 64 69 72 5d 7d 20 7b 0a 20 20 73 65 74 20 74  tdir]} {.  set t
0200: 65 73 74 64 69 72 20 5b 66 69 6c 65 20 6a 6f 69  estdir [file joi
0210: 6e 20 5b 66 69 6c 65 20 64 69 72 6e 61 6d 65 20  n [file dirname 
0220: 24 61 72 67 76 30 5d 20 2e 2e 20 2e 2e 20 74 65  $argv0] .. .. te
0230: 73 74 5d 0a 7d 20 0a 73 6f 75 72 63 65 20 24 74  st].} .source $t
0240: 65 73 74 64 69 72 2f 74 65 73 74 65 72 2e 74 63  estdir/tester.tc
0250: 6c 0a 0a 69 66 63 61 70 61 62 6c 65 20 21 72 74  l..ifcapable !rt
0260: 72 65 65 20 7b 0a 20 20 66 69 6e 69 73 68 5f 74  ree {.  finish_t
0270: 65 73 74 0a 20 20 72 65 74 75 72 6e 0a 7d 0a 0a  est.  return.}..
0280: 73 65 74 20 3a 3a 4e 52 4f 57 20 32 35 30 30 0a  set ::NROW 2500.
0290: 69 66 20 7b 5b 69 6e 66 6f 20 65 78 69 73 74 73  if {[info exists
02a0: 20 49 53 51 55 49 43 4b 5d 20 26 26 20 24 49 53   ISQUICK] && $IS
02b0: 51 55 49 43 4b 7d 20 7b 0a 20 20 73 65 74 20 3a  QUICK} {.  set :
02c0: 3a 4e 52 4f 57 20 32 35 30 0a 7d 0a 0a 23 20 52  :NROW 250.}..# R
02d0: 65 74 75 72 6e 20 61 20 66 6c 6f 61 74 69 6e 67  eturn a floating
02e0: 20 70 6f 69 6e 74 20 6e 75 6d 62 65 72 20 62 65   point number be
02f0: 74 77 65 65 6e 20 2d 58 20 61 6e 64 20 58 2e 0a  tween -X and X..
0300: 23 20 0a 70 72 6f 63 20 72 61 6e 64 20 7b 58 7d  # .proc rand {X}
0310: 20 7b 0a 20 20 72 65 74 75 72 6e 20 5b 65 78 70   {.  return [exp
0320: 72 20 7b 69 6e 74 28 28 72 61 6e 64 28 29 2d 30  r {int((rand()-0
0330: 2e 35 29 2a 31 30 32 34 2e 30 2a 24 58 29 2f 35  .5)*1024.0*$X)/5
0340: 31 32 2e 30 7d 5d 0a 7d 0a 0a 23 20 52 65 74 75  12.0}].}..# Retu
0350: 72 6e 20 61 20 70 6f 73 69 74 69 76 65 20 66 6c  rn a positive fl
0360: 6f 61 74 69 6e 67 20 70 6f 69 6e 74 20 6e 75 6d  oating point num
0370: 62 65 72 20 6c 65 73 73 20 74 68 61 6e 20 6f 72  ber less than or
0380: 20 65 71 75 61 6c 20 74 6f 20 58 0a 23 0a 70 72   equal to X.#.pr
0390: 6f 63 20 72 61 6e 64 69 6e 63 72 20 7b 58 7d 20  oc randincr {X} 
03a0: 7b 0a 20 20 77 68 69 6c 65 20 31 20 7b 0a 20 20  {.  while 1 {.  
03b0: 20 20 73 65 74 20 72 20 5b 65 78 70 72 20 7b 69    set r [expr {i
03c0: 6e 74 28 72 61 6e 64 28 29 2a 24 58 2a 33 32 2e  nt(rand()*$X*32.
03d0: 30 29 2f 33 32 2e 30 7d 5d 0a 20 20 20 20 69 66  0)/32.0}].    if
03e0: 20 7b 24 72 3e 30 2e 30 7d 20 7b 72 65 74 75 72   {$r>0.0} {retur
03f0: 6e 20 24 72 7d 0a 20 20 7d 0a 7d 0a 0a 23 20 53  n $r}.  }.}..# S
0400: 63 72 61 6d 62 6c 65 20 74 68 65 20 24 69 6e 6c  cramble the $inl
0410: 69 73 74 20 69 6e 74 6f 20 61 20 72 61 6e 64 6f  ist into a rando
0420: 6d 20 6f 72 64 65 72 2e 0a 23 0a 70 72 6f 63 20  m order..#.proc 
0430: 73 63 72 61 6d 62 6c 65 20 7b 69 6e 6c 69 73 74  scramble {inlist
0440: 7d 20 7b 0a 20 20 73 65 74 20 79 20 7b 7d 0a 20  } {.  set y {}. 
0450: 20 66 6f 72 65 61 63 68 20 78 20 24 69 6e 6c 69   foreach x $inli
0460: 73 74 20 7b 0a 20 20 20 20 6c 61 70 70 65 6e 64  st {.    lappend
0470: 20 79 20 5b 6c 69 73 74 20 5b 65 78 70 72 20 7b   y [list [expr {
0480: 72 61 6e 64 28 29 7d 5d 20 24 78 5d 0a 20 20 7d  rand()}] $x].  }
0490: 0a 20 20 73 65 74 20 79 20 5b 6c 73 6f 72 74 20  .  set y [lsort 
04a0: 24 79 5d 0a 20 20 73 65 74 20 6f 75 74 6c 69 73  $y].  set outlis
04b0: 74 20 7b 7d 0a 20 20 66 6f 72 65 61 63 68 20 78  t {}.  foreach x
04c0: 20 24 79 20 7b 0a 20 20 20 20 6c 61 70 70 65 6e   $y {.    lappen
04d0: 64 20 6f 75 74 6c 69 73 74 20 5b 6c 69 6e 64 65  d outlist [linde
04e0: 78 20 24 78 20 31 5d 0a 20 20 7d 0a 20 20 72 65  x $x 1].  }.  re
04f0: 74 75 72 6e 20 24 6f 75 74 6c 69 73 74 0a 7d 0a  turn $outlist.}.
0500: 0a 23 20 41 6c 77 61 79 73 20 75 73 65 20 74 68  .# Always use th
0510: 65 20 73 61 6d 65 20 72 61 6e 64 6f 6d 20 73 65  e same random se
0520: 65 64 20 73 6f 20 74 68 61 74 20 74 68 65 20 73  ed so that the s
0530: 65 71 75 65 6e 63 65 20 6f 66 20 74 65 73 74 73  equence of tests
0540: 0a 23 20 69 73 20 72 65 70 65 61 74 61 62 6c 65  .# is repeatable
0550: 2e 0a 23 0a 65 78 70 72 20 7b 73 72 61 6e 64 28  ..#.expr {srand(
0560: 31 32 33 34 29 7d 0a 0a 23 20 52 75 6e 20 74 68  1234)}..# Run th
0570: 65 73 65 20 74 65 73 74 73 20 66 6f 72 20 61 6c  ese tests for al
0580: 6c 20 6e 75 6d 62 65 72 20 6f 66 20 64 69 6d 65  l number of dime
0590: 6e 73 69 6f 6e 73 20 62 65 74 77 65 65 6e 20 31  nsions between 1
05a0: 20 61 6e 64 20 35 2e 0a 23 0a 66 6f 72 20 7b 73   and 5..#.for {s
05b0: 65 74 20 6e 44 69 6d 20 31 7d 20 7b 24 6e 44 69  et nDim 1} {$nDi
05c0: 6d 3c 3d 35 7d 20 7b 69 6e 63 72 20 6e 44 69 6d  m<=5} {incr nDim
05d0: 7d 20 7b 0a 0a 20 20 23 20 43 6f 6e 73 74 72 75  } {..  # Constru
05e0: 63 74 20 61 6e 20 72 74 72 65 65 20 76 69 72 74  ct an rtree virt
05f0: 75 61 6c 20 74 61 62 6c 65 20 61 6e 64 20 61 6e  ual table and an
0600: 20 6f 72 64 69 6e 61 72 79 20 62 74 72 65 65 20   ordinary btree 
0610: 74 61 62 6c 65 0a 20 20 23 20 74 6f 20 6d 69 72  table.  # to mir
0620: 72 6f 72 20 69 74 2e 20 20 54 68 65 20 6f 72 64  ror it.  The ord
0630: 69 6e 61 72 79 20 74 61 62 6c 65 20 73 68 6f 75  inary table shou
0640: 6c 64 20 62 65 20 6d 75 63 68 20 73 6c 6f 77 65  ld be much slowe
0650: 72 20 28 73 69 6e 63 65 0a 20 20 23 20 69 74 20  r (since.  # it 
0660: 68 61 73 20 74 6f 20 64 6f 20 61 20 66 75 6c 6c  has to do a full
0670: 20 74 61 62 6c 65 20 73 63 61 6e 29 20 62 75 74   table scan) but
0680: 20 73 68 6f 75 6c 64 20 67 69 76 65 20 74 68 65   should give the
0690: 20 65 78 61 63 74 20 73 61 6d 65 0a 20 20 23 20   exact same.  # 
06a0: 61 6e 73 77 65 72 73 2e 0a 20 20 23 0a 20 20 64  answers..  #.  d
06b0: 6f 5f 74 65 73 74 20 72 74 72 65 65 34 2d 24 6e  o_test rtree4-$n
06c0: 44 69 6d 2e 31 20 7b 0a 20 20 20 20 73 65 74 20  Dim.1 {.    set 
06d0: 63 6c 69 73 74 20 7b 7d 0a 20 20 20 20 73 65 74  clist {}.    set
06e0: 20 63 6b 6c 69 73 74 20 7b 7d 0a 20 20 20 20 66   cklist {}.    f
06f0: 6f 72 20 7b 73 65 74 20 69 20 30 7d 20 7b 24 69  or {set i 0} {$i
0700: 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 69 7d  <$nDim} {incr i}
0710: 20 7b 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64   {.      lappend
0720: 20 63 6c 69 73 74 20 6d 6e 24 69 20 6d 78 24 69   clist mn$i mx$i
0730: 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20 63  .      lappend c
0740: 6b 6c 69 73 74 20 22 6d 6e 24 69 3c 6d 78 24 69  klist "mn$i<mx$i
0750: 22 0a 20 20 20 20 7d 0a 20 20 20 20 64 62 20 65  ".    }.    db e
0760: 76 61 6c 20 22 44 52 4f 50 20 54 41 42 4c 45 20  val "DROP TABLE 
0770: 49 46 20 45 58 49 53 54 53 20 72 78 22 0a 20 20  IF EXISTS rx".  
0780: 20 20 64 62 20 65 76 61 6c 20 22 44 52 4f 50 20    db eval "DROP 
0790: 54 41 42 4c 45 20 49 46 20 45 58 49 53 54 53 20  TABLE IF EXISTS 
07a0: 62 78 22 0a 20 20 20 20 64 62 20 65 76 61 6c 20  bx".    db eval 
07b0: 22 43 52 45 41 54 45 20 56 49 52 54 55 41 4c 20  "CREATE VIRTUAL 
07c0: 54 41 42 4c 45 20 72 78 20 55 53 49 4e 47 20 72  TABLE rx USING r
07d0: 74 72 65 65 28 69 64 2c 20 5b 6a 6f 69 6e 20 24  tree(id, [join $
07e0: 63 6c 69 73 74 20 2c 5d 29 22 0a 20 20 20 20 64  clist ,])".    d
07f0: 62 20 65 76 61 6c 20 22 43 52 45 41 54 45 20 54  b eval "CREATE T
0800: 41 42 4c 45 20 62 78 28 69 64 20 49 4e 54 45 47  ABLE bx(id INTEG
0810: 45 52 20 50 52 49 4d 41 52 59 20 4b 45 59 2c 5c  ER PRIMARY KEY,\
0820: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
0830: 20 5b 6a 6f 69 6e 20 24 63 6c 69 73 74 20 2c 5d   [join $clist ,]
0840: 2c 20 43 48 45 43 4b 28 20 5b 6a 6f 69 6e 20 24  , CHECK( [join $
0850: 63 6b 6c 69 73 74 20 7b 20 41 4e 44 20 7d 5d 20  cklist { AND }] 
0860: 29 29 22 0a 20 20 7d 20 7b 7d 0a 0a 20 20 23 20  ))".  } {}..  # 
0870: 44 6f 20 6d 61 6e 79 20 69 6e 73 65 72 74 69 6f  Do many insertio
0880: 6e 73 20 6f 66 20 73 6d 61 6c 6c 20 6f 62 6a 65  ns of small obje
0890: 63 74 73 2e 20 20 44 6f 20 62 6f 74 68 20 6f 76  cts.  Do both ov
08a0: 65 72 6c 61 70 70 69 6e 67 20 61 6e 64 0a 20 20  erlapping and.  
08b0: 23 20 63 6f 6e 74 61 69 6e 65 64 2d 77 69 74 68  # contained-with
08c0: 69 6e 20 71 75 65 72 69 65 73 20 61 66 74 65 72  in queries after
08d0: 20 65 61 63 68 20 69 6e 73 65 72 74 20 74 6f 20   each insert to 
08e0: 76 65 72 69 66 79 20 74 68 61 74 20 61 6c 6c 0a  verify that all.
08f0: 20 20 23 20 69 73 20 77 65 6c 6c 2e 0a 20 20 23    # is well..  #
0900: 0a 20 20 75 6e 73 65 74 20 2d 6e 6f 63 6f 6d 70  .  unset -nocomp
0910: 6c 61 69 6e 20 77 68 65 72 65 0a 20 20 66 6f 72  lain where.  for
0920: 20 7b 73 65 74 20 69 20 31 7d 20 7b 24 69 3c 24   {set i 1} {$i<$
0930: 3a 3a 4e 52 4f 57 7d 20 7b 69 6e 63 72 20 69 7d  ::NROW} {incr i}
0940: 20 7b 0a 20 20 20 20 23 20 44 6f 20 61 20 72 61   {.    # Do a ra
0950: 6e 64 6f 6d 20 69 6e 73 65 72 74 0a 20 20 20 20  ndom insert.    
0960: 23 0a 20 20 20 20 64 6f 5f 74 65 73 74 20 72 74  #.    do_test rt
0970: 72 65 65 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 31  ree-$nDim.2.$i.1
0980: 20 7b 0a 20 20 20 20 20 20 73 65 74 20 76 6c 69   {.      set vli
0990: 73 74 20 7b 7d 0a 20 20 20 20 20 20 66 6f 72 20  st {}.      for 
09a0: 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e  {set j 0} {$j<$n
09b0: 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a  Dim} {incr j} {.
09c0: 20 20 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b          set mn [
09d0: 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20  rand 10000].    
09e0: 20 20 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72      set mx [expr
09f0: 20 7b 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20   {$mn+[randincr 
0a00: 35 30 5d 7d 5d 0a 20 20 20 20 20 20 20 20 6c 61  50]}].        la
0a10: 70 70 65 6e 64 20 76 6c 69 73 74 20 24 6d 6e 20  ppend vlist $mn 
0a20: 24 6d 78 0a 20 20 20 20 20 20 7d 0a 20 20 20 20  $mx.      }.    
0a30: 20 20 64 62 20 65 76 61 6c 20 22 49 4e 53 45 52    db eval "INSER
0a40: 54 20 49 4e 54 4f 20 72 78 20 56 41 4c 55 45 53  T INTO rx VALUES
0a50: 28 4e 55 4c 4c 2c 20 5b 6a 6f 69 6e 20 24 76 6c  (NULL, [join $vl
0a60: 69 73 74 20 2c 5d 29 22 0a 20 20 20 20 20 20 64  ist ,])".      d
0a70: 62 20 65 76 61 6c 20 22 49 4e 53 45 52 54 20 49  b eval "INSERT I
0a80: 4e 54 4f 20 62 78 20 56 41 4c 55 45 53 28 4e 55  NTO bx VALUES(NU
0a90: 4c 4c 2c 20 5b 6a 6f 69 6e 20 24 76 6c 69 73 74  LL, [join $vlist
0aa0: 20 2c 5d 29 22 0a 20 20 20 20 7d 20 7b 7d 0a 0a   ,])".    } {}..
0ab0: 20 20 20 20 23 20 44 6f 20 61 20 63 6f 6e 74 61      # Do a conta
0ac0: 69 6e 65 64 2d 69 6e 20 71 75 65 72 79 20 6f 6e  ined-in query on
0ad0: 20 61 6c 6c 20 64 69 6d 65 6e 73 69 6f 6e 73 0a   all dimensions.
0ae0: 20 20 20 20 23 0a 20 20 20 20 73 65 74 20 77 68      #.    set wh
0af0: 65 72 65 20 7b 7d 0a 20 20 20 20 66 6f 72 20 7b  ere {}.    for {
0b00: 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44  set j 0} {$j<$nD
0b10: 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20  im} {incr j} {. 
0b20: 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72 61 6e       set mn [ran
0b30: 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20 20 73  d 10000].      s
0b40: 65 74 20 6d 78 20 5b 65 78 70 72 20 7b 24 6d 6e  et mx [expr {$mn
0b50: 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30 30 5d 7d  +[randincr 500]}
0b60: 5d 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20  ].      lappend 
0b70: 77 68 65 72 65 20 6d 6e 24 6a 3e 3d 24 6d 6e 20  where mn$j>=$mn 
0b80: 6d 78 24 6a 3c 3d 24 6d 78 0a 20 20 20 20 7d 0a  mx$j<=$mx.    }.
0b90: 20 20 20 20 73 65 74 20 77 68 65 72 65 20 22 57      set where "W
0ba0: 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72  HERE [join $wher
0bb0: 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20  e { AND }]".    
0bc0: 64 6f 5f 74 65 73 74 20 72 74 72 65 65 2d 24 6e  do_test rtree-$n
0bd0: 44 69 6d 2e 32 2e 24 69 2e 32 20 7b 0a 20 20 20  Dim.2.$i.2 {.   
0be0: 20 20 20 6c 69 73 74 20 24 77 68 65 72 65 20 5b     list $where [
0bf0: 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20  db eval "SELECT 
0c00: 69 64 20 46 52 4f 4d 20 72 78 20 24 77 68 65 72  id FROM rx $wher
0c10: 65 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d 0a  e ORDER BY id"].
0c20: 20 20 20 20 7d 20 5b 6c 69 73 74 20 24 77 68 65      } [list $whe
0c30: 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c  re [db eval "SEL
0c40: 45 43 54 20 69 64 20 46 52 4f 4d 20 62 78 20 24  ECT id FROM bx $
0c50: 77 68 65 72 65 20 4f 52 44 45 52 20 42 59 20 69  where ORDER BY i
0c60: 64 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f 20 61  d"]]..    # Do a
0c70: 6e 20 6f 76 65 72 6c 61 70 73 20 71 75 65 72 79  n overlaps query
0c80: 20 6f 6e 20 61 6c 6c 20 64 69 6d 65 6e 73 69 6f   on all dimensio
0c90: 6e 73 0a 20 20 20 20 23 0a 20 20 20 20 73 65 74  ns.    #.    set
0ca0: 20 77 68 65 72 65 20 7b 7d 0a 20 20 20 20 66 6f   where {}.    fo
0cb0: 72 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c  r {set j 0} {$j<
0cc0: 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20  $nDim} {incr j} 
0cd0: 7b 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b  {.      set mn [
0ce0: 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20  rand 10000].    
0cf0: 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20 7b    set mx [expr {
0d00: 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30  $mn+[randincr 50
0d10: 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70 65  0]}].      lappe
0d20: 6e 64 20 77 68 65 72 65 20 6d 78 24 6a 3e 3d 24  nd where mx$j>=$
0d30: 6d 6e 20 6d 6e 24 6a 3c 3d 24 6d 78 0a 20 20 20  mn mn$j<=$mx.   
0d40: 20 7d 0a 20 20 20 20 73 65 74 20 77 68 65 72 65   }.    set where
0d50: 20 22 57 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77   "WHERE [join $w
0d60: 68 65 72 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20  here { AND }]". 
0d70: 20 20 20 64 6f 5f 74 65 73 74 20 72 74 72 65 65     do_test rtree
0d80: 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 33 20 7b 0a  -$nDim.2.$i.3 {.
0d90: 20 20 20 20 20 20 6c 69 73 74 20 24 77 68 65 72        list $wher
0da0: 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45  e [db eval "SELE
0db0: 43 54 20 69 64 20 46 52 4f 4d 20 72 78 20 24 77  CT id FROM rx $w
0dc0: 68 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64  here ORDER BY id
0dd0: 22 5d 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20 24  "].    } [list $
0de0: 77 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22  where [db eval "
0df0: 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 62  SELECT id FROM b
0e00: 78 20 24 77 68 65 72 65 20 4f 52 44 45 52 20 42  x $where ORDER B
0e10: 59 20 69 64 22 5d 5d 0a 0a 20 20 20 20 23 20 44  Y id"]]..    # D
0e20: 6f 20 61 20 63 6f 6e 74 61 69 6e 65 64 2d 69 6e  o a contained-in
0e30: 20 71 75 65 72 79 20 77 69 74 68 20 73 75 72 70   query with surp
0e40: 6c 75 73 20 63 6f 6e 74 72 61 69 6e 74 73 20 61  lus contraints a
0e50: 74 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 2e  t the beginning.
0e60: 0a 20 20 20 20 23 20 54 68 69 73 20 73 68 6f 75  .    # This shou
0e70: 6c 64 20 66 6f 72 63 65 20 61 20 66 75 6c 6c 2d  ld force a full-
0e80: 74 61 62 6c 65 20 73 63 61 6e 20 6f 6e 20 74 68  table scan on th
0e90: 65 20 72 74 72 65 65 2e 0a 20 20 20 20 23 0a 20  e rtree..    #. 
0ea0: 20 20 20 73 65 74 20 77 68 65 72 65 20 7b 7d 0a     set where {}.
0eb0: 20 20 20 20 66 6f 72 20 7b 73 65 74 20 6a 20 30      for {set j 0
0ec0: 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e  } {$j<$nDim} {in
0ed0: 63 72 20 6a 7d 20 7b 0a 20 20 20 20 20 20 6c 61  cr j} {.      la
0ee0: 70 70 65 6e 64 20 77 68 65 72 65 20 6d 6e 24 6a  ppend where mn$j
0ef0: 3e 2d 31 30 30 30 30 20 6d 78 24 6a 3c 31 30 30  >-10000 mx$j<100
0f00: 30 30 0a 20 20 20 20 7d 0a 20 20 20 20 66 6f 72  00.    }.    for
0f10: 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24   {set j 0} {$j<$
0f20: 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b  nDim} {incr j} {
0f30: 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72  .      set mn [r
0f40: 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20  and 10000].     
0f50: 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20 7b 24   set mx [expr {$
0f60: 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30 30  mn+[randincr 500
0f70: 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70 65 6e  ]}].      lappen
0f80: 64 20 77 68 65 72 65 20 6d 6e 24 6a 3e 3d 24 6d  d where mn$j>=$m
0f90: 6e 20 6d 78 24 6a 3c 3d 24 6d 78 0a 20 20 20 20  n mx$j<=$mx.    
0fa0: 7d 0a 20 20 20 20 73 65 74 20 77 68 65 72 65 20  }.    set where 
0fb0: 22 57 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77 68  "WHERE [join $wh
0fc0: 65 72 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20 20  ere { AND }]".  
0fd0: 20 20 64 6f 5f 74 65 73 74 20 72 74 72 65 65 2d    do_test rtree-
0fe0: 24 6e 44 69 6d 2e 32 2e 24 69 2e 33 20 7b 0a 20  $nDim.2.$i.3 {. 
0ff0: 20 20 20 20 20 6c 69 73 74 20 24 77 68 65 72 65       list $where
1000: 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43   [db eval "SELEC
1010: 54 20 69 64 20 46 52 4f 4d 20 72 78 20 24 77 68  T id FROM rx $wh
1020: 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22  ere ORDER BY id"
1030: 5d 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20 24 77  ].    } [list $w
1040: 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53  here [db eval "S
1050: 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 62 78  ELECT id FROM bx
1060: 20 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59   $where ORDER BY
1070: 20 69 64 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f   id"]]..    # Do
1080: 20 61 6e 20 6f 76 65 72 6c 61 70 73 20 71 75 65   an overlaps que
1090: 72 79 20 77 69 74 68 20 73 75 72 70 6c 75 73 20  ry with surplus 
10a0: 63 6f 6e 74 72 61 69 6e 74 73 20 61 74 20 74 68  contraints at th
10b0: 65 20 62 65 67 69 6e 6e 69 6e 67 2e 0a 20 20 20  e beginning..   
10c0: 20 23 20 54 68 69 73 20 73 68 6f 75 6c 64 20 66   # This should f
10d0: 6f 72 63 65 20 61 20 66 75 6c 6c 2d 74 61 62 6c  orce a full-tabl
10e0: 65 20 73 63 61 6e 20 6f 6e 20 74 68 65 20 72 74  e scan on the rt
10f0: 72 65 65 2e 0a 20 20 20 20 23 0a 20 20 20 20 73  ree..    #.    s
1100: 65 74 20 77 68 65 72 65 20 7b 7d 0a 20 20 20 20  et where {}.    
1110: 66 6f 72 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24  for {set j 0} {$
1120: 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a  j<$nDim} {incr j
1130: 7d 20 7b 0a 20 20 20 20 20 20 6c 61 70 70 65 6e  } {.      lappen
1140: 64 20 77 68 65 72 65 20 6d 6e 24 6a 3e 3d 2d 31  d where mn$j>=-1
1150: 30 30 30 30 20 6d 78 24 6a 3c 3d 31 30 30 30 30  0000 mx$j<=10000
1160: 0a 20 20 20 20 7d 0a 20 20 20 20 66 6f 72 20 7b  .    }.    for {
1170: 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44  set j 0} {$j<$nD
1180: 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20  im} {incr j} {. 
1190: 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72 61 6e       set mn [ran
11a0: 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20 20 73  d 10000].      s
11b0: 65 74 20 6d 78 20 5b 65 78 70 72 20 7b 24 6d 6e  et mx [expr {$mn
11c0: 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30 30 5d 7d  +[randincr 500]}
11d0: 5d 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20  ].      lappend 
11e0: 77 68 65 72 65 20 6d 78 24 6a 3e 24 6d 6e 20 6d  where mx$j>$mn m
11f0: 6e 24 6a 3c 24 6d 78 0a 20 20 20 20 7d 0a 20 20  n$j<$mx.    }.  
1200: 20 20 73 65 74 20 77 68 65 72 65 20 22 57 48 45    set where "WHE
1210: 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72 65 20  RE [join $where 
1220: 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20 64 6f  { AND }]".    do
1230: 5f 74 65 73 74 20 72 74 72 65 65 2d 24 6e 44 69  _test rtree-$nDi
1240: 6d 2e 32 2e 24 69 2e 34 20 7b 0a 20 20 20 20 20  m.2.$i.4 {.     
1250: 20 6c 69 73 74 20 24 77 68 65 72 65 20 5b 64 62   list $where [db
1260: 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20 69 64   eval "SELECT id
1270: 20 46 52 4f 4d 20 72 78 20 24 77 68 65 72 65 20   FROM rx $where 
1280: 4f 52 44 45 52 20 42 59 20 69 64 22 5d 0a 20 20  ORDER BY id"].  
1290: 20 20 7d 20 5b 6c 69 73 74 20 24 77 68 65 72 65    } [list $where
12a0: 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43   [db eval "SELEC
12b0: 54 20 69 64 20 46 52 4f 4d 20 62 78 20 24 77 68  T id FROM bx $wh
12c0: 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22  ere ORDER BY id"
12d0: 5d 5d 0a 0a 20 20 20 20 23 20 44 6f 20 61 20 63  ]]..    # Do a c
12e0: 6f 6e 74 61 69 6e 65 64 2d 69 6e 20 71 75 65 72  ontained-in quer
12f0: 79 20 77 69 74 68 20 73 75 72 70 6c 75 73 20 63  y with surplus c
1300: 6f 6e 74 72 61 69 6e 74 73 20 61 74 20 74 68 65  ontraints at the
1310: 20 65 6e 64 0a 20 20 20 20 23 0a 20 20 20 20 73   end.    #.    s
1320: 65 74 20 77 68 65 72 65 20 7b 7d 0a 20 20 20 20  et where {}.    
1330: 66 6f 72 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24  for {set j 0} {$
1340: 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a  j<$nDim} {incr j
1350: 7d 20 7b 0a 20 20 20 20 20 20 73 65 74 20 6d 6e  } {.      set mn
1360: 20 5b 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20   [rand 10000].  
1370: 20 20 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72      set mx [expr
1380: 20 7b 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20   {$mn+[randincr 
1390: 35 30 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70  500]}].      lap
13a0: 70 65 6e 64 20 77 68 65 72 65 20 6d 6e 24 6a 3e  pend where mn$j>
13b0: 3d 24 6d 6e 20 6d 78 24 6a 3c 24 6d 78 0a 20 20  =$mn mx$j<$mx.  
13c0: 20 20 7d 0a 20 20 20 20 66 6f 72 20 7b 73 65 74    }.    for {set
13d0: 20 6a 20 5b 65 78 70 72 20 7b 24 6e 44 69 6d 2d   j [expr {$nDim-
13e0: 31 7d 5d 7d 20 7b 24 6a 3e 3d 30 7d 20 7b 69 6e  1}]} {$j>=0} {in
13f0: 63 72 20 6a 20 2d 31 7d 20 7b 0a 20 20 20 20 20  cr j -1} {.     
1400: 20 6c 61 70 70 65 6e 64 20 77 68 65 72 65 20 6d   lappend where m
1410: 6e 24 6a 3e 3d 2d 31 30 30 30 30 20 6d 78 24 6a  n$j>=-10000 mx$j
1420: 3c 31 30 30 30 30 0a 20 20 20 20 7d 0a 20 20 20  <10000.    }.   
1430: 20 73 65 74 20 77 68 65 72 65 20 22 57 48 45 52   set where "WHER
1440: 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72 65 20 7b  E [join $where {
1450: 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20 64 6f 5f   AND }]".    do_
1460: 74 65 73 74 20 72 74 72 65 65 2d 24 6e 44 69 6d  test rtree-$nDim
1470: 2e 32 2e 24 69 2e 35 20 7b 0a 20 20 20 20 20 20  .2.$i.5 {.      
1480: 6c 69 73 74 20 24 77 68 65 72 65 20 5b 64 62 20  list $where [db 
1490: 65 76 61 6c 20 22 53 45 4c 45 43 54 20 69 64 20  eval "SELECT id 
14a0: 46 52 4f 4d 20 72 78 20 24 77 68 65 72 65 20 4f  FROM rx $where O
14b0: 52 44 45 52 20 42 59 20 69 64 22 5d 0a 20 20 20  RDER BY id"].   
14c0: 20 7d 20 5b 6c 69 73 74 20 24 77 68 65 72 65 20   } [list $where 
14d0: 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54  [db eval "SELECT
14e0: 20 69 64 20 46 52 4f 4d 20 62 78 20 24 77 68 65   id FROM bx $whe
14f0: 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d  re ORDER BY id"]
1500: 5d 0a 0a 20 20 20 20 23 20 44 6f 20 61 6e 20 6f  ]..    # Do an o
1510: 76 65 72 6c 61 70 73 20 71 75 65 72 79 20 77 69  verlaps query wi
1520: 74 68 20 73 75 72 70 6c 75 73 20 63 6f 6e 74 72  th surplus contr
1530: 61 69 6e 74 73 20 61 74 20 74 68 65 20 65 6e 64  aints at the end
1540: 0a 20 20 20 20 23 0a 20 20 20 20 73 65 74 20 77  .    #.    set w
1550: 68 65 72 65 20 7b 7d 0a 20 20 20 20 66 6f 72 20  here {}.    for 
1560: 7b 73 65 74 20 6a 20 5b 65 78 70 72 20 7b 24 6e  {set j [expr {$n
1570: 44 69 6d 2d 31 7d 5d 7d 20 7b 24 6a 3e 3d 30 7d  Dim-1}]} {$j>=0}
1580: 20 7b 69 6e 63 72 20 6a 20 2d 31 7d 20 7b 0a 20   {incr j -1} {. 
1590: 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72 61 6e       set mn [ran
15a0: 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20 20 73  d 10000].      s
15b0: 65 74 20 6d 78 20 5b 65 78 70 72 20 7b 24 6d 6e  et mx [expr {$mn
15c0: 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30 30 5d 7d  +[randincr 500]}
15d0: 5d 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20  ].      lappend 
15e0: 77 68 65 72 65 20 6d 78 24 6a 3e 24 6d 6e 20 6d  where mx$j>$mn m
15f0: 6e 24 6a 3c 3d 24 6d 78 0a 20 20 20 20 7d 0a 20  n$j<=$mx.    }. 
1600: 20 20 20 66 6f 72 20 7b 73 65 74 20 6a 20 30 7d     for {set j 0}
1610: 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63   {$j<$nDim} {inc
1620: 72 20 6a 7d 20 7b 0a 20 20 20 20 20 20 6c 61 70  r j} {.      lap
1630: 70 65 6e 64 20 77 68 65 72 65 20 6d 78 24 6a 3e  pend where mx$j>
1640: 2d 31 30 30 30 30 20 6d 6e 24 6a 3c 3d 31 30 30  -10000 mn$j<=100
1650: 30 30 0a 20 20 20 20 7d 0a 20 20 20 20 73 65 74  00.    }.    set
1660: 20 77 68 65 72 65 20 22 57 48 45 52 45 20 5b 6a   where "WHERE [j
1670: 6f 69 6e 20 24 77 68 65 72 65 20 7b 20 41 4e 44  oin $where { AND
1680: 20 7d 5d 22 0a 20 20 20 20 64 6f 5f 74 65 73 74   }]".    do_test
1690: 20 72 74 72 65 65 2d 24 6e 44 69 6d 2e 32 2e 24   rtree-$nDim.2.$
16a0: 69 2e 36 20 7b 0a 20 20 20 20 20 20 6c 69 73 74  i.6 {.      list
16b0: 20 24 77 68 65 72 65 20 5b 64 62 20 65 76 61 6c   $where [db eval
16c0: 20 22 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d   "SELECT id FROM
16d0: 20 72 78 20 24 77 68 65 72 65 20 4f 52 44 45 52   rx $where ORDER
16e0: 20 42 59 20 69 64 22 5d 0a 20 20 20 20 7d 20 5b   BY id"].    } [
16f0: 6c 69 73 74 20 24 77 68 65 72 65 20 5b 64 62 20  list $where [db 
1700: 65 76 61 6c 20 22 53 45 4c 45 43 54 20 69 64 20  eval "SELECT id 
1710: 46 52 4f 4d 20 62 78 20 24 77 68 65 72 65 20 4f  FROM bx $where O
1720: 52 44 45 52 20 42 59 20 69 64 22 5d 5d 0a 0a 20  RDER BY id"]].. 
1730: 20 20 20 23 20 44 6f 20 61 20 63 6f 6e 74 61 69     # Do a contai
1740: 6e 65 64 2d 69 6e 20 71 75 65 72 79 20 77 69 74  ned-in query wit
1750: 68 20 73 75 72 70 6c 75 73 20 63 6f 6e 74 72 61  h surplus contra
1760: 69 6e 74 73 20 77 68 65 72 65 20 74 68 65 20 0a  ints where the .
1770: 20 20 20 20 23 20 63 6f 6e 73 74 72 61 69 6e 74      # constraint
1780: 73 20 61 70 70 65 61 72 20 69 6e 20 61 20 72 61  s appear in a ra
1790: 6e 64 6f 6d 20 6f 72 64 65 72 2e 0a 20 20 20 20  ndom order..    
17a0: 23 0a 20 20 20 20 73 65 74 20 77 68 65 72 65 20  #.    set where 
17b0: 7b 7d 0a 20 20 20 20 66 6f 72 20 7b 73 65 74 20  {}.    for {set 
17c0: 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20  j 0} {$j<$nDim} 
17d0: 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20 20 20 20 20  {incr j} {.     
17e0: 20 73 65 74 20 6d 6e 31 20 5b 72 61 6e 64 20 31   set mn1 [rand 1
17f0: 30 30 30 30 5d 0a 20 20 20 20 20 20 73 65 74 20  0000].      set 
1800: 6d 6e 32 20 5b 65 78 70 72 20 7b 24 6d 6e 31 2b  mn2 [expr {$mn1+
1810: 5b 72 61 6e 64 69 6e 63 72 20 31 30 30 5d 7d 5d  [randincr 100]}]
1820: 0a 20 20 20 20 20 20 73 65 74 20 6d 78 31 20 5b  .      set mx1 [
1830: 65 78 70 72 20 7b 24 6d 6e 32 2b 5b 72 61 6e 64  expr {$mn2+[rand
1840: 69 6e 63 72 20 34 30 30 5d 7d 5d 0a 20 20 20 20  incr 400]}].    
1850: 20 20 73 65 74 20 6d 78 32 20 5b 65 78 70 72 20    set mx2 [expr 
1860: 7b 24 6d 78 31 2b 5b 72 61 6e 64 69 6e 63 72 20  {$mx1+[randincr 
1870: 31 30 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70  100]}].      lap
1880: 70 65 6e 64 20 77 68 65 72 65 20 6d 6e 24 6a 3e  pend where mn$j>
1890: 3d 24 6d 6e 31 20 6d 6e 24 6a 3e 24 6d 6e 32 20  =$mn1 mn$j>$mn2 
18a0: 6d 78 24 6a 3c 24 6d 78 31 20 6d 78 24 6a 3c 3d  mx$j<$mx1 mx$j<=
18b0: 24 6d 78 32 0a 20 20 20 20 7d 0a 20 20 20 20 73  $mx2.    }.    s
18c0: 65 74 20 77 68 65 72 65 20 22 57 48 45 52 45 20  et where "WHERE 
18d0: 5b 6a 6f 69 6e 20 5b 73 63 72 61 6d 62 6c 65 20  [join [scramble 
18e0: 24 77 68 65 72 65 5d 20 7b 20 41 4e 44 20 7d 5d  $where] { AND }]
18f0: 22 0a 20 20 20 20 64 6f 5f 74 65 73 74 20 72 74  ".    do_test rt
1900: 72 65 65 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 37  ree-$nDim.2.$i.7
1910: 20 7b 0a 20 20 20 20 20 20 6c 69 73 74 20 24 77   {.      list $w
1920: 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53  here [db eval "S
1930: 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 72 78  ELECT id FROM rx
1940: 20 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59   $where ORDER BY
1950: 20 69 64 22 5d 0a 20 20 20 20 7d 20 5b 6c 69 73   id"].    } [lis
1960: 74 20 24 77 68 65 72 65 20 5b 64 62 20 65 76 61  t $where [db eva
1970: 6c 20 22 53 45 4c 45 43 54 20 69 64 20 46 52 4f  l "SELECT id FRO
1980: 4d 20 62 78 20 24 77 68 65 72 65 20 4f 52 44 45  M bx $where ORDE
1990: 52 20 42 59 20 69 64 22 5d 5d 0a 0a 20 20 20 20  R BY id"]]..    
19a0: 23 20 44 6f 20 61 6e 20 6f 76 65 72 6c 61 70 73  # Do an overlaps
19b0: 20 71 75 65 72 79 20 77 69 74 68 20 73 75 72 70   query with surp
19c0: 6c 75 73 20 63 6f 6e 74 72 61 69 6e 74 73 20 77  lus contraints w
19d0: 68 65 72 65 20 74 68 65 0a 20 20 20 20 23 20 63  here the.    # c
19e0: 6f 6e 73 74 72 61 69 6e 74 73 20 61 70 70 65 61  onstraints appea
19f0: 72 20 69 6e 20 61 20 72 61 6e 64 6f 6d 20 6f 72  r in a random or
1a00: 64 65 72 2e 0a 20 20 20 20 23 0a 20 20 20 20 73  der..    #.    s
1a10: 65 74 20 77 68 65 72 65 20 7b 7d 0a 20 20 20 20  et where {}.    
1a20: 66 6f 72 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24  for {set j 0} {$
1a30: 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a  j<$nDim} {incr j
1a40: 7d 20 7b 0a 20 20 20 20 20 20 73 65 74 20 6d 6e  } {.      set mn
1a50: 31 20 5b 72 61 6e 64 20 31 30 30 30 30 5d 0a 20  1 [rand 10000]. 
1a60: 20 20 20 20 20 73 65 74 20 6d 6e 32 20 5b 65 78       set mn2 [ex
1a70: 70 72 20 7b 24 6d 6e 31 2b 5b 72 61 6e 64 69 6e  pr {$mn1+[randin
1a80: 63 72 20 31 30 30 5d 7d 5d 0a 20 20 20 20 20 20  cr 100]}].      
1a90: 73 65 74 20 6d 78 31 20 5b 65 78 70 72 20 7b 24  set mx1 [expr {$
1aa0: 6d 6e 32 2b 5b 72 61 6e 64 69 6e 63 72 20 34 30  mn2+[randincr 40
1ab0: 30 5d 7d 5d 0a 20 20 20 20 20 20 73 65 74 20 6d  0]}].      set m
1ac0: 78 32 20 5b 65 78 70 72 20 7b 24 6d 78 31 2b 5b  x2 [expr {$mx1+[
1ad0: 72 61 6e 64 69 6e 63 72 20 31 30 30 5d 7d 5d 0a  randincr 100]}].
1ae0: 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20 77 68        lappend wh
1af0: 65 72 65 20 6d 78 24 6a 3e 3d 24 6d 6e 31 20 6d  ere mx$j>=$mn1 m
1b00: 78 24 6a 3e 24 6d 6e 32 20 6d 6e 24 6a 3c 24 6d  x$j>$mn2 mn$j<$m
1b10: 78 31 20 6d 6e 24 6a 3c 3d 24 6d 78 32 0a 20 20  x1 mn$j<=$mx2.  
1b20: 20 20 7d 0a 20 20 20 20 73 65 74 20 77 68 65 72    }.    set wher
1b30: 65 20 22 57 48 45 52 45 20 5b 6a 6f 69 6e 20 5b  e "WHERE [join [
1b40: 73 63 72 61 6d 62 6c 65 20 24 77 68 65 72 65 5d  scramble $where]
1b50: 20 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20 64   { AND }]".    d
1b60: 6f 5f 74 65 73 74 20 72 74 72 65 65 2d 24 6e 44  o_test rtree-$nD
1b70: 69 6d 2e 32 2e 24 69 2e 38 20 7b 0a 20 20 20 20  im.2.$i.8 {.    
1b80: 20 20 6c 69 73 74 20 24 77 68 65 72 65 20 5b 64    list $where [d
1b90: 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20 69  b eval "SELECT i
1ba0: 64 20 46 52 4f 4d 20 72 78 20 24 77 68 65 72 65  d FROM rx $where
1bb0: 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d 0a 20   ORDER BY id"]. 
1bc0: 20 20 20 7d 20 5b 6c 69 73 74 20 24 77 68 65 72     } [list $wher
1bd0: 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45  e [db eval "SELE
1be0: 43 54 20 69 64 20 46 52 4f 4d 20 62 78 20 24 77  CT id FROM bx $w
1bf0: 68 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64  here ORDER BY id
1c00: 22 5d 5d 0a 20 20 7d 0a 0a 7d 0a 0a 66 69 6e 69  "]].  }..}..fini
1c10: 73 68 5f 74 65 73 74 0a                          sh_test.