codekingpro/portable-devtools

1<?xml version="1.0" encoding="UTF-8" standalone="no"?>2<!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 16.3 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 <a href="#BTREE-BEHAVIOR" class="id_link">#</a></h2></div></div></div><p>3  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 operator4  class must provide five comparison operators,5  <code class="literal">&lt;</code>,6  <code class="literal">&lt;=</code>,7  <code class="literal">=</code>,8  <code class="literal">&gt;=</code> and9  <code class="literal">&gt;</code>.10  One might expect that <code class="literal">&lt;&gt;</code> should also be part of11  the operator class, but it is not, because it would almost never be12  useful to use a <code class="literal">&lt;&gt;</code> WHERE clause in an index13  search.  (For some purposes, the planner treats <code class="literal">&lt;&gt;</code>14  as associated with a btree operator class; but it finds that operator via15  the <code class="literal">=</code> operator's negator link, rather than16  from <code class="structname">pg_amop</code>.)17 </p><p>18  When several data types share near-identical sorting semantics, their19  operator classes can be grouped into an operator family.  Doing so is20  advantageous because it allows the planner to make deductions about21  cross-type comparisons.  Each operator class within the family should22  contain the single-type operators (and associated support functions)23  for its input data type, while cross-type comparison operators and24  support functions are <span class="quote">“<span class="quote">loose</span>”</span> in the family.  It is25  recommendable that a complete set of cross-type operators be included26  in the family, thus ensuring that the planner can represent any27  comparison conditions that it deduces from transitivity.28 </p><p>29  There are some basic assumptions that a btree operator family must30  satisfy:31 </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>32    An <code class="literal">=</code> operator must be an equivalence relation; that33    is, for all non-null values <em class="replaceable"><code>A</code></em>,34    <em class="replaceable"><code>B</code></em>, <em class="replaceable"><code>C</code></em> of the35    data type:36 37    </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p>38       <em class="replaceable"><code>A</code></em> <code class="literal">=</code>39       <em class="replaceable"><code>A</code></em> is true40       (<em class="firstterm">reflexive law</em>)41      </p></li><li class="listitem"><p>42       if <em class="replaceable"><code>A</code></em> <code class="literal">=</code>43       <em class="replaceable"><code>B</code></em>,44       then <em class="replaceable"><code>B</code></em> <code class="literal">=</code>45       <em class="replaceable"><code>A</code></em>46       (<em class="firstterm">symmetric law</em>)47      </p></li><li class="listitem"><p>48       if <em class="replaceable"><code>A</code></em> <code class="literal">=</code>49       <em class="replaceable"><code>B</code></em> and <em class="replaceable"><code>B</code></em>50       <code class="literal">=</code> <em class="replaceable"><code>C</code></em>,51       then <em class="replaceable"><code>A</code></em> <code class="literal">=</code>52       <em class="replaceable"><code>C</code></em>53       (<em class="firstterm">transitive law</em>)54      </p></li></ul></div><p>55   </p></li><li class="listitem"><p>56    A <code class="literal">&lt;</code> operator must be a strong ordering relation;57    that is, for all non-null values <em class="replaceable"><code>A</code></em>,58    <em class="replaceable"><code>B</code></em>, <em class="replaceable"><code>C</code></em>:59 60    </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p>61       <em class="replaceable"><code>A</code></em> <code class="literal">&lt;</code>62       <em class="replaceable"><code>A</code></em> is false63       (<em class="firstterm">irreflexive law</em>)64      </p></li><li class="listitem"><p>65       if <em class="replaceable"><code>A</code></em> <code class="literal">&lt;</code>66       <em class="replaceable"><code>B</code></em>67       and <em class="replaceable"><code>B</code></em> <code class="literal">&lt;</code>68       <em class="replaceable"><code>C</code></em>,69       then <em class="replaceable"><code>A</code></em> <code class="literal">&lt;</code>70       <em class="replaceable"><code>C</code></em>71       (<em class="firstterm">transitive law</em>)72      </p></li></ul></div><p>73   </p></li><li class="listitem"><p>74    Furthermore, the ordering is total; that is, for all non-null75    values <em class="replaceable"><code>A</code></em>, <em class="replaceable"><code>B</code></em>:76 77    </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p>78       exactly one of <em class="replaceable"><code>A</code></em> <code class="literal">&lt;</code>79       <em class="replaceable"><code>B</code></em>, <em class="replaceable"><code>A</code></em>80       <code class="literal">=</code> <em class="replaceable"><code>B</code></em>, and81       <em class="replaceable"><code>B</code></em> <code class="literal">&lt;</code>82       <em class="replaceable"><code>A</code></em> is true83       (<em class="firstterm">trichotomy law</em>)84      </p></li></ul></div><p>85 86    (The trichotomy law justifies the definition of the comparison support87    function, of course.)88   </p></li></ul></div><p>89  The other three operators are defined in terms of <code class="literal">=</code>90  and <code class="literal">&lt;</code> in the obvious way, and must act consistently91  with them.92 </p><p>93  For an operator family supporting multiple data types, the above laws must94  hold when <em class="replaceable"><code>A</code></em>, <em class="replaceable"><code>B</code></em>,95  <em class="replaceable"><code>C</code></em> are taken from any data types in the family.96  The transitive laws are the trickiest to ensure, as in cross-type97  situations they represent statements that the behaviors of two or three98  different operators are consistent.99  As an example, it would not work to put <code class="type">float8</code>100  and <code class="type">numeric</code> into the same operator family, at least not with101  the current semantics that <code class="type">numeric</code> values are converted102  to <code class="type">float8</code> for comparison to a <code class="type">float8</code>.  Because103  of the limited accuracy of <code class="type">float8</code>, this means there are104  distinct <code class="type">numeric</code> values that will compare equal to the105  same <code class="type">float8</code> value, and thus the transitive law would fail.106 </p><p>107  Another requirement for a multiple-data-type family is that any implicit108  or binary-coercion casts that are defined between data types included in109  the operator family must not change the associated sort ordering.110 </p><p>111  It should be fairly clear why a btree index requires these laws to hold112  within a single data type: without them there is no ordering to arrange113  the keys with.  Also, index searches using a comparison key of a114  different data type require comparisons to behave sanely across two115  data types.  The extensions to three or more data types within a family116  are not strictly required by the btree index mechanism itself, but the117  planner relies on them for optimization purposes.118 </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 16.3 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 67.3. B-Tree Support Functions</td></tr></table></div></body></html>