Skip to content

Commit af9d504

Browse files
ankaneankane
committed
Added support for indexing L1 distance
1 parent 6dad846 commit af9d504

13 files changed

Lines changed: 122 additions & 10 deletions

‎CHANGELOG.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
- Added `halfvec` type
44
- Added `sparsevec` type
55
- Added support for indexing `bit` type
6+
- Added support for indexing L1 distance
67
- Added `binary_quantize` function
78
- Added `hamming_distance` function
89
- Added `jaccard_distance` function

‎README.md‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -227,6 +227,12 @@ Cosine distance
227227
CREATE INDEX ON items USING hnsw (embedding vector_cosine_ops);
228228
```
229229

230+
L1 distance - unreleased
231+
232+
```sql
233+
CREATE INDEX ON items USING hnsw (embedding vector_l1_ops);
234+
```
235+
230236
Hamming distance - unreleased
231237

232238
```sql
@@ -349,6 +355,12 @@ Cosine distance
349355
CREATE INDEX ON items USING ivfflat (embedding vector_cosine_ops) WITH (lists = 100);
350356
```
351357

358+
L1 distance - unreleased
359+
360+
```sql
361+
CREATE INDEX ON items USING ivfflat (embedding vector_l1_ops) WITH (lists = 100);
362+
```
363+
352364
Supported types are:
353365

354366
- `vector` - up to 2,000 dimensions
@@ -855,6 +867,7 @@ Operator | Description | Added
855867
<-> | Euclidean distance |
856868
<#> | negative inner product |
857869
<=> | cosine distance |
870+
<+> | taxicab distance | unreleased
858871

859872
### Vector Functions
860873

‎sql/vector--0.6.2--0.7.0.sql‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,10 +13,26 @@ CREATE FUNCTION subvector(vector, int, int) RETURNS vector
1313
CREATE FUNCTION vector_concat(vector, vector) RETURNS vector
1414
AS 'MODULE_PATHNAME' LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
1515

16+
CREATE OPERATOR <+> (
17+
LEFTARG = vector, RIGHTARG = vector, PROCEDURE = l1_distance,
18+
COMMUTATOR = '<+>'
19+
);
20+
1621
CREATE OPERATOR || (
1722
LEFTARG = vector, RIGHTARG = vector, PROCEDURE = vector_concat
1823
);
1924

25+
CREATE OPERATOR CLASS vector_l1_ops
26+
FOR TYPE vector USING ivfflat AS
27+
OPERATOR 1 <+> (vector, vector) FOR ORDER BY float_ops,
28+
FUNCTION 1 l1_distance(vector, vector),
29+
FUNCTION 3 l1_distance(vector, vector);
30+
31+
CREATE OPERATOR CLASS vector_l1_ops
32+
FOR TYPE vector USING hnsw AS
33+
OPERATOR 1 <+> (vector, vector) FOR ORDER BY float_ops,
34+
FUNCTION 1 l1_distance(vector, vector);
35+
2036
CREATE FUNCTION hamming_distance(bit, bit) RETURNS float8
2137
AS 'MODULE_PATHNAME' LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
2238

‎sql/vector.sql‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,6 +186,11 @@ CREATE OPERATOR <=> (
186186
COMMUTATOR = '<=>'
187187
);
188188

189+
CREATE OPERATOR <+> (
190+
LEFTARG = vector, RIGHTARG = vector, PROCEDURE = l1_distance,
191+
COMMUTATOR = '<+>'
192+
);
193+
189194
CREATE OPERATOR + (
190195
LEFTARG = vector, RIGHTARG = vector, PROCEDURE = vector_add,
191196
COMMUTATOR = +
@@ -288,6 +293,12 @@ CREATE OPERATOR CLASS vector_cosine_ops
288293
FUNCTION 3 vector_spherical_distance(vector, vector),
289294
FUNCTION 4 vector_norm(vector);
290295

296+
CREATE OPERATOR CLASS vector_l1_ops
297+
FOR TYPE vector USING ivfflat AS
298+
OPERATOR 1 <+> (vector, vector) FOR ORDER BY float_ops,
299+
FUNCTION 1 l1_distance(vector, vector),
300+
FUNCTION 3 l1_distance(vector, vector);
301+
291302
CREATE OPERATOR CLASS vector_l2_ops
292303
FOR TYPE vector USING hnsw AS
293304
OPERATOR 1 <-> (vector, vector) FOR ORDER BY float_ops,
@@ -304,6 +315,11 @@ CREATE OPERATOR CLASS vector_cosine_ops
304315
FUNCTION 1 vector_negative_inner_product(vector, vector),
305316
FUNCTION 2 vector_norm(vector);
306317

318+
CREATE OPERATOR CLASS vector_l1_ops
319+
FOR TYPE vector USING hnsw AS
320+
OPERATOR 1 <+> (vector, vector) FOR ORDER BY float_ops,
321+
FUNCTION 1 l1_distance(vector, vector);
322+
307323
-- bit functions
308324

309325
CREATE FUNCTION hamming_distance(bit, bit) RETURNS float8

‎test/expected/hnsw_l1.out‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
SET enable_seqscan = off;
2+
CREATE TABLE t (val vector(3));
3+
INSERT INTO t (val) VALUES ('[0,0,0]'), ('[1,2,3]'), ('[1,1,1]'), (NULL);
4+
CREATE INDEX ON t USING hnsw (val vector_l1_ops);
5+
INSERT INTO t (val) VALUES ('[1,2,4]');
6+
SELECT * FROM t ORDER BY val <+> '[3,3,3]';
7+
val
8+
---------
9+
[1,2,3]
10+
[1,2,4]
11+
[1,1,1]
12+
[0,0,0]
13+
(4 rows)
14+
15+
SELECT COUNT(*) FROM (SELECT * FROM t ORDER BY val <+> (SELECT NULL::vector)) t2;
16+
count
17+
-------
18+
4
19+
(1 row)
20+
21+
DROP TABLE t;

‎test/expected/ivfflat_l1.out‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
SET enable_seqscan = off;
2+
CREATE TABLE t (val vector(3));
3+
INSERT INTO t (val) VALUES ('[0,0,0]'), ('[1,2,3]'), ('[1,1,1]'), (NULL);
4+
CREATE INDEX ON t USING ivfflat (val vector_l1_ops) WITH (lists = 1);
5+
INSERT INTO t (val) VALUES ('[1,2,4]');
6+
SELECT * FROM t ORDER BY val <+> '[3,3,3]';
7+
val
8+
---------
9+
[1,2,3]
10+
[1,2,4]
11+
[1,1,1]
12+
[0,0,0]
13+
(4 rows)
14+
15+
SELECT COUNT(*) FROM (SELECT * FROM t ORDER BY val <+> (SELECT NULL::vector)) t2;
16+
count
17+
-------
18+
4
19+
(1 row)
20+
21+
DROP TABLE t;

‎test/sql/hnsw_l1.sql‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
SET enable_seqscan = off;
2+
3+
CREATE TABLE t (val vector(3));
4+
INSERT INTO t (val) VALUES ('[0,0,0]'), ('[1,2,3]'), ('[1,1,1]'), (NULL);
5+
CREATE INDEX ON t USING hnsw (val vector_l1_ops);
6+
7+
INSERT INTO t (val) VALUES ('[1,2,4]');
8+
9+
SELECT * FROM t ORDER BY val <+> '[3,3,3]';
10+
SELECT COUNT(*) FROM (SELECT * FROM t ORDER BY val <+> (SELECT NULL::vector)) t2;
11+
12+
DROP TABLE t;

‎test/sql/ivfflat_l1.sql‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
SET enable_seqscan = off;
2+
3+
CREATE TABLE t (val vector(3));
4+
INSERT INTO t (val) VALUES ('[0,0,0]'), ('[1,2,3]'), ('[1,1,1]'), (NULL);
5+
CREATE INDEX ON t USING ivfflat (val vector_l1_ops) WITH (lists = 1);
6+
7+
INSERT INTO t (val) VALUES ('[1,2,4]');
8+
9+
SELECT * FROM t ORDER BY val <+> '[3,3,3]';
10+
SELECT COUNT(*) FROM (SELECT * FROM t ORDER BY val <+> (SELECT NULL::vector)) t2;
11+
12+
DROP TABLE t;

‎test/t/003_ivfflat_build_recall.pl‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -70,8 +70,8 @@ sub test_recall
7070
}
7171

7272
# Check each index type
73-
my @operators = ("<->", "<#>", "<=>");
74-
my @opclasses = ("vector_l2_ops", "vector_ip_ops", "vector_cosine_ops");
73+
my @operators = ("<->", "<#>", "<=>", "<+>");
74+
my @opclasses = ("vector_l2_ops", "vector_ip_ops", "vector_cosine_ops", "vector_l1_ops");
7575

7676
for my $i (0 .. $#operators)
7777
{

‎test/t/005_ivfflat_query_recall.pl‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,8 +17,8 @@
1717
);
1818

1919
# Check each index type
20-
my @operators = ("<->", "<#>", "<=>");
21-
my @opclasses = ("vector_l2_ops", "vector_ip_ops", "vector_cosine_ops");
20+
my @operators = ("<->", "<#>", "<=>", "<+>");
21+
my @opclasses = ("vector_l2_ops", "vector_ip_ops", "vector_cosine_ops", "vector_l1_ops");
2222

2323
for my $i (0 .. $#operators)
2424
{

0 commit comments

Comments
 (0)