1<!-- doc/src/sgml/cube.sgml --> 2 3<sect1 id="cube" xreflabel="cube"> 4 <title>cube</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> 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 — 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> 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> 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>&&</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>@></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><@</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>-></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>~></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><-></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><#></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><=></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 (Before PostgreSQL 8.2, the containment operators <literal>@></literal> and <literal><@</literal> were 227 respectively called <literal>@</literal> and <literal>~</literal>. These names are still available, but are 228 deprecated and will eventually be retired. Notice that the old names 229 are reversed from the convention formerly followed by the core geometric 230 data types!) 231 </para> 232 233 <para> 234 In addition to the above operators, the usual comparison 235 operators shown in <xref linkend="functions-comparison-op-table"/> are 236 available for type <type>cube</type>. These 237 operators first compare the first coordinates, and if those are equal, 238 compare the second coordinates, etc. They exist mainly to support the 239 b-tree index operator class for <type>cube</type>, which can be useful for 240 example if you would like a UNIQUE constraint on a <type>cube</type> column. 241 Otherwise, this ordering is not of much practical use. 242 </para> 243 244 <para> 245 The <filename>cube</filename> module also provides a GiST index operator class for 246 <type>cube</type> values. 247 A <type>cube</type> GiST index can be used to search for values using the 248 <literal>=</literal>, <literal>&&</literal>, <literal>@></literal>, and 249 <literal><@</literal> operators in <literal>WHERE</literal> clauses. 250 </para> 251 252 <para> 253 In addition, a <type>cube</type> GiST index can be used to find nearest 254 neighbors using the metric operators 255 <literal><-></literal>, <literal><#></literal>, and 256 <literal><=></literal> in <literal>ORDER BY</literal> clauses. 257 For example, the nearest neighbor of the 3-D point (0.5, 0.5, 0.5) 258 could be found efficiently with: 259<programlisting> 260SELECT c FROM test ORDER BY c <-> cube(array[0.5,0.5,0.5]) LIMIT 1; 261</programlisting> 262 </para> 263 264 <para> 265 The <literal>~></literal> operator can also be used in this way to 266 efficiently retrieve the first few values sorted by a selected coordinate. 267 For example, to get the first few cubes ordered by the first coordinate 268 (lower left corner) ascending one could use the following query: 269<programlisting> 270SELECT c FROM test ORDER BY c ~> 1 LIMIT 5; 271</programlisting> 272 And to get 2-D cubes ordered by the first coordinate of the upper right 273 corner descending: 274<programlisting> 275SELECT c FROM test ORDER BY c ~> 3 DESC LIMIT 5; 276</programlisting> 277 </para> 278 279 <para> 280 <xref linkend="cube-functions-table"/> shows the available functions. 281 </para> 282 283 <table id="cube-functions-table"> 284 <title>Cube Functions</title> 285 <tgroup cols="1"> 286 <thead> 287 <row> 288 <entry role="func_table_entry"><para role="func_signature"> 289 Function 290 </para> 291 <para> 292 Description 293 </para> 294 <para> 295 Example(s) 296 </para></entry> 297 </row> 298 </thead> 299 300 <tbody> 301 <row> 302 <entry role="func_table_entry"><para role="func_signature"> 303 <function>cube</function> ( <type>float8</type> ) 304 <returnvalue>cube</returnvalue> 305 </para> 306 <para> 307 Makes a one dimensional cube with both coordinates the same. 308 </para> 309 <para> 310 <literal>cube(1)</literal> 311 <returnvalue>(1)</returnvalue> 312 </para></entry> 313 </row> 314 315 <row> 316 <entry role="func_table_entry"><para role="func_signature"> 317 <function>cube</function> ( <type>float8</type>, <type>float8</type> ) 318 <returnvalue>cube</returnvalue> 319 </para> 320 <para> 321 Makes a one dimensional cube. 322 </para> 323 <para> 324 <literal>cube(1,2)</literal> 325 <returnvalue>(1),(2)</returnvalue> 326 </para></entry> 327 </row> 328 329 <row> 330 <entry role="func_table_entry"><para role="func_signature"> 331 <function>cube</function> ( <type>float8[]</type> ) 332 <returnvalue>cube</returnvalue> 333 </para> 334 <para> 335 Makes a zero-volume cube using the coordinates defined by the array. 336 </para> 337 <para> 338 <literal>cube(ARRAY[1,2,3])</literal> 339 <returnvalue>(1, 2, 3)</returnvalue> 340 </para></entry> 341 </row> 342 343 <row> 344 <entry role="func_table_entry"><para role="func_signature"> 345 <function>cube</function> ( <type>float8[]</type>, <type>float8[]</type> ) 346 <returnvalue>cube</returnvalue> 347 </para> 348 <para> 349 Makes a cube with upper right and lower left coordinates as defined by 350 the two arrays, which must be of the same length. 351 </para> 352 <para> 353 <literal>cube(ARRAY[1,2], ARRAY[3,4])</literal> 354 <returnvalue>(1, 2),(3, 4)</returnvalue> 355 </para></entry> 356 </row> 357 358 <row> 359 <entry role="func_table_entry"><para role="func_signature"> 360 <function>cube</function> ( <type>cube</type>, <type>float8</type> ) 361 <returnvalue>cube</returnvalue> 362 </para> 363 <para> 364 Makes a new cube by adding a dimension on to an existing cube, 365 with the same values for both endpoints of the new coordinate. This 366 is useful for building cubes piece by piece from calculated values. 367 </para> 368 <para> 369 <literal>cube('(1,2),(3,4)'::cube, 5)</literal> 370 <returnvalue>(1, 2, 5),(3, 4, 5)</returnvalue> 371 </para></entry> 372 </row> 373 374 <row> 375 <entry role="func_table_entry"><para role="func_signature"> 376 <function>cube</function> ( <type>cube</type>, <type>float8</type>, <type>float8</type> ) 377 <returnvalue>cube</returnvalue> 378 </para> 379 <para> 380 Makes a new cube by adding a dimension on to an existing cube. This is 381 useful for building cubes piece by piece from calculated values. 382 </para> 383 <para> 384 <literal>cube('(1,2),(3,4)'::cube, 5, 6)</literal> 385 <returnvalue>(1, 2, 5),(3, 4, 6)</returnvalue> 386 </para></entry> 387 </row> 388 389 <row> 390 <entry role="func_table_entry"><para role="func_signature"> 391 <function>cube_dim</function> ( <type>cube</type> ) 392 <returnvalue>integer</returnvalue> 393 </para> 394 <para> 395 Returns the number of dimensions of the cube. 396 </para> 397 <para> 398 <literal>cube_dim('(1,2),(3,4)')</literal> 399 <returnvalue>2</returnvalue> 400 </para></entry> 401 </row> 402 403 <row> 404 <entry role="func_table_entry"><para role="func_signature"> 405 <function>cube_ll_coord</function> ( <type>cube</type>, <type>integer</type> ) 406 <returnvalue>float8</returnvalue> 407 </para> 408 <para> 409 Returns the <parameter>n</parameter>-th coordinate value for the lower 410 left corner of the cube. 411 </para> 412 <para> 413 <literal>cube_ll_coord('(1,2),(3,4)', 2)</literal> 414 <returnvalue>2</returnvalue> 415 </para></entry> 416 </row> 417 418 <row> 419 <entry role="func_table_entry"><para role="func_signature"> 420 <function>cube_ur_coord</function> ( <type>cube</type>, <type>integer</type> ) 421 <returnvalue>float8</returnvalue> 422 </para> 423 <para> 424 Returns the <parameter>n</parameter>-th coordinate value for the 425 upper right corner of the cube. 426 </para> 427 <para> 428 <literal>cube_ur_coord('(1,2),(3,4)', 2)</literal> 429 <returnvalue>4</returnvalue> 430 </para></entry> 431 </row> 432 433 <row> 434 <entry role="func_table_entry"><para role="func_signature"> 435 <function>cube_is_point</function> ( <type>cube</type> ) 436 <returnvalue>boolean</returnvalue> 437 </para> 438 <para> 439 Returns true if the cube is a point, that is, 440 the two defining corners are the same. 441 </para> 442 <para> 443 <literal>cube_is_point(cube(1,1))</literal> 444 <returnvalue>t</returnvalue> 445 </para></entry> 446 </row> 447 448 <row> 449 <entry role="func_table_entry"><para role="func_signature"> 450 <function>cube_distance</function> ( <type>cube</type>, <type>cube</type> ) 451 <returnvalue>float8</returnvalue> 452 </para> 453 <para> 454 Returns the distance between two cubes. If both 455 cubes are points, this is the normal distance function. 456 </para> 457 <para> 458 <literal>cube_distance('(1,2)', '(3,4)')</literal> 459 <returnvalue>2.8284271247461903</returnvalue> 460 </para></entry> 461 </row> 462 463 <row> 464 <entry role="func_table_entry"><para role="func_signature"> 465 <function>cube_subset</function> ( <type>cube</type>, <type>integer[]</type> ) 466 <returnvalue>cube</returnvalue> 467 </para> 468 <para> 469 Makes a new cube from an existing cube, using a list of 470 dimension indexes from an array. Can be used to extract the endpoints 471 of a single dimension, or to drop dimensions, or to reorder them as 472 desired. 473 </para> 474 <para> 475 <literal>cube_subset(cube('(1,3,5),(6,7,8)'), ARRAY[2])</literal> 476 <returnvalue>(3),(7)</returnvalue> 477 </para> 478 <para> 479 <literal>cube_subset(cube('(1,3,5),(6,7,8)'), ARRAY[3,2,1,1])</literal> 480 <returnvalue>(5, 3, 1, 1),(8, 7, 6, 6)</returnvalue> 481 </para></entry> 482 </row> 483 484 <row> 485 <entry role="func_table_entry"><para role="func_signature"> 486 <function>cube_union</function> ( <type>cube</type>, <type>cube</type> ) 487 <returnvalue>cube</returnvalue> 488 </para> 489 <para> 490 Produces the union of two cubes. 491 </para> 492 <para> 493 <literal>cube_union('(1,2)', '(3,4)')</literal> 494 <returnvalue>(1, 2),(3, 4)</returnvalue> 495 </para></entry> 496 </row> 497 498 <row> 499 <entry role="func_table_entry"><para role="func_signature"> 500 <function>cube_inter</function> ( <type>cube</type>, <type>cube</type> ) 501 <returnvalue>cube</returnvalue> 502 </para> 503 <para> 504 Produces the intersection of two cubes. 505 </para> 506 <para> 507 <literal>cube_inter('(1,2)', '(3,4)')</literal> 508 <returnvalue>(3, 4),(1, 2)</returnvalue> 509 </para></entry> 510 </row> 511 512 <row> 513 <entry role="func_table_entry"><para role="func_signature"> 514 <function>cube_enlarge</function> ( <parameter>c</parameter> <type>cube</type>, <parameter>r</parameter> <type>double</type>, <parameter>n</parameter> <type>integer</type> ) 515 <returnvalue>cube</returnvalue> 516 </para> 517 <para> 518 Increases the size of the cube by the specified 519 radius <parameter>r</parameter> in at least <parameter>n</parameter> 520 dimensions. If the radius is negative the cube is shrunk instead. 521 All defined dimensions are changed by the 522 radius <parameter>r</parameter>. Lower-left coordinates are decreased 523 by <parameter>r</parameter> and upper-right coordinates are increased 524 by <parameter>r</parameter>. If a lower-left coordinate is increased 525 to more than the corresponding upper-right coordinate (this can only 526 happen when <parameter>r</parameter> < 0) than both coordinates are 527 set to their average. If <parameter>n</parameter> is greater than the 528 number of defined dimensions and the cube is being enlarged 529 (<parameter>r</parameter> > 0), then extra dimensions are added to 530 make <parameter>n</parameter> altogether; 0 is used as the initial 531 value for the extra coordinates. This function is useful for creating 532 bounding boxes around a point for searching for nearby points. 533 </para> 534 <para> 535 <literal>cube_enlarge('(1,2),(3,4)', 0.5, 3)</literal> 536 <returnvalue>(0.5, 1.5, -0.5),(3.5, 4.5, 0.5)</returnvalue> 537 </para></entry> 538 </row> 539 </tbody> 540 </tgroup> 541 </table> 542 </sect2> 543 544 <sect2> 545 <title>Defaults</title> 546 547 <para> 548 I believe this union: 549 </para> 550<programlisting> 551select cube_union('(0,5,2),(2,3,1)', '0'); 552cube_union 553------------------- 554(0, 0, 0),(2, 5, 2) 555(1 row) 556</programlisting> 557 558 <para> 559 does not contradict common sense, neither does the intersection 560 </para> 561 562<programlisting> 563select cube_inter('(0,-1),(1,1)', '(-2),(2)'); 564cube_inter 565------------- 566(0, 0),(1, 0) 567(1 row) 568</programlisting> 569 570 <para> 571 In all binary operations on differently-dimensioned cubes, I assume the 572 lower-dimensional one to be a Cartesian projection, i. e., having zeroes 573 in place of coordinates omitted in the string representation. The above 574 examples are equivalent to: 575 </para> 576 577<programlisting> 578cube_union('(0,5,2),(2,3,1)','(0,0,0),(0,0,0)'); 579cube_inter('(0,-1),(1,1)','(-2,0),(2,0)'); 580</programlisting> 581 582 <para> 583 The following containment predicate uses the point syntax, 584 while in fact the second argument is internally represented by a box. 585 This syntax makes it unnecessary to define a separate point type 586 and functions for (box,point) predicates. 587 </para> 588 589<programlisting> 590select cube_contains('(0,0),(1,1)', '0.5,0.5'); 591cube_contains 592-------------- 593t 594(1 row) 595</programlisting> 596 </sect2> 597 598 <sect2> 599 <title>Notes</title> 600 601 <para> 602 For examples of usage, see the regression test <filename>sql/cube.sql</filename>. 603 </para> 604 605 <para> 606 To make it harder for people to break things, there 607 is a limit of 100 on the number of dimensions of cubes. This is set 608 in <filename>cubedata.h</filename> if you need something bigger. 609 </para> 610 </sect2> 611 612 <sect2> 613 <title>Credits</title> 614 615 <para> 616 Original author: Gene Selkov, Jr. <email>selkovjr@mcs.anl.gov</email>, 617 Mathematics and Computer Science Division, Argonne National Laboratory. 618 </para> 619 620 <para> 621 My thanks are primarily to Prof. Joe Hellerstein 622 (<ulink url="https://dsf.berkeley.edu/jmh/"></ulink>) for elucidating the 623 gist of the GiST (<ulink url="http://gist.cs.berkeley.edu/"></ulink>), and 624 to his former student Andy Dong for his example written for Illustra. 625 I am also grateful to all Postgres developers, present and past, for 626 enabling myself to create my own world and live undisturbed in it. And I 627 would like to acknowledge my gratitude to Argonne Lab and to the 628 U.S. Department of Energy for the years of faithful support of my database 629 research. 630 </para> 631 632 <para> 633 Minor updates to this package were made by Bruno Wolff III 634 <email>bruno@wolff.to</email> in August/September of 2002. These include 635 changing the precision from single precision to double precision and adding 636 some new functions. 637 </para> 638 639 <para> 640 Additional updates were made by Joshua Reich <email>josh@root.net</email> in 641 July 2006. These include <literal>cube(float8[], float8[])</literal> and 642 cleaning up the code to use the V1 call protocol instead of the deprecated 643 V0 protocol. 644 </para> 645 </sect2> 646 647</sect1> 648