- Added support for iterativesearch

- Added support for iterativeindex scans

- Added casts for arrays to`sparsevec`

- Improved cost estimation

- Improved performance of HNSW inserts and on-disk index builds

CREATETABLEitems (embedding vector(3), category_idint) PARTITION BY LIST(category_id);

*Unreleased*

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

Starting with 0.8.0, you can enable iterativesearch. If too few results from the initialindexscan 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.

Starting with 0.8.0, you can enable iterativeindex 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.

There are two modes for iterativesearch: strict and relaxed (due to the streaming nature of Postgres executor).

There are two modes for iterativescans: strict and relaxed.

Strict ensures results are in the exact order by distance

SEThnsw.iterative_search= strict_order;

SEThnsw.iterative_scan= strict_order;

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

SEThnsw.iterative_search= relaxed_order;

SEThnsw.iterative_scan= relaxed_order;

SETivfflat.iterative_search= relaxed_order;

SETivfflat.iterative_scan= relaxed_order;

Note: IVFFlat only supports relaxedorder for iterativesearch

Note: IVFFlat only supports relaxedordering for iterativescans

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

)SELECT*FROM filtered_resultsWHERE distance<0.1ORDER BY distance;

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

Specify the max number of tuplesvisited (20,000 by default)

Specify the max number of tuplesto visit (20,000 by default)

SEThnsw.max_search_tuples=20000;

SEThnsw.max_scan_tuples=20000;

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

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)

SEThnsw.search_mem_multiplier=4;

SEThnsw.scan_mem_multiplier=4;

You can see when this is needed by enabling debug messages

#defineMarkGUCPrefixReserved(x) EmitWarningsOnPlaceholders(x)

staticconststructconfig_enum_entryhnsw_iterative_search_options[]= {

{"off",HNSW_ITERATIVE_SEARCH_OFF, false},

{"relaxed_order",HNSW_ITERATIVE_SEARCH_RELAXED, false},

{"strict_order",HNSW_ITERATIVE_SEARCH_STRICT, false},

staticconststructconfig_enum_entryhnsw_iterative_scan_options[]= {

{"off",HNSW_ITERATIVE_SCAN_OFF, false},

{"relaxed_order",HNSW_ITERATIVE_SCAN_RELAXED, false},

{"strict_order",HNSW_ITERATIVE_SCAN_STRICT, false},

{NULL,0, false}

};

inthnsw_ef_search;

inthnsw_iterative_search;

inthnsw_max_search_tuples;

doublehnsw_search_mem_multiplier;

inthnsw_iterative_scan;

inthnsw_max_scan_tuples;

doublehnsw_scan_mem_multiplier;

inthnsw_lock_tranche_id;

staticrelopt_kindhnsw_relopt_kind;

"Valid range is 1..1000.",&hnsw_ef_search,

HNSW_DEFAULT_EF_SEARCH,HNSW_MIN_EF_SEARCH,HNSW_MAX_EF_SEARCH,PGC_USERSET,0,NULL,NULL,NULL);

DefineCustomEnumVariable("hnsw.iterative_search","Sets theiterative search mode",

NULL,&hnsw_iterative_search,

HNSW_ITERATIVE_SEARCH_OFF,hnsw_iterative_search_options,PGC_USERSET,0,NULL,NULL,NULL);

DefineCustomEnumVariable("hnsw.iterative_scan","Sets themode for iterative scans",

NULL,&hnsw_iterative_scan,

HNSW_ITERATIVE_SCAN_OFF,hnsw_iterative_scan_options,PGC_USERSET,0,NULL,NULL,NULL);

DefineCustomIntVariable("hnsw.max_search_tuples","Sets the max number ofcandidates to visit for iterativesearch",

NULL,&hnsw_max_search_tuples,

DefineCustomIntVariable("hnsw.max_scan_tuples","Sets the max number oftuples to visit for iterativescans",

NULL,&hnsw_max_scan_tuples,

20000,1,INT_MAX,PGC_USERSET,0,NULL,NULL,NULL);

DefineCustomRealVariable("hnsw.search_mem_multiplier","Sets the multiple of work_mem to use for iterativesearch",

NULL,&hnsw_search_mem_multiplier,

DefineCustomRealVariable("hnsw.scan_mem_multiplier","Sets the multiple of work_mem to use for iterativescans",

NULL,&hnsw_scan_mem_multiplier,

2,1,1000,PGC_USERSET,0,NULL,NULL,NULL);

MarkGUCPrefixReserved("hnsw");

externinthnsw_ef_search;

externinthnsw_iterative_search;

externinthnsw_max_search_tuples;

externdoublehnsw_search_mem_multiplier;

externinthnsw_iterative_scan;

externinthnsw_max_scan_tuples;

externdoublehnsw_scan_mem_multiplier;

externinthnsw_lock_tranche_id;

{

HNSW_ITERATIVE_SEARCH_OFF,

HNSW_ITERATIVE_SEARCH_RELAXED,

}HnswIterativeSearchMode;

HNSW_ITERATIVE_SCAN_OFF,

HNSW_ITERATIVE_SCAN_RELAXED,

}HnswIterativeScanMode;

typedefstructHnswElementDataHnswElementData;

typedefstructHnswNeighborArrayHnswNeighborArray;

ep=w;

}

returnHnswSearchLayer(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);

returnHnswSearchLayer(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);

}

HnswInitSupport(&so->support,index);

so->maxMemory= (Size) (work_mem*1024.0*hnsw_search_mem_multiplier);

so->maxMemory= (Size) (work_mem*1024.0*hnsw_scan_mem_multiplier);

scan->opaque=so;

if (list_length(so->w)==0)

{

if (hnsw_iterative_search==HNSW_ITERATIVE_SEARCH_OFF)

if (hnsw_iterative_scan==HNSW_ITERATIVE_SCAN_OFF)

break;

if (so->discarded==NULL)

break;

if (so->tuples >=hnsw_max_search_tuples)

if (so->tuples >=hnsw_max_scan_tuples)

{

if (pairingheap_is_empty(so->discarded))

break;

{

ereport(DEBUG1,

(errmsg("hnsw index scan reached memory limit after "INT64_FORMAT" tuples",so->tuples),

errhint("Increase hnsw.search_mem_multiplier to scan more tuples.")));

errhint("Increase hnsw.scan_mem_multiplier to scan more tuples.")));

break;

}

so->w=list_delete_last(so->w);

if (hnsw_iterative_search!=HNSW_ITERATIVE_SEARCH_OFF)

if (hnsw_iterative_scan!=HNSW_ITERATIVE_SCAN_OFF)

{

pfree(element);

pfree(sc);

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

if (hnsw_iterative_search==HNSW_ITERATIVE_SEARCH_STRICT)

if (hnsw_iterative_scan==HNSW_ITERATIVE_SCAN_STRICT)

{

if (sc->distance<so->previousDistance)

continue;

intivfflat_probes;

intivfflat_iterative_search;

intivfflat_iterative_scan;

intivfflat_max_probes;

staticrelopt_kindivfflat_relopt_kind;

staticconststructconfig_enum_entryivfflat_iterative_search_options[]= {

{"off",IVFFLAT_ITERATIVE_SEARCH_OFF, false},

{"relaxed_order",IVFFLAT_ITERATIVE_SEARCH_RELAXED, false},

staticconststructconfig_enum_entryivfflat_iterative_scan_options[]= {

{"off",IVFFLAT_ITERATIVE_SCAN_OFF, false},

{"relaxed_order",IVFFLAT_ITERATIVE_SCAN_RELAXED, false},

{NULL,0, false}

};

"Valid range is 1..lists.",&ivfflat_probes,

IVFFLAT_DEFAULT_PROBES,IVFFLAT_MIN_LISTS,IVFFLAT_MAX_LISTS,PGC_USERSET,0,NULL,NULL,NULL);

DefineCustomEnumVariable("ivfflat.iterative_search","Sets theiterative search mode",

NULL,&ivfflat_iterative_search,

IVFFLAT_ITERATIVE_SEARCH_OFF,ivfflat_iterative_search_options,PGC_USERSET,0,NULL,NULL,NULL);

DefineCustomEnumVariable("ivfflat.iterative_scan","Sets themode for iterative scans",

NULL,&ivfflat_iterative_scan,

IVFFLAT_ITERATIVE_SCAN_OFF,ivfflat_iterative_scan_options,PGC_USERSET,0,NULL,NULL,NULL);

DefineCustomIntVariable("ivfflat.max_probes","Sets the max number of probes for iterativesearch",

DefineCustomIntVariable("ivfflat.max_probes","Sets the max number of probes for iterativescans",

NULL,&ivfflat_max_probes,

IVFFLAT_MAX_LISTS,IVFFLAT_MIN_LISTS,IVFFLAT_MAX_LISTS,PGC_USERSET,0,NULL,NULL,NULL);

externintivfflat_probes;

externintivfflat_iterative_search;

externintivfflat_iterative_scan;

externintivfflat_max_probes;

{

IVFFLAT_ITERATIVE_SEARCH_OFF,

}IvfflatIterativeSearchMode;

IVFFLAT_ITERATIVE_SCAN_OFF,

}IvfflatIterativeScanMode;

{

}

}

if (tuples<100&&ivfflat_iterative_search==IVFFLAT_ITERATIVE_SEARCH_OFF)

if (tuples<100&&ivfflat_iterative_scan==IVFFLAT_ITERATIVE_SCAN_OFF)

ereport(DEBUG1,

(errmsg("index scan found few tuples"),

errdetail("Index may have been created with little data."),

IvfflatGetMetaPageInfo(index,&lists,&dimensions);

if (ivfflat_iterative_search!=IVFFLAT_ITERATIVE_SEARCH_OFF)

if (ivfflat_iterative_scan!=IVFFLAT_ITERATIVE_SCAN_OFF)

maxProbes=Max(ivfflat_max_probes,probes);

maxProbes=probes;

CREATE TABLE t (val vector(3));

INSERT INTO t (val) VALUES ('[0,0,0]'), ('[1,2,3]'), ('[1,1,1]'), (NULL);

CREATE INDEX ON t USING hnsw (val vector_l2_ops);

SET hnsw.iterative_search = strict_order;

SET hnsw.iterative_scan = strict_order;

SET hnsw.ef_search = 1;

SELECT * FROM t ORDER BY val <-> '[3,3,3]';

val

[0,0,0]

(3 rows)

SET hnsw.iterative_search = relaxed_order;

SET hnsw.iterative_scan = relaxed_order;

SELECT * FROM t ORDER BY val <-> '[3,3,3]';

val

---------

[0,0,0]

(3 rows)

RESET hnsw.iterative_search;

RESET hnsw.iterative_scan;

RESET hnsw.ef_search;

DROP TABLE t;

-- unlogged

ERROR: 0 is outside the valid range for parameter "hnsw.ef_search" (1 .. 1000)

SET hnsw.ef_search = 1001;

ERROR: 1001 is outside the valid range for parameter "hnsw.ef_search" (1 .. 1000)

SHOW hnsw.iterative_search;

hnsw.iterative_search

-----------------------

SHOW hnsw.iterative_scan;

hnsw.iterative_scan

---------------------

off

(1 row)

SET hnsw.iterative_search = on;

ERROR: invalid value for parameter "hnsw.iterative_search": "on"

SET hnsw.iterative_scan = on;

ERROR: invalid value for parameter "hnsw.iterative_scan": "on"

HINT: Available values: off, relaxed_order, strict_order.

SHOW hnsw.max_search_tuples;

hnsw.max_search_tuples

------------------------

SHOW hnsw.max_scan_tuples;

hnsw.max_scan_tuples

----------------------

20000

(1 row)

SET hnsw.max_search_tuples = 0;

ERROR: 0 is outside the valid range for parameter "hnsw.max_search_tuples" (1 .. 2147483647)

SET hnsw.max_scan_tuples = 0;

ERROR: 0 is outside the valid range for parameter "hnsw.max_scan_tuples" (1 .. 2147483647)

DROP TABLE t;

CREATE TABLE t (val vector(3));

INSERT INTO t (val) VALUES ('[0,0,0]'), ('[1,2,3]'), ('[1,1,1]'), (NULL);

CREATE INDEX ON t USING ivfflat (val vector_l2_ops) WITH (lists = 3);

SET ivfflat.iterative_search = relaxed_order;

SET ivfflat.iterative_scan = relaxed_order;

SELECT * FROM t ORDER BY val <-> '[3,3,3]';

val

---------

[1,1,1]

(2 rows)

RESET ivfflat.iterative_search;

RESET ivfflat.iterative_scan;

RESET ivfflat.max_probes;

DROP TABLE t;

-- unlogged

ERROR: 0 is outside the valid range for parameter "ivfflat.probes" (1 .. 32768)

SET ivfflat.probes = 32769;

ERROR: 32769 is outside the valid range for parameter "ivfflat.probes" (1 .. 32768)

SHOW ivfflat.iterative_search;

ivfflat.iterative_search

--------------------------

SHOW ivfflat.iterative_scan;

ivfflat.iterative_scan

------------------------

off

(1 row)

SET ivfflat.iterative_search = on;

ERROR: invalid value for parameter "ivfflat.iterative_search": "on"

SET ivfflat.iterative_scan = on;

ERROR: invalid value for parameter "ivfflat.iterative_scan": "on"

HINT: Available values: off, relaxed_order.

SHOW ivfflat.max_probes;

ivfflat.max_probes