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
|
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>67.2. Behavior of B-Tree Operator Classes</title><link rel="stylesheet" type="text/css" href="stylesheet.css" /><link rev="made" href="pgsql-docs@lists.postgresql.org" /><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><link rel="prev" href="btree-intro.html" title="67.1. Introduction" /><link rel="next" href="btree-support-funcs.html" title="67.3. B-Tree Support Functions" /></head><body id="docContent" class="container-fluid col-10"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">67.2. Behavior of B-Tree Operator Classes</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="btree-intro.html" title="67.1. Introduction">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="btree.html" title="Chapter 67. B-Tree Indexes">Up</a></td><th width="60%" align="center">Chapter 67. B-Tree Indexes</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 15.4 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="btree-support-funcs.html" title="67.3. B-Tree Support Functions">Next</a></td></tr></table><hr /></div><div class="sect1" id="BTREE-BEHAVIOR"><div class="titlepage"><div><div><h2 class="title" style="clear: both">67.2. Behavior of B-Tree Operator Classes</h2></div></div></div><p>
As shown in <a class="xref" href="xindex.html#XINDEX-BTREE-STRAT-TABLE" title="Table 38.3. B-Tree Strategies">Table 38.3</a>, a btree operator
class must provide five comparison operators,
<code class="literal"><</code>,
<code class="literal"><=</code>,
<code class="literal">=</code>,
<code class="literal">>=</code> and
<code class="literal">></code>.
One might expect that <code class="literal"><></code> should also be part of
the operator class, but it is not, because it would almost never be
useful to use a <code class="literal"><></code> WHERE clause in an index
search. (For some purposes, the planner treats <code class="literal"><></code>
as associated with a btree operator class; but it finds that operator via
the <code class="literal">=</code> operator's negator link, rather than
from <code class="structname">pg_amop</code>.)
</p><p>
When several data types share near-identical sorting semantics, their
operator classes can be grouped into an operator family. Doing so is
advantageous because it allows the planner to make deductions about
cross-type comparisons. Each operator class within the family should
contain the single-type operators (and associated support functions)
for its input data type, while cross-type comparison operators and
support functions are <span class="quote">“<span class="quote">loose</span>”</span> in the family. It is
recommendable that a complete set of cross-type operators be included
in the family, thus ensuring that the planner can represent any
comparison conditions that it deduces from transitivity.
</p><p>
There are some basic assumptions that a btree operator family must
satisfy:
</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>
An <code class="literal">=</code> operator must be an equivalence relation; that
is, for all non-null values <em class="replaceable"><code>A</code></em>,
<em class="replaceable"><code>B</code></em>, <em class="replaceable"><code>C</code></em> of the
data type:
</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p>
<em class="replaceable"><code>A</code></em> <code class="literal">=</code>
<em class="replaceable"><code>A</code></em> is true
(<em class="firstterm">reflexive law</em>)
</p></li><li class="listitem"><p>
if <em class="replaceable"><code>A</code></em> <code class="literal">=</code>
<em class="replaceable"><code>B</code></em>,
then <em class="replaceable"><code>B</code></em> <code class="literal">=</code>
<em class="replaceable"><code>A</code></em>
(<em class="firstterm">symmetric law</em>)
</p></li><li class="listitem"><p>
if <em class="replaceable"><code>A</code></em> <code class="literal">=</code>
<em class="replaceable"><code>B</code></em> and <em class="replaceable"><code>B</code></em>
<code class="literal">=</code> <em class="replaceable"><code>C</code></em>,
then <em class="replaceable"><code>A</code></em> <code class="literal">=</code>
<em class="replaceable"><code>C</code></em>
(<em class="firstterm">transitive law</em>)
</p></li></ul></div><p>
</p></li><li class="listitem"><p>
A <code class="literal"><</code> operator must be a strong ordering relation;
that is, for all non-null values <em class="replaceable"><code>A</code></em>,
<em class="replaceable"><code>B</code></em>, <em class="replaceable"><code>C</code></em>:
</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p>
<em class="replaceable"><code>A</code></em> <code class="literal"><</code>
<em class="replaceable"><code>A</code></em> is false
(<em class="firstterm">irreflexive law</em>)
</p></li><li class="listitem"><p>
if <em class="replaceable"><code>A</code></em> <code class="literal"><</code>
<em class="replaceable"><code>B</code></em>
and <em class="replaceable"><code>B</code></em> <code class="literal"><</code>
<em class="replaceable"><code>C</code></em>,
then <em class="replaceable"><code>A</code></em> <code class="literal"><</code>
<em class="replaceable"><code>C</code></em>
(<em class="firstterm">transitive law</em>)
</p></li></ul></div><p>
</p></li><li class="listitem"><p>
Furthermore, the ordering is total; that is, for all non-null
values <em class="replaceable"><code>A</code></em>, <em class="replaceable"><code>B</code></em>:
</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p>
exactly one of <em class="replaceable"><code>A</code></em> <code class="literal"><</code>
<em class="replaceable"><code>B</code></em>, <em class="replaceable"><code>A</code></em>
<code class="literal">=</code> <em class="replaceable"><code>B</code></em>, and
<em class="replaceable"><code>B</code></em> <code class="literal"><</code>
<em class="replaceable"><code>A</code></em> is true
(<em class="firstterm">trichotomy law</em>)
</p></li></ul></div><p>
(The trichotomy law justifies the definition of the comparison support
function, of course.)
</p></li></ul></div><p>
The other three operators are defined in terms of <code class="literal">=</code>
and <code class="literal"><</code> in the obvious way, and must act consistently
with them.
</p><p>
For an operator family supporting multiple data types, the above laws must
hold when <em class="replaceable"><code>A</code></em>, <em class="replaceable"><code>B</code></em>,
<em class="replaceable"><code>C</code></em> are taken from any data types in the family.
The transitive laws are the trickiest to ensure, as in cross-type
situations they represent statements that the behaviors of two or three
different operators are consistent.
As an example, it would not work to put <code class="type">float8</code>
and <code class="type">numeric</code> into the same operator family, at least not with
the current semantics that <code class="type">numeric</code> values are converted
to <code class="type">float8</code> for comparison to a <code class="type">float8</code>. Because
of the limited accuracy of <code class="type">float8</code>, this means there are
distinct <code class="type">numeric</code> values that will compare equal to the
same <code class="type">float8</code> value, and thus the transitive law would fail.
</p><p>
Another requirement for a multiple-data-type family is that any implicit
or binary-coercion casts that are defined between data types included in
the operator family must not change the associated sort ordering.
</p><p>
It should be fairly clear why a btree index requires these laws to hold
within a single data type: without them there is no ordering to arrange
the keys with. Also, index searches using a comparison key of a
different data type require comparisons to behave sanely across two
data types. The extensions to three or more data types within a family
are not strictly required by the btree index mechanism itself, but the
planner relies on them for optimization purposes.
</p></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="btree-intro.html" title="67.1. Introduction">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="btree.html" title="Chapter 67. B-Tree Indexes">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="btree-support-funcs.html" title="67.3. B-Tree Support Functions">Next</a></td></tr><tr><td width="40%" align="left" valign="top">67.1. Introduction </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 15.4 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 67.3. B-Tree Support Functions</td></tr></table></div></body></html>
|
