Team Ai
Datasetpublic

codekingpro/portable-devtools

sourceHugging Faceupdated 5mo agoView on Hugging Face
1likes14kdownloads
btree-support-funcs.html291 linesDownload Raw Back to html
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.3. B-Tree Support Functions</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-behavior.html" title="67.2. Behavior of B-Tree Operator Classes" /><link rel="next" href="btree-implementation.html" title="67.4. Implementation" /></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.3. B-Tree Support Functions</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="btree-behavior.html" title="67.2. Behavior of B-Tree Operator Classes">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-implementation.html" title="67.4. Implementation">Next</a></td></tr></table><hr /></div><div class="sect1" id="BTREE-SUPPORT-FUNCS"><div class="titlepage"><div><div><h2 class="title" style="clear: both">67.3. B-Tree Support Functions <a href="#BTREE-SUPPORT-FUNCS" class="id_link">#</a></h2></div></div></div><p>3  As shown in <a class="xref" href="xindex.html#XINDEX-BTREE-SUPPORT-TABLE" title="Table 38.9. B-Tree Support Functions">Table 38.9</a>, btree defines4  one required and four optional support functions.  The five5  user-defined methods are:6 </p><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="function">order</code></span></dt><dd><p>7     For each combination of data types that a btree operator family8     provides comparison operators for, it must provide a comparison9     support function, registered in10     <code class="structname">pg_amproc</code> with support function number 111     and12     <code class="structfield">amproclefttype</code>/<code class="structfield">amprocrighttype</code>13     equal to the left and right data types for the comparison (i.e.,14     the same data types that the matching operators are registered15     with in <code class="structname">pg_amop</code>).  The comparison16     function must take two non-null values17     <em class="replaceable"><code>A</code></em> and <em class="replaceable"><code>B</code></em> and18     return an <code class="type">int32</code> value that is19     <code class="literal">&lt;</code> <code class="literal">0</code>,20     <code class="literal">0</code>, or <code class="literal">&gt;</code>21     <code class="literal">0</code> when <em class="replaceable"><code>A</code></em>22     <code class="literal">&lt;</code> <em class="replaceable"><code>B</code></em>,23     <em class="replaceable"><code>A</code></em> <code class="literal">=</code>24     <em class="replaceable"><code>B</code></em>, or <em class="replaceable"><code>A</code></em>25     <code class="literal">&gt;</code> <em class="replaceable"><code>B</code></em>,26     respectively.  A null result is disallowed: all values of the27     data type must be comparable.  See28     <code class="filename">src/backend/access/nbtree/nbtcompare.c</code> for29     examples.30    </p><p>31     If the compared values are of a collatable data type, the32     appropriate collation OID will be passed to the comparison33     support function, using the standard34     <code class="function">PG_GET_COLLATION()</code> mechanism.35    </p></dd><dt><span class="term"><code class="function">sortsupport</code></span></dt><dd><p>36     Optionally, a btree operator family may provide <em class="firstterm">sort37      support</em> function(s), registered under support38     function number 2.  These functions allow implementing39     comparisons for sorting purposes in a more efficient way than40     naively calling the comparison support function.  The APIs41     involved in this are defined in42     <code class="filename">src/include/utils/sortsupport.h</code>.43    </p></dd><dt><span class="term"><code class="function">in_range</code></span></dt><dd><a id="id-1.10.18.5.3.3.2.1" class="indexterm"></a><a id="id-1.10.18.5.3.3.2.2" class="indexterm"></a><p>44     Optionally, a btree operator family may provide45     <em class="firstterm">in_range</em> support function(s), registered46     under support function number 3.  These are not used during btree47     index operations; rather, they extend the semantics of the48     operator family so that it can support window clauses containing49     the <code class="literal">RANGE</code> <em class="replaceable"><code>offset</code></em>50     <code class="literal">PRECEDING</code> and <code class="literal">RANGE</code>51     <em class="replaceable"><code>offset</code></em> <code class="literal">FOLLOWING</code>52     frame bound types (see <a class="xref" href="sql-expressions.html#SYNTAX-WINDOW-FUNCTIONS" title="4.2.8. Window Function Calls">Section 4.2.8</a>).  Fundamentally, the extra53     information provided is how to add or subtract an54     <em class="replaceable"><code>offset</code></em> value in a way that is55     compatible with the family's data ordering.56    </p><p>57     An <code class="function">in_range</code> function must have the signature58</p><pre class="synopsis">59in_range(<em class="replaceable"><code>val</code></em> type1, <em class="replaceable"><code>base</code></em> type1, <em class="replaceable"><code>offset</code></em> type2, <em class="replaceable"><code>sub</code></em> bool, <em class="replaceable"><code>less</code></em> bool)60returns bool61</pre><p>62     <em class="replaceable"><code>val</code></em> and63     <em class="replaceable"><code>base</code></em> must be of the same type, which64     is one of the types supported by the operator family (i.e., a65     type for which it provides an ordering).  However,66     <em class="replaceable"><code>offset</code></em> could be of a different type,67     which might be one otherwise unsupported by the family.  An68     example is that the built-in <code class="literal">time_ops</code> family69     provides an <code class="function">in_range</code> function that has70     <em class="replaceable"><code>offset</code></em> of type <code class="type">interval</code>.71     A family can provide <code class="function">in_range</code> functions for72     any of its supported types and one or more73     <em class="replaceable"><code>offset</code></em> types.  Each74     <code class="function">in_range</code> function should be entered in75     <code class="structname">pg_amproc</code> with76     <code class="structfield">amproclefttype</code> equal to77     <code class="type">type1</code> and <code class="structfield">amprocrighttype</code>78     equal to <code class="type">type2</code>.79    </p><p>80     The essential semantics of an <code class="function">in_range</code>81     function depend on the two Boolean flag parameters.  It should82     add or subtract <em class="replaceable"><code>base</code></em> and83     <em class="replaceable"><code>offset</code></em>, then compare84     <em class="replaceable"><code>val</code></em> to the result, as follows:85     </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>86        if <code class="literal">!</code><em class="replaceable"><code>sub</code></em> and87        <code class="literal">!</code><em class="replaceable"><code>less</code></em>, return88        <em class="replaceable"><code>val</code></em> <code class="literal">&gt;=</code>89        (<em class="replaceable"><code>base</code></em> <code class="literal">+</code>90        <em class="replaceable"><code>offset</code></em>)91       </p></li><li class="listitem"><p>92        if <code class="literal">!</code><em class="replaceable"><code>sub</code></em> and93        <em class="replaceable"><code>less</code></em>, return94        <em class="replaceable"><code>val</code></em> <code class="literal">&lt;=</code>95        (<em class="replaceable"><code>base</code></em> <code class="literal">+</code>96        <em class="replaceable"><code>offset</code></em>)97       </p></li><li class="listitem"><p>98        if <em class="replaceable"><code>sub</code></em> and99        <code class="literal">!</code><em class="replaceable"><code>less</code></em>, return100        <em class="replaceable"><code>val</code></em> <code class="literal">&gt;=</code>101        (<em class="replaceable"><code>base</code></em> <code class="literal">-</code>102        <em class="replaceable"><code>offset</code></em>)103       </p></li><li class="listitem"><p>104        if <em class="replaceable"><code>sub</code></em> and105        <em class="replaceable"><code>less</code></em>, return106        <em class="replaceable"><code>val</code></em> <code class="literal">&lt;=</code>107        (<em class="replaceable"><code>base</code></em> <code class="literal">-</code>108        <em class="replaceable"><code>offset</code></em>)109       </p></li></ul></div><p>110     Before doing so, the function should check the sign of111     <em class="replaceable"><code>offset</code></em>: if it is less than zero, raise112     error113     <code class="literal">ERRCODE_INVALID_PRECEDING_OR_FOLLOWING_SIZE</code>114     (22013) with error text like <span class="quote">“<span class="quote">invalid preceding or115      following size in window function</span>”</span>.  (This is required by116     the SQL standard, although nonstandard operator families might117     perhaps choose to ignore this restriction, since there seems to118     be little semantic necessity for it.) This requirement is119     delegated to the <code class="function">in_range</code> function so that120     the core code needn't understand what <span class="quote">“<span class="quote">less than121      zero</span>”</span> means for a particular data type.122    </p><p>123     An additional expectation is that <code class="function">in_range</code>124     functions should, if practical, avoid throwing an error if125     <em class="replaceable"><code>base</code></em> <code class="literal">+</code>126     <em class="replaceable"><code>offset</code></em> or127     <em class="replaceable"><code>base</code></em> <code class="literal">-</code>128     <em class="replaceable"><code>offset</code></em> would overflow.  The correct129     comparison result can be determined even if that value would be130     out of the data type's range.  Note that if the data type131     includes concepts such as <span class="quote">“<span class="quote">infinity</span>”</span> or132     <span class="quote">“<span class="quote">NaN</span>”</span>, extra care may be needed to ensure that133     <code class="function">in_range</code>'s results agree with the normal134     sort order of the operator family.135    </p><p>136     The results of the <code class="function">in_range</code> function must be137     consistent with the sort ordering imposed by the operator family.138     To be precise, given any fixed values of139     <em class="replaceable"><code>offset</code></em> and140     <em class="replaceable"><code>sub</code></em>, then:141     </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>142        If <code class="function">in_range</code> with143        <em class="replaceable"><code>less</code></em> = true is true for some144        <em class="replaceable"><code>val1</code></em> and145        <em class="replaceable"><code>base</code></em>, it must be true for every146        <em class="replaceable"><code>val2</code></em> <code class="literal">&lt;=</code>147        <em class="replaceable"><code>val1</code></em> with the same148        <em class="replaceable"><code>base</code></em>.149       </p></li><li class="listitem"><p>150        If <code class="function">in_range</code> with151        <em class="replaceable"><code>less</code></em> = true is false for some152        <em class="replaceable"><code>val1</code></em> and153        <em class="replaceable"><code>base</code></em>, it must be false for every154        <em class="replaceable"><code>val2</code></em> <code class="literal">&gt;=</code>155        <em class="replaceable"><code>val1</code></em> with the same156        <em class="replaceable"><code>base</code></em>.157       </p></li><li class="listitem"><p>158        If <code class="function">in_range</code> with159        <em class="replaceable"><code>less</code></em> = true is true for some160        <em class="replaceable"><code>val</code></em> and161        <em class="replaceable"><code>base1</code></em>, it must be true for every162        <em class="replaceable"><code>base2</code></em> <code class="literal">&gt;=</code>163        <em class="replaceable"><code>base1</code></em> with the same164        <em class="replaceable"><code>val</code></em>.165       </p></li><li class="listitem"><p>166        If <code class="function">in_range</code> with167        <em class="replaceable"><code>less</code></em> = true is false for some168        <em class="replaceable"><code>val</code></em> and169        <em class="replaceable"><code>base1</code></em>, it must be false for every170        <em class="replaceable"><code>base2</code></em> <code class="literal">&lt;=</code>171        <em class="replaceable"><code>base1</code></em> with the same172        <em class="replaceable"><code>val</code></em>.173       </p></li></ul></div><p>174     Analogous statements with inverted conditions hold when175     <em class="replaceable"><code>less</code></em> = false.176    </p><p>177     If the type being ordered (<code class="type">type1</code>) is collatable, the178     appropriate collation OID will be passed to the179     <code class="function">in_range</code> function, using the standard180     PG_GET_COLLATION() mechanism.181    </p><p>182     <code class="function">in_range</code> functions need not handle NULL183     inputs, and typically will be marked strict.184    </p></dd><dt><span class="term"><code class="function">equalimage</code></span></dt><dd><p>185     Optionally, a btree operator family may provide186     <code class="function">equalimage</code> (<span class="quote">“<span class="quote">equality implies image187      equality</span>”</span>) support functions, registered under support188     function number 4.  These functions allow the core code to189     determine when it is safe to apply the btree deduplication190     optimization.  Currently, <code class="function">equalimage</code>191     functions are only called when building or rebuilding an index.192    </p><p>193     An <code class="function">equalimage</code> function must have the194     signature195</p><pre class="synopsis">196equalimage(<em class="replaceable"><code>opcintype</code></em> <code class="type">oid</code>) returns bool197</pre><p>198     The return value is static information about an operator class199     and collation.  Returning <code class="literal">true</code> indicates that200     the <code class="function">order</code> function for the operator class is201     guaranteed to only return <code class="literal">0</code> (<span class="quote">“<span class="quote">arguments202      are equal</span>”</span>) when its <em class="replaceable"><code>A</code></em> and203     <em class="replaceable"><code>B</code></em> arguments are also interchangeable204     without any loss of semantic information.  Not registering an205     <code class="function">equalimage</code> function or returning206     <code class="literal">false</code> indicates that this condition cannot be207     assumed to hold.208    </p><p>209     The <em class="replaceable"><code>opcintype</code></em> argument is the210     <code class="literal"><code class="structname">pg_type</code>.oid</code> of the211     data type that the operator class indexes.  This is a convenience212     that allows reuse of the same underlying213     <code class="function">equalimage</code> function across operator classes.214     If <em class="replaceable"><code>opcintype</code></em> is a collatable data215     type, the appropriate collation OID will be passed to the216     <code class="function">equalimage</code> function, using the standard217     <code class="function">PG_GET_COLLATION()</code> mechanism.218    </p><p>219     As far as the operator class is concerned, returning220     <code class="literal">true</code> indicates that deduplication is safe (or221     safe for the collation whose OID was passed to its222     <code class="function">equalimage</code> function).  However, the core223     code will only deem deduplication safe for an index when224     <span class="emphasis"><em>every</em></span> indexed column uses an operator class225     that registers an <code class="function">equalimage</code> function, and226     each function actually returns <code class="literal">true</code> when227     called.228    </p><p>229     Image equality is <span class="emphasis"><em>almost</em></span> the same condition230     as simple bitwise equality.  There is one subtle difference: When231     indexing a varlena data type, the on-disk representation of two232     image equal datums may not be bitwise equal due to inconsistent233     application of <acronym class="acronym">TOAST</acronym> compression on input.234     Formally, when an operator class's235     <code class="function">equalimage</code> function returns236     <code class="literal">true</code>, it is safe to assume that the237     <code class="literal">datum_image_eq()</code> C function will always agree238     with the operator class's <code class="function">order</code> function239     (provided that the same collation OID is passed to both the240     <code class="function">equalimage</code> and <code class="function">order</code>241     functions).242    </p><p>243     The core code is fundamentally unable to deduce anything about244     the <span class="quote">“<span class="quote">equality implies image equality</span>”</span> status of an245     operator class within a multiple-data-type family based on246     details from other operator classes in the same family.  Also, it247     is not sensible for an operator family to register a cross-type248     <code class="function">equalimage</code> function, and attempting to do so249     will result in an error.  This is because <span class="quote">“<span class="quote">equality implies250      image equality</span>”</span> status does not just depend on251     sorting/equality semantics, which are more or less defined at the252     operator family level.  In general, the semantics that one253     particular data type implements must be considered separately.254    </p><p>255     The convention followed by the operator classes included with the256     core <span class="productname">PostgreSQL</span> distribution is to257     register a stock, generic <code class="function">equalimage</code>258     function.  Most operator classes register259     <code class="function">btequalimage()</code>, which indicates that260     deduplication is safe unconditionally.  Operator classes for261     collatable data types such as <code class="type">text</code> register262     <code class="function">btvarstrequalimage()</code>, which indicates that263     deduplication is safe with deterministic collations.  Best264     practice for third-party extensions is to register their own265     custom function to retain control.266    </p></dd><dt><span class="term"><code class="function">options</code></span></dt><dd><p>267     Optionally, a B-tree operator family may provide268     <code class="function">options</code> (<span class="quote">“<span class="quote">operator class specific269     options</span>”</span>) support functions, registered under support270     function number 5.  These functions define a set of user-visible271     parameters that control operator class behavior.272    </p><p>273     An <code class="function">options</code> support function must have the274     signature275</p><pre class="synopsis">276options(<em class="replaceable"><code>relopts</code></em> <code class="type">local_relopts *</code>) returns void277</pre><p>278     The function is passed a pointer to a <code class="structname">local_relopts</code>279     struct, which needs to be filled with a set of operator class280     specific options.  The options can be accessed from other support281     functions using the <code class="literal">PG_HAS_OPCLASS_OPTIONS()</code> and282     <code class="literal">PG_GET_OPCLASS_OPTIONS()</code> macros.283    </p><p>284     Currently, no B-Tree operator class has an <code class="function">options</code>285     support function.  B-tree doesn't allow flexible representation of keys286     like GiST, SP-GiST, GIN and BRIN do.  So, <code class="function">options</code>287     probably doesn't have much application in the current B-tree index288     access method.  Nevertheless, this support function was added to B-tree289     for uniformity, and will probably find uses during further290     evolution of B-tree in <span class="productname">PostgreSQL</span>.291    </p></dd></dl></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="btree-behavior.html" title="67.2. Behavior of B-Tree Operator Classes">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-implementation.html" title="67.4. Implementation">Next</a></td></tr><tr><td width="40%" align="left" valign="top">67.2. Behavior of B-Tree Operator Classes </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.4. Implementation</td></tr></table></div></body></html>
codekingpro/portable-devtools · Team Ai