8000 Renamed iterative_search to iterative_scan · postgrespro/pgvector@857d716 · GitHub
[go: up one dir, main page]
Skip to content

Commit 857d716

Browse files
ankaneankane
committed
Renamed iterative_search to iterative_scan
1 parent c5dd2af commit 857d716

16 files changed

+100
-100
lines changed

‎CHANGELOG.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
## 0.8.0 (unreleased)
22

3-
- Added support for iterative search
3+
- Added support for iterative index scans
44
- Added casts for arrays to `sparsevec`
55
- Improved cost estimation
66
- Improved performance of HNSW inserts and on-disk index builds

‎README.md

Lines changed: 12 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -451,31 +451,31 @@ Use [partitioning](https://www.postgresql.org/docs/current/ddl-partitioning.html
451451
CREATE TABLE items (embedding vector(3), category_id int) PARTITION BY LIST(category_id);
452452
```
453453

454-
## Iterative Search
454+
## Iterative Index Scans
455455

456456
*Unreleased*
457457

458458
With approximate indexes, queries with filtering can return less results (due to post-filtering).
459459

460-
Starting with 0.8.0, you can enable iterative search. If too few results from the initial index scan match the filters, the scan will resume until enough results are found (or it reaches `hnsw.max_search_tuples` or `ivfflat.max_probes`). This can significantly improve recall.
460+
Starting with 0.8.0, you can enable iterative index scans. If too few results from the initial scan match the filters, the scan will resume until enough results are found (or it reaches `hnsw.max_scan_tuples` or `ivfflat.max_probes`). This can significantly improve recall.
461461

462-
There are two modes for iterative search: strict and relaxed (due to the streaming nature of Postgres executor).
462+
There are two modes for iterative scans: strict and relaxed.
463463

464464
Strict ensures results are in the exact order by distance
465465

466466
```sql
467-
SET hnsw.iterative_search = strict_order;
467+
SET hnsw.iterative_scan = strict_order;
468468
```
469469

470470
Relaxed allows results to be slightly out of order by distance, but provides better recall
471471

472472
```sql
473-
SET hnsw.iterative_search = relaxed_order;
473+
SET hnsw.iterative_scan = relaxed_order;
474474
# or
475-
SET ivfflat.iterative_search = relaxed_order;
475+
SET ivfflat.iterative_scan = relaxed_order;
476476
```
477477

478-
Note: IVFFlat only supports relaxed order for iterative search
478+
Note: IVFFlat only supports relaxed ordering for iterative scans
479479

480480
With relaxed ordering, you can use a [materialized CTE](https://www.postgresql.org/docs/current/queries-with.html#QUERIES-WITH-CTE-MATERIALIZATION) to get strict ordering
481481

@@ -493,24 +493,24 @@ WITH filtered_results AS MATERIALIZED (
493493
) SELECT * FROM filtered_results WHERE distance < 0.1 ORDER BY distance;
494494
```
495495

496-
### Iterative Options
496+
### Iterative Scan Options
497497

498498
Since scanning a large portion of an approximate index is expensive, there are options to control when a scan ends
499499

500500
#### HNSW
501501

502-
Specify the max number of tuples visited (20,000 by default)
502+
Specify the max number of tuples to visit (20,000 by default)
503503

504504
```sql
505-
SET hnsw.max_search_tuples = 20000;
505+
SET hnsw.max_scan_tuples = 20000;
506506
```
507507

508508
Note: This is approximate and does not apply to the initial scan
509509

510510
When increasing this, you may also need to increase the max amount of memory an iterative scan can use, which is a multiple of `work_mem` (2 by default)
511511

512512
```sql
513-
SET hnsw.search_mem_multiplier = 4;
513+
SET hnsw.scan_mem_multiplier = 4;
514514
```
515515

516516
You can see when this is needed by enabling debug messages
@@ -523,7 +523,7 @@ which will show when a scan reaches the memory limit
523523

524524
```text
525525
DEBUG: hnsw index scan reached memory limit after 40000 tuples
526-
HINT: Increase hnsw.search_mem_multiplier to scan more tuples.
526+
HINT: Increase hnsw.scan_mem_multiplier to scan more tuples.
527527
```
528528

529529
#### IVFFlat

‎src/hnsw.c

Lines changed: 14 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -18,17 +18,17 @@
1818
#define MarkGUCPrefixReserved(x) EmitWarningsOnPlaceholders(x)
1919
#endif
2020

21-
static const struct config_enum_entry hnsw_iterative_search_options[] = {
22-
{"off", HNSW_ITERATIVE_SEARCH_OFF, false},
23-
{"relaxed_order", HNSW_ITERATIVE_SEARCH_RELAXED, false},
24-
{"strict_order", HNSW_ITERATIVE_SEARCH_STRICT, false},
21+
static const struct config_enum_entry hnsw_iterative_scan_options[] = {
22+
{"off", HNSW_ITERATIVE_SCAN_OFF, false},
23+
{"relaxed_order", HNSW_ITERATIVE_SCAN_RELAXED, false},
24+
{"strict_order", HNSW_ITERATIVE_SCAN_STRICT, false},
2525
{NULL, 0, false}
2626
};
2727

2828
int hnsw_ef_search;
29-
int hnsw_iterative_search;
30-
int hnsw_max_search_tuples;
31-
double hnsw_search_mem_multiplier;
29+
int hnsw_iterative_scan;
30+
int hnsw_max_scan_tuples;
31+
double hnsw_scan_mem_multiplier;
3232
int hnsw_lock_tranche_id;
3333
static relopt_kind hnsw_relopt_kind;
3434

@@ -79,18 +79,18 @@ HnswInit(void)
7979
"Valid range is 1..1000.", &hnsw_ef_search,
8080
HNSW_DEFAULT_EF_SEARCH, HNSW_MIN_EF_SEARCH, HNSW_MAX_EF_SEARCH, PGC_USERSET, 0, NULL, NULL, NULL);
8181

82-
DefineCustomEnumVariable("hnsw.iterative_search", "Sets the iterative search mode",
83-
NULL, &hnsw_iterative_search,
84-
HNSW_ITERATIVE_SEARCH_OFF, hnsw_iterative_search_options, PGC_USERSET, 0, NULL, NULL, NULL);
82+
DefineCustomEnumVariable("hnsw.iterative_scan", "Sets the mode for iterative scans",
83+
NULL, &hnsw_iterative_scan,
84+
HNSW_ITERATIVE_SCAN_OFF, hnsw_iterative_scan_options, PGC_USERSET, 0, NULL, NULL, NULL);
8585

8686
/* This is approximate and does not apply to the initial scan */
87-
DefineCustomIntVariable("hnsw.max_search_tuples", "Sets the max number of candidates to visit for iterative search",
88-
NULL, &hnsw_max_search_tuples,
87+
DefineCustomIntVariable("hnsw.max_scan_tuples", "Sets the max number of tuples to visit for iterative scans",
88+
NULL, &hnsw_max_scan_tuples,
8989
20000, 1, INT_MAX, PGC_USERSET, 0, NULL, NULL, NULL);
9090

9191
/* Same range and default as hash_mem_multiplier */
92-
DefineCustomRealVariable("hnsw.search_mem_multiplier", "Sets the multiple of work_mem to use for iterative search",
93-
NULL, &hnsw_search_mem_multiplier,
92+
DefineCustomRealVariable("hnsw.scan_mem_multiplier", "Sets the multiple of work_mem to use for iterative scans",
93+
NULL, &hnsw_scan_mem_multiplier,
9494
2, 1, 1000, PGC_USERSET, 0, NULL, NULL, NULL);
9595

9696
MarkGUCPrefixReserved("hnsw");

‎src/hnsw.h

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -109,17 +109,17 @@
109109

110110
/* Variables */
111111
extern int hnsw_ef_search;
112-
extern int hnsw_iterative_search;
113-
extern int hnsw_max_search_tuples;
114-
extern double hnsw_search_mem_multiplier;
112+
extern int hnsw_iterative_scan;
113+
extern int hnsw_max_scan_tuples;
114+
extern double hnsw_scan_mem_multiplier;
115115
extern int hnsw_lock_tranche_id;
116116

117-
typedef enum HnswIterativeSearchMode
117+
typedef enum HnswIterativeScanMode
118118
{
119-
HNSW_ITERATIVE_SEARCH_OFF,
120-
HNSW_ITERATIVE_SEARCH_RELAXED,
121-
HNSW_ITERATIVE_SEARCH_STRICT
122-
} HnswIterativeSearchMode;
119+
HNSW_ITERATIVE_SCAN_OFF,
120+
HNSW_ITERATIVE_SCAN_RELAXED,
121+
HNSW_ITERATIVE_SCAN_STRICT
122+
} HnswIterativeScanMode;
123123

124124
typedef struct HnswElementData HnswElementData;
125125
typedef struct HnswNeighborArray HnswNeighborArray;

‎src/hnswscan.c

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,7 @@ GetScanItems(IndexScanDesc scan, Datum value)
4141
ep = w;
4242
}
4343

44-
return HnswSearchLayer(base, q, ep, hnsw_ef_search, 0, index, support, m, false, NULL, &so->v, hnsw_iterative_search != HNSW_ITERATIVE_SEARCH_OFF ? &so->discarded : NULL, true, &so->tuples);
44+
return HnswSearchLayer(base, q, ep, hnsw_ef_search, 0, index, support, m, false, NULL, &so->v, hnsw_iterative_scan != HNSW_ITERATIVE_SCAN_OFF ? &so->discarded : NULL, true, &so->tuples);
4545
}
4646

4747
/*
@@ -138,7 +138,7 @@ hnswbeginscan(Relation index, int nkeys, int norderbys)
138138
/* Set support functions */
139139
HnswInitSupport(&so->support, index);
140140

141-
so->maxMemory = (Size) (work_mem * 1024.0 * hnsw_search_mem_multiplier);
141+
so->maxMemory = (Size) (work_mem * 1024.0 * hnsw_scan_mem_multiplier);
142142

143143
scan->opaque = so;
144144

@@ -229,15 +229,15 @@ hnswgettuple(IndexScanDesc scan, ScanDirection dir)
229229

230230
if (list_length(so->w) == 0)
231231
{
232-
if (hnsw_iterative_search == HNSW_ITERATIVE_SEARCH_OFF)
232+
if (hnsw_iterative_scan == HNSW_ITERATIVE_SCAN_OFF)
233233
break;
234234

235235
/* Empty index */
236236
if (so->discarded == NULL)
237237
break;
238238

239239
/* Reached max number of tuples */
240-
if (so->tuples >= hnsw_max_search_tuples)
240+
if (so->tuples >= hnsw_max_scan_tuples)
241241
{
242242
if (pairingheap_is_empty(so->discarded))
243243
break;
@@ -252,7 +252,7 @@ hnswgettuple(IndexScanDesc scan, ScanDirection dir)
252252
{
253253
ereport(DEBUG1,
254254
(errmsg("hnsw index scan reached memory limit after " INT64_FORMAT " tuples", so->tuples),
255-
errhint("Increase hnsw.search_mem_multiplier to scan more tuples.")));
255+
errhint("Increase hnsw.scan_mem_multiplier to scan more tuples.")));
256256

257257
break;
258258
}
@@ -295,7 +295,7 @@ hnswgettuple(IndexScanDesc scan, ScanDirection dir)
295295
so->w = list_delete_last(so->w);
296296

297297
/* Mark memory as free for next iteration */
298-
if (hnsw_iterative_search != HNSW_ITERATIVE_SEARCH_OFF)
298+
if (hnsw_iterative_scan != HNSW_ITERATIVE_SCAN_OFF)
299299
{
300300
pfree(element);
301301
pfree(sc);
@@ -306,7 +306,7 @@ hnswgettuple(IndexScanDesc scan, ScanDirection dir)
306306

307307
heaptid = &element->heaptids[--element->heaptidsLength];
308308

309-
if (hnsw_iterative_search == HNSW_ITERATIVE_SEARCH_STRICT)
309+
if (hnsw_iterative_scan == HNSW_ITERATIVE_SCAN_STRICT)
310310
{
311311
if (sc->distance < so->previousDistance)
312312
continue;

‎src/ivfflat.c

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -17,13 +17,13 @@
1717
#endif
1818

1919
int ivfflat_probes;
20-
int ivfflat_iterative_search;
20+
int ivfflat_iterative_scan;
2121
int ivfflat_max_probes;
2222
static relopt_kind ivfflat_relopt_kind;
2323

24-
static const struct config_enum_entry ivfflat_iterative_search_options[] = {
25-
{"off", IVFFLAT_ITERATIVE_SEARCH_OFF, false},
26-
{"relaxed_order", IVFFLAT_ITERATIVE_SEARCH_RELAXED, false},
24+
static const struct config_enum_entry ivfflat_iterative_scan_options[] = {
25+
{"off", IVFFLAT_ITERATIVE_SCAN_OFF, false},
26+
{"relaxed_order", IVFFLAT_ITERATIVE_SCAN_RELAXED, false},
2727
{NULL, 0, false}
2828
};
2929

@@ -41,12 +41,12 @@ IvfflatInit(void)
4141
"Valid range is 1..lists.", &ivfflat_probes,
4242
IVFFLAT_DEFAULT_PROBES, IVFFLAT_MIN_LISTS, IVFFLAT_MAX_LISTS, PGC_USERSET, 0, NULL, NULL, NULL);
4343

44-
DefineCustomEnumVariable("ivfflat.iterative_search", "Sets the iterative search mode",
45-
NULL, &ivfflat_iterative_search,
46-
IVFFLAT_ITERATIVE_SEARCH_OFF, ivfflat_iterative_search_options, PGC_USERSET, 0, NULL, NULL, NULL);
44+
DefineCustomEnumVariable("ivfflat.iterative_scan", "Sets the mode for iterative scans",
45+
NULL, &ivfflat_iterative_scan,
46+
IVFFLAT_ITERATIVE_SCAN_OFF, ivfflat_iterative_scan_options, PGC_USERSET, 0, NULL, NULL, NULL);
4747

4848
/* If this is less than probes, probes is used */
49-
DefineCustomIntVariable("ivfflat.max_probes", "Sets the max number of probes for iterative search",
49+
DefineCustomIntVariable("ivfflat.max_probes", "Sets the max number of probes for iterative scans",
5050
NULL, &ivfflat_max_probes,
5151
IVFFLAT_MAX_LISTS, IVFFLAT_MIN_LISTS, IVFFLAT_MAX_LISTS, PGC_USERSET, 0, NULL, NULL, NULL);
5252

‎src/ivfflat.h

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -80,14 +80,14 @@
8080

8181
/* Variables */
8282
extern int ivfflat_probes;
83-
extern int ivfflat_iterative_search;
83+
extern int ivfflat_iterative_scan;
8484
extern int ivfflat_max_probes;
8585

86-
typedef enum IvfflatIterativeSearchMode
86+
typedef enum IvfflatIterativeScanMode
8787
{
88-
IVFFLAT_ITERATIVE_SEARCH_OFF,
89-
IVFFLAT_ITERATIVE_SEARCH_RELAXED
90-
} IvfflatIterativeSearchMode;
88+
IVFFLAT_ITERATIVE_SCAN_OFF,
89+
IVFFLAT_ITERATIVE_SCAN_RELAXED
90+
} IvfflatIterativeScanMode;
9191

9292
typedef struct VectorArrayData
9393
{

‎src/ivfscan.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -171,7 +171,7 @@ GetScanItems(IndexScanDesc scan, Datum value)
171171
}
172172
}
173173

174-
if (tuples < 100 && ivfflat_iterative_search == IVFFLAT_ITERATIVE_SEARCH_OFF)
174+
if (tuples < 100 && ivfflat_iterative_scan == IVFFLAT_ITERATIVE_SCAN_OFF)
175175
ereport(DEBUG1,
176176
(errmsg("index scan found few tuples"),
177177
errdetail("Index may have been created with little data."),
@@ -263,7 +263,7 @@ ivfflatbeginscan(Relation index, int nkeys, int norderbys)
263263
/* Get lists and dimensions from metapage */
264264
IvfflatGetMetaPageInfo(index, &lists, &dimensions);
265265

266-
if (ivfflat_iterative_search != IVFFLAT_ITERATIVE_SEARCH_OFF)
266+
if (ivfflat_iterative_scan != IVFFLAT_ITERATIVE_SCAN_OFF)
267267
maxProbes = Max(ivfflat_max_probes, probes);
268268
else
269269
maxProbes = probes;

‎test/expected/hnsw_vector.out

Lines changed: 13 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -104,7 +104,7 @@ DROP TABLE t;
104104
CREATE TABLE t (val vector(3));
105105
INSERT INTO t (val) VALUES ('[0,0,0]'), ('[1,2,3]'), ('[1,1,1]'), (NULL);
106106CREATE INDEX ON t USING hnsw (val vector_l2_ops);
107-
SET hnsw.iterative_search = strict_order;
107+
SET hnsw.iterative_scan = strict_order;
108108
SET hnsw.ef_search = 1;
109109
SELECT * FROM t ORDER BY val <-> '[3,3,3]';
110110
val
@@ -114,7 +114,7 @@ SELECT * FROM t ORDER BY val <-> '[3,3,3]';
114114
[0,0,0]
115115
(3 rows)
116116

117-
SET hnsw.iterative_search = relaxed_order;
117+
SET hnsw.iterative_scan = relaxed_order;
118118
SELECT * FROM t ORDER BY val <-> '[3,3,3]';
119119
val
120120
---------
@@ -123,7 +123,7 @@ SELECT * FROM t ORDER BY val <-> '[3,3,3]';
123123
[0,0,0]
124124
(3 rows)
125125

126-
RESET hnsw.iterative_search;
126+
RESET hnsw.iterative_scan;
127127
RESET hnsw.ef_search;
128128
DROP TABLE t;
129129
-- unlogged
@@ -165,21 +165,21 @@ SET hnsw.ef_search = 0;
165165
ERROR: 0 is outside the valid range for parameter "hnsw.ef_search" (1 .. 1000)
166166
SET hnsw.ef_search = 1001;
167167
ERROR: 1001 is outside the valid range for parameter "hnsw.ef_search" (1 .. 1000)
168-
SHOW hnsw.iterative_search;
169-
hnsw.iterative_search
170-
-----------------------
168+
SHOW hnsw.iterative_scan;
169+
hnsw.iterative_scan
170+
---------------------
171171
off
172172
(1 row)
173173

174-
SET hnsw.iterative_search = on;
175-
ERROR: invalid value for parameter "hnsw.iterative_search": "on"
174+
SET hnsw.iterative_scan = on;
175+
ERROR: invalid value for parameter "hnsw.iterative_scan": "on"
176176
HINT: Available values: off, relaxed_order, strict_order.
177-
SHOW hnsw.max_search_tuples;
178-
hnsw.max_search_tuples
179-
------------------------
177+
SHOW hnsw.max_scan_tuples;
178+
hnsw.max_scan_tuples
179+
----------------------
180180
20000
181181
(1 row)
182182

183-
SET hnsw.max_search_tuples = 0;
184-
ERROR: 0 is outside the valid range for parameter "hnsw.max_search_tuples" (1 .. 2147483647)
183+
SET hnsw.max_scan_tuples = 0;
184+
ERROR: 0 is outside the valid range for parameter "hnsw.max_scan_tuples" (1 .. 2147483647)
185185
DROP TABLE t;

‎test/expected/ivfflat_vector.out

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -86,7 +86,7 @@ DROP TABLE t;
8686
CREATE TABLE t (val vector(3));
8787
INSERT INTO t (val) VALUES ('[0,0,0]'), ('[1,2,3]'), ('[1,1,1]'), (NULL);
8888
CREATE INDEX ON t USING ivfflat (val vector_l2_ops) WITH (lists = 3);
89-
SET ivfflat.iterative_search = relaxed_order;
89+
SET ivfflat.iterative_scan = relaxed_order;
9090
SELECT * FROM t ORDER BY val <-> '[3,3,3]';
9191
val
9292
---------
@@ -110,7 +110,7 @@ SELECT * FROM t ORDER BY val <-> '[3,3,3]';
110110
[1,1,1]
111111
(2 rows)
112112

113-
RESET ivfflat.iterative_search;
113+
RESET ivfflat.iterative_scan;
114114
RESET ivfflat.max_probes;
115115
DROP TABLE t;
116116
-- unlogged
@@ -144,14 +144,14 @@ SET ivfflat.probes = 0;
144144
ERROR: 0 is outside the valid range for parameter "ivfflat.probes" (1 .. 32768)
145145
SET ivfflat.probes = 32769;
146146
ERROR: 32769 is outside the valid range for parameter "ivfflat.probes" (1 .. 32768)
147-
SHOW ivfflat.iterative_search;
148-
ivfflat.iterative_search
149-
--------------------------
147+
SHOW ivfflat.iterative_scan;
148+
ivfflat.iterative_scan
149+
------------------------
150150
off
151151
(1 row)
152152

153-
SET ivfflat.iterative_search = on;
154-
ERROR: invalid value for parameter "ivfflat.iterative_search": "on"
153+
SET ivfflat.iterative_scan = on;
154+
ERROR: invalid value for parameter "ivfflat.iterative_scan": "on"
155155
HINT: Available values: off, relaxed_order.
156156
SHOW ivfflat.max_probes;
157157
ivfflat.max_probes

0 commit comments

Comments
 (0)
0