Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf50c80d

Browse files
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. Neverthelessit would be useful to support descending ordering by ~> (cube, int) operator.We provide workaround for that: negative coordinate give us inversed valueof corresponding cube bound. Therefore, knn search using negative coordinategives us an effect of descending ordering by cube bound.Author: Alexander KorotkovReviewed by: Tomas Vondra, Andrey BorodinDiscussion:https://www.postgresql.org/message-id/flat/a9657f6a-b497-36ff-e56-482a2c7e3292@2ndquadrant.com
1 parent563a053 commitf50c80d

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
intcoord=PG_GETARG_INT32(1);
13451345
boolisLeaf=GistPageIsLeaf(entry->page);
1346+
boolinverse= 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
float8result;
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 index0isout of bounds
1557+
ERROR:zerocube index isnot 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)
[8]ページ先頭
©2009-2025 Movatter.jp