Skip to content

Commit 485f0aa

Browse files
tglsfdctglsfdc
committed
Add hash support functions and hash opclass for contrib/ltree.
This also enables hash join and hash aggregation on ltree columns. Tommy Pavlicek, reviewed by jian he Discussion: https://postgr.es/m/CAEhP-W9ZEoHeaP_nKnPCVd_o1c3BAUvq1gWHrq8EbkNRiS9CvQ@mail.gmail.com
1 parent 0997e0a commit 485f0aa

File tree

9 files changed

+221
-3
lines changed

9 files changed

+221
-3
lines changed

‎contrib/ltree/Makefile

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,8 @@ OBJS = \
1414
ltxtquery_op.o
1515

1616
EXTENSION = ltree
17-
DATA = ltree--1.1--1.2.sql ltree--1.1.sql ltree--1.0--1.1.sql
17+
DATA = ltree--1.2--1.3.sql ltree--1.1--1.2.sql ltree--1.1.sql \
18+
ltree--1.0--1.1.sql
1819
PGFILEDESC = "ltree - hierarchical label data type"
1920

2021
HEADERS = ltree.h

‎contrib/ltree/expected/ltree.out

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1433,8 +1433,27 @@ SELECT '{j.k.l.m, g.b.c.d.e}'::ltree[] ?~ 'A*@|g.b.c.d.e';
14331433
g.b.c.d.e
14341434
(1 row)
14351435

1436+
-- Check that the hash_ltree() and hash_ltree_extended() function's lower
1437+
-- 32 bits match when the seed is 0 and do not match when the seed != 0
1438+
SELECT v as value, hash_ltree(v)::bit(32) as standard,
1439+
hash_ltree_extended(v, 0)::bit(32) as extended0,
1440+
hash_ltree_extended(v, 1)::bit(32) as extended1
1441+
FROM (VALUES (NULL::ltree), (''::ltree), ('0'::ltree), ('0.1'::ltree),
1442+
('0.1.2'::ltree), ('0'::ltree), ('0_asd.1_ASD'::ltree)) x(v)
1443+
WHERE hash_ltree(v)::bit(32) != hash_ltree_extended(v, 0)::bit(32)
1444+
OR hash_ltree(v)::bit(32) = hash_ltree_extended(v, 1)::bit(32);
1445+
value | standard | extended0 | extended1
1446+
-------+----------+-----------+-----------
1447+
(0 rows)
1448+
14361449
CREATE TABLE ltreetest (t ltree);
14371450
\copy ltreetest FROM 'data/ltree.data'
1451+
SELECT count(*) from ltreetest;
1452+
count
1453+
-------
1454+
1006
1455+
(1 row)
1456+
14381457
SELECT * FROM ltreetest WHERE t < '12.3' order by t asc;
14391458
t
14401459
----------------------------------
@@ -7833,6 +7852,55 @@ SELECT * FROM ltreetest WHERE t ? '{23.*.1,23.*.2}' order by t asc;
78337852
(4 rows)
78347853

78357854
drop index tstidx;
7855+
--- test hash index
7856+
create index tstidx on ltreetest using hash (t);
7857+
set enable_seqscan=off;
7858+
set enable_bitmapscan=off;
7859+
EXPLAIN (COSTS OFF)
7860+
SELECT * FROM ltreetest WHERE t = '12.3' order by t asc;
7861+
QUERY PLAN
7862+
--------------------------------------
7863+
Index Scan using tstidx on ltreetest
7864+
Index Cond: (t = '12.3'::ltree)
7865+
(2 rows)
7866+
7867+
SELECT * FROM ltreetest WHERE t = '12.3' order by t asc;
7868+
t
7869+
------
7870+
12.3
7871+
(1 row)
7872+
7873+
reset enable_seqscan;
7874+
reset enable_bitmapscan;
7875+
-- test hash aggregate
7876+
set enable_hashagg=on;
7877+
set enable_sort=off;
7878+
EXPLAIN (COSTS OFF)
7879+
SELECT count(*) FROM (
7880+
SELECT t FROM (SELECT * FROM ltreetest UNION ALL SELECT * FROM ltreetest) t1 GROUP BY t
7881+
) t2;
7882+
QUERY PLAN
7883+
-----------------------------------------------------
7884+
Aggregate
7885+
-> HashAggregate
7886+
Group Key: ltreetest.t
7887+
-> Append
7888+
-> Seq Scan on ltreetest
7889+
-> Seq Scan on ltreetest ltreetest_1
7890+
(6 rows)
7891+
7892+
SELECT count(*) FROM (
7893+
SELECT t FROM (SELECT * FROM ltreetest UNION ALL SELECT * FROM ltreetest) t1 GROUP BY t
7894+
) t2;
7895+
count
7896+
-------
7897+
1006
7898+
(1 row)
7899+
7900+
reset enable_hashagg;
7901+
reset enable_sort;
7902+
drop index tstidx;
7903+
-- test gist index
78367904
create index tstidx on ltreetest using gist (t gist_ltree_ops(siglen=0));
78377905
ERROR: value 0 out of bounds for option "siglen"
78387906
DETAIL: Valid values are between "4" and "2024".

‎contrib/ltree/ltree--1.2--1.3.sql

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
/* contrib/ltree/ltree--1.2--1.3.sql */
2+
3+
-- complain if script is sourced in psql, rather than via ALTER EXTENSION
4+
\echo Use "ALTER EXTENSION ltree UPDATE TO '1.3'" to load this file. \quit
5+
6+
CREATE FUNCTION hash_ltree(ltree)
7+
RETURNS integer
8+
AS 'MODULE_PATHNAME'
9+
LANGUAGE C STRICT IMMUTABLE PARALLEL SAFE;
10+
11+
CREATE FUNCTION hash_ltree_extended(ltree, bigint)
12+
RETURNS bigint
13+
AS 'MODULE_PATHNAME'
14+
LANGUAGE C STRICT IMMUTABLE PARALLEL SAFE;
15+
16+
CREATE OPERATOR CLASS hash_ltree_ops
17+
DEFAULT FOR TYPE ltree USING hash
18+
AS
19+
OPERATOR 1 = ,
20+
FUNCTION 1 hash_ltree(ltree),
21+
FUNCTION 2 hash_ltree_extended(ltree, bigint);
22+
23+
ALTER OPERATOR =(ltree, ltree) SET (HASHES);

‎contrib/ltree/ltree.control

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
# ltree extension
22
comment = 'data type for hierarchical tree-like structures'
3-
default_version = '1.2'
3+
default_version = '1.3'
44
module_pathname = '$libdir/ltree'
55
relocatable = true
66
trusted = true

‎contrib/ltree/ltree_op.c

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99

1010
#include "access/htup_details.h"
1111
#include "catalog/pg_statistic.h"
12+
#include "common/hashfn.h"
1213
#include "ltree.h"
1314
#include "utils/builtins.h"
1415
#include "utils/lsyscache.h"
@@ -24,6 +25,8 @@ PG_FUNCTION_INFO_V1(ltree_eq);
2425
PG_FUNCTION_INFO_V1(ltree_ne);
2526
PG_FUNCTION_INFO_V1(ltree_ge);
2627
PG_FUNCTION_INFO_V1(ltree_gt);
28+
PG_FUNCTION_INFO_V1(hash_ltree);
29+
PG_FUNCTION_INFO_V1(hash_ltree_extended);
2730
PG_FUNCTION_INFO_V1(nlevel);
2831
PG_FUNCTION_INFO_V1(ltree_isparent);
2932
PG_FUNCTION_INFO_V1(ltree_risparent);
@@ -129,6 +132,72 @@ ltree_ne(PG_FUNCTION_ARGS)
129132
PG_RETURN_BOOL(res != 0);
130133
}
131134

135+
/* Compute a hash for the ltree */
136+
Datum
137+
hash_ltree(PG_FUNCTION_ARGS)
138+
{
139+
ltree *a = PG_GETARG_LTREE_P(0);
140+
uint32 result = 1;
141+
int an = a->numlevel;
142+
ltree_level *al = LTREE_FIRST(a);
143+
144+
while (an > 0)
145+
{
146+
uint32 levelHash = DatumGetUInt32(hash_any((unsigned char *) al->name, al->len));
147+
148+
/*
149+
* Combine hash values of successive elements by multiplying the
150+
* current value by 31 and adding on the new element's hash value.
151+
*
152+
* This method is borrowed from hash_array(), which see for further
153+
* commentary.
154+
*/
155+
result = (result << 5) - result + levelHash;
156+
157+
an--;
158+
al = LEVEL_NEXT(al);
159+
}
160+
161+
PG_FREE_IF_COPY(a, 0);
162+
PG_RETURN_UINT32(result);
163+
}
164+
165+
/* Compute an extended hash for the ltree */
166+
Datum
167+
hash_ltree_extended(PG_FUNCTION_ARGS)
168+
{
169+
ltree *a = PG_GETARG_LTREE_P(0);
170+
const uint64 seed = PG_GETARG_INT64(1);
171+
uint64 result = 1;
172+
int an = a->numlevel;
173+
ltree_level *al = LTREE_FIRST(a);
174+
175+
/*
176+
* If the path has length zero, return 1 + seed to ensure that the low 32
177+
* bits of the result match hash_ltree when the seed is 0, as required by
178+
* the hash index support functions, but to also return a different value
179+
* when there is a seed.
180+
*/
181+
if (an == 0)
182+
{
183+
PG_FREE_IF_COPY(a, 0);
184+
PG_RETURN_UINT64(result + seed);
185+
}
186+
187+
while (an > 0)
188+
{
189+
uint64 levelHash = DatumGetUInt64(hash_any_extended((unsigned char *) al->name, al->len, seed));
190+
191+
result = (result << 5) - result + levelHash;
192+
193+
an--;
194+
al = LEVEL_NEXT(al);
195+
}
196+
197+
PG_FREE_IF_COPY(a, 0);
198+
PG_RETURN_UINT64(result);
199+
}
200+
132201
Datum
133202
nlevel(PG_FUNCTION_ARGS)
134203
{

‎contrib/ltree/ltreetest.sql

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,3 +19,4 @@ INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
1919
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
2020
CREATE INDEX path_gist_idx ON test USING gist(path);
2121
CREATE INDEX path_idx ON test USING btree(path);
22+
CREATE INDEX path_hash_idx ON test USING hash(path);

‎contrib/ltree/meson.build

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,8 +30,9 @@ contrib_targets += ltree
3030
install_data(
3131
'ltree.control',
3232
'ltree--1.0--1.1.sql',
33-
'ltree--1.1--1.2.sql',
3433
'ltree--1.1.sql',
34+
'ltree--1.1--1.2.sql',
35+
'ltree--1.2--1.3.sql',
3536
kwargs: contrib_data_args,
3637
)
3738

‎contrib/ltree/sql/ltree.sql

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -282,9 +282,21 @@ SELECT ('{3456,1.2.3.4}'::ltree[] ?<@ '1.2.5') is null;
282282
SELECT '{ltree.asd, tree.awdfg}'::ltree[] ?@ 'tree & aWdfg@'::ltxtquery;
283283
SELECT '{j.k.l.m, g.b.c.d.e}'::ltree[] ?~ 'A*@|g.b.c.d.e';
284284

285+
-- Check that the hash_ltree() and hash_ltree_extended() function's lower
286+
-- 32 bits match when the seed is 0 and do not match when the seed != 0
287+
SELECT v as value, hash_ltree(v)::bit(32) as standard,
288+
hash_ltree_extended(v, 0)::bit(32) as extended0,
289+
hash_ltree_extended(v, 1)::bit(32) as extended1
290+
FROM (VALUES (NULL::ltree), (''::ltree), ('0'::ltree), ('0.1'::ltree),
291+
('0.1.2'::ltree), ('0'::ltree), ('0_asd.1_ASD'::ltree)) x(v)
292+
WHERE hash_ltree(v)::bit(32) != hash_ltree_extended(v, 0)::bit(32)
293+
OR hash_ltree(v)::bit(32) = hash_ltree_extended(v, 1)::bit(32);
294+
285295
CREATE TABLE ltreetest (t ltree);
286296
\copy ltreetest FROM 'data/ltree.data'
287297

298+
SELECT count(*) from ltreetest;
299+
288300
SELECT * FROM ltreetest WHERE t < '12.3' order by t asc;
289301
SELECT * FROM ltreetest WHERE t <= '12.3' order by t asc;
290302
SELECT * FROM ltreetest WHERE t = '12.3' order by t asc;
@@ -329,6 +341,41 @@ SELECT * FROM ltreetest WHERE t ~ '23.*.2' order by t asc;
329341
SELECT * FROM ltreetest WHERE t ? '{23.*.1,23.*.2}' order by t asc;
330342

331343
drop index tstidx;
344+
345+
--- test hash index
346+
347+
create index tstidx on ltreetest using hash (t);
348+
set enable_seqscan=off;
349+
set enable_bitmapscan=off;
350+
351+
EXPLAIN (COSTS OFF)
352+
SELECT * FROM ltreetest WHERE t = '12.3' order by t asc;
353+
SELECT * FROM ltreetest WHERE t = '12.3' order by t asc;
354+
355+
reset enable_seqscan;
356+
reset enable_bitmapscan;
357+
358+
-- test hash aggregate
359+
360+
set enable_hashagg=on;
361+
set enable_sort=off;
362+
363+
EXPLAIN (COSTS OFF)
364+
SELECT count(*) FROM (
365+
SELECT t FROM (SELECT * FROM ltreetest UNION ALL SELECT * FROM ltreetest) t1 GROUP BY t
366+
) t2;
367+
368+
SELECT count(*) FROM (
369+
SELECT t FROM (SELECT * FROM ltreetest UNION ALL SELECT * FROM ltreetest) t1 GROUP BY t
370+
) t2;
371+
372+
reset enable_hashagg;
373+
reset enable_sort;
374+
375+
drop index tstidx;
376+
377+
-- test gist index
378+
332379
create index tstidx on ltreetest using gist (t gist_ltree_ops(siglen=0));
333380
create index tstidx on ltreetest using gist (t gist_ltree_ops(siglen=2025));
334381
create index tstidx on ltreetest using gist (t gist_ltree_ops(siglen=2028));

‎doc/src/sgml/ltree.sgml

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -623,6 +623,13 @@ Europe &amp; Russia*@ &amp; !Transportation
623623
<literal>&gt;=</literal>, <literal>&gt;</literal>
624624
</para>
625625
</listitem>
626+
<listitem>
627+
<para>
628+
Hash index over <type>ltree</type>:
629+
<literal>=</literal>
630+
</para>
631+
</listitem>
632+
626633
<listitem>
627634
<para>
628635
GiST index over <type>ltree</type> (<literal>gist_ltree_ops</literal>
@@ -712,6 +719,7 @@ INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
712719
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
713720
CREATE INDEX path_gist_idx ON test USING GIST (path);
714721
CREATE INDEX path_idx ON test USING BTREE (path);
722+
CREATE INDEX path_hash_idx ON test USING HASH (path);
715723
</programlisting>
716724

717725
<para>

0 commit comments

Comments
 (0)