doc/src/sgml/cube.sgml

   1 <!-- doc/src/sgml/cube.sgml -->
   2
   3 <sect1 id="cube" xreflabel="cube">
   4  <title>cube &mdash; a multi-dimensional cube data type</title>
   5
   6  <indexterm zone="cube">
   7   <primary>cube (extension)</primary>
   8  </indexterm>
   9
  10  <para>
  11   This module implements a data type <type>cube</type> for
  12   representing multidimensional cubes.
  13  </para>
  14
  15  <para>
  16   This module is considered <quote>trusted</quote>, that is, it can be
  17   installed by non-superusers who have <literal>CREATE</literal> privilege
  18   on the current database.
  19  </para>
  20
  21  <sect2 id="cube-syntax">
  22   <title>Syntax</title>
  23
  24   <para>
  25    <xref linkend="cube-repr-table"/> shows the valid external
  26    representations for the <type>cube</type>
  27    type.  <replaceable>x</replaceable>, <replaceable>y</replaceable>, etc. denote
  28    floating-point numbers.
  29   </para>
  30
  31   <table id="cube-repr-table">
  32    <title>Cube External Representations</title>
  33    <tgroup cols="2">
  34     <thead>
  35      <row>
  36       <entry>External Syntax</entry>
  37       <entry>Meaning</entry>
  38      </row>
  39     </thead>
  40
  41     <tbody>
  42      <row>
  43       <entry><literal><replaceable>x</replaceable></literal></entry>
  44       <entry>A one-dimensional point
  45        (or, zero-length one-dimensional interval)
  46       </entry>
  47      </row>
  48      <row>
  49       <entry><literal>(<replaceable>x</replaceable>)</literal></entry>
  50       <entry>Same as above</entry>
  51      </row>
  52      <row>
  53       <entry><literal><replaceable>x1</replaceable>,<replaceable>x2</replaceable>,...,<replaceable>xn</replaceable></literal></entry>
  54       <entry>A point in n-dimensional space, represented internally as a
  55       zero-volume cube
  56       </entry>
  57      </row>
  58      <row>
  59       <entry><literal>(<replaceable>x1</replaceable>,<replaceable>x2</replaceable>,...,<replaceable>xn</replaceable>)</literal></entry>
  60       <entry>Same as above</entry>
  61      </row>
  62      <row>
  63       <entry><literal>(<replaceable>x</replaceable>),(<replaceable>y</replaceable>)</literal></entry>
  64       <entry>A one-dimensional interval starting at <replaceable>x</replaceable> and ending at <replaceable>y</replaceable> or vice versa; the
  65        order does not matter
  66       </entry>
  67      </row>
  68      <row>
  69       <entry><literal>[(<replaceable>x</replaceable>),(<replaceable>y</replaceable>)]</literal></entry>
  70       <entry>Same as above</entry>
  71      </row>
  72      <row>
  73       <entry><literal>(<replaceable>x1</replaceable>,...,<replaceable>xn</replaceable>),(<replaceable>y1</replaceable>,...,<replaceable>yn</replaceable>)</literal></entry>
  74       <entry>An n-dimensional cube represented by a pair of its diagonally
  75        opposite corners
  76       </entry>
  77      </row>
  78      <row>
  79       <entry><literal>[(<replaceable>x1</replaceable>,...,<replaceable>xn</replaceable>),(<replaceable>y1</replaceable>,...,<replaceable>yn</replaceable>)]</literal></entry>
  80       <entry>Same as above</entry>
  81      </row>
  82     </tbody>
  83    </tgroup>
  84   </table>
  85
  86   <para>
  87    It does not matter which order the opposite corners of a cube are
  88    entered in.  The <type>cube</type> functions
  89    automatically swap values if needed to create a uniform
  90    <quote>lower left &mdash; upper right</quote> internal representation.
  91    When the corners coincide, <type>cube</type> stores only one corner
  92    along with an <quote>is point</quote> flag to avoid wasting space.
  93   </para>
  94
  95   <para>
  96    White space is ignored on input, so
  97    <literal>[(<replaceable>x</replaceable>),(<replaceable>y</replaceable>)]</literal> is the same as
  98    <literal>[ ( <replaceable>x</replaceable> ), ( <replaceable>y</replaceable> ) ]</literal>.
  99   </para>
 100  </sect2>
 101
 102  <sect2 id="cube-precision">
 103   <title>Precision</title>
 104
 105   <para>
 106    Values are stored internally as 64-bit floating point numbers. This means
 107    that numbers with more than about 16 significant digits will be truncated.
 108   </para>
 109  </sect2>
 110
 111  <sect2 id="cube-usage">
 112   <title>Usage</title>
 113
 114   <para>
 115    <xref linkend="cube-operators-table"/> shows the specialized operators
 116    provided for type <type>cube</type>.
 117   </para>
 118
 119   <table id="cube-operators-table">
 120    <title>Cube Operators</title>
 121     <tgroup cols="1">
 122      <thead>
 123       <row>
 124        <entry role="func_table_entry"><para role="func_signature">
 125         Operator
 126        </para>
 127        <para>
 128         Description
 129        </para></entry>
 130       </row>
 131      </thead>
 132
 133      <tbody>
 134       <row>
 135        <entry role="func_table_entry"><para role="func_signature">
 136         <type>cube</type> <literal>&amp;&amp;</literal> <type>cube</type>
 137         <returnvalue>boolean</returnvalue>
 138        </para>
 139        <para>
 140         Do the cubes overlap?
 141        </para></entry>
 142       </row>
 143
 144       <row>
 145        <entry role="func_table_entry"><para role="func_signature">
 146         <type>cube</type> <literal>@&gt;</literal> <type>cube</type>
 147         <returnvalue>boolean</returnvalue>
 148        </para>
 149        <para>
 150         Does the first cube contain the second?
 151        </para></entry>
 152       </row>
 153
 154       <row>
 155        <entry role="func_table_entry"><para role="func_signature">
 156         <type>cube</type> <literal>&lt;@</literal> <type>cube</type>
 157         <returnvalue>boolean</returnvalue>
 158        </para>
 159        <para>
 160         Is the first cube contained in the second?
 161        </para></entry>
 162       </row>
 163
 164       <row>
 165        <entry role="func_table_entry"><para role="func_signature">
 166         <type>cube</type> <literal>-&gt;</literal> <type>integer</type>
 167         <returnvalue>float8</returnvalue>
 168        </para>
 169        <para>
 170         Extracts the <parameter>n</parameter>-th coordinate of the cube
 171         (counting from 1).
 172        </para></entry>
 173       </row>
 174
 175       <row>
 176        <entry role="func_table_entry"><para role="func_signature">
 177         <type>cube</type> <literal>~&gt;</literal> <type>integer</type>
 178         <returnvalue>float8</returnvalue>
 179        </para>
 180        <para>
 181         Extracts the <parameter>n</parameter>-th coordinate of the cube,
 182         counting in the following way: <parameter>n</parameter> = 2
 183         * <parameter>k</parameter> - 1 means lower bound
 184         of <parameter>k</parameter>-th dimension, <parameter>n</parameter> = 2
 185         * <parameter>k</parameter> means upper bound of
 186         <parameter>k</parameter>-th dimension.  Negative
 187         <parameter>n</parameter> denotes the inverse value of the corresponding
 188         positive coordinate.  This operator is designed for KNN-GiST support.
 189        </para></entry>
 190       </row>
 191
 192       <row>
 193        <entry role="func_table_entry"><para role="func_signature">
 194         <type>cube</type> <literal>&lt;-&gt;</literal> <type>cube</type>
 195         <returnvalue>float8</returnvalue>
 196        </para>
 197        <para>
 198         Computes the Euclidean distance between the two cubes.
 199        </para></entry>
 200       </row>
 201
 202       <row>
 203        <entry role="func_table_entry"><para role="func_signature">
 204         <type>cube</type> <literal>&lt;#&gt;</literal> <type>cube</type>
 205         <returnvalue>float8</returnvalue>
 206        </para>
 207        <para>
 208         Computes the taxicab (L-1 metric) distance between the two cubes.
 209        </para></entry>
 210       </row>
 211
 212       <row>
 213        <entry role="func_table_entry"><para role="func_signature">
 214         <type>cube</type> <literal>&lt;=&gt;</literal> <type>cube</type>
 215         <returnvalue>float8</returnvalue>
 216        </para>
 217        <para>
 218         Computes the Chebyshev (L-inf metric) distance between the two cubes.
 219        </para></entry>
 220       </row>
 221      </tbody>
 222    </tgroup>
 223   </table>
 224
 225   <para>
 226    In addition to the above operators, the usual comparison
 227    operators shown in <xref linkend="functions-comparison-op-table"/> are
 228    available for type <type>cube</type>.  These
 229    operators first compare the first coordinates, and if those are equal,
 230    compare the second coordinates, etc.  They exist mainly to support the
 231    b-tree index operator class for <type>cube</type>, which can be useful for
 232    example if you would like a UNIQUE constraint on a <type>cube</type> column.
 233    Otherwise, this ordering is not of much practical use.
 234   </para>
 235
 236   <para>
 237    The <filename>cube</filename> module also provides a GiST index operator class for
 238    <type>cube</type> values.
 239    A <type>cube</type> GiST index can be used to search for values using the
 240    <literal>=</literal>, <literal>&amp;&amp;</literal>, <literal>@&gt;</literal>, and
 241    <literal>&lt;@</literal> operators in <literal>WHERE</literal> clauses.
 242   </para>
 243
 244   <para>
 245    In addition, a <type>cube</type> GiST index can be used to find nearest
 246    neighbors using the metric operators
 247    <literal>&lt;-&gt;</literal>, <literal>&lt;#&gt;</literal>, and
 248    <literal>&lt;=&gt;</literal> in <literal>ORDER BY</literal> clauses.
 249    For example, the nearest neighbor of the 3-D point (0.5, 0.5, 0.5)
 250    could be found efficiently with:
 251 <programlisting>
 252 SELECT c FROM test ORDER BY c &lt;-&gt; cube(array[0.5,0.5,0.5]) LIMIT 1;
 253 </programlisting>
 254   </para>
 255
 256   <para>
 257    The <literal>~&gt;</literal> operator can also be used in this way to
 258    efficiently retrieve the first few values sorted by a selected coordinate.
 259    For example, to get the first few cubes ordered by the first coordinate
 260    (lower left corner) ascending one could use the following query:
 261 <programlisting>
 262 SELECT c FROM test ORDER BY c ~&gt; 1 LIMIT 5;
 263 </programlisting>
 264    And to get 2-D cubes ordered by the first coordinate of the upper right
 265    corner descending:
 266 <programlisting>
 267 SELECT c FROM test ORDER BY c ~&gt; 3 DESC LIMIT 5;
 268 </programlisting>
 269   </para>
 270
 271   <para>
 272    <xref linkend="cube-functions-table"/> shows the available functions.
 273   </para>
 274
 275   <table id="cube-functions-table">
 276    <title>Cube Functions</title>
 277     <tgroup cols="1">
 278      <thead>
 279       <row>
 280        <entry role="func_table_entry"><para role="func_signature">
 281         Function
 282        </para>
 283        <para>
 284         Description
 285        </para>
 286        <para>
 287         Example(s)
 288        </para></entry>
 289       </row>
 290      </thead>
 291
 292      <tbody>
 293       <row>
 294        <entry role="func_table_entry"><para role="func_signature">
 295         <function>cube</function> ( <type>float8</type> )
 296         <returnvalue>cube</returnvalue>
 297        </para>
 298        <para>
 299         Makes a one dimensional cube with both coordinates the same.
 300        </para>
 301        <para>
 302         <literal>cube(1)</literal>
 303         <returnvalue>(1)</returnvalue>
 304        </para></entry>
 305       </row>
 306
 307       <row>
 308        <entry role="func_table_entry"><para role="func_signature">
 309         <function>cube</function> ( <type>float8</type>, <type>float8</type> )
 310         <returnvalue>cube</returnvalue>
 311        </para>
 312        <para>
 313         Makes a one dimensional cube.
 314        </para>
 315        <para>
 316         <literal>cube(1, 2)</literal>
 317         <returnvalue>(1),(2)</returnvalue>
 318        </para></entry>
 319       </row>
 320
 321       <row>
 322        <entry role="func_table_entry"><para role="func_signature">
 323         <function>cube</function> ( <type>float8[]</type> )
 324         <returnvalue>cube</returnvalue>
 325        </para>
 326        <para>
 327         Makes a zero-volume cube using the coordinates defined by the array.
 328        </para>
 329        <para>
 330         <literal>cube(ARRAY[1,2,3])</literal>
 331         <returnvalue>(1, 2, 3)</returnvalue>
 332        </para></entry>
 333       </row>
 334
 335       <row>
 336        <entry role="func_table_entry"><para role="func_signature">
 337         <function>cube</function> ( <type>float8[]</type>, <type>float8[]</type> )
 338         <returnvalue>cube</returnvalue>
 339        </para>
 340        <para>
 341         Makes a cube with upper right and lower left coordinates as defined by
 342         the two arrays, which must be of the same length.
 343        </para>
 344        <para>
 345         <literal>cube(ARRAY[1,2], ARRAY[3,4])</literal>
 346         <returnvalue>(1, 2),(3, 4)</returnvalue>
 347        </para></entry>
 348       </row>
 349
 350       <row>
 351        <entry role="func_table_entry"><para role="func_signature">
 352         <function>cube</function> ( <type>cube</type>, <type>float8</type> )
 353         <returnvalue>cube</returnvalue>
 354        </para>
 355        <para>
 356         Makes a new cube by adding a dimension on to an existing cube,
 357         with the same values for both endpoints of the new coordinate.  This
 358         is useful for building cubes piece by piece from calculated values.
 359        </para>
 360        <para>
 361         <literal>cube('(1,2),(3,4)'::cube, 5)</literal>
 362         <returnvalue>(1, 2, 5),(3, 4, 5)</returnvalue>
 363        </para></entry>
 364       </row>
 365
 366       <row>
 367        <entry role="func_table_entry"><para role="func_signature">
 368         <function>cube</function> ( <type>cube</type>, <type>float8</type>, <type>float8</type> )
 369         <returnvalue>cube</returnvalue>
 370        </para>
 371        <para>
 372         Makes a new cube by adding a dimension on to an existing cube. This is
 373         useful for building cubes piece by piece from calculated values.
 374        </para>
 375        <para>
 376         <literal>cube('(1,2),(3,4)'::cube, 5, 6)</literal>
 377         <returnvalue>(1, 2, 5),(3, 4, 6)</returnvalue>
 378        </para></entry>
 379       </row>
 380
 381       <row>
 382        <entry role="func_table_entry"><para role="func_signature">
 383         <function>cube_dim</function> ( <type>cube</type> )
 384         <returnvalue>integer</returnvalue>
 385        </para>
 386        <para>
 387         Returns the number of dimensions of the cube.
 388        </para>
 389        <para>
 390         <literal>cube_dim('(1,2),(3,4)')</literal>
 391         <returnvalue>2</returnvalue>
 392        </para></entry>
 393       </row>
 394
 395       <row>
 396        <entry role="func_table_entry"><para role="func_signature">
 397         <function>cube_ll_coord</function> ( <type>cube</type>, <type>integer</type> )
 398         <returnvalue>float8</returnvalue>
 399        </para>
 400        <para>
 401         Returns the <parameter>n</parameter>-th coordinate value for the lower
 402         left corner of the cube.
 403        </para>
 404        <para>
 405         <literal>cube_ll_coord('(1,2),(3,4)', 2)</literal>
 406         <returnvalue>2</returnvalue>
 407        </para></entry>
 408       </row>
 409
 410       <row>
 411        <entry role="func_table_entry"><para role="func_signature">
 412         <function>cube_ur_coord</function> ( <type>cube</type>, <type>integer</type> )
 413         <returnvalue>float8</returnvalue>
 414        </para>
 415        <para>
 416         Returns the <parameter>n</parameter>-th coordinate value for the
 417         upper right corner of the cube.
 418        </para>
 419        <para>
 420         <literal>cube_ur_coord('(1,2),(3,4)', 2)</literal>
 421         <returnvalue>4</returnvalue>
 422        </para></entry>
 423       </row>
 424
 425       <row>
 426        <entry role="func_table_entry"><para role="func_signature">
 427         <function>cube_is_point</function> ( <type>cube</type> )
 428         <returnvalue>boolean</returnvalue>
 429        </para>
 430        <para>
 431         Returns true if the cube is a point, that is,
 432         the two defining corners are the same.
 433        </para>
 434        <para>
 435         <literal>cube_is_point(cube(1,1))</literal>
 436         <returnvalue>t</returnvalue>
 437        </para></entry>
 438       </row>
 439
 440       <row>
 441        <entry role="func_table_entry"><para role="func_signature">
 442         <function>cube_distance</function> ( <type>cube</type>, <type>cube</type> )
 443         <returnvalue>float8</returnvalue>
 444        </para>
 445        <para>
 446         Returns the distance between two cubes. If both
 447         cubes are points, this is the normal distance function.
 448        </para>
 449        <para>
 450         <literal>cube_distance('(1,2)', '(3,4)')</literal>
 451         <returnvalue>2.8284271247461903</returnvalue>
 452        </para></entry>
 453       </row>
 454
 455       <row>
 456        <entry role="func_table_entry"><para role="func_signature">
 457         <function>cube_subset</function> ( <type>cube</type>, <type>integer[]</type> )
 458         <returnvalue>cube</returnvalue>
 459        </para>
 460        <para>
 461         Makes a new cube from an existing cube, using a list of
 462         dimension indexes from an array. Can be used to extract the endpoints
 463         of a single dimension, or to drop dimensions, or to reorder them as
 464         desired.
 465        </para>
 466        <para>
 467         <literal>cube_subset(cube('(1,3,5),(6,7,8)'), ARRAY[2])</literal>
 468         <returnvalue>(3),(7)</returnvalue>
 469        </para>
 470        <para>
 471         <literal>cube_subset(cube('(1,3,5),(6,7,8)'), ARRAY[3,2,1,1])</literal>
 472         <returnvalue>(5, 3, 1, 1),(8, 7, 6, 6)</returnvalue>
 473        </para></entry>
 474       </row>
 475
 476       <row>
 477        <entry role="func_table_entry"><para role="func_signature">
 478         <function>cube_union</function> ( <type>cube</type>, <type>cube</type> )
 479         <returnvalue>cube</returnvalue>
 480        </para>
 481        <para>
 482         Produces the union of two cubes.
 483        </para>
 484        <para>
 485         <literal>cube_union('(1,2)', '(3,4)')</literal>
 486         <returnvalue>(1, 2),(3, 4)</returnvalue>
 487        </para></entry>
 488       </row>
 489
 490       <row>
 491        <entry role="func_table_entry"><para role="func_signature">
 492         <function>cube_inter</function> ( <type>cube</type>, <type>cube</type> )
 493         <returnvalue>cube</returnvalue>
 494        </para>
 495        <para>
 496         Produces the intersection of two cubes.
 497        </para>
 498        <para>
 499         <literal>cube_inter('(1,2)', '(3,4)')</literal>
 500         <returnvalue>(3, 4),(1, 2)</returnvalue>
 501        </para></entry>
 502       </row>
 503
 504       <row>
 505        <entry role="func_table_entry"><para role="func_signature">
 506         <function>cube_enlarge</function> ( <parameter>c</parameter> <type>cube</type>, <parameter>r</parameter> <type>double</type>, <parameter>n</parameter> <type>integer</type> )
 507         <returnvalue>cube</returnvalue>
 508        </para>
 509        <para>
 510         Increases the size of the cube by the specified
 511         radius <parameter>r</parameter> in at least <parameter>n</parameter>
 512         dimensions.  If the radius is negative the cube is shrunk instead.
 513         All defined dimensions are changed by the
 514         radius <parameter>r</parameter>.  Lower-left coordinates are decreased
 515         by <parameter>r</parameter> and upper-right coordinates are increased
 516         by <parameter>r</parameter>.  If a lower-left coordinate is increased
 517         to more than the corresponding upper-right coordinate (this can only
 518         happen when <parameter>r</parameter> &lt; 0) than both coordinates are
 519         set to their average.  If <parameter>n</parameter> is greater than the
 520         number of defined dimensions and the cube is being enlarged
 521         (<parameter>r</parameter> &gt; 0), then extra dimensions are added to
 522         make <parameter>n</parameter> altogether; 0 is used as the initial
 523         value for the extra coordinates.  This function is useful for creating
 524         bounding boxes around a point for searching for nearby points.
 525        </para>
 526        <para>
 527         <literal>cube_enlarge('(1,2),(3,4)', 0.5, 3)</literal>
 528         <returnvalue>(0.5, 1.5, -0.5),(3.5, 4.5, 0.5)</returnvalue>
 529        </para></entry>
 530       </row>
 531      </tbody>
 532     </tgroup>
 533   </table>
 534  </sect2>
 535
 536  <sect2 id="cube-defaults">
 537   <title>Defaults</title>
 538
 539   <para>
 540    This union:
 541   </para>
 542 <programlisting>
 543 select cube_union('(0,5,2),(2,3,1)', '0');
 544 cube_union
 545 -------------------
 546 (0, 0, 0),(2, 5, 2)
 547 (1 row)
 548 </programlisting>
 549
 550    <para>
 551     does not contradict common sense, neither does the intersection:
 552    </para>
 553
 554 <programlisting>
 555 select cube_inter('(0,-1),(1,1)', '(-2),(2)');
 556 cube_inter
 557 -------------
 558 (0, 0),(1, 0)
 559 (1 row)
 560 </programlisting>
 561
 562    <para>
 563     In all binary operations on differently-dimensioned cubes,
 564     the lower-dimensional one is assumed to be a Cartesian projection, i. e., having zeroes
 565     in place of coordinates omitted in the string representation. The above
 566     examples are equivalent to:
 567    </para>
 568
 569 <programlisting>
 570 cube_union('(0,5,2),(2,3,1)','(0,0,0),(0,0,0)');
 571 cube_inter('(0,-1),(1,1)','(-2,0),(2,0)');
 572 </programlisting>
 573
 574    <para>
 575     The following containment predicate uses the point syntax,
 576     while in fact the second argument is internally represented by a box.
 577     This syntax makes it unnecessary to define a separate point type
 578     and functions for (box,point) predicates.
 579    </para>
 580
 581 <programlisting>
 582 select cube_contains('(0,0),(1,1)', '0.5,0.5');
 583 cube_contains
 584 --------------
 585 t
 586 (1 row)
 587 </programlisting>
 588  </sect2>
 589
 590  <sect2 id="cube-notes">
 591   <title>Notes</title>
 592
 593   <para>
 594    For examples of usage, see the regression test <filename>sql/cube.sql</filename>.
 595   </para>
 596
 597   <para>
 598    To make it harder for people to break things, there
 599    is a limit of 100 on the number of dimensions of cubes. This is set
 600    in <filename>cubedata.h</filename> if you need something bigger.
 601   </para>
 602  </sect2>
 603
 604  <sect2 id="cube-credits">
 605   <title>Credits</title>
 606
 607   <para>
 608    Original author: Gene Selkov, Jr. <email>selkovjr@mcs.anl.gov</email>,
 609    Mathematics and Computer Science Division, Argonne National Laboratory.
 610   </para>
 611
 612   <para>
 613    My thanks are primarily to Prof. Joe Hellerstein
 614    (<ulink url="https://dsf.berkeley.edu/jmh/"></ulink>) for elucidating the
 615    gist of the GiST (<ulink url="http://gist.cs.berkeley.edu/"></ulink>), and
 616    to his former student Andy Dong for his example written for Illustra.
 617    I am also grateful to all Postgres developers, present and past, for
 618    enabling myself to create my own world and live undisturbed in it. And I
 619    would like to acknowledge my gratitude to Argonne Lab and to the
 620    U.S. Department of Energy for the years of faithful support of my database
 621    research.
 622   </para>
 623
 624   <para>
 625    Minor updates to this package were made by Bruno Wolff III
 626    <email>bruno@wolff.to</email> in August/September of 2002. These include
 627    changing the precision from single precision to double precision and adding
 628    some new functions.
 629   </para>
 630
 631   <para>
 632    Additional updates were made by Joshua Reich <email>josh@root.net</email> in
 633    July 2006. These include <literal>cube(float8[], float8[])</literal> and
 634    cleaning up the code to use the V1 call protocol instead of the deprecated
 635    V0 protocol.
 636   </para>
 637  </sect2>
 638
 639 </sect1>