/ Hex Artifact Content
Login

Artifact c8fe384f60ebd49540a5fecc990041bf452eb6e0:


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 0a 69 66 20 7b 21 5b  nsion..#..if {![
01a0: 69 6e 66 6f 20 65 78 69 73 74 73 20 74 65 73 74  info exists test
01b0: 64 69 72 5d 7d 20 7b 0a 20 20 73 65 74 20 74 65  dir]} {.  set te
01c0: 73 74 64 69 72 20 5b 66 69 6c 65 20 6a 6f 69 6e  stdir [file join
01d0: 20 5b 66 69 6c 65 20 64 69 72 6e 61 6d 65 20 5b   [file dirname [
01e0: 69 6e 66 6f 20 73 63 72 69 70 74 5d 5d 20 2e 2e  info script]] ..
01f0: 20 2e 2e 20 74 65 73 74 5d 0a 7d 20 0a 73 6f 75   .. test].} .sou
0200: 72 63 65 20 24 74 65 73 74 64 69 72 2f 74 65 73  rce $testdir/tes
0210: 74 65 72 2e 74 63 6c 0a 0a 69 66 63 61 70 61 62  ter.tcl..ifcapab
0220: 6c 65 20 21 72 74 72 65 65 20 7b 0a 20 20 66 69  le !rtree {.  fi
0230: 6e 69 73 68 5f 74 65 73 74 0a 20 20 72 65 74 75  nish_test.  retu
0240: 72 6e 0a 7d 0a 0a 73 65 74 20 3a 3a 4e 52 4f 57  rn.}..set ::NROW
0250: 20 32 35 30 30 0a 69 66 20 7b 5b 69 6e 66 6f 20   2500.if {[info 
0260: 65 78 69 73 74 73 20 47 28 69 73 71 75 69 63 6b  exists G(isquick
0270: 29 5d 20 26 26 20 24 47 28 69 73 71 75 69 63 6b  )] && $G(isquick
0280: 29 7d 20 7b 0a 20 20 73 65 74 20 3a 3a 4e 52 4f  )} {.  set ::NRO
0290: 57 20 32 35 30 0a 7d 0a 0a 69 66 63 61 70 61 62  W 250.}..ifcapab
02a0: 6c 65 20 21 72 74 72 65 65 5f 69 6e 74 5f 6f 6e  le !rtree_int_on
02b0: 6c 79 20 7b 0a 20 20 23 20 52 65 74 75 72 6e 20  ly {.  # Return 
02c0: 61 20 66 6c 6f 61 74 69 6e 67 20 70 6f 69 6e 74  a floating point
02d0: 20 6e 75 6d 62 65 72 20 62 65 74 77 65 65 6e 20   number between 
02e0: 2d 58 20 61 6e 64 20 58 2e 0a 20 20 23 20 0a 20  -X and X..  # . 
02f0: 20 70 72 6f 63 20 72 61 6e 64 20 7b 58 7d 20 7b   proc rand {X} {
0300: 0a 20 20 20 20 72 65 74 75 72 6e 20 5b 65 78 70  .    return [exp
0310: 72 20 7b 69 6e 74 28 28 72 61 6e 64 28 29 2d 30  r {int((rand()-0
0320: 2e 35 29 2a 31 30 32 34 2e 30 2a 24 58 29 2f 35  .5)*1024.0*$X)/5
0330: 31 32 2e 30 7d 5d 0a 20 20 7d 0a 20 20 0a 20 20  12.0}].  }.  .  
0340: 23 20 52 65 74 75 72 6e 20 61 20 70 6f 73 69 74  # Return a posit
0350: 69 76 65 20 66 6c 6f 61 74 69 6e 67 20 70 6f 69  ive floating poi
0360: 6e 74 20 6e 75 6d 62 65 72 20 6c 65 73 73 20 74  nt number less t
0370: 68 61 6e 20 6f 72 20 65 71 75 61 6c 20 74 6f 20  han or equal to 
0380: 58 0a 20 20 23 0a 20 20 70 72 6f 63 20 72 61 6e  X.  #.  proc ran
0390: 64 69 6e 63 72 20 7b 58 7d 20 7b 0a 20 20 20 20  dincr {X} {.    
03a0: 77 68 69 6c 65 20 31 20 7b 0a 20 20 20 20 20 20  while 1 {.      
03b0: 73 65 74 20 72 20 5b 65 78 70 72 20 7b 69 6e 74  set r [expr {int
03c0: 28 72 61 6e 64 28 29 2a 24 58 2a 33 32 2e 30 29  (rand()*$X*32.0)
03d0: 2f 33 32 2e 30 7d 5d 0a 20 20 20 20 20 20 69 66  /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 20 20 7d 0a 20 20 7d 0a  n $r}.    }.  }.
0400: 7d 20 65 6c 73 65 20 7b 0a 20 20 23 20 46 6f 72  } else {.  # For
0410: 20 72 74 72 65 65 5f 69 6e 74 5f 6f 6e 6c 79 2c   rtree_int_only,
0420: 20 72 65 74 75 72 6e 20 61 6e 20 6e 75 6d 62 65   return an numbe
0430: 72 20 62 65 74 77 65 65 6e 20 2d 58 20 61 6e 64  r between -X and
0440: 20 58 2e 0a 20 20 23 20 0a 20 20 70 72 6f 63 20   X..  # .  proc 
0450: 72 61 6e 64 20 7b 58 7d 20 7b 0a 20 20 20 20 72  rand {X} {.    r
0460: 65 74 75 72 6e 20 5b 65 78 70 72 20 7b 69 6e 74  eturn [expr {int
0470: 28 28 72 61 6e 64 28 29 2d 30 2e 35 29 2a 32 2a  ((rand()-0.5)*2*
0480: 24 58 29 7d 5d 0a 20 20 7d 0a 20 20 0a 20 20 23  $X)}].  }.  .  #
0490: 20 52 65 74 75 72 6e 20 61 20 70 6f 73 69 74 69   Return a positi
04a0: 76 65 20 69 6e 74 65 67 65 72 20 6c 65 73 73 20  ve integer less 
04b0: 74 68 61 6e 20 6f 72 20 65 71 75 61 6c 20 74 6f  than or equal to
04c0: 20 58 0a 20 20 23 0a 20 20 70 72 6f 63 20 72 61   X.  #.  proc ra
04d0: 6e 64 69 6e 63 72 20 7b 58 7d 20 7b 0a 20 20 20  ndincr {X} {.   
04e0: 20 77 68 69 6c 65 20 31 20 7b 0a 20 20 20 20 20   while 1 {.     
04f0: 20 73 65 74 20 72 20 5b 65 78 70 72 20 7b 69 6e   set r [expr {in
0500: 74 28 72 61 6e 64 28 29 2a 24 58 29 2b 31 7d 5d  t(rand()*$X)+1}]
0510: 0a 20 20 20 20 20 20 69 66 20 7b 24 72 3e 30 7d  .      if {$r>0}
0520: 20 7b 72 65 74 75 72 6e 20 24 72 7d 0a 20 20 20   {return $r}.   
0530: 20 7d 0a 20 20 7d 0a 7d 0a 20 20 0a 23 20 53 63   }.  }.}.  .# Sc
0540: 72 61 6d 62 6c 65 20 74 68 65 20 24 69 6e 6c 69  ramble the $inli
0550: 73 74 20 69 6e 74 6f 20 61 20 72 61 6e 64 6f 6d  st into a random
0560: 20 6f 72 64 65 72 2e 0a 23 0a 70 72 6f 63 20 73   order..#.proc s
0570: 63 72 61 6d 62 6c 65 20 7b 69 6e 6c 69 73 74 7d  cramble {inlist}
0580: 20 7b 0a 20 20 73 65 74 20 79 20 7b 7d 0a 20 20   {.  set y {}.  
0590: 66 6f 72 65 61 63 68 20 78 20 24 69 6e 6c 69 73  foreach x $inlis
05a0: 74 20 7b 0a 20 20 20 20 6c 61 70 70 65 6e 64 20  t {.    lappend 
05b0: 79 20 5b 6c 69 73 74 20 5b 65 78 70 72 20 7b 72  y [list [expr {r
05c0: 61 6e 64 28 29 7d 5d 20 24 78 5d 0a 20 20 7d 0a  and()}] $x].  }.
05d0: 20 20 73 65 74 20 79 20 5b 6c 73 6f 72 74 20 24    set y [lsort $
05e0: 79 5d 0a 20 20 73 65 74 20 6f 75 74 6c 69 73 74  y].  set outlist
05f0: 20 7b 7d 0a 20 20 66 6f 72 65 61 63 68 20 78 20   {}.  foreach x 
0600: 24 79 20 7b 0a 20 20 20 20 6c 61 70 70 65 6e 64  $y {.    lappend
0610: 20 6f 75 74 6c 69 73 74 20 5b 6c 69 6e 64 65 78   outlist [lindex
0620: 20 24 78 20 31 5d 0a 20 20 7d 0a 20 20 72 65 74   $x 1].  }.  ret
0630: 75 72 6e 20 24 6f 75 74 6c 69 73 74 0a 7d 0a 0a  urn $outlist.}..
0640: 23 20 41 6c 77 61 79 73 20 75 73 65 20 74 68 65  # Always use the
0650: 20 73 61 6d 65 20 72 61 6e 64 6f 6d 20 73 65 65   same random see
0660: 64 20 73 6f 20 74 68 61 74 20 74 68 65 20 73 65  d so that the se
0670: 71 75 65 6e 63 65 20 6f 66 20 74 65 73 74 73 0a  quence of tests.
0680: 23 20 69 73 20 72 65 70 65 61 74 61 62 6c 65 2e  # is repeatable.
0690: 0a 23 0a 65 78 70 72 20 7b 73 72 61 6e 64 28 31  .#.expr {srand(1
06a0: 32 33 34 29 7d 0a 0a 23 20 52 75 6e 20 74 68 65  234)}..# Run the
06b0: 73 65 20 74 65 73 74 73 20 66 6f 72 20 61 6c 6c  se tests for all
06c0: 20 6e 75 6d 62 65 72 20 6f 66 20 64 69 6d 65 6e   number of dimen
06d0: 73 69 6f 6e 73 20 62 65 74 77 65 65 6e 20 31 20  sions between 1 
06e0: 61 6e 64 20 35 2e 0a 23 0a 66 6f 72 20 7b 73 65  and 5..#.for {se
06f0: 74 20 6e 44 69 6d 20 31 7d 20 7b 24 6e 44 69 6d  t nDim 1} {$nDim
0700: 3c 3d 35 7d 20 7b 69 6e 63 72 20 6e 44 69 6d 7d  <=5} {incr nDim}
0710: 20 7b 0a 0a 20 20 23 20 43 6f 6e 73 74 72 75 63   {..  # Construc
0720: 74 20 61 6e 20 72 74 72 65 65 20 76 69 72 74 75  t an rtree virtu
0730: 61 6c 20 74 61 62 6c 65 20 61 6e 64 20 61 6e 20  al table and an 
0740: 6f 72 64 69 6e 61 72 79 20 62 74 72 65 65 20 74  ordinary btree t
0750: 61 62 6c 65 0a 20 20 23 20 74 6f 20 6d 69 72 72  able.  # to mirr
0760: 6f 72 20 69 74 2e 20 20 54 68 65 20 6f 72 64 69  or it.  The ordi
0770: 6e 61 72 79 20 74 61 62 6c 65 20 73 68 6f 75 6c  nary table shoul
0780: 64 20 62 65 20 6d 75 63 68 20 73 6c 6f 77 65 72  d be much slower
0790: 20 28 73 69 6e 63 65 0a 20 20 23 20 69 74 20 68   (since.  # it h
07a0: 61 73 20 74 6f 20 64 6f 20 61 20 66 75 6c 6c 20  as to do a full 
07b0: 74 61 62 6c 65 20 73 63 61 6e 29 20 62 75 74 20  table scan) but 
07c0: 73 68 6f 75 6c 64 20 67 69 76 65 20 74 68 65 20  should give the 
07d0: 65 78 61 63 74 20 73 61 6d 65 0a 20 20 23 20 61  exact same.  # a
07e0: 6e 73 77 65 72 73 2e 0a 20 20 23 0a 20 20 64 6f  nswers..  #.  do
07f0: 5f 74 65 73 74 20 72 74 72 65 65 34 2d 24 6e 44  _test rtree4-$nD
0800: 69 6d 2e 31 20 7b 0a 20 20 20 20 73 65 74 20 63  im.1 {.    set c
0810: 6c 69 73 74 20 7b 7d 0a 20 20 20 20 73 65 74 20  list {}.    set 
0820: 63 6b 6c 69 73 74 20 7b 7d 0a 20 20 20 20 66 6f  cklist {}.    fo
0830: 72 20 7b 73 65 74 20 69 20 30 7d 20 7b 24 69 3c  r {set i 0} {$i<
0840: 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 69 7d 20  $nDim} {incr i} 
0850: 7b 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20  {.      lappend 
0860: 63 6c 69 73 74 20 6d 6e 24 69 20 6d 78 24 69 0a  clist mn$i mx$i.
0870: 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20 63 6b        lappend ck
0880: 6c 69 73 74 20 22 6d 6e 24 69 3c 6d 78 24 69 22  list "mn$i<mx$i"
0890: 0a 20 20 20 20 7d 0a 20 20 20 20 64 62 20 65 76  .    }.    db ev
08a0: 61 6c 20 22 44 52 4f 50 20 54 41 42 4c 45 20 49  al "DROP TABLE I
08b0: 46 20 45 58 49 53 54 53 20 72 78 22 0a 20 20 20  F EXISTS rx".   
08c0: 20 64 62 20 65 76 61 6c 20 22 44 52 4f 50 20 54   db eval "DROP T
08d0: 41 42 4c 45 20 49 46 20 45 58 49 53 54 53 20 62  ABLE IF EXISTS b
08e0: 78 22 0a 20 20 20 20 64 62 20 65 76 61 6c 20 22  x".    db eval "
08f0: 43 52 45 41 54 45 20 56 49 52 54 55 41 4c 20 54  CREATE VIRTUAL T
0900: 41 42 4c 45 20 72 78 20 55 53 49 4e 47 20 72 74  ABLE rx USING rt
0910: 72 65 65 28 69 64 2c 20 5b 6a 6f 69 6e 20 24 63  ree(id, [join $c
0920: 6c 69 73 74 20 2c 5d 29 22 0a 20 20 20 20 64 62  list ,])".    db
0930: 20 65 76 61 6c 20 22 43 52 45 41 54 45 20 54 41   eval "CREATE TA
0940: 42 4c 45 20 62 78 28 69 64 20 49 4e 54 45 47 45  BLE bx(id INTEGE
0950: 52 20 50 52 49 4d 41 52 59 20 4b 45 59 2c 5c 0a  R PRIMARY KEY,\.
0960: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0970: 5b 6a 6f 69 6e 20 24 63 6c 69 73 74 20 2c 5d 2c  [join $clist ,],
0980: 20 43 48 45 43 4b 28 20 5b 6a 6f 69 6e 20 24 63   CHECK( [join $c
0990: 6b 6c 69 73 74 20 7b 20 41 4e 44 20 7d 5d 20 29  klist { AND }] )
09a0: 29 22 0a 20 20 7d 20 7b 7d 0a 0a 20 20 23 20 44  )".  } {}..  # D
09b0: 6f 20 6d 61 6e 79 20 69 6e 73 65 72 74 69 6f 6e  o many insertion
09c0: 73 20 6f 66 20 73 6d 61 6c 6c 20 6f 62 6a 65 63  s of small objec
09d0: 74 73 2e 20 20 44 6f 20 62 6f 74 68 20 6f 76 65  ts.  Do both ove
09e0: 72 6c 61 70 70 69 6e 67 20 61 6e 64 0a 20 20 23  rlapping and.  #
09f0: 20 63 6f 6e 74 61 69 6e 65 64 2d 77 69 74 68 69   contained-withi
0a00: 6e 20 71 75 65 72 69 65 73 20 61 66 74 65 72 20  n queries after 
0a10: 65 61 63 68 20 69 6e 73 65 72 74 20 74 6f 20 76  each insert to v
0a20: 65 72 69 66 79 20 74 68 61 74 20 61 6c 6c 0a 20  erify that all. 
0a30: 20 23 20 69 73 20 77 65 6c 6c 2e 0a 20 20 23 0a   # is well..  #.
0a40: 20 20 75 6e 73 65 74 20 2d 6e 6f 63 6f 6d 70 6c    unset -nocompl
0a50: 61 69 6e 20 77 68 65 72 65 0a 20 20 66 6f 72 20  ain where.  for 
0a60: 7b 73 65 74 20 69 20 31 7d 20 7b 24 69 3c 24 3a  {set i 1} {$i<$:
0a70: 3a 4e 52 4f 57 7d 20 7b 69 6e 63 72 20 69 7d 20  :NROW} {incr i} 
0a80: 7b 0a 20 20 20 20 23 20 44 6f 20 61 20 72 61 6e  {.    # Do a ran
0a90: 64 6f 6d 20 69 6e 73 65 72 74 0a 20 20 20 20 23  dom insert.    #
0aa0: 0a 20 20 20 20 64 6f 5f 74 65 73 74 20 72 74 72  .    do_test rtr
0ab0: 65 65 34 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 31  ee4-$nDim.2.$i.1
0ac0: 20 7b 0a 20 20 20 20 20 20 73 65 74 20 76 6c 69   {.      set vli
0ad0: 73 74 20 7b 7d 0a 20 20 20 20 20 20 66 6f 72 20  st {}.      for 
0ae0: 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e  {set j 0} {$j<$n
0af0: 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a  Dim} {incr j} {.
0b00: 20 20 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b          set mn [
0b10: 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20  rand 10000].    
0b20: 20 20 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72      set mx [expr
0b30: 20 7b 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20   {$mn+[randincr 
0b40: 35 30 5d 7d 5d 0a 20 20 20 20 20 20 20 20 6c 61  50]}].        la
0b50: 70 70 65 6e 64 20 76 6c 69 73 74 20 24 6d 6e 20  ppend vlist $mn 
0b60: 24 6d 78 0a 20 20 20 20 20 20 7d 0a 20 20 20 20  $mx.      }.    
0b70: 20 20 64 62 20 65 76 61 6c 20 22 49 4e 53 45 52    db eval "INSER
0b80: 54 20 49 4e 54 4f 20 72 78 20 56 41 4c 55 45 53  T INTO rx VALUES
0b90: 28 4e 55 4c 4c 2c 20 5b 6a 6f 69 6e 20 24 76 6c  (NULL, [join $vl
0ba0: 69 73 74 20 2c 5d 29 22 0a 20 20 20 20 20 20 64  ist ,])".      d
0bb0: 62 20 65 76 61 6c 20 22 49 4e 53 45 52 54 20 49  b eval "INSERT I
0bc0: 4e 54 4f 20 62 78 20 56 41 4c 55 45 53 28 4e 55  NTO bx VALUES(NU
0bd0: 4c 4c 2c 20 5b 6a 6f 69 6e 20 24 76 6c 69 73 74  LL, [join $vlist
0be0: 20 2c 5d 29 22 0a 20 20 20 20 7d 20 7b 7d 0a 0a   ,])".    } {}..
0bf0: 20 20 20 20 23 20 44 6f 20 61 20 63 6f 6e 74 61      # Do a conta
0c00: 69 6e 65 64 2d 69 6e 20 71 75 65 72 79 20 6f 6e  ined-in query on
0c10: 20 61 6c 6c 20 64 69 6d 65 6e 73 69 6f 6e 73 0a   all dimensions.
0c20: 20 20 20 20 23 0a 20 20 20 20 73 65 74 20 77 68      #.    set wh
0c30: 65 72 65 20 7b 7d 0a 20 20 20 20 66 6f 72 20 7b  ere {}.    for {
0c40: 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44  set j 0} {$j<$nD
0c50: 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20  im} {incr j} {. 
0c60: 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72 61 6e       set mn [ran
0c70: 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20 20 73  d 10000].      s
0c80: 65 74 20 6d 78 20 5b 65 78 70 72 20 7b 24 6d 6e  et mx [expr {$mn
0c90: 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30 30 5d 7d  +[randincr 500]}
0ca0: 5d 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20  ].      lappend 
0cb0: 77 68 65 72 65 20 6d 6e 24 6a 3e 3d 24 6d 6e 20  where mn$j>=$mn 
0cc0: 6d 78 24 6a 3c 3d 24 6d 78 0a 20 20 20 20 7d 0a  mx$j<=$mx.    }.
0cd0: 20 20 20 20 73 65 74 20 77 68 65 72 65 20 22 57      set where "W
0ce0: 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72  HERE [join $wher
0cf0: 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20  e { AND }]".    
0d00: 64 6f 5f 74 65 73 74 20 72 74 72 65 65 34 2d 24  do_test rtree4-$
0d10: 6e 44 69 6d 2e 32 2e 24 69 2e 32 20 7b 0a 20 20  nDim.2.$i.2 {.  
0d20: 20 20 20 20 6c 69 73 74 20 24 77 68 65 72 65 20      list $where 
0d30: 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54  [db eval "SELECT
0d40: 20 69 64 20 46 52 4f 4d 20 72 78 20 24 77 68 65   id FROM rx $whe
0d50: 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d  re ORDER BY id"]
0d60: 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20 24 77 68  .    } [list $wh
0d70: 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45  ere [db eval "SE
0d80: 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 62 78 20  LECT id FROM bx 
0d90: 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59 20  $where ORDER BY 
0da0: 69 64 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f 20  id"]]..    # Do 
0db0: 61 6e 20 6f 76 65 72 6c 61 70 73 20 71 75 65 72  an overlaps quer
0dc0: 79 20 6f 6e 20 61 6c 6c 20 64 69 6d 65 6e 73 69  y on all dimensi
0dd0: 6f 6e 73 0a 20 20 20 20 23 0a 20 20 20 20 73 65  ons.    #.    se
0de0: 74 20 77 68 65 72 65 20 7b 7d 0a 20 20 20 20 66  t where {}.    f
0df0: 6f 72 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a  or {set j 0} {$j
0e00: 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d  <$nDim} {incr j}
0e10: 20 7b 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 20   {.      set mn 
0e20: 5b 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20  [rand 10000].   
0e30: 20 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20     set mx [expr 
0e40: 7b 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35  {$mn+[randincr 5
0e50: 30 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70  00]}].      lapp
0e60: 65 6e 64 20 77 68 65 72 65 20 6d 78 24 6a 3e 3d  end where mx$j>=
0e70: 24 6d 6e 20 6d 6e 24 6a 3c 3d 24 6d 78 0a 20 20  $mn mn$j<=$mx.  
0e80: 20 20 7d 0a 20 20 20 20 73 65 74 20 77 68 65 72    }.    set wher
0e90: 65 20 22 57 48 45 52 45 20 5b 6a 6f 69 6e 20 24  e "WHERE [join $
0ea0: 77 68 65 72 65 20 7b 20 41 4e 44 20 7d 5d 22 0a  where { AND }]".
0eb0: 20 20 20 20 64 6f 5f 74 65 73 74 20 72 74 72 65      do_test rtre
0ec0: 65 34 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 33 20  e4-$nDim.2.$i.3 
0ed0: 7b 0a 20 20 20 20 20 20 6c 69 73 74 20 24 77 68  {.      list $wh
0ee0: 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45  ere [db eval "SE
0ef0: 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 72 78 20  LECT id FROM rx 
0f00: 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59 20  $where ORDER BY 
0f10: 69 64 22 5d 0a 20 20 20 20 7d 20 5b 6c 69 73 74  id"].    } [list
0f20: 20 24 77 68 65 72 65 20 5b 64 62 20 65 76 61 6c   $where [db eval
0f30: 20 22 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d   "SELECT id FROM
0f40: 20 62 78 20 24 77 68 65 72 65 20 4f 52 44 45 52   bx $where ORDER
0f50: 20 42 59 20 69 64 22 5d 5d 0a 0a 20 20 20 20 23   BY id"]]..    #
0f60: 20 44 6f 20 61 20 63 6f 6e 74 61 69 6e 65 64 2d   Do a contained-
0f70: 69 6e 20 71 75 65 72 79 20 77 69 74 68 20 73 75  in query with su
0f80: 72 70 6c 75 73 20 63 6f 6e 74 72 61 69 6e 74 73  rplus contraints
0f90: 20 61 74 20 74 68 65 20 62 65 67 69 6e 6e 69 6e   at the beginnin
0fa0: 67 2e 0a 20 20 20 20 23 20 54 68 69 73 20 73 68  g..    # This sh
0fb0: 6f 75 6c 64 20 66 6f 72 63 65 20 61 20 66 75 6c  ould force a ful
0fc0: 6c 2d 74 61 62 6c 65 20 73 63 61 6e 20 6f 6e 20  l-table scan on 
0fd0: 74 68 65 20 72 74 72 65 65 2e 0a 20 20 20 20 23  the rtree..    #
0fe0: 0a 20 20 20 20 73 65 74 20 77 68 65 72 65 20 7b  .    set where {
0ff0: 7d 0a 20 20 20 20 66 6f 72 20 7b 73 65 74 20 6a  }.    for {set j
1000: 20 30 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b   0} {$j<$nDim} {
1010: 69 6e 63 72 20 6a 7d 20 7b 0a 20 20 20 20 20 20  incr j} {.      
1020: 6c 61 70 70 65 6e 64 20 77 68 65 72 65 20 6d 6e  lappend where mn
1030: 24 6a 3e 2d 31 30 30 30 30 20 6d 78 24 6a 3c 31  $j>-10000 mx$j<1
1040: 30 30 30 30 0a 20 20 20 20 7d 0a 20 20 20 20 66  0000.    }.    f
1050: 6f 72 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a  or {set j 0} {$j
1060: 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d  <$nDim} {incr j}
1070: 20 7b 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 20   {.      set mn 
1080: 5b 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20  [rand 10000].   
1090: 20 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20     set mx [expr 
10a0: 7b 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35  {$mn+[randincr 5
10b0: 30 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70  00]}].      lapp
10c0: 65 6e 64 20 77 68 65 72 65 20 6d 6e 24 6a 3e 3d  end where mn$j>=
10d0: 24 6d 6e 20 6d 78 24 6a 3c 3d 24 6d 78 0a 20 20  $mn mx$j<=$mx.  
10e0: 20 20 7d 0a 20 20 20 20 73 65 74 20 77 68 65 72    }.    set wher
10f0: 65 20 22 57 48 45 52 45 20 5b 6a 6f 69 6e 20 24  e "WHERE [join $
1100: 77 68 65 72 65 20 7b 20 41 4e 44 20 7d 5d 22 0a  where { AND }]".
1110: 20 20 20 20 64 6f 5f 74 65 73 74 20 72 74 72 65      do_test rtre
1120: 65 34 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 33 20  e4-$nDim.2.$i.3 
1130: 7b 0a 20 20 20 20 20 20 6c 69 73 74 20 24 77 68  {.      list $wh
1140: 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45  ere [db eval "SE
1150: 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 72 78 20  LECT id FROM rx 
1160: 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59 20  $where ORDER BY 
1170: 69 64 22 5d 0a 20 20 20 20 7d 20 5b 6c 69 73 74  id"].    } [list
1180: 20 24 77 68 65 72 65 20 5b 64 62 20 65 76 61 6c   $where [db eval
1190: 20 22 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d   "SELECT id FROM
11a0: 20 62 78 20 24 77 68 65 72 65 20 4f 52 44 45 52   bx $where ORDER
11b0: 20 42 59 20 69 64 22 5d 5d 0a 0a 20 20 20 20 23   BY id"]]..    #
11c0: 20 44 6f 20 61 6e 20 6f 76 65 72 6c 61 70 73 20   Do an overlaps 
11d0: 71 75 65 72 79 20 77 69 74 68 20 73 75 72 70 6c  query with surpl
11e0: 75 73 20 63 6f 6e 74 72 61 69 6e 74 73 20 61 74  us contraints at
11f0: 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 2e 0a   the beginning..
1200: 20 20 20 20 23 20 54 68 69 73 20 73 68 6f 75 6c      # This shoul
1210: 64 20 66 6f 72 63 65 20 61 20 66 75 6c 6c 2d 74  d force a full-t
1220: 61 62 6c 65 20 73 63 61 6e 20 6f 6e 20 74 68 65  able scan on the
1230: 20 72 74 72 65 65 2e 0a 20 20 20 20 23 0a 20 20   rtree..    #.  
1240: 20 20 73 65 74 20 77 68 65 72 65 20 7b 7d 0a 20    set where {}. 
1250: 20 20 20 66 6f 72 20 7b 73 65 74 20 6a 20 30 7d     for {set j 0}
1260: 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63   {$j<$nDim} {inc
1270: 72 20 6a 7d 20 7b 0a 20 20 20 20 20 20 6c 61 70  r j} {.      lap
1280: 70 65 6e 64 20 77 68 65 72 65 20 6d 6e 24 6a 3e  pend where mn$j>
1290: 3d 2d 31 30 30 30 30 20 6d 78 24 6a 3c 3d 31 30  =-10000 mx$j<=10
12a0: 30 30 30 0a 20 20 20 20 7d 0a 20 20 20 20 66 6f  000.    }.    fo
12b0: 72 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c  r {set j 0} {$j<
12c0: 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20  $nDim} {incr j} 
12d0: 7b 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b  {.      set mn [
12e0: 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20  rand 10000].    
12f0: 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20 7b    set mx [expr {
1300: 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30  $mn+[randincr 50
1310: 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70 65  0]}].      lappe
1320: 6e 64 20 77 68 65 72 65 20 6d 78 24 6a 3e 24 6d  nd where mx$j>$m
1330: 6e 20 6d 6e 24 6a 3c 24 6d 78 0a 20 20 20 20 7d  n mn$j<$mx.    }
1340: 0a 20 20 20 20 73 65 74 20 77 68 65 72 65 20 22  .    set where "
1350: 57 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65  WHERE [join $whe
1360: 72 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20  re { AND }]".   
1370: 20 64 6f 5f 74 65 73 74 20 72 74 72 65 65 34 2d   do_test rtree4-
1380: 24 6e 44 69 6d 2e 32 2e 24 69 2e 34 20 7b 0a 20  $nDim.2.$i.4 {. 
1390: 20 20 20 20 20 6c 69 73 74 20 24 77 68 65 72 65       list $where
13a0: 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43   [db eval "SELEC
13b0: 54 20 69 64 20 46 52 4f 4d 20 72 78 20 24 77 68  T id FROM rx $wh
13c0: 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22  ere ORDER BY id"
13d0: 5d 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20 24 77  ].    } [list $w
13e0: 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53  here [db eval "S
13f0: 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 62 78  ELECT id FROM bx
1400: 20 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59   $where ORDER BY
1410: 20 69 64 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f   id"]]..    # Do
1420: 20 61 20 63 6f 6e 74 61 69 6e 65 64 2d 69 6e 20   a contained-in 
1430: 71 75 65 72 79 20 77 69 74 68 20 73 75 72 70 6c  query with surpl
1440: 75 73 20 63 6f 6e 74 72 61 69 6e 74 73 20 61 74  us contraints at
1450: 20 74 68 65 20 65 6e 64 0a 20 20 20 20 23 0a 20   the end.    #. 
1460: 20 20 20 73 65 74 20 77 68 65 72 65 20 7b 7d 0a     set where {}.
1470: 20 20 20 20 66 6f 72 20 7b 73 65 74 20 6a 20 30      for {set j 0
1480: 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e  } {$j<$nDim} {in
1490: 63 72 20 6a 7d 20 7b 0a 20 20 20 20 20 20 73 65  cr j} {.      se
14a0: 74 20 6d 6e 20 5b 72 61 6e 64 20 31 30 30 30 30  t mn [rand 10000
14b0: 5d 0a 20 20 20 20 20 20 73 65 74 20 6d 78 20 5b  ].      set mx [
14c0: 65 78 70 72 20 7b 24 6d 6e 2b 5b 72 61 6e 64 69  expr {$mn+[randi
14d0: 6e 63 72 20 35 30 30 5d 7d 5d 0a 20 20 20 20 20  ncr 500]}].     
14e0: 20 6c 61 70 70 65 6e 64 20 77 68 65 72 65 20 6d   lappend where m
14f0: 6e 24 6a 3e 3d 24 6d 6e 20 6d 78 24 6a 3c 24 6d  n$j>=$mn mx$j<$m
1500: 78 0a 20 20 20 20 7d 0a 20 20 20 20 66 6f 72 20  x.    }.    for 
1510: 7b 73 65 74 20 6a 20 5b 65 78 70 72 20 7b 24 6e  {set j [expr {$n
1520: 44 69 6d 2d 31 7d 5d 7d 20 7b 24 6a 3e 3d 30 7d  Dim-1}]} {$j>=0}
1530: 20 7b 69 6e 63 72 20 6a 20 2d 31 7d 20 7b 0a 20   {incr j -1} {. 
1540: 20 20 20 20 20 6c 61 70 70 65 6e 64 20 77 68 65       lappend whe
1550: 72 65 20 6d 6e 24 6a 3e 3d 2d 31 30 30 30 30 20  re mn$j>=-10000 
1560: 6d 78 24 6a 3c 31 30 30 30 30 0a 20 20 20 20 7d  mx$j<10000.    }
1570: 0a 20 20 20 20 73 65 74 20 77 68 65 72 65 20 22  .    set where "
1580: 57 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65  WHERE [join $whe
1590: 72 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20  re { AND }]".   
15a0: 20 64 6f 5f 74 65 73 74 20 72 74 72 65 65 34 2d   do_test rtree4-
15b0: 24 6e 44 69 6d 2e 32 2e 24 69 2e 35 20 7b 0a 20  $nDim.2.$i.5 {. 
15c0: 20 20 20 20 20 6c 69 73 74 20 24 77 68 65 72 65       list $where
15d0: 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43   [db eval "SELEC
15e0: 54 20 69 64 20 46 52 4f 4d 20 72 78 20 24 77 68  T id FROM rx $wh
15f0: 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22  ere ORDER BY id"
1600: 5d 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20 24 77  ].    } [list $w
1610: 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53  here [db eval "S
1620: 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 62 78  ELECT id FROM bx
1630: 20 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59   $where ORDER BY
1640: 20 69 64 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f   id"]]..    # Do
1650: 20 61 6e 20 6f 76 65 72 6c 61 70 73 20 71 75 65   an overlaps que
1660: 72 79 20 77 69 74 68 20 73 75 72 70 6c 75 73 20  ry with surplus 
1670: 63 6f 6e 74 72 61 69 6e 74 73 20 61 74 20 74 68  contraints at th
1680: 65 20 65 6e 64 0a 20 20 20 20 23 0a 20 20 20 20  e end.    #.    
1690: 73 65 74 20 77 68 65 72 65 20 7b 7d 0a 20 20 20  set where {}.   
16a0: 20 66 6f 72 20 7b 73 65 74 20 6a 20 5b 65 78 70   for {set j [exp
16b0: 72 20 7b 24 6e 44 69 6d 2d 31 7d 5d 7d 20 7b 24  r {$nDim-1}]} {$
16c0: 6a 3e 3d 30 7d 20 7b 69 6e 63 72 20 6a 20 2d 31  j>=0} {incr j -1
16d0: 7d 20 7b 0a 20 20 20 20 20 20 73 65 74 20 6d 6e  } {.      set mn
16e0: 20 5b 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20   [rand 10000].  
16f0: 20 20 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72      set mx [expr
1700: 20 7b 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20   {$mn+[randincr 
1710: 35 30 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70  500]}].      lap
1720: 70 65 6e 64 20 77 68 65 72 65 20 6d 78 24 6a 3e  pend where mx$j>
1730: 24 6d 6e 20 6d 6e 24 6a 3c 3d 24 6d 78 0a 20 20  $mn mn$j<=$mx.  
1740: 20 20 7d 0a 20 20 20 20 66 6f 72 20 7b 73 65 74    }.    for {set
1750: 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d   j 0} {$j<$nDim}
1760: 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20 20 20 20   {incr j} {.    
1770: 20 20 6c 61 70 70 65 6e 64 20 77 68 65 72 65 20    lappend where 
1780: 6d 78 24 6a 3e 2d 31 30 30 30 30 20 6d 6e 24 6a  mx$j>-10000 mn$j
1790: 3c 3d 31 30 30 30 30 0a 20 20 20 20 7d 0a 20 20  <=10000.    }.  
17a0: 20 20 73 65 74 20 77 68 65 72 65 20 22 57 48 45    set where "WHE
17b0: 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72 65 20  RE [join $where 
17c0: 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20 64 6f  { AND }]".    do
17d0: 5f 74 65 73 74 20 72 74 72 65 65 34 2d 24 6e 44  _test rtree4-$nD
17e0: 69 6d 2e 32 2e 24 69 2e 36 20 7b 0a 20 20 20 20  im.2.$i.6 {.    
17f0: 20 20 6c 69 73 74 20 24 77 68 65 72 65 20 5b 64    list $where [d
1800: 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20 69  b eval "SELECT i
1810: 64 20 46 52 4f 4d 20 72 78 20 24 77 68 65 72 65  d FROM rx $where
1820: 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d 0a 20   ORDER BY id"]. 
1830: 20 20 20 7d 20 5b 6c 69 73 74 20 24 77 68 65 72     } [list $wher
1840: 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45  e [db eval "SELE
1850: 43 54 20 69 64 20 46 52 4f 4d 20 62 78 20 24 77  CT id FROM bx $w
1860: 68 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64  here ORDER BY id
1870: 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f 20 61 20  "]]..    # Do a 
1880: 63 6f 6e 74 61 69 6e 65 64 2d 69 6e 20 71 75 65  contained-in que
1890: 72 79 20 77 69 74 68 20 73 75 72 70 6c 75 73 20  ry with surplus 
18a0: 63 6f 6e 74 72 61 69 6e 74 73 20 77 68 65 72 65  contraints where
18b0: 20 74 68 65 20 0a 20 20 20 20 23 20 63 6f 6e 73   the .    # cons
18c0: 74 72 61 69 6e 74 73 20 61 70 70 65 61 72 20 69  traints appear i
18d0: 6e 20 61 20 72 61 6e 64 6f 6d 20 6f 72 64 65 72  n a random order
18e0: 2e 0a 20 20 20 20 23 0a 20 20 20 20 73 65 74 20  ..    #.    set 
18f0: 77 68 65 72 65 20 7b 7d 0a 20 20 20 20 66 6f 72  where {}.    for
1900: 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24   {set j 0} {$j<$
1910: 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b  nDim} {incr j} {
1920: 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 31 20 5b  .      set mn1 [
1930: 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20  rand 10000].    
1940: 20 20 73 65 74 20 6d 6e 32 20 5b 65 78 70 72 20    set mn2 [expr 
1950: 7b 24 6d 6e 31 2b 5b 72 61 6e 64 69 6e 63 72 20  {$mn1+[randincr 
1960: 31 30 30 5d 7d 5d 0a 20 20 20 20 20 20 73 65 74  100]}].      set
1970: 20 6d 78 31 20 5b 65 78 70 72 20 7b 24 6d 6e 32   mx1 [expr {$mn2
1980: 2b 5b 72 61 6e 64 69 6e 63 72 20 34 30 30 5d 7d  +[randincr 400]}
1990: 5d 0a 20 20 20 20 20 20 73 65 74 20 6d 78 32 20  ].      set mx2 
19a0: 5b 65 78 70 72 20 7b 24 6d 78 31 2b 5b 72 61 6e  [expr {$mx1+[ran
19b0: 64 69 6e 63 72 20 31 30 30 5d 7d 5d 0a 20 20 20  dincr 100]}].   
19c0: 20 20 20 6c 61 70 70 65 6e 64 20 77 68 65 72 65     lappend where
19d0: 20 6d 6e 24 6a 3e 3d 24 6d 6e 31 20 6d 6e 24 6a   mn$j>=$mn1 mn$j
19e0: 3e 24 6d 6e 32 20 6d 78 24 6a 3c 24 6d 78 31 20  >$mn2 mx$j<$mx1 
19f0: 6d 78 24 6a 3c 3d 24 6d 78 32 0a 20 20 20 20 7d  mx$j<=$mx2.    }
1a00: 0a 20 20 20 20 73 65 74 20 77 68 65 72 65 20 22  .    set where "
1a10: 57 48 45 52 45 20 5b 6a 6f 69 6e 20 5b 73 63 72  WHERE [join [scr
1a20: 61 6d 62 6c 65 20 24 77 68 65 72 65 5d 20 7b 20  amble $where] { 
1a30: 41 4e 44 20 7d 5d 22 0a 20 20 20 20 64 6f 5f 74  AND }]".    do_t
1a40: 65 73 74 20 72 74 72 65 65 34 2d 24 6e 44 69 6d  est rtree4-$nDim
1a50: 2e 32 2e 24 69 2e 37 20 7b 0a 20 20 20 20 20 20  .2.$i.7 {.      
1a60: 6c 69 73 74 20 24 77 68 65 72 65 20 5b 64 62 20  list $where [db 
1a70: 65 76 61 6c 20 22 53 45 4c 45 43 54 20 69 64 20  eval "SELECT id 
1a80: 46 52 4f 4d 20 72 78 20 24 77 68 65 72 65 20 4f  FROM rx $where O
1a90: 52 44 45 52 20 42 59 20 69 64 22 5d 0a 20 20 20  RDER BY id"].   
1aa0: 20 7d 20 5b 6c 69 73 74 20 24 77 68 65 72 65 20   } [list $where 
1ab0: 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54  [db eval "SELECT
1ac0: 20 69 64 20 46 52 4f 4d 20 62 78 20 24 77 68 65   id FROM bx $whe
1ad0: 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d  re ORDER BY id"]
1ae0: 5d 0a 0a 20 20 20 20 23 20 44 6f 20 61 6e 20 6f  ]..    # Do an o
1af0: 76 65 72 6c 61 70 73 20 71 75 65 72 79 20 77 69  verlaps query wi
1b00: 74 68 20 73 75 72 70 6c 75 73 20 63 6f 6e 74 72  th surplus contr
1b10: 61 69 6e 74 73 20 77 68 65 72 65 20 74 68 65 0a  aints where the.
1b20: 20 20 20 20 23 20 63 6f 6e 73 74 72 61 69 6e 74      # constraint
1b30: 73 20 61 70 70 65 61 72 20 69 6e 20 61 20 72 61  s appear in a ra
1b40: 6e 64 6f 6d 20 6f 72 64 65 72 2e 0a 20 20 20 20  ndom order..    
1b50: 23 0a 20 20 20 20 73 65 74 20 77 68 65 72 65 20  #.    set where 
1b60: 7b 7d 0a 20 20 20 20 66 6f 72 20 7b 73 65 74 20  {}.    for {set 
1b70: 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20  j 0} {$j<$nDim} 
1b80: 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20 20 20 20 20  {incr j} {.     
1b90: 20 73 65 74 20 6d 6e 31 20 5b 72 61 6e 64 20 31   set mn1 [rand 1
1ba0: 30 30 30 30 5d 0a 20 20 20 20 20 20 73 65 74 20  0000].      set 
1bb0: 6d 6e 32 20 5b 65 78 70 72 20 7b 24 6d 6e 31 2b  mn2 [expr {$mn1+
1bc0: 5b 72 61 6e 64 69 6e 63 72 20 31 30 30 5d 7d 5d  [randincr 100]}]
1bd0: 0a 20 20 20 20 20 20 73 65 74 20 6d 78 31 20 5b  .      set mx1 [
1be0: 65 78 70 72 20 7b 24 6d 6e 32 2b 5b 72 61 6e 64  expr {$mn2+[rand
1bf0: 69 6e 63 72 20 34 30 30 5d 7d 5d 0a 20 20 20 20  incr 400]}].    
1c00: 20 20 73 65 74 20 6d 78 32 20 5b 65 78 70 72 20    set mx2 [expr 
1c10: 7b 24 6d 78 31 2b 5b 72 61 6e 64 69 6e 63 72 20  {$mx1+[randincr 
1c20: 31 30 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70  100]}].      lap
1c30: 70 65 6e 64 20 77 68 65 72 65 20 6d 78 24 6a 3e  pend where mx$j>
1c40: 3d 24 6d 6e 31 20 6d 78 24 6a 3e 24 6d 6e 32 20  =$mn1 mx$j>$mn2 
1c50: 6d 6e 24 6a 3c 24 6d 78 31 20 6d 6e 24 6a 3c 3d  mn$j<$mx1 mn$j<=
1c60: 24 6d 78 32 0a 20 20 20 20 7d 0a 20 20 20 20 73  $mx2.    }.    s
1c70: 65 74 20 77 68 65 72 65 20 22 57 48 45 52 45 20  et where "WHERE 
1c80: 5b 6a 6f 69 6e 20 5b 73 63 72 61 6d 62 6c 65 20  [join [scramble 
1c90: 24 77 68 65 72 65 5d 20 7b 20 41 4e 44 20 7d 5d  $where] { AND }]
1ca0: 22 0a 20 20 20 20 64 6f 5f 74 65 73 74 20 72 74  ".    do_test rt
1cb0: 72 65 65 34 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e  ree4-$nDim.2.$i.
1cc0: 38 20 7b 0a 20 20 20 20 20 20 6c 69 73 74 20 24  8 {.      list $
1cd0: 77 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22  where [db eval "
1ce0: 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 72  SELECT id FROM r
1cf0: 78 20 24 77 68 65 72 65 20 4f 52 44 45 52 20 42  x $where ORDER B
1d00: 59 20 69 64 22 5d 0a 20 20 20 20 7d 20 5b 6c 69  Y id"].    } [li
1d10: 73 74 20 24 77 68 65 72 65 20 5b 64 62 20 65 76  st $where [db ev
1d20: 61 6c 20 22 53 45 4c 45 43 54 20 69 64 20 46 52  al "SELECT id FR
1d30: 4f 4d 20 62 78 20 24 77 68 65 72 65 20 4f 52 44  OM bx $where ORD
1d40: 45 52 20 42 59 20 69 64 22 5d 5d 0a 20 20 7d 0a  ER BY id"]].  }.
1d50: 0a 7d 0a 0a 66 69 6e 69 73 68 5f 74 65 73 74 0a  .}..finish_test.