summaryrefslogtreecommitdiffstats
path: root/doc/src/sgml/html/btree-behavior.html
blob: ae71a0be343ecc0885761c26053bdeb8fe647b10 (plain)
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.6 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">&lt;</code>,
  <code class="literal">&lt;=</code>,
  <code class="literal">=</code>,
  <code class="literal">&gt;=</code> and
  <code class="literal">&gt;</code>.
  One might expect that <code class="literal">&lt;&gt;</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">&lt;&gt;</code> WHERE clause in an index
  search.  (For some purposes, the planner treats <code class="literal">&lt;&gt;</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">&lt;</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">&lt;</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">&lt;</code>
       <em class="replaceable"><code>B</code></em>
       and <em class="replaceable"><code>B</code></em> <code class="literal">&lt;</code>
       <em class="replaceable"><code>C</code></em>,
       then <em class="replaceable"><code>A</code></em> <code class="literal">&lt;</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">&lt;</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">&lt;</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">&lt;</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.6 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 67.3. B-Tree Support Functions</td></tr></table></div></body></html>