diff options
Diffstat (limited to 'doc/src/sgml/html/btree-behavior.html')
| -rw-r--r-- | doc/src/sgml/html/btree-behavior.html | 118 |
1 files changed, 118 insertions, 0 deletions
diff --git a/doc/src/sgml/html/btree-behavior.html b/doc/src/sgml/html/btree-behavior.html new file mode 100644 index 0000000..f6fb8dd --- /dev/null +++ b/doc/src/sgml/html/btree-behavior.html @@ -0,0 +1,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>
\ No newline at end of file |