Debian Codegraph @

doc/src/sgml/indices.sgml

raw
1 <!-- doc/src/sgml/indices.sgml -->
2
3 <chapter id="indexes">
4 <title>Indexes</title>
5
6 <indexterm zone="indexes">
7 <primary>index</primary>
8 </indexterm>
9
10 <para>
11 Indexes are a common way to enhance database performance. An index
12 allows the database server to find and retrieve specific rows much
13 faster than it could do without an index. But indexes also add
14 overhead to the database system as a whole, so they should be used
15 sensibly.
16 </para>
17
18
19 <sect1 id="indexes-intro">
20 <title>Introduction</title>
21
22 <para>
23 Suppose we have a table similar to this:
24 <programlisting>
25 CREATE TABLE test1 (
26 id integer,
27 content varchar
28 );
29 </programlisting>
30 and the application issues many queries of the form:
31 <programlisting>
32 SELECT content FROM test1 WHERE id = <replaceable>constant</replaceable>;
33 </programlisting>
34 With no advance preparation, the system would have to scan the entire
35 <structname>test1</structname> table, row by row, to find all
36 matching entries. If there are many rows in
37 <structname>test1</structname> and only a few rows (perhaps zero
38 or one) that would be returned by such a query, this is clearly an
39 inefficient method. But if the system has been instructed to maintain an
40 index on the <structfield>id</structfield> column, it can use a more
41 efficient method for locating matching rows. For instance, it
42 might only have to walk a few levels deep into a search tree.
43 </para>
44
45 <para>
46 A similar approach is used in most non-fiction books: terms and
47 concepts that are frequently looked up by readers are collected in
48 an alphabetic index at the end of the book. The interested reader
49 can scan the index relatively quickly and flip to the appropriate
50 page(s), rather than having to read the entire book to find the
51 material of interest. Just as it is the task of the author to
52 anticipate the items that readers are likely to look up,
53 it is the task of the database programmer to foresee which indexes
54 will be useful.
55 </para>
56
57 <para>
58 The following command can be used to create an index on the
59 <structfield>id</structfield> column, as discussed:
60 <programlisting>
61 CREATE INDEX test1_id_index ON test1 (id);
62 </programlisting>
63 The name <structname>test1_id_index</structname> can be chosen
64 freely, but you should pick something that enables you to remember
65 later what the index was for.
66 </para>
67
68 <para>
69 To remove an index, use the <command>DROP INDEX</command> command.
70 Indexes can be added to and removed from tables at any time.
71 </para>
72
73 <para>
74 Once an index is created, no further intervention is required: the
75 system will update the index when the table is modified, and it will
76 use the index in queries when it thinks doing so would be more efficient
77 than a sequential table scan. But you might have to run the
78 <command>ANALYZE</command> command regularly to update
79 statistics to allow the query planner to make educated decisions.
80 See <xref linkend="performance-tips"/> for information about
81 how to find out whether an index is used and when and why the
82 planner might choose <emphasis>not</emphasis> to use an index.
83 </para>
84
85 <para>
86 Indexes can also benefit <command>UPDATE</command> and
87 <command>DELETE</command> commands with search conditions.
88 Indexes can moreover be used in join searches. Thus,
89 an index defined on a column that is part of a join condition can
90 also significantly speed up queries with joins.
91 </para>
92
93 <para>
94 In general, <productname>PostgreSQL</productname> indexes can be used
95 to optimize queries that contain one or more <literal>WHERE</literal>
96 or <literal>JOIN</literal> clauses of the form
97
98 <synopsis>
99 <replaceable>indexed-column</replaceable> <replaceable>indexable-operator</replaceable> <replaceable>comparison-value</replaceable>
100 </synopsis>
101
102 Here, the <replaceable>indexed-column</replaceable> is whatever
103 column or expression the index has been defined on.
104 The <replaceable>indexable-operator</replaceable> is an operator that
105 is a member of the index's <firstterm>operator class</firstterm> for
106 the indexed column. (More details about that appear below.)
107 And the <replaceable>comparison-value</replaceable> can be any
108 expression that is not volatile and does not reference the index's
109 table.
110 </para>
111
112 <para>
113 In some cases the query planner can extract an indexable clause of
114 this form from another SQL construct. A simple example is that if
115 the original clause was
116
117 <synopsis>
118 <replaceable>comparison-value</replaceable> <replaceable>operator</replaceable> <replaceable>indexed-column</replaceable>
119 </synopsis>
120
121 then it can be flipped around into indexable form if the
122 original <replaceable>operator</replaceable> has a commutator
123 operator that is a member of the index's operator class.
124 </para>
125
126 <para>
127 Creating an index on a large table can take a long time. By default,
128 <productname>PostgreSQL</productname> allows reads (<command>SELECT</command> statements) to occur
129 on the table in parallel with index creation, but writes (<command>INSERT</command>,
130 <command>UPDATE</command>, <command>DELETE</command>) are blocked until the index build is finished.
131 In production environments this is often unacceptable.
132 It is possible to allow writes to occur in parallel with index
133 creation, but there are several caveats to be aware of &mdash;
134 for more information see <xref linkend="sql-createindex-concurrently"/>.
135 </para>
136
137 <para>
138 After an index is created, the system has to keep it synchronized with the
139 table. This adds overhead to data manipulation operations. Indexes can
140 also prevent the creation of <link linkend="storage-hot">heap-only
141 tuples</link>.
142 Therefore indexes that are seldom or never used in queries
143 should be removed.
144 </para>
145 </sect1>
146
147
148 <sect1 id="indexes-types">
149 <title>Index Types</title>
150
151 <para>
152 <productname>PostgreSQL</productname> provides several index types:
153 B-tree, Hash, GiST, SP-GiST, GIN, BRIN, and the extension <link
154 linkend="bloom">bloom</link>.
155 Each index type uses a different
156 algorithm that is best suited to different types of indexable clauses.
157 By default, the <link linkend="sql-createindex"><command>CREATE
158 INDEX</command></link> command creates
159 B-tree indexes, which fit the most common situations.
160 The other index types are selected by writing the keyword
161 <literal>USING</literal> followed by the index type name.
162 For example, to create a Hash index:
163 <programlisting>
164 CREATE INDEX <replaceable>name</replaceable> ON <replaceable>table</replaceable> USING HASH (<replaceable>column</replaceable>);
165 </programlisting>
166 </para>
167
168 <sect2 id="indexes-types-btree">
169 <title>B-Tree</title>
170
171 <indexterm>
172 <primary>index</primary>
173 <secondary>B-Tree</secondary>
174 </indexterm>
175 <indexterm>
176 <primary>B-Tree</primary>
177 <see>index</see>
178 </indexterm>
179
180 <para>
181 B-trees can handle equality and range queries on data that can be sorted
182 into some ordering.
183 In particular, the <productname>PostgreSQL</productname> query planner
184 will consider using a B-tree index whenever an indexed column is
185 involved in a comparison using one of these operators:
186
187 <synopsis>
188 &lt; &nbsp; &lt;= &nbsp; = &nbsp; &gt;= &nbsp; &gt;
189 </synopsis>
190
191 Constructs equivalent to combinations of these operators, such as
192 <literal>BETWEEN</literal> and <literal>IN</literal>, can also be implemented with
193 a B-tree index search. Also, an <literal>IS NULL</literal> or <literal>IS NOT
194 NULL</literal> condition on an index column can be used with a B-tree index.
195 </para>
196
197 <para>
198 The optimizer can also use a B-tree index for queries involving the
199 pattern matching operators <literal>LIKE</literal> and <literal>~</literal>
200 <emphasis>if</emphasis> the pattern is a constant and is anchored to
201 the beginning of the string &mdash; for example, <literal>col LIKE
202 'foo%'</literal> or <literal>col ~ '^foo'</literal>, but not
203 <literal>col LIKE '%bar'</literal>. However, if your database does not
204 use the C locale you will need to create the index with a special
205 operator class to support indexing of pattern-matching queries; see
206 <xref linkend="indexes-opclass"/> below. It is also possible to use
207 B-tree indexes for <literal>ILIKE</literal> and
208 <literal>~*</literal>, but only if the pattern starts with
209 non-alphabetic characters, i.e., characters that are not affected by
210 upper/lower case conversion.
211 </para>
212
213 <para>
214 B-tree indexes can also be used to retrieve data in sorted order.
215 This is not always faster than a simple scan and sort, but it is
216 often helpful.
217 </para>
218 </sect2>
219
220 <sect2 id="indexes-types-hash">
221 <title>Hash</title>
222
223 <indexterm>
224 <primary>index</primary>
225 <secondary>hash</secondary>
226 </indexterm>
227 <indexterm>
228 <primary>hash</primary>
229 <see>index</see>
230 </indexterm>
231
232 <para>
233 Hash indexes store a 32-bit hash code derived from the
234 value of the indexed column. Hence,
235 such indexes can only handle simple equality comparisons.
236 The query planner will consider using a hash index whenever an
237 indexed column is involved in a comparison using the
238 equal operator:
239
240 <synopsis>
241 =
242 </synopsis>
243 </para>
244 </sect2>
245
246 <sect2 id="indexes-type-gist">
247 <title>GiST</title>
248
249 <indexterm>
250 <primary>index</primary>
251 <secondary>GiST</secondary>
252 </indexterm>
253 <indexterm>
254 <primary>GiST</primary>
255 <see>index</see>
256 </indexterm>
257
258 <para>
259 GiST indexes are not a single kind of index, but rather an infrastructure
260 within which many different indexing strategies can be implemented.
261 Accordingly, the particular operators with which a GiST index can be
262 used vary depending on the indexing strategy (the <firstterm>operator
263 class</firstterm>). As an example, the standard distribution of
264 <productname>PostgreSQL</productname> includes GiST operator classes
265 for several two-dimensional geometric data types, which support indexed
266 queries using these operators:
267
268 <synopsis>
269 &lt;&lt; &nbsp; &amp;&lt; &nbsp; &amp;&gt; &nbsp; &gt;&gt; &nbsp; &lt;&lt;| &nbsp; &amp;&lt;| &nbsp; |&amp;&gt; &nbsp; |&gt;&gt; &nbsp; @&gt; &nbsp; &lt;@ &nbsp; ~= &nbsp; &amp;&amp;
270 </synopsis>
271
272 (See <xref linkend="functions-geometry"/> for the meaning of
273 these operators.)
274 The GiST operator classes included in the standard distribution are
275 documented in <xref linkend="gist-builtin-opclasses-table"/>.
276 Many other GiST operator
277 classes are available in the <literal>contrib</literal> collection or as separate
278 projects. For more information see <xref linkend="gist"/>.
279 </para>
280
281 <para>
282 GiST indexes are also capable of optimizing <quote>nearest-neighbor</quote>
283 searches, such as
284 <programlisting><![CDATA[
285 SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10;
286 ]]>
287 </programlisting>
288 which finds the ten places closest to a given target point. The ability
289 to do this is again dependent on the particular operator class being used.
290 In <xref linkend="gist-builtin-opclasses-table"/>, operators that can be
291 used in this way are listed in the column <quote>Ordering Operators</quote>.
292 </para>
293 </sect2>
294
295 <sect2 id="indexes-type-spgist">
296 <title>SP-GiST</title>
297
298 <indexterm>
299 <primary>index</primary>
300 <secondary>SP-GiST</secondary>
301 </indexterm>
302 <indexterm>
303 <primary>SP-GiST</primary>
304 <see>index</see>
305 </indexterm>
306
307 <para>
308 SP-GiST indexes, like GiST indexes, offer an infrastructure that supports
309 various kinds of searches. SP-GiST permits implementation of a wide range
310 of different non-balanced disk-based data structures, such as quadtrees,
311 k-d trees, and radix trees (tries). As an example, the standard distribution of
312 <productname>PostgreSQL</productname> includes SP-GiST operator classes
313 for two-dimensional points, which support indexed
314 queries using these operators:
315
316 <synopsis>
317 &lt;&lt; &nbsp; &gt;&gt; &nbsp; ~= &nbsp; &lt;@ &nbsp; &lt;&lt;| &nbsp; |&gt;&gt;
318 </synopsis>
319
320 (See <xref linkend="functions-geometry"/> for the meaning of
321 these operators.)
322 The SP-GiST operator classes included in the standard distribution are
323 documented in <xref linkend="spgist-builtin-opclasses-table"/>.
324 For more information see <xref linkend="spgist"/>.
325 </para>
326
327 <para>
328 Like GiST, SP-GiST supports <quote>nearest-neighbor</quote> searches.
329 For SP-GiST operator classes that support distance ordering, the
330 corresponding operator is listed in the <quote>Ordering Operators</quote>
331 column in <xref linkend="spgist-builtin-opclasses-table"/>.
332 </para>
333 </sect2>
334
335 <sect2 id="indexes-types-gin">
336 <title>GIN</title>
337
338 <indexterm>
339 <primary>index</primary>
340 <secondary>GIN</secondary>
341 </indexterm>
342 <indexterm>
343 <primary>GIN</primary>
344 <see>index</see>
345 </indexterm>
346
347 <para>
348 GIN indexes are <quote>inverted indexes</quote> which are appropriate for
349 data values that contain multiple component values, such as arrays. An
350 inverted index contains a separate entry for each component value, and
351 can efficiently handle queries that test for the presence of specific
352 component values.
353 </para>
354
355 <para>
356 Like GiST and SP-GiST, GIN can support
357 many different user-defined indexing strategies, and the particular
358 operators with which a GIN index can be used vary depending on the
359 indexing strategy.
360 As an example, the standard distribution of
361 <productname>PostgreSQL</productname> includes a GIN operator class
362 for arrays, which supports indexed queries using these operators:
363
364 <synopsis>
365 &lt;@ &nbsp; @&gt; &nbsp; = &nbsp; &amp;&amp;
366 </synopsis>
367
368 (See <xref linkend="functions-array"/> for the meaning of
369 these operators.)
370 The GIN operator classes included in the standard distribution are
371 documented in <xref linkend="gin-builtin-opclasses-table"/>.
372 Many other GIN operator
373 classes are available in the <literal>contrib</literal> collection or as separate
374 projects. For more information see <xref linkend="gin"/>.
375 </para>
376 </sect2>
377
378 <sect2 id="indexes-types-brin">
379 <title>BRIN</title>
380
381 <indexterm>
382 <primary>index</primary>
383 <secondary>BRIN</secondary>
384 </indexterm>
385 <indexterm>
386 <primary>BRIN</primary>
387 <see>index</see>
388 </indexterm>
389
390 <para>
391 BRIN indexes (a shorthand for Block Range INdexes) store summaries about
392 the values stored in consecutive physical block ranges of a table.
393 Thus, they are most effective for columns whose values are well-correlated
394 with the physical order of the table rows.
395 Like GiST, SP-GiST and GIN,
396 BRIN can support many different indexing strategies,
397 and the particular operators with which a BRIN index can be used
398 vary depending on the indexing strategy.
399 For data types that have a linear sort order, the indexed data
400 corresponds to the minimum and maximum values of the
401 values in the column for each block range. This supports indexed queries
402 using these operators:
403
404 <synopsis>
405 &lt; &nbsp; &lt;= &nbsp; = &nbsp; &gt;= &nbsp; &gt;
406 </synopsis>
407
408 The BRIN operator classes included in the standard distribution are
409 documented in <xref linkend="brin-builtin-opclasses-table"/>.
410 For more information see <xref linkend="brin"/>.
411 </para>
412 </sect2>
413 </sect1>
414
415
416 <sect1 id="indexes-multicolumn">
417 <title>Multicolumn Indexes</title>
418
419 <indexterm zone="indexes-multicolumn">
420 <primary>index</primary>
421 <secondary>multicolumn</secondary>
422 </indexterm>
423
424 <para>
425 An index can be defined on more than one column of a table. For example, if
426 you have a table of this form:
427 <programlisting>
428 CREATE TABLE test2 (
429 major int,
430 minor int,
431 name varchar
432 );
433 </programlisting>
434 (say, you keep your <filename class="directory">/dev</filename>
435 directory in a database...) and you frequently issue queries like:
436 <programlisting>
437 SELECT name FROM test2 WHERE major = <replaceable>constant</replaceable> AND minor = <replaceable>constant</replaceable>;
438 </programlisting>
439 then it might be appropriate to define an index on the columns
440 <structfield>major</structfield> and
441 <structfield>minor</structfield> together, e.g.:
442 <programlisting>
443 CREATE INDEX test2_mm_idx ON test2 (major, minor);
444 </programlisting>
445 </para>
446
447 <para>
448 Currently, only the B-tree, GiST, GIN, and BRIN index types support
449 multiple-key-column indexes. Whether there can be multiple key
450 columns is independent of whether <literal>INCLUDE</literal> columns
451 can be added to the index. Indexes can have up to 32 columns,
452 including <literal>INCLUDE</literal> columns. (This limit can be
453 altered when building <productname>PostgreSQL</productname>; see the
454 file <filename>pg_config_manual.h</filename>.)
455 </para>
456
457 <para>
458 A multicolumn B-tree index can be used with query conditions that
459 involve any subset of the index's columns, but the index is most
460 efficient when there are constraints on the leading (leftmost) columns.
461 The exact rule is that equality constraints on leading columns, plus
462 any inequality constraints on the first column that does not have an
463 equality constraint, will always be used to limit the portion of the index
464 that is scanned. Constraints on columns to the right of these columns
465 are checked in the index, so they'll always save visits to the table
466 proper, but they do not necessarily reduce the portion of the index that
467 has to be scanned. If a B-tree index scan can apply the skip scan
468 optimization effectively, it will apply every column constraint when
469 navigating through the index via repeated index searches. This can reduce
470 the portion of the index that has to be read, even though one or more
471 columns (prior to the least significant index column from the query
472 predicate) lacks a conventional equality constraint. Skip scan works by
473 generating a dynamic equality constraint internally, that matches every
474 possible value in an index column (though only given a column that lacks
475 an equality constraint that comes from the query predicate, and only when
476 the generated constraint can be used in conjunction with a later column
477 constraint from the query predicate).
478 </para>
479
480 <para>
481 For example, given an index on <literal>(x, y)</literal>, and a query
482 condition <literal>WHERE y = 7700</literal>, a B-tree index scan might be
483 able to apply the skip scan optimization. This generally happens when the
484 query planner expects that repeated <literal>WHERE x = N AND y = 7700</literal>
485 searches for every possible value of <literal>N</literal> (or for every
486 <literal>x</literal> value that is actually stored in the index) is the
487 fastest possible approach, given the available indexes on the table. This
488 approach is generally only taken when there are so few distinct
489 <literal>x</literal> values that the planner expects the scan to skip over
490 most of the index (because most of its leaf pages cannot possibly contain
491 relevant tuples). If there are many distinct <literal>x</literal> values,
492 then the entire index will have to be scanned, so in most cases the planner
493 will prefer a sequential table scan over using the index.
494 </para>
495
496 <para>
497 The skip scan optimization can also be applied selectively, during B-tree
498 scans that have at least some useful constraints from the query predicate.
499 For example, given an index on <literal>(a, b, c)</literal> and a
500 query condition <literal>WHERE a = 5 AND b &gt;= 42 AND c &lt; 77</literal>,
501 the index might have to be scanned from the first entry with
502 <literal>a</literal> = 5 and <literal>b</literal> = 42 up through the last
503 entry with <literal>a</literal> = 5. Index entries with
504 <literal>c</literal> &gt;= 77 will never need to be filtered at the table
505 level, but it may or may not be profitable to skip over them within the
506 index. When skipping takes place, the scan starts a new index search to
507 reposition itself from the end of the current <literal>a</literal> = 5 and
508 <literal>b</literal> = N grouping (i.e. from the position in the index
509 where the first tuple <literal>a = 5 AND b = N AND c &gt;= 77</literal>
510 appears), to the start of the next such grouping (i.e. the position in the
511 index where the first tuple <literal>a = 5 AND b = N + 1</literal>
512 appears).
513 </para>
514
515 <para>
516 A multicolumn GiST index can be used with query conditions that
517 involve any subset of the index's columns. Conditions on additional
518 columns restrict the entries returned by the index, but the condition on
519 the first column is the most important one for determining how much of
520 the index needs to be scanned. A GiST index will be relatively
521 ineffective if its first column has only a few distinct values, even if
522 there are many distinct values in additional columns.
523 </para>
524
525 <para>
526 A multicolumn GIN index can be used with query conditions that
527 involve any subset of the index's columns. Unlike B-tree or GiST,
528 index search effectiveness is the same regardless of which index column(s)
529 the query conditions use.
530 </para>
531
532 <para>
533 A multicolumn BRIN index can be used with query conditions that
534 involve any subset of the index's columns. Like GIN and unlike B-tree or
535 GiST, index search effectiveness is the same regardless of which index
536 column(s) the query conditions use. The only reason to have multiple BRIN
537 indexes instead of one multicolumn BRIN index on a single table is to have
538 a different <literal>pages_per_range</literal> storage parameter.
539 </para>
540
541 <para>
542 Of course, each column must be used with operators appropriate to the index
543 type; clauses that involve other operators will not be considered.
544 </para>
545
546 <para>
547 Multicolumn indexes should be used sparingly. In most situations,
548 an index on a single column is sufficient and saves space and time.
549 Indexes with more than three columns are unlikely to be helpful
550 unless the usage of the table is extremely stylized. See also
551 <xref linkend="indexes-bitmap-scans"/> and
552 <xref linkend="indexes-index-only-scans"/> for some discussion of the
553 merits of different index configurations.
554 </para>
555 </sect1>
556
557
558 <sect1 id="indexes-ordering">
559 <title>Indexes and <literal>ORDER BY</literal></title>
560
561 <indexterm zone="indexes-ordering">
562 <primary>index</primary>
563 <secondary>and <literal>ORDER BY</literal></secondary>
564 </indexterm>
565
566 <para>
567 In addition to simply finding the rows to be returned by a query,
568 an index may be able to deliver them in a specific sorted order.
569 This allows a query's <literal>ORDER BY</literal> specification to be honored
570 without a separate sorting step. Of the index types currently
571 supported by <productname>PostgreSQL</productname>, only B-tree
572 can produce sorted output &mdash; the other index types return
573 matching rows in an unspecified, implementation-dependent order.
574 </para>
575
576 <para>
577 The planner will consider satisfying an <literal>ORDER BY</literal> specification
578 either by scanning an available index that matches the specification,
579 or by scanning the table in physical order and doing an explicit
580 sort. For a query that requires scanning a large fraction of the
581 table, an explicit sort is likely to be faster than using an index
582 because it requires
583 less disk I/O due to following a sequential access pattern. Indexes are
584 more useful when only a few rows need be fetched. An important
585 special case is <literal>ORDER BY</literal> in combination with
586 <literal>LIMIT</literal> <replaceable>n</replaceable>: an explicit sort will have to process
587 all the data to identify the first <replaceable>n</replaceable> rows, but if there is
588 an index matching the <literal>ORDER BY</literal>, the first <replaceable>n</replaceable>
589 rows can be retrieved directly, without scanning the remainder at all.
590 </para>
591
592 <para>
593 By default, B-tree indexes store their entries in ascending order
594 with nulls last (table TID is treated as a tiebreaker column among
595 otherwise equal entries). This means that a forward scan of an
596 index on column <literal>x</literal> produces output satisfying <literal>ORDER BY x</literal>
597 (or more verbosely, <literal>ORDER BY x ASC NULLS LAST</literal>). The
598 index can also be scanned backward, producing output satisfying
599 <literal>ORDER BY x DESC</literal>
600 (or more verbosely, <literal>ORDER BY x DESC NULLS FIRST</literal>, since
601 <literal>NULLS FIRST</literal> is the default for <literal>ORDER BY DESC</literal>).
602 </para>
603
604 <para>
605 You can adjust the ordering of a B-tree index by including the
606 options <literal>ASC</literal>, <literal>DESC</literal>, <literal>NULLS FIRST</literal>,
607 and/or <literal>NULLS LAST</literal> when creating the index; for example:
608 <programlisting>
609 CREATE INDEX test2_info_nulls_low ON test2 (info NULLS FIRST);
610 CREATE INDEX test3_desc_index ON test3 (id DESC NULLS LAST);
611 </programlisting>
612 An index stored in ascending order with nulls first can satisfy
613 either <literal>ORDER BY x ASC NULLS FIRST</literal> or
614 <literal>ORDER BY x DESC NULLS LAST</literal> depending on which direction
615 it is scanned in.
616 </para>
617
618 <para>
619 You might wonder why bother providing all four options, when two
620 options together with the possibility of backward scan would cover
621 all the variants of <literal>ORDER BY</literal>. In single-column indexes
622 the options are indeed redundant, but in multicolumn indexes they can be
623 useful. Consider a two-column index on <literal>(x, y)</literal>: this can
624 satisfy <literal>ORDER BY x, y</literal> if we scan forward, or
625 <literal>ORDER BY x DESC, y DESC</literal> if we scan backward.
626 But it might be that the application frequently needs to use
627 <literal>ORDER BY x ASC, y DESC</literal>. There is no way to get that
628 ordering from a plain index, but it is possible if the index is defined
629 as <literal>(x ASC, y DESC)</literal> or <literal>(x DESC, y ASC)</literal>.
630 </para>
631
632 <para>
633 Obviously, indexes with non-default sort orderings are a fairly
634 specialized feature, but sometimes they can produce tremendous
635 speedups for certain queries. Whether it's worth maintaining such an
636 index depends on how often you use queries that require a special
637 sort ordering.
638 </para>
639 </sect1>
640
641
642 <sect1 id="indexes-bitmap-scans">
643 <title>Combining Multiple Indexes</title>
644
645 <indexterm zone="indexes-bitmap-scans">
646 <primary>index</primary>
647 <secondary>combining multiple indexes</secondary>
648 </indexterm>
649
650 <indexterm zone="indexes-bitmap-scans">
651 <primary>bitmap scan</primary>
652 </indexterm>
653
654 <para>
655 A single index scan can only use query clauses that use the index's
656 columns with operators of its operator class and are joined with
657 <literal>AND</literal>. For example, given an index on <literal>(a, b)</literal>
658 a query condition like <literal>WHERE a = 5 AND b = 6</literal> could
659 use the index, but a query like <literal>WHERE a = 5 OR b = 6</literal> could not
660 directly use the index.
661 </para>
662
663 <para>
664 Fortunately,
665 <productname>PostgreSQL</productname> has the ability to combine multiple indexes
666 (including multiple uses of the same index) to handle cases that cannot
667 be implemented by single index scans. The system can form <literal>AND</literal>
668 and <literal>OR</literal> conditions across several index scans. For example,
669 a query like <literal>WHERE x = 42 OR x = 47 OR x = 53 OR x = 99</literal>
670 could be broken down into four separate scans of an index on <literal>x</literal>,
671 each scan using one of the query clauses. The results of these scans are
672 then ORed together to produce the result. Another example is that if we
673 have separate indexes on <literal>x</literal> and <literal>y</literal>, one possible
674 implementation of a query like <literal>WHERE x = 5 AND y = 6</literal> is to
675 use each index with the appropriate query clause and then AND together
676 the index results to identify the result rows.
677 </para>
678
679 <para>
680 To combine multiple indexes, the system scans each needed index and
681 prepares a <firstterm>bitmap</firstterm> in memory giving the locations of
682 table rows that are reported as matching that index's conditions.
683 The bitmaps are then ANDed and ORed together as needed by the query.
684 Finally, the actual table rows are visited and returned. The table rows
685 are visited in physical order, because that is how the bitmap is laid
686 out; this means that any ordering of the original indexes is lost, and
687 so a separate sort step will be needed if the query has an <literal>ORDER
688 BY</literal> clause. For this reason, and because each additional index scan
689 adds extra time, the planner will sometimes choose to use a simple index
690 scan even though additional indexes are available that could have been
691 used as well.
692 </para>
693
694 <para>
695 In all but the simplest applications, there are various combinations of
696 indexes that might be useful, and the database developer must make
697 trade-offs to decide which indexes to provide. Sometimes multicolumn
698 indexes are best, but sometimes it's better to create separate indexes
699 and rely on the index-combination feature. For example, if your
700 workload includes a mix of queries that sometimes involve only column
701 <literal>x</literal>, sometimes only column <literal>y</literal>, and sometimes both
702 columns, you might choose to create two separate indexes on
703 <literal>x</literal> and <literal>y</literal>, relying on index combination to
704 process the queries that use both columns. You could also create a
705 multicolumn index on <literal>(x, y)</literal>. This index would typically be
706 more efficient than index combination for queries involving both
707 columns, but as discussed in <xref linkend="indexes-multicolumn"/>, it
708 would be less useful for queries involving only <literal>y</literal>. Just
709 how useful will depend on how effective the B-tree index skip scan
710 optimization is; if <literal>x</literal> has no more than several hundred
711 distinct values, skip scan will make searches for specific
712 <literal>y</literal> values execute reasonably efficiently. A combination
713 of a multicolumn index on <literal>(x, y)</literal> and a separate index on
714 <literal>y</literal> might also serve reasonably well. For
715 queries involving only <literal>x</literal>, the multicolumn index could be
716 used, though it would be larger and hence slower than an index on
717 <literal>x</literal> alone. The last alternative is to create all three
718 indexes, but this is probably only reasonable if the table is searched
719 much more often than it is updated and all three types of query are
720 common. If one of the types of query is much less common than the
721 others, you'd probably settle for creating just the two indexes that
722 best match the common types.
723 </para>
724
725 </sect1>
726
727
728 <sect1 id="indexes-unique">
729 <title>Unique Indexes</title>
730
731 <indexterm zone="indexes-unique">
732 <primary>index</primary>
733 <secondary>unique</secondary>
734 </indexterm>
735
736 <para>
737 Indexes can also be used to enforce uniqueness of a column's value,
738 or the uniqueness of the combined values of more than one column.
739 <synopsis>
740 CREATE UNIQUE INDEX <replaceable>name</replaceable> ON <replaceable>table</replaceable> (<replaceable>column</replaceable> <optional>, ...</optional>) <optional> NULLS <optional> NOT </optional> DISTINCT </optional>;
741 </synopsis>
742 Currently, only B-tree indexes can be declared unique.
743 </para>
744
745 <para>
746 When an index is declared unique, multiple table rows with equal
747 indexed values are not allowed. By default, null values in a unique column
748 are not considered equal, allowing multiple nulls in the column. The
749 <literal>NULLS NOT DISTINCT</literal> option modifies this and causes the
750 index to treat nulls as equal. A multicolumn unique index will only reject
751 cases where all indexed columns are equal in multiple rows.
752 </para>
753
754 <para>
755 <productname>PostgreSQL</productname> automatically creates a unique
756 index when a unique constraint or primary key is defined for a table.
757 The index covers the columns that make up the primary key or unique
758 constraint (a multicolumn index, if appropriate), and is the mechanism
759 that enforces the constraint.
760 </para>
761
762 <note>
763 <para>
764 There's no need to manually
765 create indexes on unique columns; doing so would just duplicate
766 the automatically-created index.
767 </para>
768 </note>
769 </sect1>
770
771
772 <sect1 id="indexes-expressional">
773 <title>Indexes on Expressions</title>
774
775 <indexterm zone="indexes-expressional">
776 <primary>index</primary>
777 <secondary sortas="expressions">on expressions</secondary>
778 </indexterm>
779
780 <para>
781 An index column need not be just a column of the underlying table,
782 but can be a function or scalar expression computed from one or
783 more columns of the table. This feature is useful to obtain fast
784 access to tables based on the results of computations.
785 </para>
786
787 <para>
788 For example, a common way to do case-insensitive comparisons is to
789 use the <function>lower</function> function:
790 <programlisting>
791 SELECT * FROM test1 WHERE lower(col1) = 'value';
792 </programlisting>
793 This query can use an index if one has been
794 defined on the result of the <literal>lower(col1)</literal>
795 function:
796 <programlisting>
797 CREATE INDEX test1_lower_col1_idx ON test1 (lower(col1));
798 </programlisting>
799 </para>
800
801 <para>
802 If we were to declare this index <literal>UNIQUE</literal>, it would prevent
803 creation of rows whose <literal>col1</literal> values differ only in case,
804 as well as rows whose <literal>col1</literal> values are actually identical.
805 Thus, indexes on expressions can be used to enforce constraints that
806 are not definable as simple unique constraints.
807 </para>
808
809 <para>
810 As another example, if one often does queries like:
811 <programlisting>
812 SELECT * FROM people WHERE (first_name || ' ' || last_name) = 'John Smith';
813 </programlisting>
814 then it might be worth creating an index like this:
815 <programlisting>
816 CREATE INDEX people_names ON people ((first_name || ' ' || last_name));
817 </programlisting>
818 </para>
819
820 <para>
821 The syntax of the <command>CREATE INDEX</command> command normally requires
822 writing parentheses around index expressions, as shown in the second
823 example. The parentheses can be omitted when the expression is just
824 a function call, as in the first example.
825 </para>
826
827 <para>
828 Index expressions are relatively expensive to maintain, because the
829 derived expression(s) must be computed for each row insertion
830 and <link linkend="storage-hot">non-HOT update</link>. However, the index expressions are
831 <emphasis>not</emphasis> recomputed during an indexed search, since they are
832 already stored in the index. In both examples above, the system
833 sees the query as just <literal>WHERE indexedcolumn = 'constant'</literal>
834 and so the speed of the search is equivalent to any other simple index
835 query. Thus, indexes on expressions are useful when retrieval speed
836 is more important than insertion and update speed.
837 </para>
838 </sect1>
839
840
841 <sect1 id="indexes-partial">
842 <title>Partial Indexes</title>
843
844 <indexterm zone="indexes-partial">
845 <primary>index</primary>
846 <secondary>partial</secondary>
847 </indexterm>
848
849 <para>
850 A <firstterm>partial index</firstterm> is an index built over a
851 subset of a table; the subset is defined by a conditional
852 expression (called the <firstterm>predicate</firstterm> of the
853 partial index). The index contains entries only for those table
854 rows that satisfy the predicate. Partial indexes are a specialized
855 feature, but there are several situations in which they are useful.
856 </para>
857
858 <para>
859 One major reason for using a partial index is to avoid indexing common
860 values. Since a query searching for a common value (one that
861 accounts for more than a few percent of all the table rows) will not
862 use the index anyway, there is no point in keeping those rows in the
863 index at all. This reduces the size of the index, which will speed
864 up those queries that do use the index. It will also speed up many table
865 update operations because the index does not need to be
866 updated in all cases. <xref linkend="indexes-partial-ex1"/> shows a
867 possible application of this idea.
868 </para>
869
870 <example id="indexes-partial-ex1">
871 <title>Setting up a Partial Index to Exclude Common Values</title>
872
873 <para>
874 Suppose you are storing web server access logs in a database.
875 Most accesses originate from the IP address range of your organization but
876 some are from elsewhere (say, employees on dial-up connections).
877 If your searches by IP are primarily for outside accesses,
878 you probably do not need to index the IP range that corresponds to your
879 organization's subnet.
880 </para>
881
882 <para>
883 Assume a table like this:
884 <programlisting>
885 CREATE TABLE access_log (
886 url varchar,
887 client_ip inet,
888 ...
889 );
890 </programlisting>
891 </para>
892
893 <para>
894 To create a partial index that suits our example, use a command
895 such as this:
896 <programlisting>
897 CREATE INDEX access_log_client_ip_ix ON access_log (client_ip)
898 WHERE NOT (client_ip &gt; inet '192.168.100.0' AND
899 client_ip &lt; inet '192.168.100.255');
900 </programlisting>
901 </para>
902
903 <para>
904 A typical query that can use this index would be:
905 <programlisting>
906 SELECT *
907 FROM access_log
908 WHERE url = '/index.html' AND client_ip = inet '212.78.10.32';
909 </programlisting>
910 Here the query's IP address is covered by the partial index. The
911 following query cannot use the partial index, as it uses an IP address
912 that is excluded from the index:
913 <programlisting>
914 SELECT *
915 FROM access_log
916 WHERE url = '/index.html' AND client_ip = inet '192.168.100.23';
917 </programlisting>
918 </para>
919
920 <para>
921 Observe that this kind of partial index requires that the common
922 values be predetermined, so such partial indexes are best used for
923 data distributions that do not change. Such indexes can be recreated
924 occasionally to adjust for new data distributions, but this adds
925 maintenance effort.
926 </para>
927 </example>
928
929 <para>
930 Another possible use for a partial index is to exclude values from the
931 index that the
932 typical query workload is not interested in; this is shown in <xref
933 linkend="indexes-partial-ex2"/>. This results in the same
934 advantages as listed above, but it prevents the
935 <quote>uninteresting</quote> values from being accessed via that
936 index, even if an index scan might be profitable in that
937 case. Obviously, setting up partial indexes for this kind of
938 scenario will require a lot of care and experimentation.
939 </para>
940
941 <example id="indexes-partial-ex2">
942 <title>Setting up a Partial Index to Exclude Uninteresting Values</title>
943
944 <para>
945 If you have a table that contains both billed and unbilled orders,
946 where the unbilled orders take up a small fraction of the total
947 table and yet those are the most-accessed rows, you can improve
948 performance by creating an index on just the unbilled rows. The
949 command to create the index would look like this:
950 <programlisting>
951 CREATE INDEX orders_unbilled_index ON orders (order_nr)
952 WHERE billed is not true;
953 </programlisting>
954 </para>
955
956 <para>
957 A possible query to use this index would be:
958 <programlisting>
959 SELECT * FROM orders WHERE billed is not true AND order_nr &lt; 10000;
960 </programlisting>
961 However, the index can also be used in queries that do not involve
962 <structfield>order_nr</structfield> at all, e.g.:
963 <programlisting>
964 SELECT * FROM orders WHERE billed is not true AND amount &gt; 5000.00;
965 </programlisting>
966 This is not as efficient as a partial index on the
967 <structfield>amount</structfield> column would be, since the system has to
968 scan the entire index. Yet, if there are relatively few unbilled
969 orders, using this partial index just to find the unbilled orders
970 could be a win.
971 </para>
972
973 <para>
974 Note that this query cannot use this index:
975 <programlisting>
976 SELECT * FROM orders WHERE order_nr = 3501;
977 </programlisting>
978 The order 3501 might be among the billed or unbilled
979 orders.
980 </para>
981 </example>
982
983 <para>
984 <xref linkend="indexes-partial-ex2"/> also illustrates that the
985 indexed column and the column used in the predicate do not need to
986 match. <productname>PostgreSQL</productname> supports partial
987 indexes with arbitrary predicates, so long as only columns of the
988 table being indexed are involved. However, keep in mind that the
989 predicate must match the conditions used in the queries that
990 are supposed to benefit from the index. To be precise, a partial
991 index can be used in a query only if the system can recognize that
992 the <literal>WHERE</literal> condition of the query mathematically implies
993 the predicate of the index.
994 <productname>PostgreSQL</productname> does not have a sophisticated
995 theorem prover that can recognize mathematically equivalent
996 expressions that are written in different forms. (Not
997 only is such a general theorem prover extremely difficult to
998 create, it would probably be too slow to be of any real use.)
999 The system can recognize simple inequality implications, for example
1000 <quote>x &lt; 1</quote> implies <quote>x &lt; 2</quote>; otherwise
1001 the predicate condition must exactly match part of the query's
1002 <literal>WHERE</literal> condition
1003 or the index will not be recognized as usable. Matching takes
1004 place at query planning time, not at run time. As a result,
1005 parameterized query clauses do not work with a partial index. For
1006 example a prepared query with a parameter might specify
1007 <quote>x &lt; ?</quote> which will never imply
1008 <quote>x &lt; 2</quote> for all possible values of the parameter.
1009 </para>
1010
1011 <para>
1012 A third possible use for partial indexes does not require the
1013 index to be used in queries at all. The idea here is to create
1014 a unique index over a subset of a table, as in <xref
1015 linkend="indexes-partial-ex3"/>. This enforces uniqueness
1016 among the rows that satisfy the index predicate, without constraining
1017 those that do not.
1018 </para>
1019
1020 <example id="indexes-partial-ex3">
1021 <title>Setting up a Partial Unique Index</title>
1022
1023 <para>
1024 Suppose that we have a table describing test outcomes. We wish
1025 to ensure that there is only one <quote>successful</quote> entry for
1026 a given subject and target combination, but there might be any number of
1027 <quote>unsuccessful</quote> entries. Here is one way to do it:
1028 <programlisting>
1029 CREATE TABLE tests (
1030 subject text,
1031 target text,
1032 success boolean,
1033 ...
1034 );
1035
1036 CREATE UNIQUE INDEX tests_success_constraint ON tests (subject, target)
1037 WHERE success;
1038 </programlisting>
1039 This is a particularly efficient approach when there are few
1040 successful tests and many unsuccessful ones. It is also possible to
1041 allow only one null in a column by creating a unique partial index
1042 with an <literal>IS NULL</literal> restriction.
1043 </para>
1044
1045 </example>
1046
1047 <para>
1048 Finally, a partial index can also be used to override the system's
1049 query plan choices. Also, data sets with peculiar
1050 distributions might cause the system to use an index when it really
1051 should not. In that case the index can be set up so that it is not
1052 available for the offending query. Normally,
1053 <productname>PostgreSQL</productname> makes reasonable choices about index
1054 usage (e.g., it avoids them when retrieving common values, so the
1055 earlier example really only saves index size, it is not required to
1056 avoid index usage), and grossly incorrect plan choices are cause
1057 for a bug report.
1058 </para>
1059
1060 <para>
1061 Keep in mind that setting up a partial index indicates that you
1062 know at least as much as the query planner knows, in particular you
1063 know when an index might be profitable. Forming this knowledge
1064 requires experience and understanding of how indexes in
1065 <productname>PostgreSQL</productname> work. In most cases, the
1066 advantage of a partial index over a regular index will be minimal.
1067 There are cases where they are quite counterproductive, as in <xref
1068 linkend="indexes-partial-ex4"/>.
1069 </para>
1070
1071 <example id="indexes-partial-ex4">
1072 <title>Do Not Use Partial Indexes as a Substitute for Partitioning</title>
1073
1074 <para>
1075 You might be tempted to create a large set of non-overlapping partial
1076 indexes, for example
1077
1078 <programlisting>
1079 CREATE INDEX mytable_cat_1 ON mytable (data) WHERE category = 1;
1080 CREATE INDEX mytable_cat_2 ON mytable (data) WHERE category = 2;
1081 CREATE INDEX mytable_cat_3 ON mytable (data) WHERE category = 3;
1082 ...
1083 CREATE INDEX mytable_cat_<replaceable>N</replaceable> ON mytable (data) WHERE category = <replaceable>N</replaceable>;
1084 </programlisting>
1085
1086 This is a bad idea! Almost certainly, you'll be better off with a
1087 single non-partial index, declared like
1088
1089 <programlisting>
1090 CREATE INDEX mytable_cat_data ON mytable (category, data);
1091 </programlisting>
1092
1093 (Put the category column first, for the reasons described in
1094 <xref linkend="indexes-multicolumn"/>.) While a search in this larger
1095 index might have to descend through a couple more tree levels than a
1096 search in a smaller index, that's almost certainly going to be cheaper
1097 than the planner effort needed to select the appropriate one of the
1098 partial indexes. The core of the problem is that the system does not
1099 understand the relationship among the partial indexes, and will
1100 laboriously test each one to see if it's applicable to the current
1101 query.
1102 </para>
1103
1104 <para>
1105 If your table is large enough that a single index really is a bad idea,
1106 you should look into using partitioning instead (see
1107 <xref linkend="ddl-partitioning"/>). With that mechanism, the system
1108 does understand that the tables and indexes are non-overlapping, so
1109 far better performance is possible.
1110 </para>
1111 </example>
1112
1113 <para>
1114 More information about partial indexes can be found in <xref
1115 linkend="ston89b"/>, <xref linkend="olson93"/>, and <xref
1116 linkend="seshadri95"/>.
1117 </para>
1118 </sect1>
1119
1120
1121 <sect1 id="indexes-index-only-scans">
1122 <title>Index-Only Scans and Covering Indexes</title>
1123
1124 <indexterm zone="indexes-index-only-scans">
1125 <primary>index</primary>
1126 <secondary>index-only scans</secondary>
1127 </indexterm>
1128 <indexterm zone="indexes-index-only-scans">
1129 <primary>index-only scan</primary>
1130 </indexterm>
1131 <indexterm zone="indexes-index-only-scans">
1132 <primary>index</primary>
1133 <secondary>covering</secondary>
1134 </indexterm>
1135 <indexterm zone="indexes-index-only-scans">
1136 <primary>covering index</primary>
1137 </indexterm>
1138
1139 <para>
1140 All indexes in <productname>PostgreSQL</productname>
1141 are <firstterm>secondary</firstterm> indexes, meaning that each index is
1142 stored separately from the table's main data area (which is called the
1143 table's <firstterm>heap</firstterm>
1144 in <productname>PostgreSQL</productname> terminology). This means that
1145 in an ordinary index scan, each row retrieval requires fetching data from
1146 both the index and the heap. Furthermore, while the index entries that
1147 match a given indexable <literal>WHERE</literal> condition are usually
1148 close together in the index, the table rows they reference might be
1149 anywhere in the heap. The heap-access portion of an index scan thus
1150 involves a lot of random access into the heap, which can be slow,
1151 particularly on traditional rotating media. (As described in
1152 <xref linkend="indexes-bitmap-scans"/>, bitmap scans try to alleviate
1153 this cost by doing the heap accesses in sorted order, but that only goes
1154 so far.)
1155 </para>
1156
1157 <para>
1158 To solve this performance problem, <productname>PostgreSQL</productname>
1159 supports <firstterm>index-only scans</firstterm>, which can answer
1160 queries from an index alone without any heap access. The basic idea is
1161 to return values directly out of each index entry instead of consulting
1162 the associated heap entry. There are two fundamental restrictions on
1163 when this method can be used:
1164
1165 <orderedlist>
1166 <listitem>
1167 <para>
1168 The index type must support index-only scans. B-tree indexes always
1169 do. GiST and SP-GiST indexes support index-only scans for some
1170 operator classes but not others. Other index types have no support.
1171 The underlying requirement is that the index must physically store, or
1172 else be able to reconstruct, the original data value for each index
1173 entry. As a counterexample, GIN indexes cannot support index-only
1174 scans because each index entry typically holds only part of the
1175 original data value.
1176 </para>
1177 </listitem>
1178
1179 <listitem>
1180 <para>
1181 The query must reference only columns stored in the index. For
1182 example, given an index on columns <literal>x</literal>
1183 and <literal>y</literal> of a table that also has a
1184 column <literal>z</literal>, these queries could use index-only scans:
1185 <programlisting>
1186 SELECT x, y FROM tab WHERE x = 'key';
1187 SELECT x FROM tab WHERE x = 'key' AND y &lt; 42;
1188 </programlisting>
1189 but these queries could not:
1190 <programlisting>
1191 SELECT x, z FROM tab WHERE x = 'key';
1192 SELECT x FROM tab WHERE x = 'key' AND z &lt; 42;
1193 </programlisting>
1194 (Expression indexes and partial indexes complicate this rule,
1195 as discussed below.)
1196 </para>
1197 </listitem>
1198 </orderedlist>
1199 </para>
1200
1201 <para>
1202 If these two fundamental requirements are met, then all the data values
1203 required by the query are available from the index, so an index-only scan
1204 is physically possible. But there is an additional requirement for any
1205 table scan in <productname>PostgreSQL</productname>: it must verify that
1206 each retrieved row be <quote>visible</quote> to the query's MVCC
1207 snapshot, as discussed in <xref linkend="mvcc"/>. Visibility information
1208 is not stored in index entries, only in heap entries; so at first glance
1209 it would seem that every row retrieval would require a heap access
1210 anyway. And this is indeed the case, if the table row has been modified
1211 recently. However, for seldom-changing data there is a way around this
1212 problem. <productname>PostgreSQL</productname> tracks, for each page in
1213 a table's heap, whether all rows stored in that page are old enough to be
1214 visible to all current and future transactions. This information is
1215 stored in a bit in the table's <firstterm>visibility map</firstterm>. An
1216 index-only scan, after finding a candidate index entry, checks the
1217 visibility map bit for the corresponding heap page. If it's set, the row
1218 is known visible and so the data can be returned with no further work.
1219 If it's not set, the heap entry must be visited to find out whether it's
1220 visible, so no performance advantage is gained over a standard index
1221 scan. Even in the successful case, this approach trades visibility map
1222 accesses for heap accesses; but since the visibility map is four orders
1223 of magnitude smaller than the heap it describes, far less physical I/O is
1224 needed to access it. In most situations the visibility map remains
1225 cached in memory all the time.
1226 </para>
1227
1228 <para>
1229 In short, while an index-only scan is possible given the two fundamental
1230 requirements, it will be a win only if a significant fraction of the
1231 table's heap pages have their all-visible map bits set. But tables in
1232 which a large fraction of the rows are unchanging are common enough to
1233 make this type of scan very useful in practice.
1234 </para>
1235
1236 <para>
1237 <indexterm>
1238 <primary><literal>INCLUDE</literal></primary>
1239 <secondary>in index definitions</secondary>
1240 </indexterm>
1241 To make effective use of the index-only scan feature, you might choose to
1242 create a <firstterm>covering index</firstterm>, which is an index
1243 specifically designed to include the columns needed by a particular
1244 type of query that you run frequently. Since queries typically need to
1245 retrieve more columns than just the ones they search
1246 on, <productname>PostgreSQL</productname> allows you to create an index
1247 in which some columns are just <quote>payload</quote> and are not part
1248 of the search key. This is done by adding an <literal>INCLUDE</literal>
1249 clause listing the extra columns. For example, if you commonly run
1250 queries like
1251 <programlisting>
1252 SELECT y FROM tab WHERE x = 'key';
1253 </programlisting>
1254 the traditional approach to speeding up such queries would be to create
1255 an index on <literal>x</literal> only. However, an index defined as
1256 <programlisting>
1257 CREATE INDEX tab_x_y ON tab(x) INCLUDE (y);
1258 </programlisting>
1259 could handle these queries as index-only scans,
1260 because <literal>y</literal> can be obtained from the index without
1261 visiting the heap.
1262 </para>
1263
1264 <para>
1265 Because column <literal>y</literal> is not part of the index's search
1266 key, it does not have to be of a data type that the index can handle;
1267 it's merely stored in the index and is not interpreted by the index
1268 machinery. Also, if the index is a unique index, that is
1269 <programlisting>
1270 CREATE UNIQUE INDEX tab_x_y ON tab(x) INCLUDE (y);
1271 </programlisting>
1272 the uniqueness condition applies to just column <literal>x</literal>,
1273 not to the combination of <literal>x</literal> and <literal>y</literal>.
1274 (An <literal>INCLUDE</literal> clause can also be written
1275 in <literal>UNIQUE</literal> and <literal>PRIMARY KEY</literal>
1276 constraints, providing alternative syntax for setting up an index like
1277 this.)
1278 </para>
1279
1280 <para>
1281 It's wise to be conservative about adding non-key payload columns to an
1282 index, especially wide columns. If an index tuple exceeds the
1283 maximum size allowed for the index type, data insertion will fail.
1284 In any case, non-key columns duplicate data from the index's table
1285 and bloat the size of the index, thus potentially slowing searches.
1286 And remember that there is little point in including payload columns in an
1287 index unless the table changes slowly enough that an index-only scan is
1288 likely to not need to access the heap. If the heap tuple must be visited
1289 anyway, it costs nothing more to get the column's value from there.
1290 Other restrictions are that expressions are not currently supported as
1291 included columns, and that only B-tree, GiST and SP-GiST indexes currently
1292 support included columns.
1293 </para>
1294
1295 <para>
1296 Before <productname>PostgreSQL</productname> had
1297 the <literal>INCLUDE</literal> feature, people sometimes made covering
1298 indexes by writing the payload columns as ordinary index columns,
1299 that is writing
1300 <programlisting>
1301 CREATE INDEX tab_x_y ON tab(x, y);
1302 </programlisting>
1303 even though they had no intention of ever using <literal>y</literal> as
1304 part of a <literal>WHERE</literal> clause. This works fine as long as
1305 the extra columns are trailing columns; making them be leading columns is
1306 unwise for the reasons explained in <xref linkend="indexes-multicolumn"/>.
1307 However, this method doesn't support the case where you want the index to
1308 enforce uniqueness on the key column(s).
1309 </para>
1310
1311 <para>
1312 <firstterm>Suffix truncation</firstterm> always removes non-key
1313 columns from upper B-Tree levels. As payload columns, they are
1314 never used to guide index scans. The truncation process also
1315 removes one or more trailing key column(s) when the remaining
1316 prefix of key column(s) happens to be sufficient to describe tuples
1317 on the lowest B-Tree level. In practice, covering indexes without
1318 an <literal>INCLUDE</literal> clause often avoid storing columns
1319 that are effectively payload in the upper levels. However,
1320 explicitly defining payload columns as non-key columns
1321 <emphasis>reliably</emphasis> keeps the tuples in upper levels
1322 small.
1323 </para>
1324
1325 <para>
1326 In principle, index-only scans can be used with expression indexes.
1327 For example, given an index on <literal>f(x)</literal>
1328 where <literal>x</literal> is a table column, it should be possible to
1329 execute
1330 <programlisting>
1331 SELECT f(x) FROM tab WHERE f(x) &lt; 1;
1332 </programlisting>
1333 as an index-only scan; and this is very attractive
1334 if <literal>f()</literal> is an expensive-to-compute function.
1335 However, <productname>PostgreSQL</productname>'s planner is currently not
1336 very smart about such cases. It considers a query to be potentially
1337 executable by index-only scan only when all <emphasis>columns</emphasis>
1338 needed by the query are available from the index. In this
1339 example, <literal>x</literal> is not needed except in the
1340 context <literal>f(x)</literal>, but the planner does not notice that and
1341 concludes that an index-only scan is not possible. If an index-only scan
1342 seems sufficiently worthwhile, this can be worked around by
1343 adding <literal>x</literal> as an included column, for example
1344 <programlisting>
1345 CREATE INDEX tab_f_x ON tab (f(x)) INCLUDE (x);
1346 </programlisting>
1347 An additional caveat, if the goal is to avoid
1348 recalculating <literal>f(x)</literal>, is that the planner won't
1349 necessarily match uses of <literal>f(x)</literal> that aren't in
1350 indexable <literal>WHERE</literal> clauses to the index column. It will
1351 usually get this right in simple queries such as shown above, but not in
1352 queries that involve joins. These deficiencies may be remedied in future
1353 versions of <productname>PostgreSQL</productname>.
1354 </para>
1355
1356 <para>
1357 Partial indexes also have interesting interactions with index-only scans.
1358 Consider the partial index shown in <xref linkend="indexes-partial-ex3"/>:
1359 <programlisting>
1360 CREATE UNIQUE INDEX tests_success_constraint ON tests (subject, target)
1361 WHERE success;
1362 </programlisting>
1363 In principle, we could do an index-only scan on this index to satisfy a
1364 query like
1365 <programlisting>
1366 SELECT target FROM tests WHERE subject = 'some-subject' AND success;
1367 </programlisting>
1368 But there's a problem: the <literal>WHERE</literal> clause refers
1369 to <literal>success</literal> which is not available as a result column
1370 of the index. Nonetheless, an index-only scan is possible because the
1371 plan does not need to recheck that part of the <literal>WHERE</literal>
1372 clause at run time: all entries found in the index necessarily
1373 have <literal>success = true</literal> so this need not be explicitly
1374 checked in the plan. <productname>PostgreSQL</productname> versions 9.6
1375 and later will recognize such cases and allow index-only scans to be
1376 generated, but older versions will not.
1377 </para>
1378 </sect1>
1379
1380
1381 <sect1 id="indexes-opclass">
1382 <title>Operator Classes and Operator Families</title>
1383
1384 <indexterm zone="indexes-opclass">
1385 <primary>operator class</primary>
1386 </indexterm>
1387
1388 <indexterm zone="indexes-opclass">
1389 <primary>operator family</primary>
1390 </indexterm>
1391
1392 <para>
1393 An index definition can specify an <firstterm>operator
1394 class</firstterm> for each column of an index.
1395 <synopsis>
1396 CREATE INDEX <replaceable>name</replaceable> ON <replaceable>table</replaceable> (<replaceable>column</replaceable> <replaceable>opclass</replaceable> [ ( <replaceable>opclass_options</replaceable> ) ] <optional><replaceable>sort options</replaceable></optional> <optional>, ...</optional>);
1397 </synopsis>
1398 The operator class identifies the operators to be used by the index
1399 for that column. For example, a B-tree index on the type <type>int4</type>
1400 would use the <literal>int4_ops</literal> class; this operator
1401 class includes comparison functions for values of type <type>int4</type>.
1402 In practice the default operator class for the column's data type is
1403 usually sufficient. The main reason for having operator classes is
1404 that for some data types, there could be more than one meaningful
1405 index behavior. For example, we might want to sort a complex-number data
1406 type either by absolute value or by real part. We could do this by
1407 defining two operator classes for the data type and then selecting
1408 the proper class when making an index. The operator class determines
1409 the basic sort ordering (which can then be modified by adding sort options
1410 <literal>COLLATE</literal>,
1411 <literal>ASC</literal>/<literal>DESC</literal> and/or
1412 <literal>NULLS FIRST</literal>/<literal>NULLS LAST</literal>).
1413 </para>
1414
1415 <para>
1416 There are also some built-in operator classes besides the default ones:
1417
1418 <itemizedlist>
1419 <listitem>
1420 <para>
1421 The operator classes <literal>text_pattern_ops</literal>,
1422 <literal>varchar_pattern_ops</literal>, and
1423 <literal>bpchar_pattern_ops</literal> support B-tree indexes on
1424 the types <type>text</type>, <type>varchar</type>, and
1425 <type>char</type> respectively. The
1426 difference from the default operator classes is that the values
1427 are compared strictly character by character rather than
1428 according to the locale-specific collation rules. This makes
1429 these operator classes suitable for use by queries involving
1430 pattern matching expressions (<literal>LIKE</literal> or POSIX
1431 regular expressions) when the database does not use the standard
1432 <quote>C</quote> locale. As an example, you might index a
1433 <type>varchar</type> column like this:
1434 <programlisting>
1435 CREATE INDEX test_index ON test_table (col varchar_pattern_ops);
1436 </programlisting>
1437 Note that you should also create an index with the default operator
1438 class if you want queries involving ordinary <literal>&lt;</literal>,
1439 <literal>&lt;=</literal>, <literal>&gt;</literal>, or <literal>&gt;=</literal> comparisons
1440 to use an index. Such queries cannot use the
1441 <literal><replaceable>xxx</replaceable>_pattern_ops</literal>
1442 operator classes. (Ordinary equality comparisons can use these
1443 operator classes, however.) It is possible to create multiple
1444 indexes on the same column with different operator classes.
1445 If you do use the C locale, you do not need the
1446 <literal><replaceable>xxx</replaceable>_pattern_ops</literal>
1447 operator classes, because an index with the default operator class
1448 is usable for pattern-matching queries in the C locale.
1449 </para>
1450 </listitem>
1451 </itemizedlist>
1452 </para>
1453
1454 <para>
1455 The following query shows all defined operator classes:
1456
1457 <programlisting>
1458 SELECT am.amname AS index_method,
1459 opc.opcname AS opclass_name,
1460 opc.opcintype::regtype AS indexed_type,
1461 opc.opcdefault AS is_default
1462 FROM pg_am am, pg_opclass opc
1463 WHERE opc.opcmethod = am.oid
1464 ORDER BY index_method, opclass_name;
1465 </programlisting>
1466 </para>
1467
1468 <para>
1469 An operator class is actually just a subset of a larger structure called an
1470 <firstterm>operator family</firstterm>. In cases where several data types have
1471 similar behaviors, it is frequently useful to define cross-data-type
1472 operators and allow these to work with indexes. To do this, the operator
1473 classes for each of the types must be grouped into the same operator
1474 family. The cross-type operators are members of the family, but are not
1475 associated with any single class within the family.
1476 </para>
1477
1478 <para>
1479 This expanded version of the previous query shows the operator family
1480 each operator class belongs to:
1481 <programlisting>
1482 SELECT am.amname AS index_method,
1483 opc.opcname AS opclass_name,
1484 opf.opfname AS opfamily_name,
1485 opc.opcintype::regtype AS indexed_type,
1486 opc.opcdefault AS is_default
1487 FROM pg_am am, pg_opclass opc, pg_opfamily opf
1488 WHERE opc.opcmethod = am.oid AND
1489 opc.opcfamily = opf.oid
1490 ORDER BY index_method, opclass_name;
1491 </programlisting>
1492 </para>
1493
1494 <para>
1495 This query shows all defined operator families and all
1496 the operators included in each family:
1497 <programlisting>
1498 SELECT am.amname AS index_method,
1499 opf.opfname AS opfamily_name,
1500 amop.amopopr::regoperator AS opfamily_operator
1501 FROM pg_am am, pg_opfamily opf, pg_amop amop
1502 WHERE opf.opfmethod = am.oid AND
1503 amop.amopfamily = opf.oid
1504 ORDER BY index_method, opfamily_name, opfamily_operator;
1505 </programlisting>
1506 </para>
1507
1508 <tip>
1509 <para>
1510 <xref linkend="app-psql"/> has
1511 commands <command>\dAc</command>, <command>\dAf</command>,
1512 and <command>\dAo</command>, which provide slightly more sophisticated
1513 versions of these queries.
1514 </para>
1515 </tip>
1516 </sect1>
1517
1518
1519 <sect1 id="indexes-collations">
1520 <title>Indexes and Collations</title>
1521
1522 <para>
1523 An index can support only one collation per index column.
1524 If multiple collations are of interest, multiple indexes may be needed.
1525 </para>
1526
1527 <para>
1528 Consider these statements:
1529 <programlisting>
1530 CREATE TABLE test1c (
1531 id integer,
1532 content varchar COLLATE "x"
1533 );
1534
1535 CREATE INDEX test1c_content_index ON test1c (content);
1536 </programlisting>
1537 The index automatically uses the collation of the
1538 underlying column. So a query of the form
1539 <programlisting>
1540 SELECT * FROM test1c WHERE content &gt; <replaceable>constant</replaceable>;
1541 </programlisting>
1542 could use the index, because the comparison will by default use the
1543 collation of the column. However, this index cannot accelerate queries
1544 that involve some other collation. So if queries of the form, say,
1545 <programlisting>
1546 SELECT * FROM test1c WHERE content &gt; <replaceable>constant</replaceable> COLLATE "y";
1547 </programlisting>
1548 are also of interest, an additional index could be created that supports
1549 the <literal>"y"</literal> collation, like this:
1550 <programlisting>
1551 CREATE INDEX test1c_content_y_index ON test1c (content COLLATE "y");
1552 </programlisting>
1553 </para>
1554 </sect1>
1555
1556
1557 <sect1 id="indexes-examine">
1558 <title>Examining Index Usage</title>
1559
1560 <indexterm zone="indexes-examine">
1561 <primary>index</primary>
1562 <secondary>examining usage</secondary>
1563 </indexterm>
1564
1565 <para>
1566 Although indexes in <productname>PostgreSQL</productname> do not need
1567 maintenance or tuning, it is still important to check
1568 which indexes are actually used by the real-life query workload.
1569 Examining index usage for an individual query is done with the
1570 <xref linkend="sql-explain"/>
1571 command; its application for this purpose is
1572 illustrated in <xref linkend="using-explain"/>.
1573 It is also possible to gather overall statistics about index usage
1574 in a running server, as described in <xref linkend="monitoring-stats"/>.
1575 </para>
1576
1577 <para>
1578 It is difficult to formulate a general procedure for determining
1579 which indexes to create. There are a number of typical cases that
1580 have been shown in the examples throughout the previous sections.
1581 A good deal of experimentation is often necessary.
1582 The rest of this section gives some tips for that:
1583 </para>
1584
1585 <itemizedlist>
1586 <listitem>
1587 <para>
1588 Always run <xref linkend="sql-analyze"/>
1589 first. This command
1590 collects statistics about the distribution of the values in the
1591 table. This information is required to estimate the number of rows
1592 returned by a query, which is needed by the planner to assign
1593 realistic costs to each possible query plan. In absence of any
1594 real statistics, some default values are assumed, which are
1595 almost certain to be inaccurate. Examining an application's
1596 index usage without having run <command>ANALYZE</command> is
1597 therefore a lost cause.
1598 See <xref linkend="vacuum-for-statistics"/>
1599 and <xref linkend="autovacuum"/> for more information.
1600 </para>
1601 </listitem>
1602
1603 <listitem>
1604 <para>
1605 Use real data for experimentation. Using test data for setting
1606 up indexes will tell you what indexes you need for the test data,
1607 but that is all.
1608 </para>
1609
1610 <para>
1611 It is especially fatal to use very small test data sets.
1612 While selecting 1000 out of 100000 rows could be a candidate for
1613 an index, selecting 1 out of 100 rows will hardly be, because the
1614 100 rows probably fit within a single disk page, and there
1615 is no plan that can beat sequentially fetching 1 disk page.
1616 </para>
1617
1618 <para>
1619 Also be careful when making up test data, which is often
1620 unavoidable when the application is not yet in production.
1621 Values that are very similar, completely random, or inserted in
1622 sorted order will skew the statistics away from the distribution
1623 that real data would have.
1624 </para>
1625 </listitem>
1626
1627 <listitem>
1628 <para>
1629 When indexes are not used, it can be useful for testing to force
1630 their use. There are run-time parameters that can turn off
1631 various plan types (see <xref linkend="runtime-config-query-enable"/>).
1632 For instance, turning off sequential scans
1633 (<varname>enable_seqscan</varname>) and nested-loop joins
1634 (<varname>enable_nestloop</varname>), which are the most basic plans,
1635 will force the system to use a different plan. If the system
1636 still chooses a sequential scan or nested-loop join then there is
1637 probably a more fundamental reason why the index is not being
1638 used; for example, the query condition does not match the index.
1639 (What kind of query can use what kind of index is explained in
1640 the previous sections.)
1641 </para>
1642 </listitem>
1643
1644 <listitem>
1645 <para>
1646 If forcing index usage does use the index, then there are two
1647 possibilities: Either the system is right and using the index is
1648 indeed not appropriate, or the cost estimates of the query plans
1649 are not reflecting reality. So you should time your query with
1650 and without indexes. The <command>EXPLAIN ANALYZE</command>
1651 command can be useful here.
1652 </para>
1653 </listitem>
1654
1655 <listitem>
1656 <para>
1657 If it turns out that the cost estimates are wrong, there are,
1658 again, two possibilities. The total cost is computed from the
1659 per-row costs of each plan node times the selectivity estimate of
1660 the plan node. The costs estimated for the plan nodes can be adjusted
1661 via run-time parameters (described in <xref
1662 linkend="runtime-config-query-constants"/>).
1663 An inaccurate selectivity estimate is due to
1664 insufficient statistics. It might be possible to improve this by
1665 tuning the statistics-gathering parameters (see
1666 <xref linkend="sql-altertable"/>).
1667 </para>
1668
1669 <para>
1670 If you do not succeed in adjusting the costs to be more
1671 appropriate, then you might have to resort to forcing index usage
1672 explicitly. You might also want to contact the
1673 <productname>PostgreSQL</productname> developers to examine the issue.
1674 </para>
1675 </listitem>
1676 </itemizedlist>
1677 </sect1>
1678 </chapter>