Documentation Source Text

Changes On Branch partial-indices
Login

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

Changes In Branch partial-indices Excluding Merge-Ins

This is equivalent to a diff from 52366f9588 to 3e022afe53

2013-08-02
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)
03:43
Add documentation on the partial index implementation. (check-in: 5723efb011 user: drh tags: partial-indices)
2013-08-01
18:23
Update syntax diagrams (on Mac OS 10.6.8 using Tk 8.5.7) for partial indices. (check-in: 6f7d9ba15e user: drh tags: partial-indices)
17:48
Fix the description of COLLATE operator precedence so that it is aligned with the implementation. (check-in: 52366f9588 user: drh tags: trunk)
2013-07-23
13:48
Merge the download page improvements that have been taking place over on the 3.7.17 branch. (check-in: 0dc4a0b22a user: drh tags: trunk)

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
80
81
82
83
84
85

86
87
88
89
90
91
92
     line RELEASE {optx SAVEPOINT} /savepoint-name
  }
  create-index-stmt {
    stack
       {line CREATE {opt UNIQUE} INDEX {opt IF NOT EXISTS}}
       {line {optx /database-name .} /index-name
             ON /table-name ( {loop indexed-column ,} )}

  }
  indexed-column {
      line /column-name {optx COLLATE /collation-name} {or ASC DESC nil} 
  }
  create-table-stmt {
    stack
       {line CREATE {or {} TEMP TEMPORARY} TABLE {opt IF NOT EXISTS}}







>







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

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

30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
}
incr bn
set b $side.b$bn
button $b -text Everything -command {draw_all_graphs}
pack $b -side top -fill x -expand 1

set tagcnt 0                      ;# tag counter
set font1 {Helvetica 14 bold}     ;# default token font
set font2 {Helvetica 12}          ;# default variable font
set RADIUS 9                      ;# default turn radius
set HSEP 17                       ;# horizontal separation
set VSEP 9                        ;# vertical separation
set DPI 80                        ;# dots per inch


# Draw a right-hand turn around.  Approximately a ")"







|
|







30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
}
incr bn
set b $side.b$bn
button $b -text Everything -command {draw_all_graphs}
pack $b -side top -fill x -expand 1

set tagcnt 0                      ;# tag counter
set font1 {Helvetica 12 bold}     ;# default token font
set font2 {Helvetica 10}           ;# default variable font
set RADIUS 9                      ;# default turn radius
set HSEP 17                       ;# horizontal separation
set VSEP 9                        ;# vertical separation
set DPI 80                        ;# dots per inch


# Draw a right-hand turn around.  Approximately a ")"
629
630
631
632
633
634
635



636
637
638
639

640
641
642
643
644
645
646
  .c delete all
  wm deiconify .
  wm title . $name
  draw_diagram "line bullet [list $spec] bullet"
  foreach {x0 y0 x1 y1} [.c bbox all] break
  .c move all [expr {2-$x0}] [expr {2-$y0}]
  foreach {x0 y0 x1 y1} [.c bbox all] break



  .c config -width $x1 -height $y1
  update
  .c postscript -file $name.ps -width [expr {$x1+2}] -height [expr {$y1+2}]
  global DPI

  exec convert -density ${DPI}x$DPI -antialias $name.ps $name.gif
  if {$do_xv} {
    if {[catch {exec xv $name.gif &}]} {
      exec display $name.gif &
    }
  }
}







>
>
>




>







629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
  .c delete all
  wm deiconify .
  wm title . $name
  draw_diagram "line bullet [list $spec] bullet"
  foreach {x0 y0 x1 y1} [.c bbox all] break
  .c move all [expr {2-$x0}] [expr {2-$y0}]
  foreach {x0 y0 x1 y1} [.c bbox all] break
  .c create rect -100 -100 [expr {$x1+100}] [expr {$y1+100}] \
     -fill white -outline white -tags bgrect
  .c lower bgrect
  .c config -width $x1 -height $y1
  update
  .c postscript -file $name.ps -width [expr {$x1+2}] -height [expr {$y1+2}]
  global DPI
  .c delete bgrect
  exec convert -density ${DPI}x$DPI -antialias $name.ps $name.gif
  if {$do_xv} {
    if {[catch {exec xv $name.gif &}]} {
      exec display $name.gif &
    }
  }
}

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
601
602
603
604
605
606


607
608
609
610
611
612
613
614
    set req [string map {&lt; < &gt; > &#91; [ &#93; ] &amp; &} $req]
    set req [string trim $req]
    set rno R-[md5-10x8 $req]
    set shortrno [string range $rno 0 12]
    append out "<a name=\"$rno\"></a><font color=\"blue\"><b>\n"
    set link "<a href=\"$matrixpath#$rno\" style=\"color: #0000ff\">"
    append out "$link$shortrno</a>:\[</b></font>"


    if {$proof($rno)>=2} {
      set clr green
    } elseif {$proof($rno)==1} {
      set clr orange
    } else {
      set clr red
    }
    append out "<font color=\"$clr\">$orig</font>\n"







>
>
|







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

Changes to pages/changes.in.

38
39
40
41
42
43
44
45

46
47
48
49
50
51
52
      http://www.sqlite.org/src/timeline</a>.</p>
    }
    hd_close_aux
    hd_enable_main 1
  }
}

chng {2013-08-15 (3.8.0)} {

<li>Cut-over to the [next generation query planner] for faster and better query plans.
<li>The [EXPLAIN QUERY PLAN] output no longer shows an estimate of the number of 
    rows generated by each loop in a join.
<li>Added the [FTS4 notindexed option], allowing non-indexed columns in an FTS4 table.
<li>Added the [SQLITE_STMTSTATUS_VM_STEP] option to [sqlite3_stmt_status()].
<li>Added the "percentile()" function as a [loadable extension] in the ext/misc
    subdirectory of the source tree.







|
>







38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
      http://www.sqlite.org/src/timeline</a>.</p>
    }
    hd_close_aux
    hd_enable_main 1
  }
}

chng {2013-08-29 (3.8.0)} {
<li>Add support for [partial indexes]</li>
<li>Cut-over to the [next generation query planner] for faster and better query plans.
<li>The [EXPLAIN QUERY PLAN] output no longer shows an estimate of the number of 
    rows generated by each loop in a join.
<li>Added the [FTS4 notindexed option], allowing non-indexed columns in an FTS4 table.
<li>Added the [SQLITE_STMTSTATUS_VM_STEP] option to [sqlite3_stmt_status()].
<li>Added the "percentile()" function as a [loadable extension] in the ext/misc
    subdirectory of the source tree.

Added pages/partialindex.in.

























































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
<title>Partial Indexes</title>
<tcl>
hd_keywords {partial index} {partial indexes} {partial indices}
</tcl>
<h1 align="center">Partial Indexes</h1>

<h2>1.0 Introduction</h2>

<p>
A partial index is an index over a subset of the rows of a table.
</p>

<p>
^In ordinary indexes, there is exactly one entry in the index for every
row in the table.  ^In partial index, only some subset of the rows in the
table have corresponding index entries.  ^For example, a partial index might
omit entries for which the column being indexed is NULL.  When used 
judiciously, partial indexes can result in smaller database files and
improvements in both query and write performance.
</p>

<h2>2.0 Creating Partial Indexes</h2>

<p>
^Create a partial index by adding a WHERE clause to the end of an 
ordinary [CREATE INDEX] statement.
</p>

<tcl>BubbleDiagram create-index-stmt</tcl>

<p>
Any index that includes the WHERE clause at the end is considered to be
a partial index.  Indexes that omit the WHERE clause (or indexes that
are created by UNIQUE or PRIMARY KEY constraints inside of CREATE TABLE
statements) are ordinary full indexes.
</p>

<p>
^The expression following the WHERE clause may contain operators,
literal values, and names of columns in the table being indexed.
^The WHERE clause may <em>not</em> contains subqueries, references to other
tables, functions, or [bound parameters].  The LIKE, GLOB, MATCH,
and REGEXP operators in SQLite as functions by the same name.
^Since functions are prohibited in the 
WHERE clause of a CREATE INDEX statement, so too are the LIKE, GLOB,
MATCH, and REGEXP operators.</p>

<p>
^Only rows of the table for which the WHERE clause evaluates to true
are included in the index.  ^If the WHERE clause expression evaluates 
to NULL or to false for some row of the table, then those rows are omitted 
from the index.
</p>

<p>
^The columns referenced in the WHERE clause of a partial index can be
any of the columns in the table, not just columns that happen to be
indexed.  However, it is very common for the WHERE clause
expression of a partial index to be a simple expression on the column
being indexed.  The following is a typical example:</p>

<blockquote>
^(CREATE INDEX po_parent ON purchaseorder(parent_po) WHERE parent_po IS NOT NULL;)^
</blockquote>

<p>In the example above, if most purchase orders do not have a "parent"
purchase order, then most parent_po values will be NULL.  That means only
a small subset of the rows in the purchaseorder table will be indexed.
Hence the index will take up much less space.  And changes to the original
purchaseorder table will run faster since the po_parent index only needs
to be updated for those exceptional rows where parent_po is not NULL.
But the index is still useful for querying.  ^(In particular, if one wants
to know all "children" of a particular purchase order "?1", the query
would be:

<blockquote>
SELECT po_num FROM purchaseorder WHERE parent_po=?1;
</blockquote>)^

<p>^The query above will use the po_parent index to help find the answer,
since the po_parent index contains entries for all rows of interest.
Note that since po_parent is smaller than a full index, the query will
likely run faster too.</p>

<h3>2.1 Unique Partial Indexes</h3>

<p>^A partial index definition may include the UNIQUE keyword.  ^If it
does, then SQLite requires every entry <em>in the index</em> to be unique.
This provides a mechanism for enforcing uniqueness across some subset of
the rows in a table.</p>

<p>For example, suppose you have a database of the members of a large
organization where each person is assigned to a particular "team".  
Each team has a "leader" who is also a member of that team.  ^(The
table might look something like this:</p>

<blockquote><pre>
CREATE TABLE person(
  person_id       INTEGER PRIMARY KEY,
  team_id         INTEGER REFERENCES team,
  is_team_leader  BOOLEAN,
  -- other fields elided
);
</pre></blockquote>)^

<p>The team_id field cannot be unique because there usually multiple people
on the same time.  One cannot make the combination of team_id and is_team_leader
unique since there are usually multiple non-leaders on each team.  ^(The
solution to enforcing one leader per team is to create a unique index
on team_id but restricted to those entries for which is_team_leader is
true:</p>

<blockquote>
CREATE UNIQUE INDEX team_leader ON person(team_id) WHERE is_team_leader;
</blockquote>)^

^(<p>Coincidentally, that same index is useful for locating the team leader
of a particular time:</p>

<blockquote>
SELECT person_id FROM person WHERE is_team_leader AND team_id=?1;
</blockquote>)^

<h2>3.0 Queries Using Partial Indexes</h2>

<p>Let X be the expression in the WHERE claues of a partial
index, and let W be the WHERE clause of a query that uses the
table that is indexed.  Then, the query is permitted to use 
the partial index if W&#x21d2;X, where the &#x21d2; operator
(usually pronounced "implies") is the logic operator 
equivalent to "X or not W".
Hence, determining whether or not a partial index
is usable in a particular query reduces to proving a theorem in
first-order logic.</p>

<p>SQLite does <u>not</u> have a sophisticated theorem
prover with which to determine W&#x21d2;X.  Instead, SQLite uses 
two simple rules to find the common cases where W&#x21d2;X is true, and
it assumes all the other cases are false.  The rules used by SQLite
are these:

<ol>
<li><p>If W is AND-connected terms and X is
OR-connected terms and if any term of W
appears as a term of X, then the partial index is usable.</p>

<p>^(For example, let the index be
<blockquote>
CREATE INDEX ex1 ON tab1(a,b) WHERE a=5 OR b=6;
</blockquote>
<p>And let the query be:
<blockquote>
SELECT * FROM tab1 WHERE b=6 AND a=7; <i>-- uses partial index</i>
</blockquote>
<p>Then the index is usable by the query because the "b=6" term appears
in both the index definition and in the query.)^  Remember: terms in the
index should be OR-connected and terms in the query should be AND-connected.</p>

<p>The terms in W and X must match exactly.  SQLite does not
do algebra to try to get them to look the same.
^The term "b=6" does not match "b=3+3" or "b-6=0" or "b BETWEEN 6 AND 6".
^"b=6" will match to "6=b" as long as "b=6" is on the index and "6=b" is
in the query.  ^If a term of the form "6=b" appears in the index, it will
never match anything.</p>

<li><p>^If a term in X is of the form "z IS NOT NULL" and if a term in
       W is a comparison operator on "z" other than "IS", then those
       terms match.</p>

^(<p>Example:  Let the index by
<blockquote>
CREATE INDEX ex2 ON tab2(b,c) WHERE c IS NOT NULL;
</blockquote>
<p>Then any query that uses operators =, &lt;, &gt;, &lt;=, &gt;=, &lt;&gt;,
or IN on column "c" would be usable with the partial index because those
comparison operators are only true if "c" is not NULL.)^  ^(So the following
query could use the partial index:
<blockquote>
SELECT * FROM tab2 WHERE b=456 AND c&lt;&gt;0;  <i>-- uses partial index</i>
</blockquote>)^
^(<p>But the next query can not use the partial index:
<blockquote>
SELECT * FROM tab2 WHERE b=456;  <i>-- cannot use partial index</i>
</blockquote>)^
<p>The latter query can not use the partial index because there might be
rows in the table with b=456 and and where c is NULL.  But those rows would
not be in the partial index.
</ol>

<p>These two rules describe how the query planner for SQLite works as of
this writing (2013-08-01).  And the rules above will always be honored.
However, future versions of SQLite might incorporate a better theorem prover
that can find other cases where W&#x21d2;X is true and thus may
find more instances where partial indexes are useful.</p>

<h2>4.0 Supported Versions</h2>

<p>
Partial indexes have been supported in SQLite since version 3.8.0.
</p>

<p>Database files that contain partial indices are not readable or writable
by versions of SQLite prior to 3.8.0.  However, a database file created
by SQLite 3.8.0 is still readable and writable by prior versions as long
as its schema contains no partial indexes.  A database that is unreadable
by legacy versions of SQLite can be made readable simply by running
[DROP INDEX] on the partial indexes.</p>

<p>If the only version of SQLite available is prior to 3.8.0, then a
database file that contains partial indexes can be made readable using
the following command sequence:</p>

<blockquote>
PRAGMA [writable_schema]=ON;<br>
DELETE FROM sqlite_master
 WHERE type='index' 
   AND sql LIKE '% where %';<br>
PRAGMA writable_schema=OFF;<br>
VACUUM;
</blockquote>