1/*-------------------------------------------------------------------------
4 * Support routines for B-Tree skip scan.
6 * B-Tree operator classes for discrete types can optionally provide a support
7 * function for skipping. This is used during skip scans.
9 * A B-tree operator class that implements skip support provides B-tree index
10 * scans with a way of enumerating and iterating through every possible value
11 * from the domain of indexable values. This gives scans a way to determine
12 * the next value in line for a given skip array/scan key/skipped attribute.
13 * Scans request the next (or previous) value whenever they run out of tuples
14 * matching the skip array's current element value. The next (or previous)
15 * value can be used to relocate the scan; it is applied in combination with
16 * at least one additional lower-order non-skip key, taken from the query.
18 * Skip support is used by discrete type (e.g., integer and date) opclasses.
19 * Indexes with an attribute whose input opclass is of one of these types tend
20 * to store adjacent values in adjoining groups of index tuples. Each time a
21 * skip scan with skip support successfully guesses that the next value in the
22 * index (for a given skipped column) is indeed the value that skip support
23 * just incremented its skip array to, it will have saved the scan some work.
24 * The scan will have avoided an index probe that directly finds the next
25 * value that appears in the index. (When skip support guesses wrong, then it
26 * won't have saved any work, but it also won't have added any useless work.
27 * The failed attempt to locate exactly-matching index tuples acts just like
28 * an explicit probe would; it'll still find the index's true next value.)
30 * It usually isn't feasible to implement skip support for an opclass whose
31 * input type is continuous. The B-Tree code falls back on next-key sentinel
32 * values for any opclass that doesn't provide its own skip support function.
33 * This isn't really an implementation restriction; there is no benefit to
34 * providing skip support for an opclass where guessing that the next indexed
35 * value is the next possible indexable value never (or hardly ever) works out.
38 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
39 * Portions Copyright (c) 1994, Regents of the University of California
41 * src/include/utils/skipsupport.h
43 *-------------------------------------------------------------------------
56 * State/callbacks used by skip arrays to procedurally generate elements.
58 * A BTSKIPSUPPORT_PROC function must set each and every field when called
59 * (there are no optional fields).
64 * low_elem and high_elem must be set with the lowest and highest possible
65 * values from the domain of indexable values (assuming ascending order)
71 * Decrement/increment functions.
73 * Returns a decremented/incremented copy of caller's existing datum,
74 * allocated in caller's memory context (for pass-by-reference types).
75 * It's not okay for these functions to leak any memory.
77 * When the decrement function (or increment function) is called with a
78 * value that already matches low_elem (or high_elem), function must set
79 * the *overflow argument. The return value is treated as undefined by
80 * the B-Tree code; it shouldn't need to be (and won't be) pfree'd.
82 * The B-Tree code's "existing" datum argument is often just a straight
83 * copy of a value from an index tuple. Operator classes must accept
84 * every possible representational variation within the underlying type.
85 * On the other hand, opclasses are _not_ required to preserve information
86 * that doesn't affect how datums are sorted (e.g., skip support for a
87 * fixed precision numeric type needn't preserve datum display scale).
88 * Operator class decrement/increment functions will never be called with
89 * a NULL "existing" argument, either.
98#endif /* SKIPSUPPORT_H */
SkipSupport PrepareSkipSupportFromOpclass(Oid opfamily, Oid opcintype, bool reverse)
Datum(* SkipSupportIncDec)(Relation rel, Datum existing, bool *overflow)
struct SkipSupportData SkipSupportData
struct SkipSupportData * SkipSupport
SkipSupportIncDec decrement
SkipSupportIncDec increment