Documentation Source Text

Check-in [f990657458]
Login

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

Overview
Comment:Enable partial indices.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f990657458d8dc37bfcd002d17a3a3a5ece316f8
User & Date: drh 2013-08-02 18:27:52
Context
2013-08-02
23:41
Updates to requirements marks. check-in: 498cd0709e user: drh tags: trunk
18:27
Enable partial indices. check-in: f990657458 user: drh tags: trunk
18:27
Corrections to partial index documentation. Closed-Leaf check-in: 3e022afe53 user: drh tags: partial-indices
2013-08-01
17:48
Fix the description of COLLATE operator precedence so that it is aligned with the implementation. check-in: 52366f9588 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to art/syntax/alter-table-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/analyze-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/attach-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/begin-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/bubble-generator-data.tcl.

    79     79        line RELEASE {optx SAVEPOINT} /savepoint-name
    80     80     }
    81     81     create-index-stmt {
    82     82       stack
    83     83          {line CREATE {opt UNIQUE} INDEX {opt IF NOT EXISTS}}
    84     84          {line {optx /database-name .} /index-name
    85     85                ON /table-name ( {loop indexed-column ,} )}
           86  +       {line {optx WHERE /expr}}
    86     87     }
    87     88     indexed-column {
    88     89         line /column-name {optx COLLATE /collation-name} {or ASC DESC nil} 
    89     90     }
    90     91     create-table-stmt {
    91     92       stack
    92     93          {line CREATE {or {} TEMP TEMPORARY} TABLE {opt IF NOT EXISTS}}

Changes to art/syntax/bubble-generator.tcl.

    30     30   }
    31     31   incr bn
    32     32   set b $side.b$bn
    33     33   button $b -text Everything -command {draw_all_graphs}
    34     34   pack $b -side top -fill x -expand 1
    35     35   
    36     36   set tagcnt 0                      ;# tag counter
    37         -set font1 {Helvetica 14 bold}     ;# default token font
    38         -set font2 {Helvetica 12}          ;# default variable font
           37  +set font1 {Helvetica 12 bold}     ;# default token font
           38  +set font2 {Helvetica 10}           ;# default variable font
    39     39   set RADIUS 9                      ;# default turn radius
    40     40   set HSEP 17                       ;# horizontal separation
    41     41   set VSEP 9                        ;# vertical separation
    42     42   set DPI 80                        ;# dots per inch
    43     43   
    44     44   
    45     45   # Draw a right-hand turn around.  Approximately a ")"
................................................................................
   629    629     .c delete all
   630    630     wm deiconify .
   631    631     wm title . $name
   632    632     draw_diagram "line bullet [list $spec] bullet"
   633    633     foreach {x0 y0 x1 y1} [.c bbox all] break
   634    634     .c move all [expr {2-$x0}] [expr {2-$y0}]
   635    635     foreach {x0 y0 x1 y1} [.c bbox all] break
          636  +  .c create rect -100 -100 [expr {$x1+100}] [expr {$y1+100}] \
          637  +     -fill white -outline white -tags bgrect
          638  +  .c lower bgrect
   636    639     .c config -width $x1 -height $y1
   637    640     update
   638    641     .c postscript -file $name.ps -width [expr {$x1+2}] -height [expr {$y1+2}]
   639    642     global DPI
          643  +  .c delete bgrect
   640    644     exec convert -density ${DPI}x$DPI -antialias $name.ps $name.gif
   641    645     if {$do_xv} {
   642    646       if {[catch {exec xv $name.gif &}]} {
   643    647         exec display $name.gif &
   644    648       }
   645    649     }
   646    650   }

Changes to art/syntax/column-constraint.gif.

cannot compute difference between binary files

Changes to art/syntax/column-def.gif.

cannot compute difference between binary files

Changes to art/syntax/comment-syntax.gif.

cannot compute difference between binary files

Changes to art/syntax/commit-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/compound-operator.gif.

cannot compute difference between binary files

Changes to art/syntax/conflict-clause.gif.

cannot compute difference between binary files

Changes to art/syntax/create-index-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/create-table-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/create-trigger-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/create-view-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/create-virtual-table-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/delete-stmt-limited.gif.

cannot compute difference between binary files

Changes to art/syntax/delete-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/detach-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/drop-index-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/drop-table-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/drop-trigger-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/drop-view-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/expr.gif.

cannot compute difference between binary files

Changes to art/syntax/foreign-key-clause.gif.

cannot compute difference between binary files

Changes to art/syntax/indexed-column.gif.

cannot compute difference between binary files

Changes to art/syntax/insert-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/join-constraint.gif.

cannot compute difference between binary files

Changes to art/syntax/join-op.gif.

cannot compute difference between binary files

Changes to art/syntax/join-source.gif.

cannot compute difference between binary files

Changes to art/syntax/literal-value.gif.

cannot compute difference between binary files

Changes to art/syntax/numeric-literal.gif.

cannot compute difference between binary files

Changes to art/syntax/ordering-term.gif.

cannot compute difference between binary files

Changes to art/syntax/pragma-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/pragma-value.gif.

cannot compute difference between binary files

Changes to art/syntax/qualified-table-name.gif.

cannot compute difference between binary files

Changes to art/syntax/raise-function.gif.

cannot compute difference between binary files

Changes to art/syntax/reindex-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/release-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/result-column.gif.

cannot compute difference between binary files

Changes to art/syntax/rollback-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/savepoint-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/select-core.gif.

cannot compute difference between binary files

Changes to art/syntax/select-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/signed-number.gif.

cannot compute difference between binary files

Changes to art/syntax/single-source.gif.

cannot compute difference between binary files

Changes to art/syntax/sql-stmt-list.gif.

cannot compute difference between binary files

Changes to art/syntax/sql-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/table-constraint.gif.

cannot compute difference between binary files

Changes to art/syntax/type-name.gif.

cannot compute difference between binary files

Changes to art/syntax/update-stmt-limited.gif.

cannot compute difference between binary files

Changes to art/syntax/update-stmt.gif.

cannot compute difference between binary files

Changes to art/syntax/vacuum-stmt.gif.

cannot compute difference between binary files

Changes to matrix.tcl.

   600    600       set req [string map {&lt; < &gt; > &#91; [ &#93; ] &amp; &} $req]
   601    601       set req [string trim $req]
   602    602       set rno R-[md5-10x8 $req]
   603    603       set shortrno [string range $rno 0 12]
   604    604       append out "<a name=\"$rno\"></a><font color=\"blue\"><b>\n"
   605    605       set link "<a href=\"$matrixpath#$rno\" style=\"color: #0000ff\">"
   606    606       append out "$link$shortrno</a>:\[</b></font>"
   607         -    if {$proof($rno)>=2} {
          607  +    if {![info exists proof($rno)]} {
          608  +      set clr red
          609  +    } elseif {$proof($rno)>=2} {
   608    610         set clr green
   609    611       } elseif {$proof($rno)==1} {
   610    612         set clr orange
   611    613       } else {
   612    614         set clr red
   613    615       }
   614    616       append out "<font color=\"$clr\">$orig</font>\n"

Changes to pages/changes.in.

    38     38         http://www.sqlite.org/src/timeline</a>.</p>
    39     39       }
    40     40       hd_close_aux
    41     41       hd_enable_main 1
    42     42     }
    43     43   }
    44     44   
    45         -chng {2013-08-15 (3.8.0)} {
           45  +chng {2013-08-29 (3.8.0)} {
           46  +<li>Add support for [partial indexes]</li>
    46     47   <li>Cut-over to the [next generation query planner] for faster and better query plans.
    47     48   <li>The [EXPLAIN QUERY PLAN] output no longer shows an estimate of the number of 
    48     49       rows generated by each loop in a join.
    49     50   <li>Added the [FTS4 notindexed option], allowing non-indexed columns in an FTS4 table.
    50     51   <li>Added the [SQLITE_STMTSTATUS_VM_STEP] option to [sqlite3_stmt_status()].
    51     52   <li>Added the "percentile()" function as a [loadable extension] in the ext/misc
    52     53       subdirectory of the source tree.

Added pages/partialindex.in.

            1  +<title>Partial Indexes</title>
            2  +<tcl>
            3  +hd_keywords {partial index} {partial indexes} {partial indices}
            4  +</tcl>
            5  +<h1 align="center">Partial Indexes</h1>
            6  +
            7  +<h2>1.0 Introduction</h2>
            8  +
            9  +<p>
           10  +A partial index is an index over a subset of the rows of a table.
           11  +</p>
           12  +
           13  +<p>
           14  +^In ordinary indexes, there is exactly one entry in the index for every
           15  +row in the table.  ^In partial index, only some subset of the rows in the
           16  +table have corresponding index entries.  ^For example, a partial index might
           17  +omit entries for which the column being indexed is NULL.  When used 
           18  +judiciously, partial indexes can result in smaller database files and
           19  +improvements in both query and write performance.
           20  +</p>
           21  +
           22  +<h2>2.0 Creating Partial Indexes</h2>
           23  +
           24  +<p>
           25  +^Create a partial index by adding a WHERE clause to the end of an 
           26  +ordinary [CREATE INDEX] statement.
           27  +</p>
           28  +
           29  +<tcl>BubbleDiagram create-index-stmt</tcl>
           30  +
           31  +<p>
           32  +Any index that includes the WHERE clause at the end is considered to be
           33  +a partial index.  Indexes that omit the WHERE clause (or indexes that
           34  +are created by UNIQUE or PRIMARY KEY constraints inside of CREATE TABLE
           35  +statements) are ordinary full indexes.
           36  +</p>
           37  +
           38  +<p>
           39  +^The expression following the WHERE clause may contain operators,
           40  +literal values, and names of columns in the table being indexed.
           41  +^The WHERE clause may <em>not</em> contains subqueries, references to other
           42  +tables, functions, or [bound parameters].  The LIKE, GLOB, MATCH,
           43  +and REGEXP operators in SQLite as functions by the same name.
           44  +^Since functions are prohibited in the 
           45  +WHERE clause of a CREATE INDEX statement, so too are the LIKE, GLOB,
           46  +MATCH, and REGEXP operators.</p>
           47  +
           48  +<p>
           49  +^Only rows of the table for which the WHERE clause evaluates to true
           50  +are included in the index.  ^If the WHERE clause expression evaluates 
           51  +to NULL or to false for some row of the table, then those rows are omitted 
           52  +from the index.
           53  +</p>
           54  +
           55  +<p>
           56  +^The columns referenced in the WHERE clause of a partial index can be
           57  +any of the columns in the table, not just columns that happen to be
           58  +indexed.  However, it is very common for the WHERE clause
           59  +expression of a partial index to be a simple expression on the column
           60  +being indexed.  The following is a typical example:</p>
           61  +
           62  +<blockquote>
           63  +^(CREATE INDEX po_parent ON purchaseorder(parent_po) WHERE parent_po IS NOT NULL;)^
           64  +</blockquote>
           65  +
           66  +<p>In the example above, if most purchase orders do not have a "parent"
           67  +purchase order, then most parent_po values will be NULL.  That means only
           68  +a small subset of the rows in the purchaseorder table will be indexed.
           69  +Hence the index will take up much less space.  And changes to the original
           70  +purchaseorder table will run faster since the po_parent index only needs
           71  +to be updated for those exceptional rows where parent_po is not NULL.
           72  +But the index is still useful for querying.  ^(In particular, if one wants
           73  +to know all "children" of a particular purchase order "?1", the query
           74  +would be:
           75  +
           76  +<blockquote>
           77  +SELECT po_num FROM purchaseorder WHERE parent_po=?1;
           78  +</blockquote>)^
           79  +
           80  +<p>^The query above will use the po_parent index to help find the answer,
           81  +since the po_parent index contains entries for all rows of interest.
           82  +Note that since po_parent is smaller than a full index, the query will
           83  +likely run faster too.</p>
           84  +
           85  +<h3>2.1 Unique Partial Indexes</h3>
           86  +
           87  +<p>^A partial index definition may include the UNIQUE keyword.  ^If it
           88  +does, then SQLite requires every entry <em>in the index</em> to be unique.
           89  +This provides a mechanism for enforcing uniqueness across some subset of
           90  +the rows in a table.</p>
           91  +
           92  +<p>For example, suppose you have a database of the members of a large
           93  +organization where each person is assigned to a particular "team".  
           94  +Each team has a "leader" who is also a member of that team.  ^(The
           95  +table might look something like this:</p>
           96  +
           97  +<blockquote><pre>
           98  +CREATE TABLE person(
           99  +  person_id       INTEGER PRIMARY KEY,
          100  +  team_id         INTEGER REFERENCES team,
          101  +  is_team_leader  BOOLEAN,
          102  +  -- other fields elided
          103  +);
          104  +</pre></blockquote>)^
          105  +
          106  +<p>The team_id field cannot be unique because there usually multiple people
          107  +on the same time.  One cannot make the combination of team_id and is_team_leader
          108  +unique since there are usually multiple non-leaders on each team.  ^(The
          109  +solution to enforcing one leader per team is to create a unique index
          110  +on team_id but restricted to those entries for which is_team_leader is
          111  +true:</p>
          112  +
          113  +<blockquote>
          114  +CREATE UNIQUE INDEX team_leader ON person(team_id) WHERE is_team_leader;
          115  +</blockquote>)^
          116  +
          117  +^(<p>Coincidentally, that same index is useful for locating the team leader
          118  +of a particular time:</p>
          119  +
          120  +<blockquote>
          121  +SELECT person_id FROM person WHERE is_team_leader AND team_id=?1;
          122  +</blockquote>)^
          123  +
          124  +<h2>3.0 Queries Using Partial Indexes</h2>
          125  +
          126  +<p>Let X be the expression in the WHERE claues of a partial
          127  +index, and let W be the WHERE clause of a query that uses the
          128  +table that is indexed.  Then, the query is permitted to use 
          129  +the partial index if W&#x21d2;X, where the &#x21d2; operator
          130  +(usually pronounced "implies") is the logic operator 
          131  +equivalent to "X or not W".
          132  +Hence, determining whether or not a partial index
          133  +is usable in a particular query reduces to proving a theorem in
          134  +first-order logic.</p>
          135  +
          136  +<p>SQLite does <u>not</u> have a sophisticated theorem
          137  +prover with which to determine W&#x21d2;X.  Instead, SQLite uses 
          138  +two simple rules to find the common cases where W&#x21d2;X is true, and
          139  +it assumes all the other cases are false.  The rules used by SQLite
          140  +are these:
          141  +
          142  +<ol>
          143  +<li><p>If W is AND-connected terms and X is
          144  +OR-connected terms and if any term of W
          145  +appears as a term of X, then the partial index is usable.</p>
          146  +
          147  +<p>^(For example, let the index be
          148  +<blockquote>
          149  +CREATE INDEX ex1 ON tab1(a,b) WHERE a=5 OR b=6;
          150  +</blockquote>
          151  +<p>And let the query be:
          152  +<blockquote>
          153  +SELECT * FROM tab1 WHERE b=6 AND a=7; <i>-- uses partial index</i>
          154  +</blockquote>
          155  +<p>Then the index is usable by the query because the "b=6" term appears
          156  +in both the index definition and in the query.)^  Remember: terms in the
          157  +index should be OR-connected and terms in the query should be AND-connected.</p>
          158  +
          159  +<p>The terms in W and X must match exactly.  SQLite does not
          160  +do algebra to try to get them to look the same.
          161  +^The term "b=6" does not match "b=3+3" or "b-6=0" or "b BETWEEN 6 AND 6".
          162  +^"b=6" will match to "6=b" as long as "b=6" is on the index and "6=b" is
          163  +in the query.  ^If a term of the form "6=b" appears in the index, it will
          164  +never match anything.</p>
          165  +
          166  +<li><p>^If a term in X is of the form "z IS NOT NULL" and if a term in
          167  +       W is a comparison operator on "z" other than "IS", then those
          168  +       terms match.</p>
          169  +
          170  +^(<p>Example:  Let the index by
          171  +<blockquote>
          172  +CREATE INDEX ex2 ON tab2(b,c) WHERE c IS NOT NULL;
          173  +</blockquote>
          174  +<p>Then any query that uses operators =, &lt;, &gt;, &lt;=, &gt;=, &lt;&gt;,
          175  +or IN on column "c" would be usable with the partial index because those
          176  +comparison operators are only true if "c" is not NULL.)^  ^(So the following
          177  +query could use the partial index:
          178  +<blockquote>
          179  +SELECT * FROM tab2 WHERE b=456 AND c&lt;&gt;0;  <i>-- uses partial index</i>
          180  +</blockquote>)^
          181  +^(<p>But the next query can not use the partial index:
          182  +<blockquote>
          183  +SELECT * FROM tab2 WHERE b=456;  <i>-- cannot use partial index</i>
          184  +</blockquote>)^
          185  +<p>The latter query can not use the partial index because there might be
          186  +rows in the table with b=456 and and where c is NULL.  But those rows would
          187  +not be in the partial index.
          188  +</ol>
          189  +
          190  +<p>These two rules describe how the query planner for SQLite works as of
          191  +this writing (2013-08-01).  And the rules above will always be honored.
          192  +However, future versions of SQLite might incorporate a better theorem prover
          193  +that can find other cases where W&#x21d2;X is true and thus may
          194  +find more instances where partial indexes are useful.</p>
          195  +
          196  +<h2>4.0 Supported Versions</h2>
          197  +
          198  +<p>
          199  +Partial indexes have been supported in SQLite since version 3.8.0.
          200  +</p>
          201  +
          202  +<p>Database files that contain partial indices are not readable or writable
          203  +by versions of SQLite prior to 3.8.0.  However, a database file created
          204  +by SQLite 3.8.0 is still readable and writable by prior versions as long
          205  +as its schema contains no partial indexes.  A database that is unreadable
          206  +by legacy versions of SQLite can be made readable simply by running
          207  +[DROP INDEX] on the partial indexes.</p>
          208  +
          209  +<p>If the only version of SQLite available is prior to 3.8.0, then a
          210  +database file that contains partial indexes can be made readable using
          211  +the following command sequence:</p>
          212  +
          213  +<blockquote>
          214  +PRAGMA [writable_schema]=ON;<br>
          215  +DELETE FROM sqlite_master
          216  + WHERE type='index' 
          217  +   AND sql LIKE '% where %';<br>
          218  +PRAGMA writable_schema=OFF;<br>
          219  +VACUUM;
          220  +</blockquote>