Skip to content

Commit f50c80d

Browse files
feodorfeodor
committed
llow negative coordinate for ~> (cube, int) operator
~> (cube, int) operator was especially designed for knn-gist search. However, knn-gist supports only ascending ordering of results. Nevertheless it would be useful to support descending ordering by ~> (cube, int) operator. We provide workaround for that: negative coordinate give us inversed value of corresponding cube bound. Therefore, knn search using negative coordinate gives us an effect of descending ordering by cube bound. Author: Alexander Korotkov Reviewed by: Tomas Vondra, Andrey Borodin Discussion: https://www.postgresql.org/message-id/flat/a9657f6a-b497-36ff-e56-482a2c7e3292@2ndquadrant.com
1 parent 563a053 commit f50c80d

File tree

5 files changed

+379
-14
lines changed

5 files changed

+379
-14
lines changed

‎contrib/cube/cube.c

Lines changed: 36 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1343,12 +1343,20 @@ g_cube_distance(PG_FUNCTION_ARGS)
13431343
*/
13441344
int coord = PG_GETARG_INT32(1);
13451345
bool isLeaf = GistPageIsLeaf(entry->page);
1346+
bool inverse = false;
13461347

13471348
/* 0 is the only unsupported coordinate value */
1348-
if (coord <= 0)
1349+
if (coord == 0)
13491350
ereport(ERROR,
13501351
(errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1351-
errmsg("cube index %d is out of bounds", coord)));
1352+
errmsg("zero cube index is not defined")));
1353+
1354+
/* Return inversed value for negative coordinate */
1355+
if (coord < 0)
1356+
{
1357+
coord = -coord;
1358+
inverse = true;
1359+
}
13521360

13531361
if (coord <= 2 * DIM(cube))
13541362
{
@@ -1376,16 +1384,25 @@ g_cube_distance(PG_FUNCTION_ARGS)
13761384
/*
13771385
* For non-leaf we should always return lower bound,
13781386
* because even upper bound of a child in the subtree can
1379-
* be as small as our lower bound.
1387+
* be as small as our lower bound. For inversed case we
1388+
* return upper bound because it becomes lower bound for
1389+
* inversed value.
13801390
*/
1381-
retval = Min(cube->x[index], cube->x[index + DIM(cube)]);
1391+
if (!inverse)
1392+
retval = Min(cube->x[index], cube->x[index + DIM(cube)]);
1393+
else
1394+
retval = Max(cube->x[index], cube->x[index + DIM(cube)]);
13821395
}
13831396
}
13841397
}
13851398
else
13861399
{
13871400
retval = 0.0;
13881401
}
1402+
1403+
/* Inverse return value if needed */
1404+
if (inverse)
1405+
retval = -retval;
13891406
}
13901407
else
13911408
{
@@ -1542,11 +1559,15 @@ cube_coord(PG_FUNCTION_ARGS)
15421559
* getter. Moreover, indexed dataset may contain cubes of different dimensions
15431560
* number. Accordingly, this coordinate getter should be able to return
15441561
* lower/upper bound for particular dimension independently on number of cube
1545-
* dimensions.
1562+
* dimensions. Also, KNN-GiST supports only ascending sorting. In order to
1563+
* support descending sorting, this function returns inverse of value when
1564+
* negative coordinate is given.
15461565
*
15471566
* Long story short, this function uses following meaning of coordinates:
15481567
* # (2 * N - 1) -- lower bound of Nth dimension,
1549-
* # (2 * N) -- upper bound of Nth dimension.
1568+
* # (2 * N) -- upper bound of Nth dimension,
1569+
* # - (2 * N - 1) -- negative of lower bound of Nth dimension,
1570+
* # - (2 * N) -- negative of upper bound of Nth dimension.
15501571
*
15511572
* When given coordinate exceeds number of cube dimensions, then 0 returned
15521573
* (reproducing logic of GiST indexing of variable-length cubes).
@@ -1560,10 +1581,17 @@ cube_coord_llur(PG_FUNCTION_ARGS)
15601581
float8 result;
15611582

15621583
/* 0 is the only unsupported coordinate value */
1563-
if (coord <= 0)
1584+
if (coord == 0)
15641585
ereport(ERROR,
15651586
(errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1566-
errmsg("cube index %d is out of bounds", coord)));
1587+
errmsg("zero cube index is not defined")));
1588+
1589+
/* Return inversed value for negative coordinate */
1590+
if (coord < 0)
1591+
{
1592+
coord = -coord;
1593+
inverse = true;
1594+
}
15671595

15681596
if (coord <= 2 * DIM(cube))
15691597
{

‎contrib/cube/expected/cube.out

Lines changed: 166 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1554,15 +1554,19 @@ SELECT cube(array[40,50,60], array[10,20,30])~>3;
15541554
(1 row)
15551555

15561556
SELECT cube(array[40,50,60], array[10,20,30])~>0;
1557-
ERROR: cube index 0 is out of bounds
1557+
ERROR: zero cube index is not defined
15581558
SELECT cube(array[40,50,60], array[10,20,30])~>4;
15591559
?column?
15601560
----------
15611561
50
15621562
(1 row)
15631563

15641564
SELECT cube(array[40,50,60], array[10,20,30])~>(-1);
1565-
ERROR: cube index -1 is out of bounds
1565+
?column?
1566+
----------
1567+
-10
1568+
(1 row)
1569+
15661570
-- Load some example data and build the index
15671571
--
15681572
CREATE TABLE test_cube (c cube);
@@ -1726,6 +1730,86 @@ SELECT c~>4, c FROM test_cube ORDER BY c~>4 LIMIT 15; -- ascending by upper boun
17261730
266 | (22684, 266),(22656, 181)
17271731
(15 rows)
17281732

1733+
SELECT c~>(-1), c FROM test_cube ORDER BY c~>(-1) LIMIT 15; -- descending by left bound
1734+
?column? | c
1735+
----------+-------------------------------
1736+
-100000 | (100000)
1737+
-49951 | (50027, 49230),(49951, 49214)
1738+
-49937 | (49980, 35004),(49937, 34963)
1739+
-49927 | (49985, 6436),(49927, 6338)
1740+
-49908 | (49999, 27218),(49908, 27176)
1741+
-49905 | (49954, 1340),(49905, 1294)
1742+
-49902 | (49944, 25163),(49902, 25153)
1743+
-49898 | (49981, 34876),(49898, 34786)
1744+
-49897 | (49957, 43390),(49897, 43384)
1745+
-49848 | (49853, 18504),(49848, 18503)
1746+
-49818 | (49902, 41752),(49818, 41746)
1747+
-49810 | (49907, 30225),(49810, 30158)
1748+
-49808 | (49843, 5175),(49808, 5145)
1749+
-49805 | (49887, 24274),(49805, 24184)
1750+
-49798 | (49847, 7128),(49798, 7067)
1751+
(15 rows)
1752+
1753+
SELECT c~>(-2), c FROM test_cube ORDER BY c~>(-2) LIMIT 15; -- descending by right bound
1754+
?column? | c
1755+
----------+-------------------------------
1756+
-100000 | (100000)
1757+
-50027 | (50027, 49230),(49951, 49214)
1758+
-49999 | (49999, 27218),(49908, 27176)
1759+
-49985 | (49985, 6436),(49927, 6338)
1760+
-49981 | (49981, 34876),(49898, 34786)
1761+
-49980 | (49980, 35004),(49937, 34963)
1762+
-49957 | (49957, 43390),(49897, 43384)
1763+
-49954 | (49954, 1340),(49905, 1294)
1764+
-49944 | (49944, 25163),(49902, 25153)
1765+
-49907 | (49907, 30225),(49810, 30158)
1766+
-49902 | (49902, 41752),(49818, 41746)
1767+
-49887 | (49887, 24274),(49805, 24184)
1768+
-49853 | (49853, 18504),(49848, 18503)
1769+
-49847 | (49847, 7128),(49798, 7067)
1770+
-49843 | (49843, 5175),(49808, 5145)
1771+
(15 rows)
1772+
1773+
SELECT c~>(-3), c FROM test_cube ORDER BY c~>(-3) LIMIT 15; -- descending by lower bound
1774+
?column? | c
1775+
----------+-------------------------------
1776+
-100000 | (0, 100000)
1777+
-49992 | (30746, 50040),(30727, 49992)
1778+
-49987 | (36311, 50073),(36258, 49987)
1779+
-49934 | (3531, 49962),(3463, 49934)
1780+
-49915 | (17954, 49975),(17865, 49915)
1781+
-49914 | (2168, 50012),(2108, 49914)
1782+
-49913 | (31287, 49923),(31236, 49913)
1783+
-49885 | (21551, 49983),(21492, 49885)
1784+
-49878 | (43925, 49912),(43888, 49878)
1785+
-49849 | (19128, 49932),(19112, 49849)
1786+
-49844 | (38266, 49852),(38233, 49844)
1787+
-49836 | (14913, 49873),(14849, 49836)
1788+
-49834 | (37595, 49849),(37581, 49834)
1789+
-49830 | (46151, 49848),(46058, 49830)
1790+
-49818 | (29261, 49910),(29247, 49818)
1791+
(15 rows)
1792+
1793+
SELECT c~>(-4), c FROM test_cube ORDER BY c~>(-4) LIMIT 15; -- descending by upper bound
1794+
?column? | c
1795+
----------+-------------------------------
1796+
-100000 | (0, 100000)
1797+
-50073 | (36311, 50073),(36258, 49987)
1798+
-50040 | (30746, 50040),(30727, 49992)
1799+
-50012 | (2168, 50012),(2108, 49914)
1800+
-49983 | (21551, 49983),(21492, 49885)
1801+
-49975 | (17954, 49975),(17865, 49915)
1802+
-49962 | (3531, 49962),(3463, 49934)
1803+
-49932 | (19128, 49932),(19112, 49849)
1804+
-49923 | (31287, 49923),(31236, 49913)
1805+
-49912 | (43925, 49912),(43888, 49878)
1806+
-49910 | (29261, 49910),(29247, 49818)
1807+
-49873 | (14913, 49873),(14849, 49836)
1808+
-49858 | (20007, 49858),(19921, 49778)
1809+
-49852 | (38266, 49852),(38233, 49844)
1810+
-49849 | (37595, 49849),(37581, 49834)
1811+
(15 rows)
1812+
17291813
-- Same queries with sequential scan (should give the same results as above)
17301814
RESET enable_seqscan;
17311815
SET enable_indexscan = OFF;
@@ -1839,4 +1923,84 @@ SELECT c~>4, c FROM test_cube ORDER BY c~>4 LIMIT 15; -- ascending by upper boun
18391923
266 | (22684, 266),(22656, 181)
18401924
(15 rows)
18411925

1926+
SELECT c~>(-1), c FROM test_cube ORDER BY c~>(-1) LIMIT 15; -- descending by left bound
1927+
?column? | c
1928+
----------+-------------------------------
1929+
-100000 | (100000)
1930+
-49951 | (50027, 49230),(49951, 49214)
1931+
-49937 | (49980, 35004),(49937, 34963)
1932+
-49927 | (49985, 6436),(49927, 6338)
1933+
-49908 | (49999, 27218),(49908, 27176)
1934+
-49905 | (49954, 1340),(49905, 1294)
1935+
-49902 | (49944, 25163),(49902, 25153)
1936+
-49898 | (49981, 34876),(49898, 34786)
1937+
-49897 | (49957, 43390),(49897, 43384)
1938+
-49848 | (49853, 18504),(49848, 18503)
1939+
-49818 | (49902, 41752),(49818, 41746)
1940+
-49810 | (49907, 30225),(49810, 30158)
1941+
-49808 | (49843, 5175),(49808, 5145)
1942+
-49805 | (49887, 24274),(49805, 24184)
1943+
-49798 | (49847, 7128),(49798, 7067)
1944+
(15 rows)
1945+
1946+
SELECT c~>(-2), c FROM test_cube ORDER BY c~>(-2) LIMIT 15; -- descending by right bound
1947+
?column? | c
1948+
----------+-------------------------------
1949+
-100000 | (100000)
1950+
-50027 | (50027, 49230),(49951, 49214)
1951+
-49999 | (49999, 27218),(49908, 27176)
1952+
-49985 | (49985, 6436),(49927, 6338)
1953+
-49981 | (49981, 34876),(49898, 34786)
1954+
-49980 | (49980, 35004),(49937, 34963)
1955+
-49957 | (49957, 43390),(49897, 43384)
1956+
-49954 | (49954, 1340),(49905, 1294)
1957+
-49944 | (49944, 25163),(49902, 25153)
1958+
-49907 | (49907, 30225),(49810, 30158)
1959+
-49902 | (49902, 41752),(49818, 41746)
1960+
-49887 | (49887, 24274),(49805, 24184)
1961+
-49853 | (49853, 18504),(49848, 18503)
1962+
-49847 | (49847, 7128),(49798, 7067)
1963+
-49843 | (49843, 5175),(49808, 5145)
1964+
(15 rows)
1965+
1966+
SELECT c~>(-3), c FROM test_cube ORDER BY c~>(-3) LIMIT 15; -- descending by lower bound
1967+
?column? | c
1968+
----------+-------------------------------
1969+
-100000 | (0, 100000)
1970+
-49992 | (30746, 50040),(30727, 49992)
1971+
-49987 | (36311, 50073),(36258, 49987)
1972+
-49934 | (3531, 49962),(3463, 49934)
1973+
-49915 | (17954, 49975),(17865, 49915)
1974+
-49914 | (2168, 50012),(2108, 49914)
1975+
-49913 | (31287, 49923),(31236, 49913)
1976+
-49885 | (21551, 49983),(21492, 49885)
1977+
-49878 | (43925, 49912),(43888, 49878)
1978+
-49849 | (19128, 49932),(19112, 49849)
1979+
-49844 | (38266, 49852),(38233, 49844)
1980+
-49836 | (14913, 49873),(14849, 49836)
1981+
-49834 | (37595, 49849),(37581, 49834)
1982+
-49830 | (46151, 49848),(46058, 49830)
1983+
-49818 | (29261, 49910),(29247, 49818)
1984+
(15 rows)
1985+
1986+
SELECT c~>(-4), c FROM test_cube ORDER BY c~>(-4) LIMIT 15; -- descending by upper bound
1987+
?column? | c
1988+
----------+-------------------------------
1989+
-100000 | (0, 100000)
1990+
-50073 | (36311, 50073),(36258, 49987)
1991+
-50040 | (30746, 50040),(30727, 49992)
1992+
-50012 | (2168, 50012),(2108, 49914)
1993+
-49983 | (21551, 49983),(21492, 49885)
1994+
-49975 | (17954, 49975),(17865, 49915)
1995+
-49962 | (3531, 49962),(3463, 49934)
1996+
-49932 | (19128, 49932),(19112, 49849)
1997+
-49923 | (31287, 49923),(31236, 49913)
1998+
-49912 | (43925, 49912),(43888, 49878)
1999+
-49910 | (29261, 49910),(29247, 49818)
2000+
-49873 | (14913, 49873),(14849, 49836)
2001+
-49858 | (20007, 49858),(19921, 49778)
2002+
-49852 | (38266, 49852),(38233, 49844)
2003+
-49849 | (37595, 49849),(37581, 49834)
2004+
(15 rows)
2005+
18422006
RESET enable_indexscan;

0 commit comments

Comments
 (0)