doc/src/sgml/ltree.sgml

   1 <!-- doc/src/sgml/ltree.sgml -->
   2
   3 <sect1 id="ltree" xreflabel="ltree">
   4  <title>ltree &mdash; hierarchical tree-like data type</title>
   5
   6  <indexterm zone="ltree">
   7   <primary>ltree</primary>
   8  </indexterm>
   9
  10  <para>
  11   This module implements a data type <type>ltree</type> for representing
  12   labels of data stored in a hierarchical tree-like structure.
  13   Extensive facilities for searching through label trees are provided.
  14  </para>
  15
  16  <para>
  17   This module is considered <quote>trusted</quote>, that is, it can be
  18   installed by non-superusers who have <literal>CREATE</literal> privilege
  19   on the current database.
  20  </para>
  21
  22  <sect2 id="ltree-definitions">
  23   <title>Definitions</title>
  24
  25   <para>
  26    A <firstterm>label</firstterm> is a sequence of alphanumeric characters,
  27    underscores, and hyphens. Valid alphanumeric character ranges are
  28    dependent on the database locale. For example, in C locale, the characters
  29    <literal>A-Za-z0-9_-</literal> are allowed.
  30    Labels must be no more than 1000 characters long.
  31   </para>
  32
  33   <para>
  34    Examples: <literal>42</literal>, <literal>Personal_Services</literal>
  35   </para>
  36
  37   <para>
  38    A <firstterm>label path</firstterm> is a sequence of zero or more
  39    labels separated by dots, for example <literal>L1.L2.L3</literal>, representing
  40    a path from the root of a hierarchical tree to a particular node.  The
  41    length of a label path cannot exceed 65535 labels.
  42   </para>
  43
  44   <para>
  45    Example: <literal>Top.Countries.Europe.Russia</literal>
  46   </para>
  47
  48   <para>
  49    The <filename>ltree</filename> module provides several data types:
  50   </para>
  51
  52   <itemizedlist>
  53    <listitem>
  54     <para>
  55      <type>ltree</type> stores a label path.
  56     </para>
  57    </listitem>
  58
  59    <listitem>
  60     <para>
  61      <type>lquery</type> represents a regular-expression-like pattern
  62      for matching <type>ltree</type> values.  A simple word matches that
  63      label within a path.  A star symbol (<literal>*</literal>) matches zero
  64      or more labels.  These can be joined with dots to form a pattern that
  65      must match the whole label path.  For example:
  66 <synopsis>
  67 foo         <lineannotation>Match the exact label path <literal>foo</literal></lineannotation>
  68 *.foo.*     <lineannotation>Match any label path containing the label <literal>foo</literal></lineannotation>
  69 *.foo       <lineannotation>Match any label path whose last label is <literal>foo</literal></lineannotation>
  70 </synopsis>
  71     </para>
  72
  73     <para>
  74      Both star symbols and simple words can be quantified to restrict how many
  75      labels they can match:
  76 <synopsis>
  77 *{<replaceable>n</replaceable>}        <lineannotation>Match exactly <replaceable>n</replaceable> labels</lineannotation>
  78 *{<replaceable>n</replaceable>,}       <lineannotation>Match at least <replaceable>n</replaceable> labels</lineannotation>
  79 *{<replaceable>n</replaceable>,<replaceable>m</replaceable>}      <lineannotation>Match at least <replaceable>n</replaceable> but not more than <replaceable>m</replaceable> labels</lineannotation>
  80 *{,<replaceable>m</replaceable>}       <lineannotation>Match at most <replaceable>m</replaceable> labels &mdash; same as </lineannotation>*{0,<replaceable>m</replaceable>}
  81 foo{<replaceable>n</replaceable>,<replaceable>m</replaceable>}    <lineannotation>Match at least <replaceable>n</replaceable> but not more than <replaceable>m</replaceable> occurrences of <literal>foo</literal></lineannotation>
  82 foo{,}      <lineannotation>Match any number of occurrences of <literal>foo</literal>, including zero</lineannotation>
  83 </synopsis>
  84      In the absence of any explicit quantifier, the default for a star symbol
  85      is to match any number of labels (that is, <literal>{,}</literal>) while
  86      the default for a non-star item is to match exactly once (that
  87      is, <literal>{1}</literal>).
  88     </para>
  89
  90     <para>
  91      There are several modifiers that can be put at the end of a non-star
  92      <type>lquery</type> item to make it match more than just the exact match:
  93 <synopsis>
  94 @           <lineannotation>Match case-insensitively, for example <literal>a@</literal> matches <literal>A</literal></lineannotation>
  95 *           <lineannotation>Match any label with this prefix, for example <literal>foo*</literal> matches <literal>foobar</literal></lineannotation>
  96 %           <lineannotation>Match initial underscore-separated words</lineannotation>
  97 </synopsis>
  98      The behavior of <literal>%</literal> is a bit complicated.  It tries to match
  99      words rather than the entire label.  For example
 100      <literal>foo_bar%</literal> matches <literal>foo_bar_baz</literal> but not
 101      <literal>foo_barbaz</literal>.  If combined with <literal>*</literal>, prefix
 102      matching applies to each word separately, for example
 103      <literal>foo_bar%*</literal> matches <literal>foo1_bar2_baz</literal> but
 104      not <literal>foo1_br2_baz</literal>.
 105     </para>
 106
 107     <para>
 108      Also, you can write several possibly-modified non-star items separated with
 109      <literal>|</literal> (OR) to match any of those items, and you can put
 110      <literal>!</literal> (NOT) at the start of a non-star group to match any
 111      label that doesn't match any of the alternatives.  A quantifier, if any,
 112      goes at the end of the group; it means some number of matches for the
 113      group as a whole (that is, some number of labels matching or not matching
 114      any of the alternatives).
 115     </para>
 116
 117     <para>
 118      Here's an annotated example of <type>lquery</type>:
 119 <programlisting>
 120 Top.*{0,2}.sport*@.!football|tennis{1,}.Russ*|Spain
 121 a.  b.     c.      d.                   e.
 122 </programlisting>
 123      This query will match any label path that:
 124     </para>
 125     <orderedlist numeration="loweralpha">
 126      <listitem>
 127       <para>
 128        begins with the label <literal>Top</literal>
 129       </para>
 130      </listitem>
 131      <listitem>
 132       <para>
 133        and next has zero to two labels before
 134       </para>
 135      </listitem>
 136      <listitem>
 137       <para>
 138        a label beginning with the case-insensitive prefix <literal>sport</literal>
 139       </para>
 140      </listitem>
 141      <listitem>
 142       <para>
 143        then has one or more labels, none of which
 144        match <literal>football</literal> nor <literal>tennis</literal>
 145       </para>
 146      </listitem>
 147      <listitem>
 148       <para>
 149        and then ends with a label beginning with <literal>Russ</literal> or
 150        exactly matching <literal>Spain</literal>.
 151       </para>
 152      </listitem>
 153     </orderedlist>
 154    </listitem>
 155
 156    <listitem>
 157     <para><type>ltxtquery</type> represents a full-text-search-like
 158     pattern for matching <type>ltree</type> values.  An
 159     <type>ltxtquery</type> value contains words, possibly with the
 160     modifiers <literal>@</literal>, <literal>*</literal>, <literal>%</literal> at the end;
 161     the modifiers have the same meanings as in <type>lquery</type>.
 162     Words can be combined with <literal>&amp;</literal> (AND),
 163     <literal>|</literal> (OR), <literal>!</literal> (NOT), and parentheses.
 164     The key difference from
 165     <type>lquery</type> is that <type>ltxtquery</type> matches words without
 166     regard to their position in the label path.
 167     </para>
 168
 169     <para>
 170      Here's an example <type>ltxtquery</type>:
 171 <programlisting>
 172 Europe &amp; Russia*@ &amp; !Transportation
 173 </programlisting>
 174      This will match paths that contain the label <literal>Europe</literal> and
 175      any label beginning with <literal>Russia</literal> (case-insensitive),
 176      but not paths containing the label <literal>Transportation</literal>.
 177      The location of these words within the path is not important.
 178      Also, when <literal>%</literal> is used, the word can be matched to any
 179      underscore-separated word within a label, regardless of position.
 180     </para>
 181    </listitem>
 182
 183   </itemizedlist>
 184
 185   <para>
 186    Note: <type>ltxtquery</type> allows whitespace between symbols, but
 187    <type>ltree</type> and <type>lquery</type> do not.
 188   </para>
 189  </sect2>
 190
 191  <sect2 id="ltree-ops-funcs">
 192   <title>Operators and Functions</title>
 193
 194   <para>
 195    Type <type>ltree</type> has the usual comparison operators
 196    <literal>=</literal>, <literal>&lt;&gt;</literal>,
 197    <literal>&lt;</literal>, <literal>&gt;</literal>, <literal>&lt;=</literal>, <literal>&gt;=</literal>.
 198    Comparison sorts in the order of a tree traversal, with the children
 199    of a node sorted by label text.  In addition, the specialized
 200    operators shown in <xref linkend="ltree-op-table"/> are available.
 201   </para>
 202
 203   <table id="ltree-op-table">
 204    <title><type>ltree</type> Operators</title>
 205     <tgroup cols="1">
 206      <thead>
 207       <row>
 208        <entry role="func_table_entry"><para role="func_signature">
 209         Operator
 210        </para>
 211        <para>
 212         Description
 213        </para></entry>
 214       </row>
 215      </thead>
 216
 217      <tbody>
 218       <row>
 219        <entry role="func_table_entry"><para role="func_signature">
 220         <type>ltree</type> <literal>@&gt;</literal> <type>ltree</type>
 221         <returnvalue>boolean</returnvalue>
 222        </para>
 223        <para>
 224         Is left argument an ancestor of right (or equal)?
 225        </para></entry>
 226       </row>
 227
 228       <row>
 229        <entry role="func_table_entry"><para role="func_signature">
 230         <type>ltree</type> <literal>&lt;@</literal> <type>ltree</type>
 231         <returnvalue>boolean</returnvalue>
 232        </para>
 233        <para>
 234         Is left argument a descendant of right (or equal)?
 235        </para></entry>
 236       </row>
 237
 238       <row>
 239        <entry role="func_table_entry"><para role="func_signature">
 240         <type>ltree</type> <literal>~</literal> <type>lquery</type>
 241         <returnvalue>boolean</returnvalue>
 242        </para>
 243        <para role="func_signature">
 244         <type>lquery</type> <literal>~</literal> <type>ltree</type>
 245         <returnvalue>boolean</returnvalue>
 246        </para>
 247        <para>
 248         Does <type>ltree</type> match <type>lquery</type>?
 249        </para></entry>
 250       </row>
 251
 252       <row>
 253        <entry role="func_table_entry"><para role="func_signature">
 254         <type>ltree</type> <literal>?</literal> <type>lquery[]</type>
 255         <returnvalue>boolean</returnvalue>
 256        </para>
 257        <para role="func_signature">
 258         <type>lquery[]</type> <literal>?</literal> <type>ltree</type>
 259         <returnvalue>boolean</returnvalue>
 260        </para>
 261        <para>
 262         Does <type>ltree</type> match any <type>lquery</type> in array?
 263        </para></entry>
 264       </row>
 265
 266       <row>
 267        <entry role="func_table_entry"><para role="func_signature">
 268         <type>ltree</type> <literal>@</literal> <type>ltxtquery</type>
 269         <returnvalue>boolean</returnvalue>
 270        </para>
 271        <para role="func_signature">
 272         <type>ltxtquery</type> <literal>@</literal> <type>ltree</type>
 273         <returnvalue>boolean</returnvalue>
 274        </para>
 275        <para>
 276         Does <type>ltree</type> match <type>ltxtquery</type>?
 277        </para></entry>
 278       </row>
 279
 280       <row>
 281        <entry role="func_table_entry"><para role="func_signature">
 282         <type>ltree</type> <literal>||</literal> <type>ltree</type>
 283         <returnvalue>ltree</returnvalue>
 284        </para>
 285        <para>
 286         Concatenates <type>ltree</type> paths.
 287        </para></entry>
 288       </row>
 289
 290       <row>
 291        <entry role="func_table_entry"><para role="func_signature">
 292         <type>ltree</type> <literal>||</literal> <type>text</type>
 293         <returnvalue>ltree</returnvalue>
 294        </para>
 295        <para role="func_signature">
 296         <type>text</type> <literal>||</literal> <type>ltree</type>
 297         <returnvalue>ltree</returnvalue>
 298        </para>
 299        <para>
 300         Converts text to <type>ltree</type> and concatenates.
 301        </para></entry>
 302       </row>
 303
 304       <row>
 305        <entry role="func_table_entry"><para role="func_signature">
 306         <type>ltree[]</type> <literal>@&gt;</literal> <type>ltree</type>
 307         <returnvalue>boolean</returnvalue>
 308        </para>
 309        <para role="func_signature">
 310         <type>ltree</type> <literal>&lt;@</literal> <type>ltree[]</type>
 311         <returnvalue>boolean</returnvalue>
 312        </para>
 313        <para>
 314         Does array contain an ancestor of <type>ltree</type>?
 315        </para></entry>
 316       </row>
 317
 318       <row>
 319        <entry role="func_table_entry"><para role="func_signature">
 320         <type>ltree[]</type> <literal>&lt;@</literal> <type>ltree</type>
 321         <returnvalue>boolean</returnvalue>
 322        </para>
 323        <para role="func_signature">
 324         <type>ltree</type> <literal>@&gt;</literal> <type>ltree[]</type>
 325         <returnvalue>boolean</returnvalue>
 326        </para>
 327        <para>
 328         Does array contain a descendant of <type>ltree</type>?
 329        </para></entry>
 330       </row>
 331
 332       <row>
 333        <entry role="func_table_entry"><para role="func_signature">
 334         <type>ltree[]</type> <literal>~</literal> <type>lquery</type>
 335         <returnvalue>boolean</returnvalue>
 336        </para>
 337        <para role="func_signature">
 338         <type>lquery</type> <literal>~</literal> <type>ltree[]</type>
 339         <returnvalue>boolean</returnvalue>
 340        </para>
 341        <para>
 342         Does array contain any path matching <type>lquery</type>?
 343        </para></entry>
 344       </row>
 345
 346       <row>
 347        <entry role="func_table_entry"><para role="func_signature">
 348         <type>ltree[]</type> <literal>?</literal> <type>lquery[]</type>
 349         <returnvalue>boolean</returnvalue>
 350        </para>
 351        <para role="func_signature">
 352         <type>lquery[]</type> <literal>?</literal> <type>ltree[]</type>
 353         <returnvalue>boolean</returnvalue>
 354        </para>
 355        <para>
 356         Does <type>ltree</type> array contain any path matching
 357         any <type>lquery</type>?
 358        </para></entry>
 359       </row>
 360
 361       <row>
 362        <entry role="func_table_entry"><para role="func_signature">
 363         <type>ltree[]</type> <literal>@</literal> <type>ltxtquery</type>
 364         <returnvalue>boolean</returnvalue>
 365        </para>
 366        <para role="func_signature">
 367         <type>ltxtquery</type> <literal>@</literal> <type>ltree[]</type>
 368         <returnvalue>boolean</returnvalue>
 369        </para>
 370        <para>
 371         Does array contain any path matching <type>ltxtquery</type>?
 372        </para></entry>
 373       </row>
 374
 375       <row>
 376        <entry role="func_table_entry"><para role="func_signature">
 377         <type>ltree[]</type> <literal>?@&gt;</literal> <type>ltree</type>
 378         <returnvalue>ltree</returnvalue>
 379        </para>
 380        <para>
 381         Returns first array entry that is an ancestor of <type>ltree</type>,
 382         or <literal>NULL</literal> if none.
 383        </para></entry>
 384       </row>
 385
 386       <row>
 387        <entry role="func_table_entry"><para role="func_signature">
 388         <type>ltree[]</type> <literal>?&lt;@</literal> <type>ltree</type>
 389         <returnvalue>ltree</returnvalue>
 390        </para>
 391        <para>
 392         Returns first array entry that is a descendant of <type>ltree</type>,
 393         or <literal>NULL</literal> if none.
 394        </para></entry>
 395       </row>
 396
 397       <row>
 398        <entry role="func_table_entry"><para role="func_signature">
 399         <type>ltree[]</type> <literal>?~</literal> <type>lquery</type>
 400         <returnvalue>ltree</returnvalue>
 401        </para>
 402        <para>
 403         Returns first array entry that matches <type>lquery</type>,
 404         or <literal>NULL</literal> if none.
 405        </para></entry>
 406       </row>
 407
 408       <row>
 409        <entry role="func_table_entry"><para role="func_signature">
 410         <type>ltree[]</type> <literal>?@</literal> <type>ltxtquery</type>
 411         <returnvalue>ltree</returnvalue>
 412        </para>
 413        <para>
 414         Returns first array entry that matches <type>ltxtquery</type>,
 415         or <literal>NULL</literal> if none.
 416        </para></entry>
 417       </row>
 418      </tbody>
 419     </tgroup>
 420   </table>
 421
 422   <para>
 423    The operators <literal>&lt;@</literal>, <literal>@&gt;</literal>,
 424    <literal>@</literal> and <literal>~</literal> have analogues
 425    <literal>^&lt;@</literal>, <literal>^@&gt;</literal>, <literal>^@</literal>,
 426    <literal>^~</literal>, which are the same except they do not use
 427    indexes.  These are useful only for testing purposes.
 428   </para>
 429
 430   <para>
 431    The available functions are shown in <xref linkend="ltree-func-table"/>.
 432   </para>
 433
 434   <table id="ltree-func-table">
 435    <title><type>ltree</type> Functions</title>
 436     <tgroup cols="1">
 437      <thead>
 438       <row>
 439        <entry role="func_table_entry"><para role="func_signature">
 440         Function
 441        </para>
 442        <para>
 443         Description
 444        </para>
 445        <para>
 446         Example(s)
 447        </para></entry>
 448       </row>
 449      </thead>
 450
 451      <tbody>
 452       <row>
 453        <entry role="func_table_entry"><para role="func_signature">
 454         <indexterm><primary>subltree</primary></indexterm>
 455         <function>subltree</function> ( <type>ltree</type>, <parameter>start</parameter> <type>integer</type>, <parameter>end</parameter> <type>integer</type> )
 456         <returnvalue>ltree</returnvalue>
 457        </para>
 458        <para>
 459         Returns subpath of <type>ltree</type> from
 460         position <parameter>start</parameter> to
 461         position <parameter>end</parameter>-1 (counting from 0).
 462        </para>
 463        <para>
 464         <literal>subltree('Top.Child1.Child2', 1, 2)</literal>
 465         <returnvalue>Child1</returnvalue>
 466        </para></entry>
 467       </row>
 468
 469       <row>
 470        <entry role="func_table_entry"><para role="func_signature">
 471         <indexterm><primary>subpath</primary></indexterm>
 472         <function>subpath</function> ( <type>ltree</type>, <parameter>offset</parameter> <type>integer</type>, <parameter>len</parameter> <type>integer</type> )
 473         <returnvalue>ltree</returnvalue>
 474        </para>
 475        <para>
 476         Returns subpath of <type>ltree</type> starting at
 477         position <parameter>offset</parameter>, with
 478         length <parameter>len</parameter>.  If <parameter>offset</parameter>
 479         is negative, subpath starts that far from the end of the path.
 480         If <parameter>len</parameter> is negative, leaves that many labels off
 481         the end of the path.
 482        </para>
 483        <para>
 484         <literal>subpath('Top.Child1.Child2', 0, 2)</literal>
 485         <returnvalue>Top.Child1</returnvalue>
 486        </para></entry>
 487       </row>
 488
 489       <row>
 490        <entry role="func_table_entry"><para role="func_signature">
 491         <function>subpath</function> ( <type>ltree</type>, <parameter>offset</parameter> <type>integer</type> )
 492         <returnvalue>ltree</returnvalue>
 493        </para>
 494        <para>
 495         Returns subpath of <type>ltree</type> starting at
 496         position <parameter>offset</parameter>, extending to end of path.
 497         If <parameter>offset</parameter> is negative, subpath starts that far
 498         from the end of the path.
 499        </para>
 500        <para>
 501         <literal>subpath('Top.Child1.Child2', 1)</literal>
 502         <returnvalue>Child1.Child2</returnvalue>
 503        </para></entry>
 504       </row>
 505
 506       <row>
 507        <entry role="func_table_entry"><para role="func_signature">
 508         <indexterm><primary>nlevel</primary></indexterm>
 509         <function>nlevel</function> ( <type>ltree</type> )
 510         <returnvalue>integer</returnvalue>
 511        </para>
 512        <para>
 513         Returns number of labels in path.
 514        </para>
 515        <para>
 516         <literal>nlevel('Top.Child1.Child2')</literal>
 517         <returnvalue>3</returnvalue>
 518        </para></entry>
 519       </row>
 520
 521       <row>
 522        <entry role="func_table_entry"><para role="func_signature">
 523         <indexterm><primary>index</primary></indexterm>
 524         <function>index</function> ( <parameter>a</parameter> <type>ltree</type>, <parameter>b</parameter> <type>ltree</type> )
 525         <returnvalue>integer</returnvalue>
 526        </para>
 527        <para>
 528         Returns position of first occurrence of <parameter>b</parameter> in
 529         <parameter>a</parameter>, or -1 if not found.
 530        </para>
 531        <para>
 532         <literal>index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6')</literal>
 533         <returnvalue>6</returnvalue>
 534        </para></entry>
 535       </row>
 536
 537       <row>
 538        <entry role="func_table_entry"><para role="func_signature">
 539         <function>index</function> ( <parameter>a</parameter> <type>ltree</type>,  <parameter>b</parameter> <type>ltree</type>, <parameter>offset</parameter> <type>integer</type> )
 540         <returnvalue>integer</returnvalue>
 541        </para>
 542        <para>
 543         Returns position of first occurrence of <parameter>b</parameter>
 544         in <parameter>a</parameter>, or -1 if not found.  The search starts at
 545         position <parameter>offset</parameter>;
 546         negative <parameter>offset</parameter> means
 547         start <parameter>-offset</parameter> labels from the end of the path.
 548        </para>
 549        <para>
 550         <literal>index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6', -4)</literal>
 551         <returnvalue>9</returnvalue>
 552        </para></entry>
 553       </row>
 554
 555       <row>
 556        <entry role="func_table_entry"><para role="func_signature">
 557         <indexterm><primary>text2ltree</primary></indexterm>
 558         <function>text2ltree</function> ( <type>text</type> )
 559         <returnvalue>ltree</returnvalue>
 560        </para>
 561        <para>
 562         Casts <type>text</type> to <type>ltree</type>.
 563        </para></entry>
 564       </row>
 565
 566       <row>
 567        <entry role="func_table_entry"><para role="func_signature">
 568         <indexterm><primary>ltree2text</primary></indexterm>
 569         <function>ltree2text</function> ( <type>ltree</type> )
 570         <returnvalue>text</returnvalue>
 571        </para>
 572        <para>
 573         Casts <type>ltree</type> to <type>text</type>.
 574        </para></entry>
 575       </row>
 576
 577       <row>
 578        <entry role="func_table_entry"><para role="func_signature">
 579         <indexterm><primary>lca</primary></indexterm>
 580         <function>lca</function> ( <type>ltree</type> <optional>, <type>ltree</type> <optional>, ... </optional></optional> )
 581         <returnvalue>ltree</returnvalue>
 582        </para>
 583        <para>
 584         Computes longest common ancestor of paths
 585         (up to 8 arguments are supported).
 586        </para>
 587        <para>
 588         <literal>lca('1.2.3', '1.2.3.4.5.6')</literal>
 589         <returnvalue>1.2</returnvalue>
 590        </para></entry>
 591       </row>
 592
 593       <row>
 594        <entry role="func_table_entry"><para role="func_signature">
 595         <function>lca</function> ( <type>ltree[]</type> )
 596         <returnvalue>ltree</returnvalue>
 597        </para>
 598        <para>
 599         Computes longest common ancestor of paths in array.
 600        </para>
 601        <para>
 602         <literal>lca(array['1.2.3'::ltree,'1.2.3.4'])</literal>
 603         <returnvalue>1.2</returnvalue>
 604        </para></entry>
 605       </row>
 606      </tbody>
 607     </tgroup>
 608   </table>
 609  </sect2>
 610
 611  <sect2 id="ltree-indexes">
 612   <title>Indexes</title>
 613   <para>
 614    <filename>ltree</filename> supports several types of indexes that can speed
 615    up the indicated operators:
 616   </para>
 617
 618   <itemizedlist>
 619    <listitem>
 620     <para>
 621      B-tree index over <type>ltree</type>:
 622      <literal>&lt;</literal>, <literal>&lt;=</literal>, <literal>=</literal>,
 623      <literal>&gt;=</literal>, <literal>&gt;</literal>
 624     </para>
 625    </listitem>
 626    <listitem>
 627     <para>
 628      Hash index over <type>ltree</type>:
 629      <literal>=</literal>
 630     </para>
 631    </listitem>
 632
 633    <listitem>
 634     <para>
 635      GiST index over <type>ltree</type> (<literal>gist_ltree_ops</literal>
 636      opclass):
 637      <literal>&lt;</literal>, <literal>&lt;=</literal>, <literal>=</literal>,
 638      <literal>&gt;=</literal>, <literal>&gt;</literal>,
 639      <literal>@&gt;</literal>, <literal>&lt;@</literal>,
 640      <literal>@</literal>, <literal>~</literal>, <literal>?</literal>
 641     </para>
 642     <para>
 643      <literal>gist_ltree_ops</literal> GiST opclass approximates a set of
 644      path labels as a bitmap signature.  Its optional integer parameter
 645      <literal>siglen</literal> determines the
 646      signature length in bytes.  The default signature length is 8 bytes.
 647      The length must be a positive multiple of <type>int</type> alignment
 648      (4 bytes on most machines)) up to 2024.  Longer
 649      signatures lead to a more precise search (scanning a smaller fraction of the index and
 650      fewer heap pages), at the cost of a larger index.
 651     </para>
 652     <para>
 653      Example of creating such an index with the default signature length of 8 bytes:
 654     </para>
 655 <programlisting>
 656 CREATE INDEX path_gist_idx ON test USING GIST (path);
 657 </programlisting>
 658     <para>
 659      Example of creating such an index with a signature length of 100 bytes:
 660     </para>
 661 <programlisting>
 662 CREATE INDEX path_gist_idx ON test USING GIST (path gist_ltree_ops(siglen=100));
 663 </programlisting>
 664    </listitem>
 665    <listitem>
 666     <para>
 667      GiST index over <type>ltree[]</type> (<literal>gist__ltree_ops</literal>
 668      opclass):
 669      <literal>ltree[] &lt;@ ltree</literal>, <literal>ltree @&gt; ltree[]</literal>,
 670      <literal>@</literal>, <literal>~</literal>, <literal>?</literal>
 671     </para>
 672     <para>
 673      <literal>gist__ltree_ops</literal> GiST opclass works similarly to
 674      <literal>gist_ltree_ops</literal> and also takes signature length as
 675      a parameter.  The default value of <literal>siglen</literal> in
 676       <literal>gist__ltree_ops</literal> is 28 bytes.
 677     </para>
 678     <para>
 679      Example of creating such an index with the default signature length of 28 bytes:
 680     </para>
 681 <programlisting>
 682 CREATE INDEX path_gist_idx ON test USING GIST (array_path);
 683 </programlisting>
 684     <para>
 685      Example of creating such an index with a signature length of 100 bytes:
 686     </para>
 687 <programlisting>
 688 CREATE INDEX path_gist_idx ON test USING GIST (array_path gist__ltree_ops(siglen=100));
 689 </programlisting>
 690     <para>
 691      Note: This index type is lossy.
 692     </para>
 693    </listitem>
 694   </itemizedlist>
 695  </sect2>
 696
 697  <sect2 id="ltree-example">
 698   <title>Example</title>
 699
 700   <para>
 701    This example uses the following data (also available in file
 702    <filename>contrib/ltree/ltreetest.sql</filename> in the source distribution):
 703   </para>
 704
 705 <programlisting>
 706 CREATE TABLE test (path ltree);
 707 INSERT INTO test VALUES ('Top');
 708 INSERT INTO test VALUES ('Top.Science');
 709 INSERT INTO test VALUES ('Top.Science.Astronomy');
 710 INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics');
 711 INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology');
 712 INSERT INTO test VALUES ('Top.Hobbies');
 713 INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy');
 714 INSERT INTO test VALUES ('Top.Collections');
 715 INSERT INTO test VALUES ('Top.Collections.Pictures');
 716 INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy');
 717 INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars');
 718 INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
 719 INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
 720 CREATE INDEX path_gist_idx ON test USING GIST (path);
 721 CREATE INDEX path_idx ON test USING BTREE (path);
 722 CREATE INDEX path_hash_idx ON test USING HASH (path);
 723 </programlisting>
 724
 725   <para>
 726    Now, we have a table <structname>test</structname> populated with data describing
 727    the hierarchy shown below:
 728   </para>
 729
 730 <literallayout class="monospaced">
 731                         Top
 732                      /   |  \
 733              Science Hobbies Collections
 734                  /       |              \
 735         Astronomy   Amateurs_Astronomy Pictures
 736            /  \                            |
 737 Astrophysics  Cosmology                Astronomy
 738                                         /  |    \
 739                                  Galaxies Stars Astronauts
 740 </literallayout>
 741
 742   <para>
 743    We can do inheritance:
 744 <screen>
 745 ltreetest=&gt; SELECT path FROM test WHERE path &lt;@ 'Top.Science';
 746                 path
 747 ------------------------------------
 748  Top.Science
 749  Top.Science.Astronomy
 750  Top.Science.Astronomy.Astrophysics
 751  Top.Science.Astronomy.Cosmology
 752 (4 rows)
 753 </screen>
 754   </para>
 755
 756   <para>
 757    Here are some examples of path matching:
 758 <screen>
 759 ltreetest=&gt; SELECT path FROM test WHERE path ~ '*.Astronomy.*';
 760                      path
 761 -----------------------------------------------
 762  Top.Science.Astronomy
 763  Top.Science.Astronomy.Astrophysics
 764  Top.Science.Astronomy.Cosmology
 765  Top.Collections.Pictures.Astronomy
 766  Top.Collections.Pictures.Astronomy.Stars
 767  Top.Collections.Pictures.Astronomy.Galaxies
 768  Top.Collections.Pictures.Astronomy.Astronauts
 769 (7 rows)
 770
 771 ltreetest=&gt; SELECT path FROM test WHERE path ~ '*.!pictures@.Astronomy.*';
 772                 path
 773 ------------------------------------
 774  Top.Science.Astronomy
 775  Top.Science.Astronomy.Astrophysics
 776  Top.Science.Astronomy.Cosmology
 777 (3 rows)
 778 </screen>
 779   </para>
 780
 781   <para>
 782    Here are some examples of full text search:
 783 <screen>
 784 ltreetest=&gt; SELECT path FROM test WHERE path @ 'Astro*% &amp; !pictures@';
 785                 path
 786 ------------------------------------
 787  Top.Science.Astronomy
 788  Top.Science.Astronomy.Astrophysics
 789  Top.Science.Astronomy.Cosmology
 790  Top.Hobbies.Amateurs_Astronomy
 791 (4 rows)
 792
 793 ltreetest=&gt; SELECT path FROM test WHERE path @ 'Astro* &amp; !pictures@';
 794                 path
 795 ------------------------------------
 796  Top.Science.Astronomy
 797  Top.Science.Astronomy.Astrophysics
 798  Top.Science.Astronomy.Cosmology
 799 (3 rows)
 800 </screen>
 801   </para>
 802
 803   <para>
 804    Path construction using functions:
 805 <screen>
 806 ltreetest=&gt; SELECT subpath(path,0,2)||'Space'||subpath(path,2) FROM test WHERE path &lt;@ 'Top.Science.Astronomy';
 807                  ?column?
 808 ------------------------------------------
 809  Top.Science.Space.Astronomy
 810  Top.Science.Space.Astronomy.Astrophysics
 811  Top.Science.Space.Astronomy.Cosmology
 812 (3 rows)
 813 </screen>
 814   </para>
 815
 816   <para>
 817    We could simplify this by creating an SQL function that inserts a label
 818    at a specified position in a path:
 819 <screen>
 820 CREATE FUNCTION ins_label(ltree, int, text) RETURNS ltree
 821     AS 'select subpath($1,0,$2) || $3 || subpath($1,$2);'
 822     LANGUAGE SQL IMMUTABLE;
 823
 824 ltreetest=&gt; SELECT ins_label(path,2,'Space') FROM test WHERE path &lt;@ 'Top.Science.Astronomy';
 825                 ins_label
 826 ------------------------------------------
 827  Top.Science.Space.Astronomy
 828  Top.Science.Space.Astronomy.Astrophysics
 829  Top.Science.Space.Astronomy.Cosmology
 830 (3 rows)
 831 </screen>
 832   </para>
 833  </sect2>
 834
 835  <sect2 id="ltree-transforms">
 836   <title>Transforms</title>
 837
 838   <para>
 839    The <literal>ltree_plpython3u</literal> extension implements transforms for
 840    the <type>ltree</type> type for PL/Python. If installed and specified when
 841    creating a function, <type>ltree</type> values are mapped to Python lists.
 842    (The reverse is currently not supported, however.)
 843   </para>
 844
 845   <caution>
 846    <para>
 847     It is strongly recommended that the transform extension be installed in
 848     the same schema as <filename>ltree</filename>.  Otherwise there are
 849     installation-time security hazards if a transform extension's schema
 850     contains objects defined by a hostile user.
 851    </para>
 852   </caution>
 853  </sect2>
 854
 855  <sect2 id="ltree-authors">
 856   <title>Authors</title>
 857
 858   <para>
 859    All work was done by Teodor Sigaev (<email>teodor@stack.net</email>) and
 860    Oleg Bartunov (<email>oleg@sai.msu.su</email>). See
 861    <ulink url="http://www.sai.msu.su/~megera/postgres/gist/"></ulink> for
 862    additional information. Authors would like to thank Eugeny Rodichev for
 863    helpful discussions. Comments and bug reports are welcome.
 864   </para>
 865  </sect2>
 866
 867 </sect1>