/ Hex Artifact Content
Login

Artifact 62d943a02f722948f4410ee0b53c3cb39acd7c41afb083df8d7004238fe90a20:


0000: 23 20 32 30 31 38 2d 30 36 2d 30 37 0a 23 0a 23  # 2018-06-07.#.#
0010: 20 54 68 65 20 61 75 74 68 6f 72 20 64 69 73 63   The author disc
0020: 6c 61 69 6d 73 20 63 6f 70 79 72 69 67 68 74 20  laims copyright 
0030: 74 6f 20 74 68 69 73 20 73 6f 75 72 63 65 20 63  to this source c
0040: 6f 64 65 2e 20 20 49 6e 20 70 6c 61 63 65 20 6f  ode.  In place o
0050: 66 0a 23 20 61 20 6c 65 67 61 6c 20 6e 6f 74 69  f.# a legal noti
0060: 63 65 2c 20 68 65 72 65 20 69 73 20 61 20 62 6c  ce, here is a bl
0070: 65 73 73 69 6e 67 3a 0a 23 0a 23 20 20 20 20 4d  essing:.#.#    M
0080: 61 79 20 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61  ay you do good a
0090: 6e 64 20 6e 6f 74 20 65 76 69 6c 2e 0a 23 20 20  nd not evil..#  
00a0: 20 20 4d 61 79 20 79 6f 75 20 66 69 6e 64 20 66    May you find f
00b0: 6f 72 67 69 76 65 6e 65 73 73 20 66 6f 72 20 79  orgiveness for y
00c0: 6f 75 72 73 65 6c 66 20 61 6e 64 20 66 6f 72 67  ourself and forg
00d0: 69 76 65 20 6f 74 68 65 72 73 2e 0a 23 20 20 20  ive others..#   
00e0: 20 4d 61 79 20 79 6f 75 20 73 68 61 72 65 20 66   May you share f
00f0: 72 65 65 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b  reely, never tak
0100: 69 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f  ing more than yo
0110: 75 20 67 69 76 65 2e 0a 23 0a 23 2a 2a 2a 2a 2a  u 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 0a 23 0a 23 20 41 20 6d 75 6c 74 69 2d 6b  **.#.# A multi-k
0170: 65 79 20 69 6e 64 65 78 20 74 68 61 74 20 75 73  ey index that us
0180: 65 73 20 61 6e 20 49 4e 20 6f 70 65 72 61 74 6f  es an IN operato
0190: 72 20 6f 6e 20 6f 6e 65 20 6f 66 20 74 68 65 20  r on one of the 
01a0: 6b 65 79 73 20 6f 74 68 65 72 0a 23 20 74 68 61  keys other.# tha
01b0: 6e 20 74 68 65 20 6c 65 66 74 2d 6d 6f 73 74 20  n the left-most 
01c0: 6b 65 79 20 69 73 20 61 62 6c 65 20 74 6f 20 61  key is able to a
01d0: 62 6f 72 74 20 74 68 65 20 49 4e 2d 6f 70 65 72  bort the IN-oper
01e0: 61 74 6f 72 20 6c 6f 6f 70 20 65 61 72 6c 79 0a  ator loop early.
01f0: 23 20 69 66 20 6b 65 79 20 74 65 72 6d 73 20 66  # if key terms f
0200: 75 72 74 68 65 72 20 74 6f 20 74 68 65 20 6c 65  urther to the le
0210: 66 74 20 64 6f 20 6e 6f 74 20 6d 61 74 63 68 2e  ft do not match.
0220: 0a 23 0a 23 20 43 61 6c 6c 20 74 68 69 73 20 74  .#.# Call this t
0230: 68 65 20 22 6d 75 6c 74 69 6b 65 79 2d 49 4e 2d  he "multikey-IN-
0240: 6f 70 65 72 61 74 6f 72 20 65 61 72 6c 79 2d 6f  operator early-o
0250: 75 74 20 6f 70 74 69 6d 69 7a 61 74 69 6f 6e 22  ut optimization"
0260: 20 6f 72 0a 23 20 6a 75 73 74 20 22 49 4e 2d 65   or.# just "IN-e
0270: 61 72 6c 79 2d 6f 75 74 22 20 6f 70 74 69 6d 69  arly-out" optimi
0280: 7a 61 74 69 6f 6e 20 66 6f 72 20 73 68 6f 72 74  zation for short
0290: 2e 0a 23 0a 0a 73 65 74 20 74 65 73 74 64 69 72  ..#..set testdir
02a0: 20 5b 66 69 6c 65 20 64 69 72 6e 61 6d 65 20 24   [file dirname $
02b0: 61 72 67 76 30 5d 0a 73 6f 75 72 63 65 20 24 74  argv0].source $t
02c0: 65 73 74 64 69 72 2f 74 65 73 74 65 72 2e 74 63  estdir/tester.tc
02d0: 6c 0a 73 65 74 20 74 65 73 74 70 72 65 66 69 78  l.set testprefix
02e0: 20 69 6e 36 0a 0a 64 6f 5f 74 65 73 74 20 69 6e   in6..do_test in
02f0: 36 2d 31 2e 31 20 7b 0a 20 20 64 62 20 65 76 61  6-1.1 {.  db eva
0300: 6c 20 7b 0a 20 20 20 20 43 52 45 41 54 45 20 54  l {.    CREATE T
0310: 41 42 4c 45 20 74 31 28 61 2c 62 2c 63 2c 64 29  ABLE t1(a,b,c,d)
0320: 3b 0a 20 20 20 20 57 49 54 48 20 52 45 43 55 52  ;.    WITH RECUR
0330: 53 49 56 45 20 63 28 78 29 20 41 53 20 28 56 41  SIVE c(x) AS (VA
0340: 4c 55 45 53 28 31 29 20 55 4e 49 4f 4e 20 41 4c  LUES(1) UNION AL
0350: 4c 20 53 45 4c 45 43 54 20 78 2b 31 20 46 52 4f  L SELECT x+1 FRO
0360: 4d 20 63 20 57 48 45 52 45 20 78 3c 31 30 30 29  M c WHERE x<100)
0370: 0a 20 20 20 20 20 20 49 4e 53 45 52 54 20 49 4e  .      INSERT IN
0380: 54 4f 20 74 31 28 61 2c 62 2c 63 2c 64 29 0a 20  TO t1(a,b,c,d). 
0390: 20 20 20 20 20 20 20 53 45 4c 45 43 54 20 31 30         SELECT 10
03a0: 30 2c 20 32 30 30 2b 78 2f 32 2c 20 33 30 30 2b  0, 200+x/2, 300+
03b0: 78 2f 35 2c 20 78 20 46 52 4f 4d 20 63 3b 0a 20  x/5, x FROM c;. 
03c0: 20 20 20 43 52 45 41 54 45 20 49 4e 44 45 58 20     CREATE INDEX 
03d0: 74 31 61 62 63 20 4f 4e 20 74 31 28 61 2c 62 2c  t1abc ON t1(a,b,
03e0: 63 29 3b 0a 20 20 20 20 41 4e 41 4c 59 5a 45 3b  c);.    ANALYZE;
03f0: 0a 20 20 20 20 55 50 44 41 54 45 20 73 71 6c 69  .    UPDATE sqli
0400: 74 65 5f 73 74 61 74 31 20 53 45 54 20 73 74 61  te_stat1 SET sta
0410: 74 3d 27 31 30 30 30 30 30 30 20 35 30 30 30 30  t='1000000 50000
0420: 30 20 35 30 30 20 35 30 27 3b 0a 20 20 20 20 41  0 500 50';.    A
0430: 4e 41 4c 59 5a 45 20 73 71 6c 69 74 65 5f 6d 61  NALYZE sqlite_ma
0440: 73 74 65 72 3b 0a 20 20 7d 0a 20 20 73 65 74 20  ster;.  }.  set 
0450: 3a 3a 73 71 6c 69 74 65 5f 73 65 61 72 63 68 5f  ::sqlite_search_
0460: 63 6f 75 6e 74 20 30 0a 20 20 64 62 20 65 76 61  count 0.  db eva
0470: 6c 20 7b 0a 20 20 20 20 53 45 4c 45 43 54 20 64  l {.    SELECT d
0480: 20 46 52 4f 4d 20 74 31 0a 20 20 20 20 20 57 48   FROM t1.     WH
0490: 45 52 45 20 61 3d 39 39 0a 20 20 20 20 20 20 20  ERE a=99.       
04a0: 41 4e 44 20 62 20 49 4e 20 28 32 30 30 2c 32 30  AND b IN (200,20
04b0: 35 2c 32 30 31 2c 32 30 34 29 0a 20 20 20 20 20  5,201,204).     
04c0: 20 20 41 4e 44 20 63 20 49 4e 20 28 33 30 34 2c    AND c IN (304,
04d0: 33 30 32 2c 33 30 39 2c 33 30 38 29 3b 0a 20 20  302,309,308);.  
04e0: 7d 0a 7d 20 7b 7d 0a 64 6f 5f 74 65 73 74 20 69  }.} {}.do_test i
04f0: 6e 36 2d 31 2e 32 20 7b 0a 20 20 73 65 74 20 3a  n6-1.2 {.  set :
0500: 3a 73 71 6c 69 74 65 5f 73 65 61 72 63 68 5f 63  :sqlite_search_c
0510: 6f 75 6e 74 0a 7d 20 7b 30 7d 20 20 3b 23 20 57  ount.} {0}  ;# W
0520: 69 74 68 6f 75 74 20 74 68 65 20 49 4e 2d 65 61  ithout the IN-ea
0530: 72 6c 79 2d 6f 75 74 20 6f 70 74 69 6d 69 7a 61  rly-out optimiza
0540: 74 69 6f 6e 2c 20 74 68 69 73 20 76 61 6c 75 65  tion, this value
0550: 20 77 6f 75 6c 64 20 62 65 20 31 35 0a 0a 23 20   would be 15..# 
0560: 54 68 65 20 6d 75 6c 74 69 6b 65 79 2d 49 4e 2d  The multikey-IN-
0570: 6f 70 65 72 61 74 6f 72 20 65 61 72 6c 79 2d 6f  operator early-o
0580: 75 74 20 6f 70 74 69 6d 69 7a 61 74 69 6f 6e 20  ut optimization 
0590: 64 6f 65 73 20 6e 6f 74 20 61 70 70 6c 79 0a 23  does not apply.#
05a0: 20 77 68 65 6e 20 74 68 65 20 49 4e 20 6f 70 65   when the IN ope
05b0: 72 61 74 6f 72 20 69 73 20 6f 6e 20 74 68 65 20  rator is on the 
05c0: 6c 65 66 74 2d 6d 6f 73 74 20 63 6f 6c 75 6d 6e  left-most column
05d0: 20 6f 66 20 74 68 65 20 69 6e 64 65 78 2e 0a 23   of the index..#
05e0: 0a 64 6f 5f 74 65 73 74 20 69 6e 36 2d 31 2e 33  .do_test in6-1.3
05f0: 20 7b 0a 20 20 64 62 20 65 76 61 6c 20 7b 0a 20   {.  db eval {. 
0600: 20 20 20 45 58 50 4c 41 49 4e 0a 20 20 20 20 53     EXPLAIN.    S
0610: 45 4c 45 43 54 20 64 20 46 52 4f 4d 20 74 31 0a  ELECT d FROM t1.
0620: 20 20 20 20 20 20 57 48 45 52 45 20 61 20 49 4e        WHERE a IN
0630: 20 28 39 38 2c 39 39 2c 31 30 30 2c 31 30 31 29   (98,99,100,101)
0640: 0a 20 20 20 20 20 20 20 20 41 4e 44 20 62 3d 32  .        AND b=2
0650: 30 30 20 41 4e 44 20 63 3d 33 30 30 3b 0a 20 20  00 AND c=300;.  
0660: 7d 0a 7d 20 7b 7e 2f 28 49 66 4e 6f 48 6f 70 65  }.} {~/(IfNoHope
0670: 7c 53 65 65 6b 48 69 74 29 2f 7d 0a 0a 73 65 74  |SeekHit)/}..set
0680: 20 73 71 6c 69 74 65 5f 73 65 61 72 63 68 5f 63   sqlite_search_c
0690: 6f 75 6e 74 20 30 0a 64 6f 5f 65 78 65 63 73 71  ount 0.do_execsq
06a0: 6c 5f 74 65 73 74 20 69 6e 36 2d 31 2e 34 20 7b  l_test in6-1.4 {
06b0: 0a 20 53 45 4c 45 43 54 20 64 20 46 52 4f 4d 20  . SELECT d FROM 
06c0: 74 31 0a 20 20 57 48 45 52 45 20 61 3d 31 30 30  t1.  WHERE a=100
06d0: 0a 20 20 20 20 41 4e 44 20 62 20 49 4e 20 28 32  .    AND b IN (2
06e0: 30 30 2c 32 30 31 2c 32 30 32 2c 32 30 34 29 0a  00,201,202,204).
06f0: 20 20 20 20 41 4e 44 20 63 20 49 4e 20 28 33 30      AND c IN (30
0700: 30 2c 33 30 32 2c 33 30 31 2c 33 30 35 29 0a 20  0,302,301,305). 
0710: 20 4f 52 44 45 52 20 42 59 20 2b 64 3b 0a 7d 20   ORDER BY +d;.} 
0720: 7b 31 20 32 20 33 20 34 20 35 20 38 20 39 7d 0a  {1 2 3 4 5 8 9}.
0730: 64 6f 5f 74 65 73 74 20 69 6e 36 2d 31 2e 35 20  do_test in6-1.5 
0740: 7b 0a 20 20 73 65 74 20 3a 3a 73 71 6c 69 74 65  {.  set ::sqlite
0750: 5f 73 65 61 72 63 68 5f 63 6f 75 6e 74 0a 7d 20  _search_count.} 
0760: 7b 33 39 7d 0a 0a 64 6f 5f 65 78 65 63 73 71 6c  {39}..do_execsql
0770: 5f 74 65 73 74 20 69 6e 36 2d 32 2e 31 20 7b 0a  _test in6-2.1 {.
0780: 20 20 43 52 45 41 54 45 20 54 41 42 4c 45 20 74    CREATE TABLE t
0790: 32 28 65 20 49 4e 54 20 55 4e 49 51 55 45 2c 20  2(e INT UNIQUE, 
07a0: 66 20 54 45 58 54 29 3b 0a 20 20 53 45 4c 45 43  f TEXT);.  SELEC
07b0: 54 20 64 2c 20 66 20 46 52 4f 4d 20 74 31 20 4c  T d, f FROM t1 L
07c0: 45 46 54 20 4a 4f 49 4e 20 74 32 20 4f 4e 20 28  EFT JOIN t2 ON (
07d0: 65 3d 64 29 0a 20 20 57 48 45 52 45 20 61 3d 31  e=d).  WHERE a=1
07e0: 30 30 0a 20 20 20 20 41 4e 44 20 62 20 49 4e 20  00.    AND b IN 
07f0: 28 32 30 30 2c 32 30 31 2c 32 30 32 2c 32 30 34  (200,201,202,204
0800: 29 0a 20 20 20 20 41 4e 44 20 63 20 49 4e 20 28  ).    AND c IN (
0810: 33 30 30 2c 33 30 32 2c 33 30 31 2c 33 30 35 29  300,302,301,305)
0820: 0a 20 20 4f 52 44 45 52 20 42 59 20 2b 64 3b 0a  .  ORDER BY +d;.
0830: 7d 20 7b 31 20 7b 7d 20 32 20 7b 7d 20 33 20 7b  } {1 {} 2 {} 3 {
0840: 7d 20 34 20 7b 7d 20 35 20 7b 7d 20 38 20 7b 7d  } 4 {} 5 {} 8 {}
0850: 20 39 20 7b 7d 7d 0a 0a 66 69 6e 69 73 68 5f 74   9 {}}..finish_t
0860: 65 73 74 0a                                      est.