← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« back to all changes in this revision

Viewing changes to doc/src/sgml/html/index-scanning.html

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/src/sgml/html/index-scanning.html
 
1
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
 
2
<HTML
 
3
><HEAD
 
4
><TITLE
 
5
>Index Scanning</TITLE
 
6
><META
 
7
NAME="GENERATOR"
 
8
CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK
 
9
REV="MADE"
 
10
HREF="mailto:pgsql-docs@postgresql.org"><LINK
 
11
REL="HOME"
 
12
TITLE="PostgreSQL 9.1beta1 Documentation"
 
13
HREF="index.html"><LINK
 
14
REL="UP"
 
15
TITLE="Index Access Method Interface Definition"
 
16
HREF="indexam.html"><LINK
 
17
REL="PREVIOUS"
 
18
TITLE="Index Access Method Functions"
 
19
HREF="index-functions.html"><LINK
 
20
REL="NEXT"
 
21
TITLE="Index Locking Considerations"
 
22
HREF="index-locking.html"><LINK
 
23
REL="STYLESHEET"
 
24
TYPE="text/css"
 
25
HREF="stylesheet.css"><META
 
26
HTTP-EQUIV="Content-Type"
 
27
CONTENT="text/html; charset=ISO-8859-1"><META
 
28
NAME="creation"
 
29
CONTENT="2011-04-27T21:20:33"></HEAD
 
30
><BODY
 
31
CLASS="SECT1"
 
32
><DIV
 
33
CLASS="NAVHEADER"
 
34
><TABLE
 
35
SUMMARY="Header navigation table"
 
36
WIDTH="100%"
 
37
BORDER="0"
 
38
CELLPADDING="0"
 
39
CELLSPACING="0"
 
40
><TR
 
41
><TH
 
42
COLSPAN="5"
 
43
ALIGN="center"
 
44
VALIGN="bottom"
 
45
><A
 
46
HREF="index.html"
 
47
>PostgreSQL 9.1beta1 Documentation</A
 
48
></TH
 
49
></TR
 
50
><TR
 
51
><TD
 
52
WIDTH="10%"
 
53
ALIGN="left"
 
54
VALIGN="top"
 
55
><A
 
56
TITLE="Index Access Method Functions"
 
57
HREF="index-functions.html"
 
58
ACCESSKEY="P"
 
59
>Prev</A
 
60
></TD
 
61
><TD
 
62
WIDTH="10%"
 
63
ALIGN="left"
 
64
VALIGN="top"
 
65
><A
 
66
TITLE="Index Access Method Interface Definition"
 
67
HREF="indexam.html"
 
68
>Fast Backward</A
 
69
></TD
 
70
><TD
 
71
WIDTH="60%"
 
72
ALIGN="center"
 
73
VALIGN="bottom"
 
74
>Chapter 52. Index Access Method Interface Definition</TD
 
75
><TD
 
76
WIDTH="10%"
 
77
ALIGN="right"
 
78
VALIGN="top"
 
79
><A
 
80
TITLE="Index Access Method Interface Definition"
 
81
HREF="indexam.html"
 
82
>Fast Forward</A
 
83
></TD
 
84
><TD
 
85
WIDTH="10%"
 
86
ALIGN="right"
 
87
VALIGN="top"
 
88
><A
 
89
TITLE="Index Locking Considerations"
 
90
HREF="index-locking.html"
 
91
ACCESSKEY="N"
 
92
>Next</A
 
93
></TD
 
94
></TR
 
95
></TABLE
 
96
><HR
 
97
ALIGN="LEFT"
 
98
WIDTH="100%"></DIV
 
99
><DIV
 
100
CLASS="SECT1"
 
101
><H1
 
102
CLASS="SECT1"
 
103
><A
 
104
NAME="INDEX-SCANNING"
 
105
>52.3. Index Scanning</A
 
106
></H1
 
107
><P
 
108
>   In an index scan, the index access method is responsible for regurgitating
 
109
   the TIDs of all the tuples it has been told about that match the
 
110
   <I
 
111
CLASS="FIRSTTERM"
 
112
>scan keys</I
 
113
>.  The access method is <SPAN
 
114
CLASS="emphasis"
 
115
><I
 
116
CLASS="EMPHASIS"
 
117
>not</I
 
118
></SPAN
 
119
> involved in
 
120
   actually fetching those tuples from the index's parent table, nor in
 
121
   determining whether they pass the scan's time qualification test or other
 
122
   conditions.
 
123
  </P
 
124
><P
 
125
>   A scan key is the internal representation of a <TT
 
126
CLASS="LITERAL"
 
127
>WHERE</TT
 
128
> clause of
 
129
   the form <TT
 
130
CLASS="REPLACEABLE"
 
131
><I
 
132
>index_key</I
 
133
></TT
 
134
> <TT
 
135
CLASS="REPLACEABLE"
 
136
><I
 
137
>operator</I
 
138
></TT
 
139
>
 
140
   <TT
 
141
CLASS="REPLACEABLE"
 
142
><I
 
143
>constant</I
 
144
></TT
 
145
>, where the index key is one of the columns of the
 
146
   index and the operator is one of the members of the operator family
 
147
   associated with that index column.  An index scan has zero or more scan
 
148
   keys, which are implicitly ANDed &mdash; the returned tuples are expected
 
149
   to satisfy all the indicated conditions.
 
150
  </P
 
151
><P
 
152
>   The access method can report that the index is <I
 
153
CLASS="FIRSTTERM"
 
154
>lossy</I
 
155
>, or
 
156
   requires rechecks, for a particular query.  This implies that the index
 
157
   scan will return all the entries that pass the scan key, plus possibly
 
158
   additional entries that do not.  The core system's index-scan machinery
 
159
   will then apply the index conditions again to the heap tuple to verify
 
160
   whether or not it really should be selected.  If the recheck option is not
 
161
   specified, the index scan must return exactly the set of matching entries.
 
162
  </P
 
163
><P
 
164
>   Note that it is entirely up to the access method to ensure that it
 
165
   correctly finds all and only the entries passing all the given scan keys.
 
166
   Also, the core system will simply hand off all the <TT
 
167
CLASS="LITERAL"
 
168
>WHERE</TT
 
169
>
 
170
   clauses that match the index keys and operator families, without any
 
171
   semantic analysis to determine whether they are redundant or
 
172
   contradictory.  As an example, given
 
173
   <TT
 
174
CLASS="LITERAL"
 
175
>WHERE x &gt; 4 AND x &gt; 14</TT
 
176
> where <TT
 
177
CLASS="LITERAL"
 
178
>x</TT
 
179
> is a b-tree
 
180
   indexed column, it is left to the b-tree <CODE
 
181
CLASS="FUNCTION"
 
182
>amrescan</CODE
 
183
> function
 
184
   to realize that the first scan key is redundant and can be discarded.
 
185
   The extent of preprocessing needed during <CODE
 
186
CLASS="FUNCTION"
 
187
>amrescan</CODE
 
188
> will
 
189
   depend on the extent to which the index access method needs to reduce
 
190
   the scan keys to a <SPAN
 
191
CLASS="QUOTE"
 
192
>"normalized"</SPAN
 
193
> form.
 
194
  </P
 
195
><P
 
196
>   Some access methods return index entries in a well-defined order, others
 
197
   do not.  There are actually two different ways that an access method can
 
198
   support sorted output:
 
199
 
 
200
    <P
 
201
></P
 
202
></P><UL
 
203
><LI
 
204
><P
 
205
>       Access methods that always return entries in the natural ordering
 
206
       of their data (such as btree) should set
 
207
       <TT
 
208
CLASS="STRUCTNAME"
 
209
>pg_am</TT
 
210
>.<TT
 
211
CLASS="STRUCTFIELD"
 
212
>amcanorder</TT
 
213
> to true.
 
214
       Currently, such access methods must use btree-compatible strategy
 
215
       numbers for their equality and ordering operators.
 
216
      </P
 
217
></LI
 
218
><LI
 
219
><P
 
220
>       Access methods that support ordering operators should set
 
221
       <TT
 
222
CLASS="STRUCTNAME"
 
223
>pg_am</TT
 
224
>.<TT
 
225
CLASS="STRUCTFIELD"
 
226
>amcanorderbyop</TT
 
227
> to true.
 
228
       This indicates that the index is capable of returning entries in
 
229
       an order satisfying <TT
 
230
CLASS="LITERAL"
 
231
>ORDER BY</TT
 
232
> <TT
 
233
CLASS="REPLACEABLE"
 
234
><I
 
235
>index_key</I
 
236
></TT
 
237
>
 
238
       <TT
 
239
CLASS="REPLACEABLE"
 
240
><I
 
241
>operator</I
 
242
></TT
 
243
> <TT
 
244
CLASS="REPLACEABLE"
 
245
><I
 
246
>constant</I
 
247
></TT
 
248
>.  Scan modifiers
 
249
       of that form can be passed to <CODE
 
250
CLASS="FUNCTION"
 
251
>amrescan</CODE
 
252
> as described
 
253
       previously.
 
254
      </P
 
255
></LI
 
256
></UL
 
257
><P>
 
258
  </P
 
259
><P
 
260
>   The <CODE
 
261
CLASS="FUNCTION"
 
262
>amgettuple</CODE
 
263
> function has a <TT
 
264
CLASS="LITERAL"
 
265
>direction</TT
 
266
> argument,
 
267
   which can be either <TT
 
268
CLASS="LITERAL"
 
269
>ForwardScanDirection</TT
 
270
> (the normal case)
 
271
   or  <TT
 
272
CLASS="LITERAL"
 
273
>BackwardScanDirection</TT
 
274
>.  If the first call after
 
275
   <CODE
 
276
CLASS="FUNCTION"
 
277
>amrescan</CODE
 
278
> specifies <TT
 
279
CLASS="LITERAL"
 
280
>BackwardScanDirection</TT
 
281
>, then the
 
282
   set of matching index entries is to be scanned back-to-front rather than in
 
283
   the normal front-to-back direction, so <CODE
 
284
CLASS="FUNCTION"
 
285
>amgettuple</CODE
 
286
> must return
 
287
   the last matching tuple in the index, rather than the first one as it
 
288
   normally would.  (This will only occur for access
 
289
   methods that set <TT
 
290
CLASS="STRUCTFIELD"
 
291
>amcanorder</TT
 
292
> to true.)  After the
 
293
   first call, <CODE
 
294
CLASS="FUNCTION"
 
295
>amgettuple</CODE
 
296
> must be prepared to advance the scan in
 
297
   either direction from the most recently returned entry.  (But if
 
298
   <TT
 
299
CLASS="STRUCTNAME"
 
300
>pg_am</TT
 
301
>.<TT
 
302
CLASS="STRUCTFIELD"
 
303
>amcanbackward</TT
 
304
> is false, all subsequent
 
305
   calls will have the same direction as the first one.)
 
306
  </P
 
307
><P
 
308
>   Access methods that support ordered scans must support <SPAN
 
309
CLASS="QUOTE"
 
310
>"marking"</SPAN
 
311
> a
 
312
   position in a scan and later returning to the marked position.  The same
 
313
   position might be restored multiple times.  However, only one position need
 
314
   be remembered per scan; a new <CODE
 
315
CLASS="FUNCTION"
 
316
>ammarkpos</CODE
 
317
> call overrides the
 
318
   previously marked position.  An access method that does not support
 
319
   ordered scans should still provide mark and restore functions in
 
320
   <TT
 
321
CLASS="STRUCTNAME"
 
322
>pg_am</TT
 
323
>, but it is sufficient to have them throw errors if
 
324
   called.
 
325
  </P
 
326
><P
 
327
>   Both the scan position and the mark position (if any) must be maintained
 
328
   consistently in the face of concurrent insertions or deletions in the
 
329
   index.  It is OK if a freshly-inserted entry is not returned by a scan that
 
330
   would have found the entry if it had existed when the scan started, or for
 
331
   the scan to return such an entry upon rescanning or backing
 
332
   up even though it had not been returned the first time through.  Similarly,
 
333
   a concurrent delete might or might not be reflected in the results of a scan.
 
334
   What is important is that insertions or deletions not cause the scan to
 
335
   miss or multiply return entries that were not themselves being inserted or
 
336
   deleted.
 
337
  </P
 
338
><P
 
339
>   Instead of using <CODE
 
340
CLASS="FUNCTION"
 
341
>amgettuple</CODE
 
342
>, an index scan can be done with
 
343
   <CODE
 
344
CLASS="FUNCTION"
 
345
>amgetbitmap</CODE
 
346
> to fetch all tuples in one call.  This can be
 
347
   noticeably more efficient than <CODE
 
348
CLASS="FUNCTION"
 
349
>amgettuple</CODE
 
350
> because it allows
 
351
   avoiding lock/unlock cycles within the access method.  In principle
 
352
   <CODE
 
353
CLASS="FUNCTION"
 
354
>amgetbitmap</CODE
 
355
> should have the same effects as repeated
 
356
   <CODE
 
357
CLASS="FUNCTION"
 
358
>amgettuple</CODE
 
359
> calls, but we impose several restrictions to
 
360
   simplify matters.  First of all, <CODE
 
361
CLASS="FUNCTION"
 
362
>amgetbitmap</CODE
 
363
> returns all
 
364
   tuples at once and marking or restoring scan positions isn't
 
365
   supported. Secondly, the tuples are returned in a bitmap which doesn't
 
366
   have any specific ordering, which is why <CODE
 
367
CLASS="FUNCTION"
 
368
>amgetbitmap</CODE
 
369
> doesn't
 
370
   take a <TT
 
371
CLASS="LITERAL"
 
372
>direction</TT
 
373
> argument.  (Ordering operators will never be
 
374
   supplied for such a scan, either.)  Finally, <CODE
 
375
CLASS="FUNCTION"
 
376
>amgetbitmap</CODE
 
377
>
 
378
   does not guarantee any locking of the returned tuples, with implications
 
379
   spelled out in <A
 
380
HREF="index-locking.html"
 
381
>Section 52.4</A
 
382
>.
 
383
  </P
 
384
><P
 
385
>   Note that it is permitted for an access method to implement only
 
386
   <CODE
 
387
CLASS="FUNCTION"
 
388
>amgetbitmap</CODE
 
389
> and not <CODE
 
390
CLASS="FUNCTION"
 
391
>amgettuple</CODE
 
392
>, or vice versa,
 
393
   if its internal implementation is unsuited to one API or the other.
 
394
  </P
 
395
></DIV
 
396
><DIV
 
397
CLASS="NAVFOOTER"
 
398
><HR
 
399
ALIGN="LEFT"
 
400
WIDTH="100%"><TABLE
 
401
SUMMARY="Footer navigation table"
 
402
WIDTH="100%"
 
403
BORDER="0"
 
404
CELLPADDING="0"
 
405
CELLSPACING="0"
 
406
><TR
 
407
><TD
 
408
WIDTH="33%"
 
409
ALIGN="left"
 
410
VALIGN="top"
 
411
><A
 
412
HREF="index-functions.html"
 
413
ACCESSKEY="P"
 
414
>Prev</A
 
415
></TD
 
416
><TD
 
417
WIDTH="34%"
 
418
ALIGN="center"
 
419
VALIGN="top"
 
420
><A
 
421
HREF="index.html"
 
422
ACCESSKEY="H"
 
423
>Home</A
 
424
></TD
 
425
><TD
 
426
WIDTH="33%"
 
427
ALIGN="right"
 
428
VALIGN="top"
 
429
><A
 
430
HREF="index-locking.html"
 
431
ACCESSKEY="N"
 
432
>Next</A
 
433
></TD
 
434
></TR
 
435
><TR
 
436
><TD
 
437
WIDTH="33%"
 
438
ALIGN="left"
 
439
VALIGN="top"
 
440
>Index Access Method Functions</TD
 
441
><TD
 
442
WIDTH="34%"
 
443
ALIGN="center"
 
444
VALIGN="top"
 
445
><A
 
446
HREF="indexam.html"
 
447
ACCESSKEY="U"
 
448
>Up</A
 
449
></TD
 
450
><TD
 
451
WIDTH="33%"
 
452
ALIGN="right"
 
453
VALIGN="top"
 
454
>Index Locking Considerations</TD
 
455
></TR
 
456
></TABLE
 
457
></DIV
 
458
></BODY
 
459
></HTML
 
460
>
 
 
b'\\ No newline at end of file'