path: root/doc/src/sgml/cube.sgml

<!-- doc/src/sgml/cube.sgml -->

<sect1 id="cube" xreflabel="cube">
 <title>cube</title>

 <indexterm zone="cube">
  <primary>cube (extension)</primary>
 </indexterm>

 <para>
  This module implements a data type <type>cube</type> for
  representing multidimensional cubes.
 </para>

 <para>
  This module is considered <quote>trusted</quote>, that is, it can be
  installed by non-superusers who have <literal>CREATE</literal> privilege
  on the current database.
 </para>

 <sect2>
  <title>Syntax</title>

  <para>
   <xref linkend="cube-repr-table"/> shows the valid external
   representations for the <type>cube</type>
   type.  <replaceable>x</replaceable>, <replaceable>y</replaceable>, etc. denote
   floating-point numbers.
  </para>

  <table id="cube-repr-table">
   <title>Cube External Representations</title>
   <tgroup cols="2">
    <thead>
     <row>
      <entry>External Syntax</entry>
      <entry>Meaning</entry>
     </row>
    </thead>

    <tbody>
     <row>
      <entry><literal><replaceable>x</replaceable></literal></entry>
      <entry>A one-dimensional point
       (or, zero-length one-dimensional interval)
      </entry>
     </row>
     <row>
      <entry><literal>(<replaceable>x</replaceable>)</literal></entry>
      <entry>Same as above</entry>
     </row>
     <row>
      <entry><literal><replaceable>x1</replaceable>,<replaceable>x2</replaceable>,...,<replaceable>xn</replaceable></literal></entry>
      <entry>A point in n-dimensional space, represented internally as a
      zero-volume cube
      </entry>
     </row>
     <row>
      <entry><literal>(<replaceable>x1</replaceable>,<replaceable>x2</replaceable>,...,<replaceable>xn</replaceable>)</literal></entry>
      <entry>Same as above</entry>
     </row>
     <row>
      <entry><literal>(<replaceable>x</replaceable>),(<replaceable>y</replaceable>)</literal></entry>
      <entry>A one-dimensional interval starting at <replaceable>x</replaceable> and ending at <replaceable>y</replaceable> or vice versa; the
       order does not matter
      </entry>
     </row>
     <row>
      <entry><literal>[(<replaceable>x</replaceable>),(<replaceable>y</replaceable>)]</literal></entry>
      <entry>Same as above</entry>
     </row>
     <row>
      <entry><literal>(<replaceable>x1</replaceable>,...,<replaceable>xn</replaceable>),(<replaceable>y1</replaceable>,...,<replaceable>yn</replaceable>)</literal></entry>
      <entry>An n-dimensional cube represented by a pair of its diagonally
       opposite corners
      </entry>
     </row>
     <row>
      <entry><literal>[(<replaceable>x1</replaceable>,...,<replaceable>xn</replaceable>),(<replaceable>y1</replaceable>,...,<replaceable>yn</replaceable>)]</literal></entry>
      <entry>Same as above</entry>
     </row>
    </tbody>
   </tgroup>
  </table>

  <para>
   It does not matter which order the opposite corners of a cube are
   entered in.  The <type>cube</type> functions
   automatically swap values if needed to create a uniform
   <quote>lower left &mdash; upper right</quote> internal representation.
   When the corners coincide, <type>cube</type> stores only one corner
   along with an <quote>is point</quote> flag to avoid wasting space.
  </para>

  <para>
   White space is ignored on input, so
   <literal>[(<replaceable>x</replaceable>),(<replaceable>y</replaceable>)]</literal> is the same as
   <literal>[ ( <replaceable>x</replaceable> ), ( <replaceable>y</replaceable> ) ]</literal>.
  </para>
 </sect2>

 <sect2>
  <title>Precision</title>

  <para>
   Values are stored internally as 64-bit floating point numbers. This means
   that numbers with more than about 16 significant digits will be truncated.
  </para>
 </sect2>

 <sect2>
  <title>Usage</title>

  <para>
   <xref linkend="cube-operators-table"/> shows the specialized operators
   provided for type <type>cube</type>.
  </para>

  <table id="cube-operators-table">
   <title>Cube Operators</title>
    <tgroup cols="1">
     <thead>
      <row>
       <entry role="func_table_entry"><para role="func_signature">
        Operator
       </para>
       <para>
        Description
       </para></entry>
      </row>
     </thead>

     <tbody>
      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <type>cube</type> <literal>&amp;&amp;</literal> <type>cube</type>
        <returnvalue>boolean</returnvalue>
       </para>
       <para>
        Do the cubes overlap?
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <type>cube</type> <literal>@&gt;</literal> <type>cube</type>
        <returnvalue>boolean</returnvalue>
       </para>
       <para>
        Does the first cube contain the second?
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <type>cube</type> <literal>&lt;@</literal> <type>cube</type>
        <returnvalue>boolean</returnvalue>
       </para>
       <para>
        Is the first cube contained in the second?
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <type>cube</type> <literal>-&gt;</literal> <type>integer</type>
        <returnvalue>float8</returnvalue>
       </para>
       <para>
        Extracts the <parameter>n</parameter>-th coordinate of the cube
        (counting from 1).
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <type>cube</type> <literal>~&gt;</literal> <type>integer</type>
        <returnvalue>float8</returnvalue>
       </para>
       <para>
        Extracts the <parameter>n</parameter>-th coordinate of the cube,
        counting in the following way: <parameter>n</parameter> = 2
        * <parameter>k</parameter> - 1 means lower bound
        of <parameter>k</parameter>-th dimension, <parameter>n</parameter> = 2
        * <parameter>k</parameter> means upper bound of
        <parameter>k</parameter>-th dimension.  Negative
        <parameter>n</parameter> denotes the inverse value of the corresponding
        positive coordinate.  This operator is designed for KNN-GiST support.
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <type>cube</type> <literal>&lt;-&gt;</literal> <type>cube</type>
        <returnvalue>float8</returnvalue>
       </para>
       <para>
        Computes the Euclidean distance between the two cubes.
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <type>cube</type> <literal>&lt;#&gt;</literal> <type>cube</type>
        <returnvalue>float8</returnvalue>
       </para>
       <para>
        Computes the taxicab (L-1 metric) distance between the two cubes.
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <type>cube</type> <literal>&lt;=&gt;</literal> <type>cube</type>
        <returnvalue>float8</returnvalue>
       </para>
       <para>
        Computes the Chebyshev (L-inf metric) distance between the two cubes.
       </para></entry>
      </row>
     </tbody>
   </tgroup>
  </table>

  <para>
   In addition to the above operators, the usual comparison
   operators shown in <xref linkend="functions-comparison-op-table"/> are
   available for type <type>cube</type>.  These
   operators first compare the first coordinates, and if those are equal,
   compare the second coordinates, etc.  They exist mainly to support the
   b-tree index operator class for <type>cube</type>, which can be useful for
   example if you would like a UNIQUE constraint on a <type>cube</type> column.
   Otherwise, this ordering is not of much practical use.
  </para>

  <para>
   The <filename>cube</filename> module also provides a GiST index operator class for
   <type>cube</type> values.
   A <type>cube</type> GiST index can be used to search for values using the
   <literal>=</literal>, <literal>&amp;&amp;</literal>, <literal>@&gt;</literal>, and
   <literal>&lt;@</literal> operators in <literal>WHERE</literal> clauses.
  </para>

  <para>
   In addition, a <type>cube</type> GiST index can be used to find nearest
   neighbors using the metric operators
   <literal>&lt;-&gt;</literal>, <literal>&lt;#&gt;</literal>, and
   <literal>&lt;=&gt;</literal> in <literal>ORDER BY</literal> clauses.
   For example, the nearest neighbor of the 3-D point (0.5, 0.5, 0.5)
   could be found efficiently with:
<programlisting>
SELECT c FROM test ORDER BY c &lt;-&gt; cube(array[0.5,0.5,0.5]) LIMIT 1;
</programlisting>
  </para>

  <para>
   The <literal>~&gt;</literal> operator can also be used in this way to
   efficiently retrieve the first few values sorted by a selected coordinate.
   For example, to get the first few cubes ordered by the first coordinate
   (lower left corner) ascending one could use the following query:
<programlisting>
SELECT c FROM test ORDER BY c ~&gt; 1 LIMIT 5;
</programlisting>
   And to get 2-D cubes ordered by the first coordinate of the upper right
   corner descending:
<programlisting>
SELECT c FROM test ORDER BY c ~&gt; 3 DESC LIMIT 5;
</programlisting>
  </para>

  <para>
   <xref linkend="cube-functions-table"/> shows the available functions.
  </para>

  <table id="cube-functions-table">
   <title>Cube Functions</title>
    <tgroup cols="1">
     <thead>
      <row>
       <entry role="func_table_entry"><para role="func_signature">
        Function
       </para>
       <para>
        Description
       </para>
       <para>
        Example(s)
       </para></entry>
      </row>
     </thead>

     <tbody>
      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube</function> ( <type>float8</type> )
        <returnvalue>cube</returnvalue>
       </para>
       <para>
        Makes a one dimensional cube with both coordinates the same.
       </para>
       <para>
        <literal>cube(1)</literal>
        <returnvalue>(1)</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube</function> ( <type>float8</type>, <type>float8</type> )
        <returnvalue>cube</returnvalue>
       </para>
       <para>
        Makes a one dimensional cube.
       </para>
       <para>
        <literal>cube(1, 2)</literal>
        <returnvalue>(1),(2)</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube</function> ( <type>float8[]</type> )
        <returnvalue>cube</returnvalue>
       </para>
       <para>
        Makes a zero-volume cube using the coordinates defined by the array.
       </para>
       <para>
        <literal>cube(ARRAY[1,2,3])</literal>
        <returnvalue>(1, 2, 3)</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube</function> ( <type>float8[]</type>, <type>float8[]</type> )
        <returnvalue>cube</returnvalue>
       </para>
       <para>
        Makes a cube with upper right and lower left coordinates as defined by
        the two arrays, which must be of the same length.
       </para>
       <para>
        <literal>cube(ARRAY[1,2], ARRAY[3,4])</literal>
        <returnvalue>(1, 2),(3, 4)</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube</function> ( <type>cube</type>, <type>float8</type> )
        <returnvalue>cube</returnvalue>
       </para>
       <para>
        Makes a new cube by adding a dimension on to an existing cube,
        with the same values for both endpoints of the new coordinate.  This
        is useful for building cubes piece by piece from calculated values.
       </para>
       <para>
        <literal>cube('(1,2),(3,4)'::cube, 5)</literal>
        <returnvalue>(1, 2, 5),(3, 4, 5)</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube</function> ( <type>cube</type>, <type>float8</type>, <type>float8</type> )
        <returnvalue>cube</returnvalue>
       </para>
       <para>
        Makes a new cube by adding a dimension on to an existing cube. This is
        useful for building cubes piece by piece from calculated values.
       </para>
       <para>
        <literal>cube('(1,2),(3,4)'::cube, 5, 6)</literal>
        <returnvalue>(1, 2, 5),(3, 4, 6)</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube_dim</function> ( <type>cube</type> )
        <returnvalue>integer</returnvalue>
       </para>
       <para>
        Returns the number of dimensions of the cube.
       </para>
       <para>
        <literal>cube_dim('(1,2),(3,4)')</literal>
        <returnvalue>2</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube_ll_coord</function> ( <type>cube</type>, <type>integer</type> )
        <returnvalue>float8</returnvalue>
       </para>
       <para>
        Returns the <parameter>n</parameter>-th coordinate value for the lower
        left corner of the cube.
       </para>
       <para>
        <literal>cube_ll_coord('(1,2),(3,4)', 2)</literal>
        <returnvalue>2</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube_ur_coord</function> ( <type>cube</type>, <type>integer</type> )
        <returnvalue>float8</returnvalue>
       </para>
       <para>
        Returns the <parameter>n</parameter>-th coordinate value for the
        upper right corner of the cube.
       </para>
       <para>
        <literal>cube_ur_coord('(1,2),(3,4)', 2)</literal>
        <returnvalue>4</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube_is_point</function> ( <type>cube</type> )
        <returnvalue>boolean</returnvalue>
       </para>
       <para>
        Returns true if the cube is a point, that is,
        the two defining corners are the same.
       </para>
       <para>
        <literal>cube_is_point(cube(1,1))</literal>
        <returnvalue>t</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube_distance</function> ( <type>cube</type>, <type>cube</type> )
        <returnvalue>float8</returnvalue>
       </para>
       <para>
        Returns the distance between two cubes. If both
        cubes are points, this is the normal distance function.
       </para>
       <para>
        <literal>cube_distance('(1,2)', '(3,4)')</literal>
        <returnvalue>2.8284271247461903</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube_subset</function> ( <type>cube</type>, <type>integer[]</type> )
        <returnvalue>cube</returnvalue>
       </para>
       <para>
        Makes a new cube from an existing cube, using a list of
        dimension indexes from an array. Can be used to extract the endpoints
        of a single dimension, or to drop dimensions, or to reorder them as
        desired.
       </para>
       <para>
        <literal>cube_subset(cube('(1,3,5),(6,7,8)'), ARRAY[2])</literal>
        <returnvalue>(3),(7)</returnvalue>
       </para>
       <para>
        <literal>cube_subset(cube('(1,3,5),(6,7,8)'), ARRAY[3,2,1,1])</literal>
        <returnvalue>(5, 3, 1, 1),(8, 7, 6, 6)</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube_union</function> ( <type>cube</type>, <type>cube</type> )
        <returnvalue>cube</returnvalue>
       </para>
       <para>
        Produces the union of two cubes.
       </para>
       <para>
        <literal>cube_union('(1,2)', '(3,4)')</literal>
        <returnvalue>(1, 2),(3, 4)</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube_inter</function> ( <type>cube</type>, <type>cube</type> )
        <returnvalue>cube</returnvalue>
       </para>
       <para>
        Produces the intersection of two cubes.
       </para>
       <para>
        <literal>cube_inter('(1,2)', '(3,4)')</literal>
        <returnvalue>(3, 4),(1, 2)</returnvalue>
       </para></entry>
      </row>

      <row>
       <entry role="func_table_entry"><para role="func_signature">
        <function>cube_enlarge</function> ( <parameter>c</parameter> <type>cube</type>, <parameter>r</parameter> <type>double</type>, <parameter>n</parameter> <type>integer</type> )
        <returnvalue>cube</returnvalue>
       </para>
       <para>
        Increases the size of the cube by the specified
        radius <parameter>r</parameter> in at least <parameter>n</parameter>
        dimensions.  If the radius is negative the cube is shrunk instead.
        All defined dimensions are changed by the
        radius <parameter>r</parameter>.  Lower-left coordinates are decreased
        by <parameter>r</parameter> and upper-right coordinates are increased
        by <parameter>r</parameter>.  If a lower-left coordinate is increased
        to more than the corresponding upper-right coordinate (this can only
        happen when <parameter>r</parameter> &lt; 0) than both coordinates are
        set to their average.  If <parameter>n</parameter> is greater than the
        number of defined dimensions and the cube is being enlarged
        (<parameter>r</parameter> &gt; 0), then extra dimensions are added to
        make <parameter>n</parameter> altogether; 0 is used as the initial
        value for the extra coordinates.  This function is useful for creating
        bounding boxes around a point for searching for nearby points.
       </para>
       <para>
        <literal>cube_enlarge('(1,2),(3,4)', 0.5, 3)</literal>
        <returnvalue>(0.5, 1.5, -0.5),(3.5, 4.5, 0.5)</returnvalue>
       </para></entry>
      </row>
     </tbody>
    </tgroup>
  </table>
 </sect2>

 <sect2>
  <title>Defaults</title>

  <para>
   I believe this union:
  </para>
<programlisting>
select cube_union('(0,5,2),(2,3,1)', '0');
cube_union
-------------------
(0, 0, 0),(2, 5, 2)
(1 row)
</programlisting>

   <para>
    does not contradict common sense, neither does the intersection
   </para>

<programlisting>
select cube_inter('(0,-1),(1,1)', '(-2),(2)');
cube_inter
-------------
(0, 0),(1, 0)
(1 row)
</programlisting>

   <para>
    In all binary operations on differently-dimensioned cubes, I assume the
    lower-dimensional one to be a Cartesian projection, i. e., having zeroes
    in place of coordinates omitted in the string representation. The above
    examples are equivalent to:
   </para>

<programlisting>
cube_union('(0,5,2),(2,3,1)','(0,0,0),(0,0,0)');
cube_inter('(0,-1),(1,1)','(-2,0),(2,0)');
</programlisting>

   <para>
    The following containment predicate uses the point syntax,
    while in fact the second argument is internally represented by a box.
    This syntax makes it unnecessary to define a separate point type
    and functions for (box,point) predicates.
   </para>

<programlisting>
select cube_contains('(0,0),(1,1)', '0.5,0.5');
cube_contains
--------------
t
(1 row)
</programlisting>
 </sect2>

 <sect2>
  <title>Notes</title>

  <para>
   For examples of usage, see the regression test <filename>sql/cube.sql</filename>.
  </para>

  <para>
   To make it harder for people to break things, there
   is a limit of 100 on the number of dimensions of cubes. This is set
   in <filename>cubedata.h</filename> if you need something bigger.
  </para>
 </sect2>

 <sect2>
  <title>Credits</title>

  <para>
   Original author: Gene Selkov, Jr. <email>selkovjr@mcs.anl.gov</email>,
   Mathematics and Computer Science Division, Argonne National Laboratory.
  </para>

  <para>
   My thanks are primarily to Prof. Joe Hellerstein
   (<ulink url="https://dsf.berkeley.edu/jmh/"></ulink>) for elucidating the
   gist of the GiST (<ulink url="http://gist.cs.berkeley.edu/"></ulink>), and
   to his former student Andy Dong for his example written for Illustra.
   I am also grateful to all Postgres developers, present and past, for
   enabling myself to create my own world and live undisturbed in it. And I
   would like to acknowledge my gratitude to Argonne Lab and to the
   U.S. Department of Energy for the years of faithful support of my database
   research.
  </para>

  <para>
   Minor updates to this package were made by Bruno Wolff III
   <email>bruno@wolff.to</email> in August/September of 2002. These include
   changing the precision from single precision to double precision and adding
   some new functions.
  </para>

  <para>
   Additional updates were made by Joshua Reich <email>josh@root.net</email> in
   July 2006. These include <literal>cube(float8[], float8[])</literal> and
   cleaning up the code to use the V1 call protocol instead of the deprecated
   V0 protocol.
  </para>
 </sect2>

</sect1>