/ Hex Artifact Content
Login

Artifact 0061e6f464fd3dc6a79f82454c5a1c3dadbe42af:


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 23 20 52 65 74 75 72  W 250.}..# Retur
02a0: 6e 20 61 20 66 6c 6f 61 74 69 6e 67 20 70 6f 69  n a floating poi
02b0: 6e 74 20 6e 75 6d 62 65 72 20 62 65 74 77 65 65  nt number betwee
02c0: 6e 20 2d 58 20 61 6e 64 20 58 2e 0a 23 20 0a 70  n -X and X..# .p
02d0: 72 6f 63 20 72 61 6e 64 20 7b 58 7d 20 7b 0a 20  roc rand {X} {. 
02e0: 20 72 65 74 75 72 6e 20 5b 65 78 70 72 20 7b 69   return [expr {i
02f0: 6e 74 28 28 72 61 6e 64 28 29 2d 30 2e 35 29 2a  nt((rand()-0.5)*
0300: 31 30 32 34 2e 30 2a 24 58 29 2f 35 31 32 2e 30  1024.0*$X)/512.0
0310: 7d 5d 0a 7d 0a 0a 23 20 52 65 74 75 72 6e 20 61  }].}..# Return a
0320: 20 70 6f 73 69 74 69 76 65 20 66 6c 6f 61 74 69   positive floati
0330: 6e 67 20 70 6f 69 6e 74 20 6e 75 6d 62 65 72 20  ng point number 
0340: 6c 65 73 73 20 74 68 61 6e 20 6f 72 20 65 71 75  less than or equ
0350: 61 6c 20 74 6f 20 58 0a 23 0a 70 72 6f 63 20 72  al to X.#.proc r
0360: 61 6e 64 69 6e 63 72 20 7b 58 7d 20 7b 0a 20 20  andincr {X} {.  
0370: 77 68 69 6c 65 20 31 20 7b 0a 20 20 20 20 73 65  while 1 {.    se
0380: 74 20 72 20 5b 65 78 70 72 20 7b 69 6e 74 28 72  t r [expr {int(r
0390: 61 6e 64 28 29 2a 24 58 2a 33 32 2e 30 29 2f 33  and()*$X*32.0)/3
03a0: 32 2e 30 7d 5d 0a 20 20 20 20 69 66 20 7b 24 72  2.0}].    if {$r
03b0: 3e 30 2e 30 7d 20 7b 72 65 74 75 72 6e 20 24 72  >0.0} {return $r
03c0: 7d 0a 20 20 7d 0a 7d 0a 0a 23 20 53 63 72 61 6d  }.  }.}..# Scram
03d0: 62 6c 65 20 74 68 65 20 24 69 6e 6c 69 73 74 20  ble the $inlist 
03e0: 69 6e 74 6f 20 61 20 72 61 6e 64 6f 6d 20 6f 72  into a random or
03f0: 64 65 72 2e 0a 23 0a 70 72 6f 63 20 73 63 72 61  der..#.proc scra
0400: 6d 62 6c 65 20 7b 69 6e 6c 69 73 74 7d 20 7b 0a  mble {inlist} {.
0410: 20 20 73 65 74 20 79 20 7b 7d 0a 20 20 66 6f 72    set y {}.  for
0420: 65 61 63 68 20 78 20 24 69 6e 6c 69 73 74 20 7b  each x $inlist {
0430: 0a 20 20 20 20 6c 61 70 70 65 6e 64 20 79 20 5b  .    lappend y [
0440: 6c 69 73 74 20 5b 65 78 70 72 20 7b 72 61 6e 64  list [expr {rand
0450: 28 29 7d 5d 20 24 78 5d 0a 20 20 7d 0a 20 20 73  ()}] $x].  }.  s
0460: 65 74 20 79 20 5b 6c 73 6f 72 74 20 24 79 5d 0a  et y [lsort $y].
0470: 20 20 73 65 74 20 6f 75 74 6c 69 73 74 20 7b 7d    set outlist {}
0480: 0a 20 20 66 6f 72 65 61 63 68 20 78 20 24 79 20  .  foreach x $y 
0490: 7b 0a 20 20 20 20 6c 61 70 70 65 6e 64 20 6f 75  {.    lappend ou
04a0: 74 6c 69 73 74 20 5b 6c 69 6e 64 65 78 20 24 78  tlist [lindex $x
04b0: 20 31 5d 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e   1].  }.  return
04c0: 20 24 6f 75 74 6c 69 73 74 0a 7d 0a 0a 23 20 41   $outlist.}..# A
04d0: 6c 77 61 79 73 20 75 73 65 20 74 68 65 20 73 61  lways use the sa
04e0: 6d 65 20 72 61 6e 64 6f 6d 20 73 65 65 64 20 73  me random seed s
04f0: 6f 20 74 68 61 74 20 74 68 65 20 73 65 71 75 65  o that the seque
0500: 6e 63 65 20 6f 66 20 74 65 73 74 73 0a 23 20 69  nce of tests.# i
0510: 73 20 72 65 70 65 61 74 61 62 6c 65 2e 0a 23 0a  s repeatable..#.
0520: 65 78 70 72 20 7b 73 72 61 6e 64 28 31 32 33 34  expr {srand(1234
0530: 29 7d 0a 0a 23 20 52 75 6e 20 74 68 65 73 65 20  )}..# Run these 
0540: 74 65 73 74 73 20 66 6f 72 20 61 6c 6c 20 6e 75  tests for all nu
0550: 6d 62 65 72 20 6f 66 20 64 69 6d 65 6e 73 69 6f  mber of dimensio
0560: 6e 73 20 62 65 74 77 65 65 6e 20 31 20 61 6e 64  ns between 1 and
0570: 20 35 2e 0a 23 0a 66 6f 72 20 7b 73 65 74 20 6e   5..#.for {set n
0580: 44 69 6d 20 31 7d 20 7b 24 6e 44 69 6d 3c 3d 35  Dim 1} {$nDim<=5
0590: 7d 20 7b 69 6e 63 72 20 6e 44 69 6d 7d 20 7b 0a  } {incr nDim} {.
05a0: 0a 20 20 23 20 43 6f 6e 73 74 72 75 63 74 20 61  .  # Construct a
05b0: 6e 20 72 74 72 65 65 20 76 69 72 74 75 61 6c 20  n rtree virtual 
05c0: 74 61 62 6c 65 20 61 6e 64 20 61 6e 20 6f 72 64  table and an ord
05d0: 69 6e 61 72 79 20 62 74 72 65 65 20 74 61 62 6c  inary btree tabl
05e0: 65 0a 20 20 23 20 74 6f 20 6d 69 72 72 6f 72 20  e.  # to mirror 
05f0: 69 74 2e 20 20 54 68 65 20 6f 72 64 69 6e 61 72  it.  The ordinar
0600: 79 20 74 61 62 6c 65 20 73 68 6f 75 6c 64 20 62  y table should b
0610: 65 20 6d 75 63 68 20 73 6c 6f 77 65 72 20 28 73  e much slower (s
0620: 69 6e 63 65 0a 20 20 23 20 69 74 20 68 61 73 20  ince.  # it has 
0630: 74 6f 20 64 6f 20 61 20 66 75 6c 6c 20 74 61 62  to do a full tab
0640: 6c 65 20 73 63 61 6e 29 20 62 75 74 20 73 68 6f  le scan) but sho
0650: 75 6c 64 20 67 69 76 65 20 74 68 65 20 65 78 61  uld give the exa
0660: 63 74 20 73 61 6d 65 0a 20 20 23 20 61 6e 73 77  ct same.  # answ
0670: 65 72 73 2e 0a 20 20 23 0a 20 20 64 6f 5f 74 65  ers..  #.  do_te
0680: 73 74 20 72 74 72 65 65 34 2d 24 6e 44 69 6d 2e  st rtree4-$nDim.
0690: 31 20 7b 0a 20 20 20 20 73 65 74 20 63 6c 69 73  1 {.    set clis
06a0: 74 20 7b 7d 0a 20 20 20 20 73 65 74 20 63 6b 6c  t {}.    set ckl
06b0: 69 73 74 20 7b 7d 0a 20 20 20 20 66 6f 72 20 7b  ist {}.    for {
06c0: 73 65 74 20 69 20 30 7d 20 7b 24 69 3c 24 6e 44  set i 0} {$i<$nD
06d0: 69 6d 7d 20 7b 69 6e 63 72 20 69 7d 20 7b 0a 20  im} {incr i} {. 
06e0: 20 20 20 20 20 6c 61 70 70 65 6e 64 20 63 6c 69       lappend cli
06f0: 73 74 20 6d 6e 24 69 20 6d 78 24 69 0a 20 20 20  st mn$i mx$i.   
0700: 20 20 20 6c 61 70 70 65 6e 64 20 63 6b 6c 69 73     lappend cklis
0710: 74 20 22 6d 6e 24 69 3c 6d 78 24 69 22 0a 20 20  t "mn$i<mx$i".  
0720: 20 20 7d 0a 20 20 20 20 64 62 20 65 76 61 6c 20    }.    db eval 
0730: 22 44 52 4f 50 20 54 41 42 4c 45 20 49 46 20 45  "DROP TABLE IF E
0740: 58 49 53 54 53 20 72 78 22 0a 20 20 20 20 64 62  XISTS rx".    db
0750: 20 65 76 61 6c 20 22 44 52 4f 50 20 54 41 42 4c   eval "DROP TABL
0760: 45 20 49 46 20 45 58 49 53 54 53 20 62 78 22 0a  E IF EXISTS bx".
0770: 20 20 20 20 64 62 20 65 76 61 6c 20 22 43 52 45      db eval "CRE
0780: 41 54 45 20 56 49 52 54 55 41 4c 20 54 41 42 4c  ATE VIRTUAL TABL
0790: 45 20 72 78 20 55 53 49 4e 47 20 72 74 72 65 65  E rx USING rtree
07a0: 28 69 64 2c 20 5b 6a 6f 69 6e 20 24 63 6c 69 73  (id, [join $clis
07b0: 74 20 2c 5d 29 22 0a 20 20 20 20 64 62 20 65 76  t ,])".    db ev
07c0: 61 6c 20 22 43 52 45 41 54 45 20 54 41 42 4c 45  al "CREATE TABLE
07d0: 20 62 78 28 69 64 20 49 4e 54 45 47 45 52 20 50   bx(id INTEGER P
07e0: 52 49 4d 41 52 59 20 4b 45 59 2c 5c 0a 20 20 20  RIMARY KEY,\.   
07f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 5b 6a 6f               [jo
0800: 69 6e 20 24 63 6c 69 73 74 20 2c 5d 2c 20 43 48  in $clist ,], CH
0810: 45 43 4b 28 20 5b 6a 6f 69 6e 20 24 63 6b 6c 69  ECK( [join $ckli
0820: 73 74 20 7b 20 41 4e 44 20 7d 5d 20 29 29 22 0a  st { AND }] ))".
0830: 20 20 7d 20 7b 7d 0a 0a 20 20 23 20 44 6f 20 6d    } {}..  # Do m
0840: 61 6e 79 20 69 6e 73 65 72 74 69 6f 6e 73 20 6f  any insertions o
0850: 66 20 73 6d 61 6c 6c 20 6f 62 6a 65 63 74 73 2e  f small objects.
0860: 20 20 44 6f 20 62 6f 74 68 20 6f 76 65 72 6c 61    Do both overla
0870: 70 70 69 6e 67 20 61 6e 64 0a 20 20 23 20 63 6f  pping and.  # co
0880: 6e 74 61 69 6e 65 64 2d 77 69 74 68 69 6e 20 71  ntained-within q
0890: 75 65 72 69 65 73 20 61 66 74 65 72 20 65 61 63  ueries after eac
08a0: 68 20 69 6e 73 65 72 74 20 74 6f 20 76 65 72 69  h insert to veri
08b0: 66 79 20 74 68 61 74 20 61 6c 6c 0a 20 20 23 20  fy that all.  # 
08c0: 69 73 20 77 65 6c 6c 2e 0a 20 20 23 0a 20 20 75  is well..  #.  u
08d0: 6e 73 65 74 20 2d 6e 6f 63 6f 6d 70 6c 61 69 6e  nset -nocomplain
08e0: 20 77 68 65 72 65 0a 20 20 66 6f 72 20 7b 73 65   where.  for {se
08f0: 74 20 69 20 31 7d 20 7b 24 69 3c 24 3a 3a 4e 52  t i 1} {$i<$::NR
0900: 4f 57 7d 20 7b 69 6e 63 72 20 69 7d 20 7b 0a 20  OW} {incr i} {. 
0910: 20 20 20 23 20 44 6f 20 61 20 72 61 6e 64 6f 6d     # Do a random
0920: 20 69 6e 73 65 72 74 0a 20 20 20 20 23 0a 20 20   insert.    #.  
0930: 20 20 64 6f 5f 74 65 73 74 20 72 74 72 65 65 34    do_test rtree4
0940: 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 31 20 7b 0a  -$nDim.2.$i.1 {.
0950: 20 20 20 20 20 20 73 65 74 20 76 6c 69 73 74 20        set vlist 
0960: 7b 7d 0a 20 20 20 20 20 20 66 6f 72 20 7b 73 65  {}.      for {se
0970: 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44 69 6d  t j 0} {$j<$nDim
0980: 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20 20 20  } {incr j} {.   
0990: 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72 61 6e       set mn [ran
09a0: 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20 20 20  d 10000].       
09b0: 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20 7b 24   set mx [expr {$
09c0: 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30 5d  mn+[randincr 50]
09d0: 7d 5d 0a 20 20 20 20 20 20 20 20 6c 61 70 70 65  }].        lappe
09e0: 6e 64 20 76 6c 69 73 74 20 24 6d 6e 20 24 6d 78  nd vlist $mn $mx
09f0: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 64  .      }.      d
0a00: 62 20 65 76 61 6c 20 22 49 4e 53 45 52 54 20 49  b eval "INSERT I
0a10: 4e 54 4f 20 72 78 20 56 41 4c 55 45 53 28 4e 55  NTO rx VALUES(NU
0a20: 4c 4c 2c 20 5b 6a 6f 69 6e 20 24 76 6c 69 73 74  LL, [join $vlist
0a30: 20 2c 5d 29 22 0a 20 20 20 20 20 20 64 62 20 65   ,])".      db e
0a40: 76 61 6c 20 22 49 4e 53 45 52 54 20 49 4e 54 4f  val "INSERT INTO
0a50: 20 62 78 20 56 41 4c 55 45 53 28 4e 55 4c 4c 2c   bx VALUES(NULL,
0a60: 20 5b 6a 6f 69 6e 20 24 76 6c 69 73 74 20 2c 5d   [join $vlist ,]
0a70: 29 22 0a 20 20 20 20 7d 20 7b 7d 0a 0a 20 20 20  )".    } {}..   
0a80: 20 23 20 44 6f 20 61 20 63 6f 6e 74 61 69 6e 65   # Do a containe
0a90: 64 2d 69 6e 20 71 75 65 72 79 20 6f 6e 20 61 6c  d-in query on al
0aa0: 6c 20 64 69 6d 65 6e 73 69 6f 6e 73 0a 20 20 20  l dimensions.   
0ab0: 20 23 0a 20 20 20 20 73 65 74 20 77 68 65 72 65   #.    set where
0ac0: 20 7b 7d 0a 20 20 20 20 66 6f 72 20 7b 73 65 74   {}.    for {set
0ad0: 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d   j 0} {$j<$nDim}
0ae0: 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20 20 20 20   {incr j} {.    
0af0: 20 20 73 65 74 20 6d 6e 20 5b 72 61 6e 64 20 31    set mn [rand 1
0b00: 30 30 30 30 5d 0a 20 20 20 20 20 20 73 65 74 20  0000].      set 
0b10: 6d 78 20 5b 65 78 70 72 20 7b 24 6d 6e 2b 5b 72  mx [expr {$mn+[r
0b20: 61 6e 64 69 6e 63 72 20 35 30 30 5d 7d 5d 0a 20  andincr 500]}]. 
0b30: 20 20 20 20 20 6c 61 70 70 65 6e 64 20 77 68 65       lappend whe
0b40: 72 65 20 6d 6e 24 6a 3e 3d 24 6d 6e 20 6d 78 24  re mn$j>=$mn mx$
0b50: 6a 3c 3d 24 6d 78 0a 20 20 20 20 7d 0a 20 20 20  j<=$mx.    }.   
0b60: 20 73 65 74 20 77 68 65 72 65 20 22 57 48 45 52   set where "WHER
0b70: 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72 65 20 7b  E [join $where {
0b80: 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20 64 6f 5f   AND }]".    do_
0b90: 74 65 73 74 20 72 74 72 65 65 34 2d 24 6e 44 69  test rtree4-$nDi
0ba0: 6d 2e 32 2e 24 69 2e 32 20 7b 0a 20 20 20 20 20  m.2.$i.2 {.     
0bb0: 20 6c 69 73 74 20 24 77 68 65 72 65 20 5b 64 62   list $where [db
0bc0: 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20 69 64   eval "SELECT id
0bd0: 20 46 52 4f 4d 20 72 78 20 24 77 68 65 72 65 20   FROM rx $where 
0be0: 4f 52 44 45 52 20 42 59 20 69 64 22 5d 0a 20 20  ORDER BY id"].  
0bf0: 20 20 7d 20 5b 6c 69 73 74 20 24 77 68 65 72 65    } [list $where
0c00: 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43   [db eval "SELEC
0c10: 54 20 69 64 20 46 52 4f 4d 20 62 78 20 24 77 68  T id FROM bx $wh
0c20: 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22  ere ORDER BY id"
0c30: 5d 5d 0a 0a 20 20 20 20 23 20 44 6f 20 61 6e 20  ]]..    # Do an 
0c40: 6f 76 65 72 6c 61 70 73 20 71 75 65 72 79 20 6f  overlaps query o
0c50: 6e 20 61 6c 6c 20 64 69 6d 65 6e 73 69 6f 6e 73  n all dimensions
0c60: 0a 20 20 20 20 23 0a 20 20 20 20 73 65 74 20 77  .    #.    set w
0c70: 68 65 72 65 20 7b 7d 0a 20 20 20 20 66 6f 72 20  here {}.    for 
0c80: 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e  {set j 0} {$j<$n
0c90: 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a  Dim} {incr j} {.
0ca0: 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72 61        set mn [ra
0cb0: 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20 20  nd 10000].      
0cc0: 73 65 74 20 6d 78 20 5b 65 78 70 72 20 7b 24 6d  set mx [expr {$m
0cd0: 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30 30 5d  n+[randincr 500]
0ce0: 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64  }].      lappend
0cf0: 20 77 68 65 72 65 20 6d 78 24 6a 3e 3d 24 6d 6e   where mx$j>=$mn
0d00: 20 6d 6e 24 6a 3c 3d 24 6d 78 0a 20 20 20 20 7d   mn$j<=$mx.    }
0d10: 0a 20 20 20 20 73 65 74 20 77 68 65 72 65 20 22  .    set where "
0d20: 57 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65  WHERE [join $whe
0d30: 72 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20  re { AND }]".   
0d40: 20 64 6f 5f 74 65 73 74 20 72 74 72 65 65 34 2d   do_test rtree4-
0d50: 24 6e 44 69 6d 2e 32 2e 24 69 2e 33 20 7b 0a 20  $nDim.2.$i.3 {. 
0d60: 20 20 20 20 20 6c 69 73 74 20 24 77 68 65 72 65       list $where
0d70: 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43   [db eval "SELEC
0d80: 54 20 69 64 20 46 52 4f 4d 20 72 78 20 24 77 68  T id FROM rx $wh
0d90: 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22  ere ORDER BY id"
0da0: 5d 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20 24 77  ].    } [list $w
0db0: 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53  here [db eval "S
0dc0: 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 62 78  ELECT id FROM bx
0dd0: 20 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59   $where ORDER BY
0de0: 20 69 64 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f   id"]]..    # Do
0df0: 20 61 20 63 6f 6e 74 61 69 6e 65 64 2d 69 6e 20   a contained-in 
0e00: 71 75 65 72 79 20 77 69 74 68 20 73 75 72 70 6c  query with surpl
0e10: 75 73 20 63 6f 6e 74 72 61 69 6e 74 73 20 61 74  us contraints at
0e20: 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 2e 0a   the beginning..
0e30: 20 20 20 20 23 20 54 68 69 73 20 73 68 6f 75 6c      # This shoul
0e40: 64 20 66 6f 72 63 65 20 61 20 66 75 6c 6c 2d 74  d force a full-t
0e50: 61 62 6c 65 20 73 63 61 6e 20 6f 6e 20 74 68 65  able scan on the
0e60: 20 72 74 72 65 65 2e 0a 20 20 20 20 23 0a 20 20   rtree..    #.  
0e70: 20 20 73 65 74 20 77 68 65 72 65 20 7b 7d 0a 20    set where {}. 
0e80: 20 20 20 66 6f 72 20 7b 73 65 74 20 6a 20 30 7d     for {set j 0}
0e90: 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63   {$j<$nDim} {inc
0ea0: 72 20 6a 7d 20 7b 0a 20 20 20 20 20 20 6c 61 70  r j} {.      lap
0eb0: 70 65 6e 64 20 77 68 65 72 65 20 6d 6e 24 6a 3e  pend where mn$j>
0ec0: 2d 31 30 30 30 30 20 6d 78 24 6a 3c 31 30 30 30  -10000 mx$j<1000
0ed0: 30 0a 20 20 20 20 7d 0a 20 20 20 20 66 6f 72 20  0.    }.    for 
0ee0: 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e  {set j 0} {$j<$n
0ef0: 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a  Dim} {incr j} {.
0f00: 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72 61        set mn [ra
0f10: 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20 20  nd 10000].      
0f20: 73 65 74 20 6d 78 20 5b 65 78 70 72 20 7b 24 6d  set mx [expr {$m
0f30: 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30 30 5d  n+[randincr 500]
0f40: 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64  }].      lappend
0f50: 20 77 68 65 72 65 20 6d 6e 24 6a 3e 3d 24 6d 6e   where mn$j>=$mn
0f60: 20 6d 78 24 6a 3c 3d 24 6d 78 0a 20 20 20 20 7d   mx$j<=$mx.    }
0f70: 0a 20 20 20 20 73 65 74 20 77 68 65 72 65 20 22  .    set where "
0f80: 57 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65  WHERE [join $whe
0f90: 72 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20  re { AND }]".   
0fa0: 20 64 6f 5f 74 65 73 74 20 72 74 72 65 65 34 2d   do_test rtree4-
0fb0: 24 6e 44 69 6d 2e 32 2e 24 69 2e 33 20 7b 0a 20  $nDim.2.$i.3 {. 
0fc0: 20 20 20 20 20 6c 69 73 74 20 24 77 68 65 72 65       list $where
0fd0: 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43   [db eval "SELEC
0fe0: 54 20 69 64 20 46 52 4f 4d 20 72 78 20 24 77 68  T id FROM rx $wh
0ff0: 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22  ere ORDER BY id"
1000: 5d 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20 24 77  ].    } [list $w
1010: 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53  here [db eval "S
1020: 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 62 78  ELECT id FROM bx
1030: 20 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59   $where ORDER BY
1040: 20 69 64 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f   id"]]..    # Do
1050: 20 61 6e 20 6f 76 65 72 6c 61 70 73 20 71 75 65   an overlaps que
1060: 72 79 20 77 69 74 68 20 73 75 72 70 6c 75 73 20  ry with surplus 
1070: 63 6f 6e 74 72 61 69 6e 74 73 20 61 74 20 74 68  contraints at th
1080: 65 20 62 65 67 69 6e 6e 69 6e 67 2e 0a 20 20 20  e beginning..   
1090: 20 23 20 54 68 69 73 20 73 68 6f 75 6c 64 20 66   # This should f
10a0: 6f 72 63 65 20 61 20 66 75 6c 6c 2d 74 61 62 6c  orce a full-tabl
10b0: 65 20 73 63 61 6e 20 6f 6e 20 74 68 65 20 72 74  e scan on the rt
10c0: 72 65 65 2e 0a 20 20 20 20 23 0a 20 20 20 20 73  ree..    #.    s
10d0: 65 74 20 77 68 65 72 65 20 7b 7d 0a 20 20 20 20  et where {}.    
10e0: 66 6f 72 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24  for {set j 0} {$
10f0: 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a  j<$nDim} {incr j
1100: 7d 20 7b 0a 20 20 20 20 20 20 6c 61 70 70 65 6e  } {.      lappen
1110: 64 20 77 68 65 72 65 20 6d 6e 24 6a 3e 3d 2d 31  d where mn$j>=-1
1120: 30 30 30 30 20 6d 78 24 6a 3c 3d 31 30 30 30 30  0000 mx$j<=10000
1130: 0a 20 20 20 20 7d 0a 20 20 20 20 66 6f 72 20 7b  .    }.    for {
1140: 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44  set j 0} {$j<$nD
1150: 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20  im} {incr j} {. 
1160: 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72 61 6e       set mn [ran
1170: 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20 20 73  d 10000].      s
1180: 65 74 20 6d 78 20 5b 65 78 70 72 20 7b 24 6d 6e  et mx [expr {$mn
1190: 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30 30 5d 7d  +[randincr 500]}
11a0: 5d 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20  ].      lappend 
11b0: 77 68 65 72 65 20 6d 78 24 6a 3e 24 6d 6e 20 6d  where mx$j>$mn m
11c0: 6e 24 6a 3c 24 6d 78 0a 20 20 20 20 7d 0a 20 20  n$j<$mx.    }.  
11d0: 20 20 73 65 74 20 77 68 65 72 65 20 22 57 48 45    set where "WHE
11e0: 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72 65 20  RE [join $where 
11f0: 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20 64 6f  { AND }]".    do
1200: 5f 74 65 73 74 20 72 74 72 65 65 34 2d 24 6e 44  _test rtree4-$nD
1210: 69 6d 2e 32 2e 24 69 2e 34 20 7b 0a 20 20 20 20  im.2.$i.4 {.    
1220: 20 20 6c 69 73 74 20 24 77 68 65 72 65 20 5b 64    list $where [d
1230: 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20 69  b eval "SELECT i
1240: 64 20 46 52 4f 4d 20 72 78 20 24 77 68 65 72 65  d FROM rx $where
1250: 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d 0a 20   ORDER BY id"]. 
1260: 20 20 20 7d 20 5b 6c 69 73 74 20 24 77 68 65 72     } [list $wher
1270: 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45  e [db eval "SELE
1280: 43 54 20 69 64 20 46 52 4f 4d 20 62 78 20 24 77  CT id FROM bx $w
1290: 68 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64  here ORDER BY id
12a0: 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f 20 61 20  "]]..    # Do a 
12b0: 63 6f 6e 74 61 69 6e 65 64 2d 69 6e 20 71 75 65  contained-in que
12c0: 72 79 20 77 69 74 68 20 73 75 72 70 6c 75 73 20  ry with surplus 
12d0: 63 6f 6e 74 72 61 69 6e 74 73 20 61 74 20 74 68  contraints at th
12e0: 65 20 65 6e 64 0a 20 20 20 20 23 0a 20 20 20 20  e end.    #.    
12f0: 73 65 74 20 77 68 65 72 65 20 7b 7d 0a 20 20 20  set where {}.   
1300: 20 66 6f 72 20 7b 73 65 74 20 6a 20 30 7d 20 7b   for {set j 0} {
1310: 24 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20  $j<$nDim} {incr 
1320: 6a 7d 20 7b 0a 20 20 20 20 20 20 73 65 74 20 6d  j} {.      set m
1330: 6e 20 5b 72 61 6e 64 20 31 30 30 30 30 5d 0a 20  n [rand 10000]. 
1340: 20 20 20 20 20 73 65 74 20 6d 78 20 5b 65 78 70       set mx [exp
1350: 72 20 7b 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72  r {$mn+[randincr
1360: 20 35 30 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61   500]}].      la
1370: 70 70 65 6e 64 20 77 68 65 72 65 20 6d 6e 24 6a  ppend where mn$j
1380: 3e 3d 24 6d 6e 20 6d 78 24 6a 3c 24 6d 78 0a 20  >=$mn mx$j<$mx. 
1390: 20 20 20 7d 0a 20 20 20 20 66 6f 72 20 7b 73 65     }.    for {se
13a0: 74 20 6a 20 5b 65 78 70 72 20 7b 24 6e 44 69 6d  t j [expr {$nDim
13b0: 2d 31 7d 5d 7d 20 7b 24 6a 3e 3d 30 7d 20 7b 69  -1}]} {$j>=0} {i
13c0: 6e 63 72 20 6a 20 2d 31 7d 20 7b 0a 20 20 20 20  ncr j -1} {.    
13d0: 20 20 6c 61 70 70 65 6e 64 20 77 68 65 72 65 20    lappend where 
13e0: 6d 6e 24 6a 3e 3d 2d 31 30 30 30 30 20 6d 78 24  mn$j>=-10000 mx$
13f0: 6a 3c 31 30 30 30 30 0a 20 20 20 20 7d 0a 20 20  j<10000.    }.  
1400: 20 20 73 65 74 20 77 68 65 72 65 20 22 57 48 45    set where "WHE
1410: 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72 65 20  RE [join $where 
1420: 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20 64 6f  { AND }]".    do
1430: 5f 74 65 73 74 20 72 74 72 65 65 34 2d 24 6e 44  _test rtree4-$nD
1440: 69 6d 2e 32 2e 24 69 2e 35 20 7b 0a 20 20 20 20  im.2.$i.5 {.    
1450: 20 20 6c 69 73 74 20 24 77 68 65 72 65 20 5b 64    list $where [d
1460: 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20 69  b eval "SELECT i
1470: 64 20 46 52 4f 4d 20 72 78 20 24 77 68 65 72 65  d FROM rx $where
1480: 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d 0a 20   ORDER BY id"]. 
1490: 20 20 20 7d 20 5b 6c 69 73 74 20 24 77 68 65 72     } [list $wher
14a0: 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45  e [db eval "SELE
14b0: 43 54 20 69 64 20 46 52 4f 4d 20 62 78 20 24 77  CT id FROM bx $w
14c0: 68 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64  here ORDER BY id
14d0: 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f 20 61 6e  "]]..    # Do an
14e0: 20 6f 76 65 72 6c 61 70 73 20 71 75 65 72 79 20   overlaps query 
14f0: 77 69 74 68 20 73 75 72 70 6c 75 73 20 63 6f 6e  with surplus con
1500: 74 72 61 69 6e 74 73 20 61 74 20 74 68 65 20 65  traints at the e
1510: 6e 64 0a 20 20 20 20 23 0a 20 20 20 20 73 65 74  nd.    #.    set
1520: 20 77 68 65 72 65 20 7b 7d 0a 20 20 20 20 66 6f   where {}.    fo
1530: 72 20 7b 73 65 74 20 6a 20 5b 65 78 70 72 20 7b  r {set j [expr {
1540: 24 6e 44 69 6d 2d 31 7d 5d 7d 20 7b 24 6a 3e 3d  $nDim-1}]} {$j>=
1550: 30 7d 20 7b 69 6e 63 72 20 6a 20 2d 31 7d 20 7b  0} {incr j -1} {
1560: 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72  .      set mn [r
1570: 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20  and 10000].     
1580: 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20 7b 24   set mx [expr {$
1590: 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30 30  mn+[randincr 500
15a0: 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70 65 6e  ]}].      lappen
15b0: 64 20 77 68 65 72 65 20 6d 78 24 6a 3e 24 6d 6e  d where mx$j>$mn
15c0: 20 6d 6e 24 6a 3c 3d 24 6d 78 0a 20 20 20 20 7d   mn$j<=$mx.    }
15d0: 0a 20 20 20 20 66 6f 72 20 7b 73 65 74 20 6a 20  .    for {set j 
15e0: 30 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b 69  0} {$j<$nDim} {i
15f0: 6e 63 72 20 6a 7d 20 7b 0a 20 20 20 20 20 20 6c  ncr j} {.      l
1600: 61 70 70 65 6e 64 20 77 68 65 72 65 20 6d 78 24  append where mx$
1610: 6a 3e 2d 31 30 30 30 30 20 6d 6e 24 6a 3c 3d 31  j>-10000 mn$j<=1
1620: 30 30 30 30 0a 20 20 20 20 7d 0a 20 20 20 20 73  0000.    }.    s
1630: 65 74 20 77 68 65 72 65 20 22 57 48 45 52 45 20  et where "WHERE 
1640: 5b 6a 6f 69 6e 20 24 77 68 65 72 65 20 7b 20 41  [join $where { A
1650: 4e 44 20 7d 5d 22 0a 20 20 20 20 64 6f 5f 74 65  ND }]".    do_te
1660: 73 74 20 72 74 72 65 65 34 2d 24 6e 44 69 6d 2e  st rtree4-$nDim.
1670: 32 2e 24 69 2e 36 20 7b 0a 20 20 20 20 20 20 6c  2.$i.6 {.      l
1680: 69 73 74 20 24 77 68 65 72 65 20 5b 64 62 20 65  ist $where [db e
1690: 76 61 6c 20 22 53 45 4c 45 43 54 20 69 64 20 46  val "SELECT id F
16a0: 52 4f 4d 20 72 78 20 24 77 68 65 72 65 20 4f 52  ROM rx $where OR
16b0: 44 45 52 20 42 59 20 69 64 22 5d 0a 20 20 20 20  DER BY id"].    
16c0: 7d 20 5b 6c 69 73 74 20 24 77 68 65 72 65 20 5b  } [list $where [
16d0: 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20  db eval "SELECT 
16e0: 69 64 20 46 52 4f 4d 20 62 78 20 24 77 68 65 72  id FROM bx $wher
16f0: 65 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d 5d  e ORDER BY id"]]
1700: 0a 0a 20 20 20 20 23 20 44 6f 20 61 20 63 6f 6e  ..    # Do a con
1710: 74 61 69 6e 65 64 2d 69 6e 20 71 75 65 72 79 20  tained-in query 
1720: 77 69 74 68 20 73 75 72 70 6c 75 73 20 63 6f 6e  with surplus con
1730: 74 72 61 69 6e 74 73 20 77 68 65 72 65 20 74 68  traints where th
1740: 65 20 0a 20 20 20 20 23 20 63 6f 6e 73 74 72 61  e .    # constra
1750: 69 6e 74 73 20 61 70 70 65 61 72 20 69 6e 20 61  ints appear in a
1760: 20 72 61 6e 64 6f 6d 20 6f 72 64 65 72 2e 0a 20   random order.. 
1770: 20 20 20 23 0a 20 20 20 20 73 65 74 20 77 68 65     #.    set whe
1780: 72 65 20 7b 7d 0a 20 20 20 20 66 6f 72 20 7b 73  re {}.    for {s
1790: 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44 69  et j 0} {$j<$nDi
17a0: 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20 20  m} {incr j} {.  
17b0: 20 20 20 20 73 65 74 20 6d 6e 31 20 5b 72 61 6e      set mn1 [ran
17c0: 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20 20 73  d 10000].      s
17d0: 65 74 20 6d 6e 32 20 5b 65 78 70 72 20 7b 24 6d  et mn2 [expr {$m
17e0: 6e 31 2b 5b 72 61 6e 64 69 6e 63 72 20 31 30 30  n1+[randincr 100
17f0: 5d 7d 5d 0a 20 20 20 20 20 20 73 65 74 20 6d 78  ]}].      set mx
1800: 31 20 5b 65 78 70 72 20 7b 24 6d 6e 32 2b 5b 72  1 [expr {$mn2+[r
1810: 61 6e 64 69 6e 63 72 20 34 30 30 5d 7d 5d 0a 20  andincr 400]}]. 
1820: 20 20 20 20 20 73 65 74 20 6d 78 32 20 5b 65 78       set mx2 [ex
1830: 70 72 20 7b 24 6d 78 31 2b 5b 72 61 6e 64 69 6e  pr {$mx1+[randin
1840: 63 72 20 31 30 30 5d 7d 5d 0a 20 20 20 20 20 20  cr 100]}].      
1850: 6c 61 70 70 65 6e 64 20 77 68 65 72 65 20 6d 6e  lappend where mn
1860: 24 6a 3e 3d 24 6d 6e 31 20 6d 6e 24 6a 3e 24 6d  $j>=$mn1 mn$j>$m
1870: 6e 32 20 6d 78 24 6a 3c 24 6d 78 31 20 6d 78 24  n2 mx$j<$mx1 mx$
1880: 6a 3c 3d 24 6d 78 32 0a 20 20 20 20 7d 0a 20 20  j<=$mx2.    }.  
1890: 20 20 73 65 74 20 77 68 65 72 65 20 22 57 48 45    set where "WHE
18a0: 52 45 20 5b 6a 6f 69 6e 20 5b 73 63 72 61 6d 62  RE [join [scramb
18b0: 6c 65 20 24 77 68 65 72 65 5d 20 7b 20 41 4e 44  le $where] { AND
18c0: 20 7d 5d 22 0a 20 20 20 20 64 6f 5f 74 65 73 74   }]".    do_test
18d0: 20 72 74 72 65 65 34 2d 24 6e 44 69 6d 2e 32 2e   rtree4-$nDim.2.
18e0: 24 69 2e 37 20 7b 0a 20 20 20 20 20 20 6c 69 73  $i.7 {.      lis
18f0: 74 20 24 77 68 65 72 65 20 5b 64 62 20 65 76 61  t $where [db eva
1900: 6c 20 22 53 45 4c 45 43 54 20 69 64 20 46 52 4f  l "SELECT id FRO
1910: 4d 20 72 78 20 24 77 68 65 72 65 20 4f 52 44 45  M rx $where ORDE
1920: 52 20 42 59 20 69 64 22 5d 0a 20 20 20 20 7d 20  R BY id"].    } 
1930: 5b 6c 69 73 74 20 24 77 68 65 72 65 20 5b 64 62  [list $where [db
1940: 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20 69 64   eval "SELECT id
1950: 20 46 52 4f 4d 20 62 78 20 24 77 68 65 72 65 20   FROM bx $where 
1960: 4f 52 44 45 52 20 42 59 20 69 64 22 5d 5d 0a 0a  ORDER BY id"]]..
1970: 20 20 20 20 23 20 44 6f 20 61 6e 20 6f 76 65 72      # Do an over
1980: 6c 61 70 73 20 71 75 65 72 79 20 77 69 74 68 20  laps query with 
1990: 73 75 72 70 6c 75 73 20 63 6f 6e 74 72 61 69 6e  surplus contrain
19a0: 74 73 20 77 68 65 72 65 20 74 68 65 0a 20 20 20  ts where the.   
19b0: 20 23 20 63 6f 6e 73 74 72 61 69 6e 74 73 20 61   # constraints a
19c0: 70 70 65 61 72 20 69 6e 20 61 20 72 61 6e 64 6f  ppear in a rando
19d0: 6d 20 6f 72 64 65 72 2e 0a 20 20 20 20 23 0a 20  m order..    #. 
19e0: 20 20 20 73 65 74 20 77 68 65 72 65 20 7b 7d 0a     set where {}.
19f0: 20 20 20 20 66 6f 72 20 7b 73 65 74 20 6a 20 30      for {set j 0
1a00: 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e  } {$j<$nDim} {in
1a10: 63 72 20 6a 7d 20 7b 0a 20 20 20 20 20 20 73 65  cr j} {.      se
1a20: 74 20 6d 6e 31 20 5b 72 61 6e 64 20 31 30 30 30  t mn1 [rand 1000
1a30: 30 5d 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 32  0].      set mn2
1a40: 20 5b 65 78 70 72 20 7b 24 6d 6e 31 2b 5b 72 61   [expr {$mn1+[ra
1a50: 6e 64 69 6e 63 72 20 31 30 30 5d 7d 5d 0a 20 20  ndincr 100]}].  
1a60: 20 20 20 20 73 65 74 20 6d 78 31 20 5b 65 78 70      set mx1 [exp
1a70: 72 20 7b 24 6d 6e 32 2b 5b 72 61 6e 64 69 6e 63  r {$mn2+[randinc
1a80: 72 20 34 30 30 5d 7d 5d 0a 20 20 20 20 20 20 73  r 400]}].      s
1a90: 65 74 20 6d 78 32 20 5b 65 78 70 72 20 7b 24 6d  et mx2 [expr {$m
1aa0: 78 31 2b 5b 72 61 6e 64 69 6e 63 72 20 31 30 30  x1+[randincr 100
1ab0: 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70 65 6e  ]}].      lappen
1ac0: 64 20 77 68 65 72 65 20 6d 78 24 6a 3e 3d 24 6d  d where mx$j>=$m
1ad0: 6e 31 20 6d 78 24 6a 3e 24 6d 6e 32 20 6d 6e 24  n1 mx$j>$mn2 mn$
1ae0: 6a 3c 24 6d 78 31 20 6d 6e 24 6a 3c 3d 24 6d 78  j<$mx1 mn$j<=$mx
1af0: 32 0a 20 20 20 20 7d 0a 20 20 20 20 73 65 74 20  2.    }.    set 
1b00: 77 68 65 72 65 20 22 57 48 45 52 45 20 5b 6a 6f  where "WHERE [jo
1b10: 69 6e 20 5b 73 63 72 61 6d 62 6c 65 20 24 77 68  in [scramble $wh
1b20: 65 72 65 5d 20 7b 20 41 4e 44 20 7d 5d 22 0a 20  ere] { AND }]". 
1b30: 20 20 20 64 6f 5f 74 65 73 74 20 72 74 72 65 65     do_test rtree
1b40: 34 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 38 20 7b  4-$nDim.2.$i.8 {
1b50: 0a 20 20 20 20 20 20 6c 69 73 74 20 24 77 68 65  .      list $whe
1b60: 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c  re [db eval "SEL
1b70: 45 43 54 20 69 64 20 46 52 4f 4d 20 72 78 20 24  ECT id FROM rx $
1b80: 77 68 65 72 65 20 4f 52 44 45 52 20 42 59 20 69  where ORDER BY i
1b90: 64 22 5d 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20  d"].    } [list 
1ba0: 24 77 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20  $where [db eval 
1bb0: 22 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20  "SELECT id FROM 
1bc0: 62 78 20 24 77 68 65 72 65 20 4f 52 44 45 52 20  bx $where ORDER 
1bd0: 42 59 20 69 64 22 5d 5d 0a 20 20 7d 0a 0a 7d 0a  BY id"]].  }..}.
1be0: 0a 66 69 6e 69 73 68 5f 74 65 73 74 0a           .finish_test.