diff --git a/src/test/regress/expected/btree_index.out b/src/test/regress/expected/btree_index.out index 0bd48dc..a8ed9da 100644 --- a/src/test/regress/expected/btree_index.out +++ b/src/test/regress/expected/btree_index.out @@ -179,3 +179,782 @@ select reloptions from pg_class WHERE oid = 'btree_idx1'::regclass; {vacuum_cleanup_index_scale_factor=70.0} (1 row) +--- +--- Test B-tree distance ordering +--- +SET enable_bitmapscan = OFF; +-- temporarily disable bt_i4_index index on bt_i4_heap(seqno) +UPDATE pg_index SET indisvalid = false WHERE indexrelid = 'bt_i4_index'::regclass; +CREATE INDEX bt_i4_heap_random_idx ON bt_i4_heap USING btree(random, seqno); +-- test unsupported orderings (by non-first index attribute or by more than one order keys) +EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY seqno <-> 0; + QUERY PLAN +------------------------------ + Sort + Sort Key: ((seqno <-> 0)) + -> Seq Scan on bt_i4_heap +(3 rows) + +EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY random <-> 0, seqno <-> 0; + QUERY PLAN +----------------------------------------------- + Sort + Sort Key: ((random <-> 0)), ((seqno <-> 0)) + -> Seq Scan on bt_i4_heap +(3 rows) + +EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY random <-> 0, random <-> 1; + QUERY PLAN +------------------------------------------------ + Sort + Sort Key: ((random <-> 0)), ((random <-> 1)) + -> Seq Scan on bt_i4_heap +(3 rows) + +EXPLAIN (COSTS OFF) +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 4000000; + QUERY PLAN +------------------------------------------------------------------------------- + Index Only Scan using bt_i4_heap_random_idx on bt_i4_heap + Index Cond: ((random > 1000000) AND (ROW(random, seqno) < ROW(6000000, 0))) + Order By: (random <-> 4000000) +(3 rows) + +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 4000000; + seqno | random +-------+--------- + 6448 | 4157193 + 9004 | 3783884 + 4408 | 4488889 + 8391 | 4825069 + 8984 | 3148979 + 1829 | 3053937 + 6262 | 3013326 + 5380 | 3000193 + 9142 | 2847247 + 8411 | 2809541 + 2859 | 5224694 + 6320 | 5257716 + 2126 | 2648497 + 8729 | 5450460 + 6862 | 5556001 + 1836 | 5593978 + 2681 | 2321799 + 2893 | 1919087 + 210 | 1809552 +(19 rows) + +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 10000000; + seqno | random +-------+--------- + 1836 | 5593978 + 6862 | 5556001 + 8729 | 5450460 + 6320 | 5257716 + 2859 | 5224694 + 8391 | 4825069 + 4408 | 4488889 + 6448 | 4157193 + 9004 | 3783884 + 8984 | 3148979 + 1829 | 3053937 + 6262 | 3013326 + 5380 | 3000193 + 9142 | 2847247 + 8411 | 2809541 + 2126 | 2648497 + 2681 | 2321799 + 2893 | 1919087 + 210 | 1809552 +(19 rows) + +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 0; + seqno | random +-------+--------- + 210 | 1809552 + 2893 | 1919087 + 2681 | 2321799 + 2126 | 2648497 + 8411 | 2809541 + 9142 | 2847247 + 5380 | 3000193 + 6262 | 3013326 + 1829 | 3053937 + 8984 | 3148979 + 9004 | 3783884 + 6448 | 4157193 + 4408 | 4488889 + 8391 | 4825069 + 2859 | 5224694 + 6320 | 5257716 + 8729 | 5450460 + 6862 | 5556001 + 1836 | 5593978 +(19 rows) + +EXPLAIN (COSTS OFF) +SELECT * FROM bt_i4_heap +WHERE + random > 1000000 AND (random, seqno) < (6000000, 0) AND + random IN (1809552, 1919087, 2321799, 2648497, 3000193, 3013326, 4157193, 4488889, 5257716, 5593978, NULL) +ORDER BY random <-> 3000000; + QUERY PLAN +-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- + Index Only Scan using bt_i4_heap_random_idx on bt_i4_heap + Index Cond: ((random > 1000000) AND (ROW(random, seqno) < ROW(6000000, 0)) AND (random = ANY ('{1809552,1919087,2321799,2648497,3000193,3013326,4157193,4488889,5257716,5593978,NULL}'::integer[]))) + Order By: (random <-> 3000000) +(3 rows) + +SELECT * FROM bt_i4_heap +WHERE + random > 1000000 AND (random, seqno) < (6000000, 0) AND + random IN (1809552, 1919087, 2321799, 2648497, 3000193, 3013326, 4157193, 4488889, 5257716, 5593978, NULL) +ORDER BY random <-> 3000000; + seqno | random +-------+--------- + 5380 | 3000193 + 6262 | 3013326 + 2126 | 2648497 + 2681 | 2321799 + 2893 | 1919087 + 6448 | 4157193 + 210 | 1809552 + 4408 | 4488889 + 6320 | 5257716 + 1836 | 5593978 +(10 rows) + +DROP INDEX bt_i4_heap_random_idx; +CREATE INDEX bt_i4_heap_random_idx ON bt_i4_heap USING btree(random DESC, seqno); +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 4000000; + seqno | random +-------+--------- + 6448 | 4157193 + 9004 | 3783884 + 4408 | 4488889 + 8391 | 4825069 + 8984 | 3148979 + 1829 | 3053937 + 6262 | 3013326 + 5380 | 3000193 + 9142 | 2847247 + 8411 | 2809541 + 2859 | 5224694 + 6320 | 5257716 + 2126 | 2648497 + 8729 | 5450460 + 6862 | 5556001 + 1836 | 5593978 + 2681 | 2321799 + 2893 | 1919087 + 210 | 1809552 +(19 rows) + +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 10000000; + seqno | random +-------+--------- + 1836 | 5593978 + 6862 | 5556001 + 8729 | 5450460 + 6320 | 5257716 + 2859 | 5224694 + 8391 | 4825069 + 4408 | 4488889 + 6448 | 4157193 + 9004 | 3783884 + 8984 | 3148979 + 1829 | 3053937 + 6262 | 3013326 + 5380 | 3000193 + 9142 | 2847247 + 8411 | 2809541 + 2126 | 2648497 + 2681 | 2321799 + 2893 | 1919087 + 210 | 1809552 +(19 rows) + +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 0; + seqno | random +-------+--------- + 210 | 1809552 + 2893 | 1919087 + 2681 | 2321799 + 2126 | 2648497 + 8411 | 2809541 + 9142 | 2847247 + 5380 | 3000193 + 6262 | 3013326 + 1829 | 3053937 + 8984 | 3148979 + 9004 | 3783884 + 6448 | 4157193 + 4408 | 4488889 + 8391 | 4825069 + 2859 | 5224694 + 6320 | 5257716 + 8729 | 5450460 + 6862 | 5556001 + 1836 | 5593978 +(19 rows) + +DROP INDEX bt_i4_heap_random_idx; +-- test parallel KNN scan +-- Serializable isolation would disable parallel query, so explicitly use an +-- arbitrary other level. +BEGIN ISOLATION LEVEL REPEATABLE READ; +SET parallel_setup_cost = 0; +SET parallel_tuple_cost = 0; +SET min_parallel_table_scan_size = 0; +SET max_parallel_workers = 4; +SET max_parallel_workers_per_gather = 4; +SET cpu_operator_cost = 0; +RESET enable_indexscan; +CREATE TABLE bt_knn_test AS SELECT i * 10 AS i FROM generate_series(1, 1000000) i; +CREATE INDEX bt_knn_test_idx ON bt_knn_test (i); +ALTER TABLE bt_knn_test SET (parallel_workers = 4); +ANALYZE bt_knn_test; +EXPLAIN (COSTS OFF) +SELECT i FROM bt_knn_test WHERE i > 8000000; + QUERY PLAN +--------------------------------------------------------------------- + Gather + Workers Planned: 4 + -> Parallel Index Only Scan using bt_knn_test_idx on bt_knn_test + Index Cond: (i > 8000000) +(4 rows) + +CREATE TABLE bt_knn_test2 AS + SELECT row_number() OVER (ORDER BY i * 10 <-> 4000003) AS n, i * 10 AS i + FROM generate_series(1, 1000000) i; +EXPLAIN (COSTS OFF) +WITH bt_knn_test1 AS ( + SELECT row_number() OVER () AS n, i + FROM bt_knn_test + ORDER BY i <-> 4000003 +) +SELECT * FROM bt_knn_test1 t1 JOIN bt_knn_test2 t2 USING (n) WHERE t1.i <> t2.i; + QUERY PLAN +----------------------------------------------------------------------------------- + Hash Join + Hash Cond: (t2.n = t1.n) + Join Filter: (t1.i <> t2.i) + CTE bt_knn_test1 + -> WindowAgg + -> Gather Merge + Workers Planned: 4 + -> Parallel Index Only Scan using bt_knn_test_idx on bt_knn_test + Order By: (i <-> 4000003) + -> Seq Scan on bt_knn_test2 t2 + -> Hash + -> CTE Scan on bt_knn_test1 t1 +(12 rows) + +WITH bt_knn_test1 AS ( + SELECT row_number() OVER () AS n, i + FROM bt_knn_test + ORDER BY i <-> 4000003 +) +SELECT * FROM bt_knn_test1 t1 JOIN bt_knn_test2 t2 USING (n) WHERE t1.i <> t2.i; + n | i | i +---+---+--- +(0 rows) + +DROP TABLE bt_knn_test; +CREATE TABLE bt_knn_test AS SELECT i FROM generate_series(1, 10) i, generate_series(1, 100000) j; +CREATE INDEX bt_knn_test_idx ON bt_knn_test (i); +ALTER TABLE bt_knn_test SET (parallel_workers = 4); +ANALYZE bt_knn_test; +EXPLAIN (COSTS OFF) +WITH +t1 AS ( + SELECT row_number() OVER () AS n, i + FROM bt_knn_test + WHERE i IN (3, 4, 7, 8, 2) + ORDER BY i <-> 4 +), +t2 AS ( + SELECT i * 100000 + j AS n, (ARRAY[4, 3, 2, 7, 8])[i + 1] AS i + FROM generate_series(0, 4) i, generate_series(1, 100000) j +) +SELECT * FROM t1 JOIN t2 USING (n) WHERE t1.i <> t2.i; + QUERY PLAN +----------------------------------------------------------------------------------- + Hash Join + Hash Cond: (t2.n = t1.n) + Join Filter: (t1.i <> t2.i) + CTE t1 + -> WindowAgg + -> Gather Merge + Workers Planned: 4 + -> Parallel Index Only Scan using bt_knn_test_idx on bt_knn_test + Index Cond: (i = ANY ('{3,4,7,8,2}'::integer[])) + Order By: (i <-> 4) + CTE t2 + -> Nested Loop + -> Function Scan on generate_series i + -> Function Scan on generate_series j + -> CTE Scan on t2 + -> Hash + -> CTE Scan on t1 +(17 rows) + +WITH +t1 AS ( + SELECT row_number() OVER () AS n, i + FROM bt_knn_test + WHERE i IN (3, 4, 7, 8, 2) + ORDER BY i <-> 4 +), +t2 AS ( + SELECT i * 100000 + j AS n, (ARRAY[4, 3, 2, 7, 8])[i + 1] AS i + FROM generate_series(0, 4) i, generate_series(1, 100000) j +) +SELECT * FROM t1 JOIN t2 USING (n) WHERE t1.i <> t2.i; + n | i | i +---+---+--- +(0 rows) + +RESET parallel_setup_cost; +RESET parallel_tuple_cost; +RESET min_parallel_table_scan_size; +RESET max_parallel_workers; +RESET max_parallel_workers_per_gather; +RESET cpu_operator_cost; +ROLLBACK; +-- enable bt_i4_index index on bt_i4_heap(seqno) +UPDATE pg_index SET indisvalid = true WHERE indexrelid = 'bt_i4_index'::regclass; +CREATE TABLE tenk3 AS SELECT thousand, tenthous FROM tenk1; +INSERT INTO tenk3 VALUES (NULL, 1), (NULL, 2), (NULL, 3); +-- Test distance ordering by ASC index +CREATE INDEX tenk3_idx ON tenk3 USING btree(thousand, tenthous); +EXPLAIN (COSTS OFF) +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) +ORDER BY thousand <-> 998; + QUERY PLAN +----------------------------------------------------------- + Index Only Scan using tenk3_idx on tenk3 + Index Cond: (ROW(thousand, tenthous) >= ROW(997, 5000)) + Order By: (thousand <-> 998) +(3 rows) + +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) +ORDER BY thousand <-> 998; + thousand | tenthous +----------+---------- + 998 | 998 + 998 | 1998 + 998 | 2998 + 998 | 3998 + 998 | 4998 + 998 | 5998 + 998 | 6998 + 998 | 7998 + 998 | 8998 + 998 | 9998 + 999 | 999 + 999 | 1999 + 999 | 2999 + 999 | 3999 + 999 | 4999 + 999 | 5999 + 999 | 6999 + 999 | 7999 + 999 | 8999 + 999 | 9999 + 997 | 9997 + 997 | 8997 + 997 | 7997 + 997 | 6997 + 997 | 5997 +(25 rows) + +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) +ORDER BY thousand <-> 0; + thousand | tenthous +----------+---------- + 997 | 5997 + 997 | 6997 + 997 | 7997 + 997 | 8997 + 997 | 9997 + 998 | 998 + 998 | 1998 + 998 | 2998 + 998 | 3998 + 998 | 4998 + 998 | 5998 + 998 | 6998 + 998 | 7998 + 998 | 8998 + 998 | 9998 + 999 | 999 + 999 | 1999 + 999 | 2999 + 999 | 3999 + 999 | 4999 + 999 | 5999 + 999 | 6999 + 999 | 7999 + 999 | 8999 + 999 | 9999 +(25 rows) + +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) AND thousand < 1000 +ORDER BY thousand <-> 10000; + thousand | tenthous +----------+---------- + 999 | 9999 + 999 | 8999 + 999 | 7999 + 999 | 6999 + 999 | 5999 + 999 | 4999 + 999 | 3999 + 999 | 2999 + 999 | 1999 + 999 | 999 + 998 | 9998 + 998 | 8998 + 998 | 7998 + 998 | 6998 + 998 | 5998 + 998 | 4998 + 998 | 3998 + 998 | 2998 + 998 | 1998 + 998 | 998 + 997 | 9997 + 997 | 8997 + 997 | 7997 + 997 | 6997 + 997 | 5997 +(25 rows) + +SELECT thousand, tenthous FROM tenk3 +ORDER BY thousand <-> 500 +OFFSET 9970; + thousand | tenthous +----------+---------- + 999 | 999 + 999 | 1999 + 999 | 2999 + 999 | 3999 + 999 | 4999 + 999 | 5999 + 999 | 6999 + 999 | 7999 + 999 | 8999 + 999 | 9999 + 1 | 9001 + 1 | 8001 + 1 | 7001 + 1 | 6001 + 1 | 5001 + 1 | 4001 + 1 | 3001 + 1 | 2001 + 1 | 1001 + 1 | 1 + 0 | 9000 + 0 | 8000 + 0 | 7000 + 0 | 6000 + 0 | 5000 + 0 | 4000 + 0 | 3000 + 0 | 2000 + 0 | 1000 + 0 | 0 + | 1 + | 2 + | 3 +(33 rows) + +EXPLAIN (COSTS OFF) +SELECT * FROM tenk3 +WHERE thousand > 100 AND thousand < 800 AND + thousand = ANY(ARRAY[0, 123, 234, 345, 456, 678, 901, NULL]::int2[]) +ORDER BY thousand <-> 300::int8; + QUERY PLAN +----------------------------------------------------------------------------------------------------------------------------- + Index Only Scan using tenk3_idx on tenk3 + Index Cond: ((thousand > 100) AND (thousand < 800) AND (thousand = ANY ('{0,123,234,345,456,678,901,NULL}'::smallint[]))) + Order By: (thousand <-> '300'::bigint) +(3 rows) + +SELECT * FROM tenk3 +WHERE thousand > 100 AND thousand < 800 AND + thousand = ANY(ARRAY[0, 123, 234, 345, 456, 678, 901, NULL]::int2[]) +ORDER BY thousand <-> 300::int8; + thousand | tenthous +----------+---------- + 345 | 345 + 345 | 1345 + 345 | 2345 + 345 | 3345 + 345 | 4345 + 345 | 5345 + 345 | 6345 + 345 | 7345 + 345 | 8345 + 345 | 9345 + 234 | 234 + 234 | 1234 + 234 | 2234 + 234 | 3234 + 234 | 4234 + 234 | 5234 + 234 | 6234 + 234 | 7234 + 234 | 8234 + 234 | 9234 + 456 | 456 + 456 | 1456 + 456 | 2456 + 456 | 3456 + 456 | 4456 + 456 | 5456 + 456 | 6456 + 456 | 7456 + 456 | 8456 + 456 | 9456 + 123 | 123 + 123 | 1123 + 123 | 2123 + 123 | 3123 + 123 | 4123 + 123 | 5123 + 123 | 6123 + 123 | 7123 + 123 | 8123 + 123 | 9123 + 678 | 678 + 678 | 1678 + 678 | 2678 + 678 | 3678 + 678 | 4678 + 678 | 5678 + 678 | 6678 + 678 | 7678 + 678 | 8678 + 678 | 9678 +(50 rows) + +DROP INDEX tenk3_idx; +-- Test distance ordering by DESC index +CREATE INDEX tenk3_idx ON tenk3 USING btree(thousand DESC, tenthous); +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) +ORDER BY thousand <-> 998; + thousand | tenthous +----------+---------- + 998 | 998 + 998 | 1998 + 998 | 2998 + 998 | 3998 + 998 | 4998 + 998 | 5998 + 998 | 6998 + 998 | 7998 + 998 | 8998 + 998 | 9998 + 997 | 5997 + 997 | 6997 + 997 | 7997 + 997 | 8997 + 997 | 9997 + 999 | 9999 + 999 | 8999 + 999 | 7999 + 999 | 6999 + 999 | 5999 + 999 | 4999 + 999 | 3999 + 999 | 2999 + 999 | 1999 + 999 | 999 +(25 rows) + +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) +ORDER BY thousand <-> 0; + thousand | tenthous +----------+---------- + 997 | 9997 + 997 | 8997 + 997 | 7997 + 997 | 6997 + 997 | 5997 + 998 | 9998 + 998 | 8998 + 998 | 7998 + 998 | 6998 + 998 | 5998 + 998 | 4998 + 998 | 3998 + 998 | 2998 + 998 | 1998 + 998 | 998 + 999 | 9999 + 999 | 8999 + 999 | 7999 + 999 | 6999 + 999 | 5999 + 999 | 4999 + 999 | 3999 + 999 | 2999 + 999 | 1999 + 999 | 999 +(25 rows) + +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) AND thousand < 1000 +ORDER BY thousand <-> 10000; + thousand | tenthous +----------+---------- + 999 | 999 + 999 | 1999 + 999 | 2999 + 999 | 3999 + 999 | 4999 + 999 | 5999 + 999 | 6999 + 999 | 7999 + 999 | 8999 + 999 | 9999 + 998 | 998 + 998 | 1998 + 998 | 2998 + 998 | 3998 + 998 | 4998 + 998 | 5998 + 998 | 6998 + 998 | 7998 + 998 | 8998 + 998 | 9998 + 997 | 5997 + 997 | 6997 + 997 | 7997 + 997 | 8997 + 997 | 9997 +(25 rows) + +SELECT thousand, tenthous FROM tenk3 +ORDER BY thousand <-> 500 +OFFSET 9970; + thousand | tenthous +----------+---------- + 1 | 1 + 1 | 1001 + 1 | 2001 + 1 | 3001 + 1 | 4001 + 1 | 5001 + 1 | 6001 + 1 | 7001 + 1 | 8001 + 1 | 9001 + 999 | 9999 + 999 | 8999 + 999 | 7999 + 999 | 6999 + 999 | 5999 + 999 | 4999 + 999 | 3999 + 999 | 2999 + 999 | 1999 + 999 | 999 + 0 | 0 + 0 | 1000 + 0 | 2000 + 0 | 3000 + 0 | 4000 + 0 | 5000 + 0 | 6000 + 0 | 7000 + 0 | 8000 + 0 | 9000 + | 3 + | 2 + | 1 +(33 rows) + +DROP INDEX tenk3_idx; +DROP TABLE tenk3; +-- Test distance ordering on by-ref types +CREATE TABLE knn_btree_ts (ts timestamp); +INSERT INTO knn_btree_ts +SELECT timestamp '2017-05-03 00:00:00' + tenthous * interval '1 hour' +FROM tenk1; +CREATE INDEX knn_btree_ts_idx ON knn_btree_ts USING btree(ts); +SELECT ts, ts <-> timestamp '2017-05-01 00:00:00' FROM knn_btree_ts ORDER BY 2 LIMIT 20; + ts | ?column? +--------------------------+------------------- + Wed May 03 00:00:00 2017 | @ 2 days + Wed May 03 01:00:00 2017 | @ 2 days 1 hour + Wed May 03 02:00:00 2017 | @ 2 days 2 hours + Wed May 03 03:00:00 2017 | @ 2 days 3 hours + Wed May 03 04:00:00 2017 | @ 2 days 4 hours + Wed May 03 05:00:00 2017 | @ 2 days 5 hours + Wed May 03 06:00:00 2017 | @ 2 days 6 hours + Wed May 03 07:00:00 2017 | @ 2 days 7 hours + Wed May 03 08:00:00 2017 | @ 2 days 8 hours + Wed May 03 09:00:00 2017 | @ 2 days 9 hours + Wed May 03 10:00:00 2017 | @ 2 days 10 hours + Wed May 03 11:00:00 2017 | @ 2 days 11 hours + Wed May 03 12:00:00 2017 | @ 2 days 12 hours + Wed May 03 13:00:00 2017 | @ 2 days 13 hours + Wed May 03 14:00:00 2017 | @ 2 days 14 hours + Wed May 03 15:00:00 2017 | @ 2 days 15 hours + Wed May 03 16:00:00 2017 | @ 2 days 16 hours + Wed May 03 17:00:00 2017 | @ 2 days 17 hours + Wed May 03 18:00:00 2017 | @ 2 days 18 hours + Wed May 03 19:00:00 2017 | @ 2 days 19 hours +(20 rows) + +SELECT ts, ts <-> timestamp '2018-01-01 00:00:00' FROM knn_btree_ts ORDER BY 2 LIMIT 20; + ts | ?column? +--------------------------+------------ + Mon Jan 01 00:00:00 2018 | @ 0 + Mon Jan 01 01:00:00 2018 | @ 1 hour + Sun Dec 31 23:00:00 2017 | @ 1 hour + Mon Jan 01 02:00:00 2018 | @ 2 hours + Sun Dec 31 22:00:00 2017 | @ 2 hours + Mon Jan 01 03:00:00 2018 | @ 3 hours + Sun Dec 31 21:00:00 2017 | @ 3 hours + Mon Jan 01 04:00:00 2018 | @ 4 hours + Sun Dec 31 20:00:00 2017 | @ 4 hours + Mon Jan 01 05:00:00 2018 | @ 5 hours + Sun Dec 31 19:00:00 2017 | @ 5 hours + Mon Jan 01 06:00:00 2018 | @ 6 hours + Sun Dec 31 18:00:00 2017 | @ 6 hours + Mon Jan 01 07:00:00 2018 | @ 7 hours + Sun Dec 31 17:00:00 2017 | @ 7 hours + Mon Jan 01 08:00:00 2018 | @ 8 hours + Sun Dec 31 16:00:00 2017 | @ 8 hours + Mon Jan 01 09:00:00 2018 | @ 9 hours + Sun Dec 31 15:00:00 2017 | @ 9 hours + Mon Jan 01 10:00:00 2018 | @ 10 hours +(20 rows) + +DROP TABLE knn_btree_ts; +RESET enable_bitmapscan; diff --git a/src/test/regress/sql/btree_index.sql b/src/test/regress/sql/btree_index.sql index 21171f7..307f2f5 100644 --- a/src/test/regress/sql/btree_index.sql +++ b/src/test/regress/sql/btree_index.sql @@ -111,3 +111,235 @@ create index btree_idx_err on btree_test(a) with (vacuum_cleanup_index_scale_fac -- Simple ALTER INDEX alter index btree_idx1 set (vacuum_cleanup_index_scale_factor = 70.0); select reloptions from pg_class WHERE oid = 'btree_idx1'::regclass; + +--- +--- Test B-tree distance ordering +--- + +SET enable_bitmapscan = OFF; + +-- temporarily disable bt_i4_index index on bt_i4_heap(seqno) +UPDATE pg_index SET indisvalid = false WHERE indexrelid = 'bt_i4_index'::regclass; + +CREATE INDEX bt_i4_heap_random_idx ON bt_i4_heap USING btree(random, seqno); + +-- test unsupported orderings (by non-first index attribute or by more than one order keys) +EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY seqno <-> 0; +EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY random <-> 0, seqno <-> 0; +EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY random <-> 0, random <-> 1; + +EXPLAIN (COSTS OFF) +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 4000000; + +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 4000000; + +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 10000000; + +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 0; + +EXPLAIN (COSTS OFF) +SELECT * FROM bt_i4_heap +WHERE + random > 1000000 AND (random, seqno) < (6000000, 0) AND + random IN (1809552, 1919087, 2321799, 2648497, 3000193, 3013326, 4157193, 4488889, 5257716, 5593978, NULL) +ORDER BY random <-> 3000000; + +SELECT * FROM bt_i4_heap +WHERE + random > 1000000 AND (random, seqno) < (6000000, 0) AND + random IN (1809552, 1919087, 2321799, 2648497, 3000193, 3013326, 4157193, 4488889, 5257716, 5593978, NULL) +ORDER BY random <-> 3000000; + +DROP INDEX bt_i4_heap_random_idx; + +CREATE INDEX bt_i4_heap_random_idx ON bt_i4_heap USING btree(random DESC, seqno); + +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 4000000; + +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 10000000; + +SELECT * FROM bt_i4_heap +WHERE random > 1000000 AND (random, seqno) < (6000000, 0) +ORDER BY random <-> 0; + +DROP INDEX bt_i4_heap_random_idx; + +-- test parallel KNN scan + +-- Serializable isolation would disable parallel query, so explicitly use an +-- arbitrary other level. +BEGIN ISOLATION LEVEL REPEATABLE READ; + +SET parallel_setup_cost = 0; +SET parallel_tuple_cost = 0; +SET min_parallel_table_scan_size = 0; +SET max_parallel_workers = 4; +SET max_parallel_workers_per_gather = 4; +SET cpu_operator_cost = 0; + +RESET enable_indexscan; + +CREATE TABLE bt_knn_test AS SELECT i * 10 AS i FROM generate_series(1, 1000000) i; +CREATE INDEX bt_knn_test_idx ON bt_knn_test (i); +ALTER TABLE bt_knn_test SET (parallel_workers = 4); +ANALYZE bt_knn_test; + +EXPLAIN (COSTS OFF) +SELECT i FROM bt_knn_test WHERE i > 8000000; + +CREATE TABLE bt_knn_test2 AS + SELECT row_number() OVER (ORDER BY i * 10 <-> 4000003) AS n, i * 10 AS i + FROM generate_series(1, 1000000) i; + +EXPLAIN (COSTS OFF) +WITH bt_knn_test1 AS ( + SELECT row_number() OVER () AS n, i + FROM bt_knn_test + ORDER BY i <-> 4000003 +) +SELECT * FROM bt_knn_test1 t1 JOIN bt_knn_test2 t2 USING (n) WHERE t1.i <> t2.i; + +WITH bt_knn_test1 AS ( + SELECT row_number() OVER () AS n, i + FROM bt_knn_test + ORDER BY i <-> 4000003 +) +SELECT * FROM bt_knn_test1 t1 JOIN bt_knn_test2 t2 USING (n) WHERE t1.i <> t2.i; + +DROP TABLE bt_knn_test; +CREATE TABLE bt_knn_test AS SELECT i FROM generate_series(1, 10) i, generate_series(1, 100000) j; +CREATE INDEX bt_knn_test_idx ON bt_knn_test (i); +ALTER TABLE bt_knn_test SET (parallel_workers = 4); +ANALYZE bt_knn_test; + +EXPLAIN (COSTS OFF) +WITH +t1 AS ( + SELECT row_number() OVER () AS n, i + FROM bt_knn_test + WHERE i IN (3, 4, 7, 8, 2) + ORDER BY i <-> 4 +), +t2 AS ( + SELECT i * 100000 + j AS n, (ARRAY[4, 3, 2, 7, 8])[i + 1] AS i + FROM generate_series(0, 4) i, generate_series(1, 100000) j +) +SELECT * FROM t1 JOIN t2 USING (n) WHERE t1.i <> t2.i; + +WITH +t1 AS ( + SELECT row_number() OVER () AS n, i + FROM bt_knn_test + WHERE i IN (3, 4, 7, 8, 2) + ORDER BY i <-> 4 +), +t2 AS ( + SELECT i * 100000 + j AS n, (ARRAY[4, 3, 2, 7, 8])[i + 1] AS i + FROM generate_series(0, 4) i, generate_series(1, 100000) j +) +SELECT * FROM t1 JOIN t2 USING (n) WHERE t1.i <> t2.i; + +RESET parallel_setup_cost; +RESET parallel_tuple_cost; +RESET min_parallel_table_scan_size; +RESET max_parallel_workers; +RESET max_parallel_workers_per_gather; +RESET cpu_operator_cost; + +ROLLBACK; + +-- enable bt_i4_index index on bt_i4_heap(seqno) +UPDATE pg_index SET indisvalid = true WHERE indexrelid = 'bt_i4_index'::regclass; + + +CREATE TABLE tenk3 AS SELECT thousand, tenthous FROM tenk1; + +INSERT INTO tenk3 VALUES (NULL, 1), (NULL, 2), (NULL, 3); + +-- Test distance ordering by ASC index +CREATE INDEX tenk3_idx ON tenk3 USING btree(thousand, tenthous); + +EXPLAIN (COSTS OFF) +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) +ORDER BY thousand <-> 998; + +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) +ORDER BY thousand <-> 998; + +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) +ORDER BY thousand <-> 0; + +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) AND thousand < 1000 +ORDER BY thousand <-> 10000; + +SELECT thousand, tenthous FROM tenk3 +ORDER BY thousand <-> 500 +OFFSET 9970; + +EXPLAIN (COSTS OFF) +SELECT * FROM tenk3 +WHERE thousand > 100 AND thousand < 800 AND + thousand = ANY(ARRAY[0, 123, 234, 345, 456, 678, 901, NULL]::int2[]) +ORDER BY thousand <-> 300::int8; + +SELECT * FROM tenk3 +WHERE thousand > 100 AND thousand < 800 AND + thousand = ANY(ARRAY[0, 123, 234, 345, 456, 678, 901, NULL]::int2[]) +ORDER BY thousand <-> 300::int8; + +DROP INDEX tenk3_idx; + +-- Test distance ordering by DESC index +CREATE INDEX tenk3_idx ON tenk3 USING btree(thousand DESC, tenthous); + +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) +ORDER BY thousand <-> 998; + +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) +ORDER BY thousand <-> 0; + +SELECT thousand, tenthous FROM tenk3 +WHERE (thousand, tenthous) >= (997, 5000) AND thousand < 1000 +ORDER BY thousand <-> 10000; + +SELECT thousand, tenthous FROM tenk3 +ORDER BY thousand <-> 500 +OFFSET 9970; + +DROP INDEX tenk3_idx; + +DROP TABLE tenk3; + +-- Test distance ordering on by-ref types +CREATE TABLE knn_btree_ts (ts timestamp); + +INSERT INTO knn_btree_ts +SELECT timestamp '2017-05-03 00:00:00' + tenthous * interval '1 hour' +FROM tenk1; + +CREATE INDEX knn_btree_ts_idx ON knn_btree_ts USING btree(ts); + +SELECT ts, ts <-> timestamp '2017-05-01 00:00:00' FROM knn_btree_ts ORDER BY 2 LIMIT 20; +SELECT ts, ts <-> timestamp '2018-01-01 00:00:00' FROM knn_btree_ts ORDER BY 2 LIMIT 20; + +DROP TABLE knn_btree_ts; + +RESET enable_bitmapscan;