Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Changes to tool/schemalint.tcl.

     1      1   
     2         -
     3         -
     4         -set ::G(lSelect)  [list]           ;# List of SELECT statements to analyze
     5         -set ::G(database) ""               ;# Name of database or SQL schema file
     6         -set ::G(trace)    [list]           ;# List of data from xTrace()
     7         -set ::G(verbose)  0                ;# True if -verbose option was passed 
            2  +set ::VERBOSE 0
     8      3   
     9      4   proc usage {} {
    10      5     puts stderr "Usage: $::argv0 ?SWITCHES? DATABASE/SCHEMA"
    11      6     puts stderr "  Switches are:"
    12      7     puts stderr "  -select SQL     (recommend indexes for SQL statement)"
    13      8     puts stderr "  -verbose        (increase verbosity of output)"
            9  +  puts stderr "  -test           (run internal tests and then exit)"
    14     10     puts stderr ""
    15     11     exit
    16     12   }
    17     13   
    18         -proc process_cmdline_args {argv} {
    19         -  global G
           14  +proc process_cmdline_args {ctxvar argv} {
           15  +  upvar $ctxvar G
    20     16     set nArg [llength $argv]
    21     17     set G(database) [lindex $argv end]
    22     18   
    23     19     for {set i 0} {$i < [llength $argv]-1} {incr i} {
    24     20       set k [lindex $argv $i]
    25     21       switch -- $k {
    26     22         -select {
    27     23           incr i
    28     24           if {$i>=[llength $argv]-1} usage
    29     25           lappend G(lSelect) [lindex $argv $i]
    30     26         }
    31     27         -verbose {
    32         -        set G(verbose) 1
           28  +        set ::VERBOSE 1
           29  +      }
           30  +      -test {
           31  +        sqlidx_internal_tests
    33     32         }
    34     33         default {
    35     34           usage
    36     35         }
    37     36       }
    38     37     }
           38  +
           39  +  if {$G(database)=="-test"} {
           40  +    sqlidx_internal_tests
           41  +  }
    39     42   }
    40     43   
    41         -proc open_database {} {
    42         -  global G
           44  +proc open_database {ctxvar} {
           45  +  upvar $ctxvar G
    43     46     sqlite3 db ""
    44     47   
    45     48     # Check if the "database" file is really an SQLite database. If so, copy
    46     49     # it into the temp db just opened. Otherwise, assume that it is an SQL
    47     50     # schema and execute it directly.
    48     51     set fd [open $G(database)]
    49     52     set hdr [read $fd 16]
................................................................................
    58     61     } else {
    59     62       append hdr [read $fd]
    60     63       db eval $hdr
    61     64       close $fd
    62     65     }
    63     66   }
    64     67   
    65         -proc analyze_selects {} {
    66         -  global G
           68  +proc analyze_selects {ctxvar} {
           69  +  upvar $ctxvar G
    67     70     set G(trace) ""
    68     71   
    69     72     # Collect a line of xTrace output for each loop in the set of SELECT
    70     73     # statements.
    71         -  proc xTrace {zMsg} { lappend ::G(trace) $zMsg }
    72         -  db trace "lappend ::G(trace)"
           74  +  proc xTrace {zMsg} { 
           75  +    upvar G G
           76  +    lappend G(trace) $zMsg 
           77  +  }
           78  +  db trace xTrace
    73     79     foreach s $G(lSelect) {
    74     80       set stmt [sqlite3_prepare_v2 db $s -1 dummy]
    75     81       set rc [sqlite3_finalize $stmt]
    76     82       if {$rc!="SQLITE_OK"} {
    77     83         error "Failed to compile SQL: [sqlite3_errmsg db]"
    78     84       }
    79     85     }
    80     86   
    81     87     db trace ""
    82         -  if {$G(verbose)} {
           88  +  if {$::VERBOSE} {
    83     89       foreach t $G(trace) { puts "trace: $t" }
    84     90     }
    85     91   
    86     92     # puts $G(trace)
    87     93   }
    88     94   
    89     95   # The argument is a list of the form:
................................................................................
   114    120   
   115    121     return $ll
   116    122   }
   117    123   
   118    124   #--------------------------------------------------------------------------
   119    125   # Formulate a CREATE INDEX statement that creates an index on table $tname.
   120    126   #
   121         -proc eqset_to_index {tname eqset {range {}}} {
   122         -  global G
          127  +proc eqset_to_index {ctxvar tname eqset {range {}}} {
          128  +  upvar $ctxvar G
          129  +
   123    130     set lCols [list]
   124    131     set idxname $tname
   125         -  foreach e [concat [lsort $eqset] [list $range]] {
          132  +  foreach e [lsort $eqset] { 
   126    133       if {[llength $e]==0} continue
   127    134       foreach {c collate} $e {}
   128    135       lappend lCols "$c collate $collate"
   129    136       append idxname "_$c"
   130    137       if {[string compare -nocase binary $collate]!=0} {
   131    138         append idxname [string tolower $collate]
   132    139       }
   133    140     }
          141  +
          142  +  foreach {c collate dir} $range {
          143  +    append idxname "_$c"
          144  +    if {[string compare -nocase binary $collate]!=0} {
          145  +      append idxname [string tolower $collate]
          146  +    }
          147  +    if {$dir=="DESC"} {
          148  +      lappend lCols "$c collate $collate DESC"
          149  +      append idxname "desc"
          150  +    } else {
          151  +      lappend lCols "$c collate $collate"
          152  +    }
          153  +  }
   134    154   
   135    155     set create_index "CREATE INDEX $idxname ON ${tname}("
   136    156     append create_index [join $lCols ", "]
   137    157     append create_index ");"
   138    158   
   139    159     set G(trial.$idxname) $create_index
   140    160   }
................................................................................
   160    180         }
   161    181         set lRet $lNew
   162    182       } 
   163    183     }
   164    184     return $lRet
   165    185   }
   166    186   
   167         -proc find_trial_indexes {} {
   168         -  global G
          187  +proc find_trial_indexes {ctxvar} {
          188  +  upvar $ctxvar G
   169    189     foreach t $G(trace) {
   170    190       set tname [lindex $t 0]
   171    191       catch { array unset mask }
   172    192   
          193  +    set orderby [list]
   173    194       if {[lindex $t end 0]=="orderby"} {
   174    195         set orderby [lrange [lindex $t end] 1 end]
   175    196       }
   176    197   
   177    198       foreach lCons [expand_or_cons [lrange $t 2 end]] {
   178         -      set constraints [list]
   179    199   
          200  +      # Populate the array mask() so that it contains an entry for each
          201  +      # combination of prerequisite scans that may lead to distinct sets
          202  +      # of constraints being usable.
          203  +      #
          204  +      catch { array unset mask }
          205  +      set mask(0) 1
   180    206         foreach a $lCons {
   181    207           set type [lindex $a 0]
   182    208           if {$type=="eq" || $type=="range"} {
   183    209             set m [lindex $a 3]
   184    210             foreach k [array names mask] { set mask([expr ($k & $m)]) 1 }
   185    211             set mask($m) 1
   186         -          lappend constraints $a
   187    212           }
   188    213         }
   189    214   
          215  +      # Loop once for each distinct prerequisite scan mask identified in
          216  +      # the previous block.
          217  +      #
   190    218         foreach k [array names mask] {
          219  +
          220  +        # Identify the constraints available for prerequisite mask $k. For
          221  +        # each == constraint, set an entry in the eq() array as follows:
          222  +        # 
          223  +        #   set eq(<col>) <collation>
          224  +        #
          225  +        # If there is more than one == constraint for a column, and they use
          226  +        # different collation sequences, <collation> is replaced with a list
          227  +        # of the possible collation sequences. For example, for:
          228  +        #
          229  +        #   SELECT * FROM t1 WHERE a=? COLLATE BINARY AND a=? COLLATE NOCASE
          230  +        #
          231  +        # Set the following entry in the eq() array:
          232  +        #
          233  +        #   set eq(a) {binary nocase}
          234  +        #
          235  +        # For each range constraint found an entry is appended to the $ranges
          236  +        # list. The entry is itself a list of the form {<col> <collation>}.
          237  +        #
   191    238           catch {array unset eq}
   192         -        foreach a $constraints {
   193         -          foreach {type col collate m} $a {
   194         -            if {($m & $k)==$m} {
   195         -              if {$type=="eq"} {
   196         -                lappend eq($col) $collate
   197         -              } else {
   198         -                set range($col.$collate) 1
          239  +        set ranges [list]
          240  +        foreach a $lCons {
          241  +          set type [lindex $a 0]
          242  +          if {$type=="eq" || $type=="range"} {
          243  +            foreach {type col collate m} $a {
          244  +              if {($m & $k)==$m} {
          245  +                if {$type=="eq"} {
          246  +                  lappend eq($col) $collate
          247  +                } else {
          248  +                  lappend ranges [list $col $collate ASC]
          249  +                }
   199    250                 }
   200    251               }
   201    252             }
   202    253           }
          254  +        set ranges [lsort -unique $ranges]
          255  +        if {$orderby != ""} {
          256  +          lappend ranges $orderby
          257  +        }
   203    258   
   204         -        #puts "mask=$k eq=[array get eq] range=[array get range]"
   205         -        
   206         -        set ranges [array names range]
   207    259           foreach eqset [expand_eq_list [array get eq]] {
   208         -          if {[llength $ranges]==0} {
   209         -            eqset_to_index $tname $eqset
   210         -          } else {
   211         -            foreach r $ranges {
          260  +          if {$eqset != ""} {
          261  +            eqset_to_index G $tname $eqset
          262  +          }
          263  +
          264  +          foreach r $ranges {
          265  +            set tail [list]
          266  +            foreach {c collate dir} $r {
   212    267                 set bSeen 0
   213         -              foreach {c collate} [split $r .] {}
   214    268                 foreach e $eqset {
   215    269                   if {[lindex $e 0] == $c} {
   216    270                     set bSeen 1
   217    271                     break
   218    272                   }
   219    273                 }
   220         -              if {$bSeen} {
   221         -                eqset_to_index $tname $eqset
   222         -              } else {
   223         -                eqset_to_index $tname $eqset [list $c $collate]
   224         -              }
          274  +              if {$bSeen==0} { lappend tail {*}$r }
          275  +            }
          276  +            if {[llength $tail]} {
          277  +              eqset_to_index G $tname $eqset $r
   225    278               }
   226    279             }
   227    280           }
   228    281         }
   229    282       }
   230    283     }
   231    284   
   232         -  if {$G(verbose)} {
          285  +  if {$::VERBOSE} {
   233    286       foreach k [array names G trial.*] { puts "index: $G($k)" }
   234    287     }
   235    288   }
   236    289   
   237         -proc run_trials {} {
   238         -  global G
          290  +proc run_trials {ctxvar} {
          291  +  upvar $ctxvar G
          292  +  set ret [list]
   239    293   
   240    294     foreach k [array names G trial.*] {
   241    295       set idxname [lindex [split $k .] 1]
   242    296       db eval $G($k)
   243    297       set pgno [db one {SELECT rootpage FROM sqlite_master WHERE name = $idxname}]
   244    298       set IDX($pgno) $idxname
   245    299     }
................................................................................
   249    303     foreach s $G(lSelect) {
   250    304       db eval "EXPLAIN $s" x {
   251    305         if {($x(opcode)=="OpenRead" || $x(opcode)=="ReopenIdx")} {
   252    306           if {[info exists IDX($x(p2))]} { set used($IDX($x(p2))) 1 }
   253    307         }
   254    308       }
   255    309       foreach idx [array names used] {
   256         -      puts $G(trial.$idx)
          310  +      lappend ret $G(trial.$idx)
   257    311       }
   258    312     }
          313  +
          314  +  set ret
          315  +}
          316  +
          317  +proc sqlidx_init_context {varname} {
          318  +  upvar $varname G
          319  +  set G(lSelect)  [list]           ;# List of SELECT statements to analyze
          320  +  set G(database) ""               ;# Name of database or SQL schema file
          321  +  set G(trace)    [list]           ;# List of data from xTrace()
          322  +}
          323  +
          324  +#-------------------------------------------------------------------------
          325  +# The following is test code only.
          326  +#
          327  +proc sqlidx_one_test {tn schema select expected} {
          328  +#  if {$tn!=2} return
          329  +  sqlidx_init_context C
          330  +
          331  +  sqlite3 db ""
          332  +  db eval $schema
          333  +  lappend C(lSelect) $select
          334  +  analyze_selects C
          335  +  find_trial_indexes C
          336  +
          337  +  set idxlist [run_trials C]
          338  +  if {$idxlist != [list {*}$expected]} {
          339  +    puts stderr "Test $tn failed"
          340  +    puts stderr "Expected: $expected"
          341  +    puts stderr "Got: $idxlist"
          342  +    exit -1
          343  +  }
          344  +
          345  +  db close
          346  +}
          347  +
          348  +proc sqlidx_internal_tests {} {
          349  +
          350  +  # No indexes for a query with no constraints.
          351  +  sqlidx_one_test 0 {
          352  +    CREATE TABLE t1(a, b, c);
          353  +  } {
          354  +    SELECT * FROM t1;
          355  +  } {
          356  +  }
          357  +
          358  +  sqlidx_one_test 1 {
          359  +    CREATE TABLE t1(a, b, c);
          360  +    CREATE TABLE t2(x, y, z);
          361  +  } {
          362  +    SELECT a FROM t1, t2 WHERE a=? AND x=c
          363  +  } {
          364  +    {CREATE INDEX t2_x ON t2(x collate BINARY);}
          365  +    {CREATE INDEX t1_a_c ON t1(a collate BINARY, c collate BINARY);}
          366  +  }
          367  +
          368  +  sqlidx_one_test 2 {
          369  +    CREATE TABLE t1(a, b, c);
          370  +  } {
          371  +    SELECT * FROM t1 WHERE b>?;
          372  +  } {
          373  +    {CREATE INDEX t1_b ON t1(b collate BINARY);}
          374  +  }
          375  +
          376  +  sqlidx_one_test 3 {
          377  +    CREATE TABLE t1(a, b, c);
          378  +  } {
          379  +    SELECT * FROM t1 WHERE b COLLATE nocase BETWEEN ? AND ?
          380  +  } {
          381  +    {CREATE INDEX t1_bnocase ON t1(b collate NOCASE);}
          382  +  }
          383  +
          384  +  sqlidx_one_test 4 {
          385  +    CREATE TABLE t1(a, b, c);
          386  +  } {
          387  +    SELECT a FROM t1 ORDER BY b;
          388  +  } {
          389  +    {CREATE INDEX t1_b ON t1(b collate BINARY);}
          390  +  }
          391  +
          392  +  sqlidx_one_test 5 {
          393  +    CREATE TABLE t1(a, b, c);
          394  +  } {
          395  +    SELECT a FROM t1 WHERE a=? ORDER BY b;
          396  +  } {
          397  +    {CREATE INDEX t1_a_b ON t1(a collate BINARY, b collate BINARY);}
          398  +  }
          399  +
          400  +  sqlidx_one_test 5 {
          401  +    CREATE TABLE t1(a, b, c);
          402  +  } {
          403  +    SELECT min(a) FROM t1
          404  +  } {
          405  +    {CREATE INDEX t1_a ON t1(a collate BINARY);}
          406  +  }
          407  +
          408  +  sqlidx_one_test 6 {
          409  +    CREATE TABLE t1(a, b, c);
          410  +  } {
          411  +    SELECT * FROM t1 ORDER BY a ASC, b COLLATE nocase DESC, c ASC;
          412  +  } {
          413  +    {CREATE INDEX t1_a_bnocasedesc_c ON t1(a collate BINARY, b collate NOCASE DESC, c collate BINARY);}
          414  +  }
          415  +
          416  +  exit
   259    417   }
          418  +# End of internal test code.
          419  +#-------------------------------------------------------------------------
   260    420   
   261         -process_cmdline_args $argv
   262         -open_database
   263         -analyze_selects
   264         -find_trial_indexes
   265         -run_trials
          421  +sqlidx_init_context D
          422  +process_cmdline_args D $argv
          423  +open_database D
          424  +analyze_selects D
          425  +find_trial_indexes D
          426  +foreach idx [run_trials D] { puts $idx }
   266    427