On 11/06/2024 07:53, Thomas Munro wrote:
Someone involved in that project mentioned that it's probably not a great topic to research in practice, because real world users of HNSW use fully cached ie prewarmed indexes, because the performance is so bad otherwise. (Though maybe that argument is a little circular...).
I think that's true in practice for *building* an HNSW index, but faster *searching* when the index is not in memory seems quite useful. And of course, faster is always better, even if it's only in a non-optimal scenario.
So although this patch clearly speeds up cold HSNW searches to a degree controlled by effective_io_concurrency, I'll probably look for something else. Suggestions for interesting index types to look at streamifying are very welcome!
GiST and GIN?
Hmm. If that's really true about HNSW though, then there may still be an opportunity to do automatic memory prefetching[1]. But then in the case of index building, "stream" is NULL in this patch anyway. It surely must also be possible to find some good places to put profitable explicit pg_mem_prefetch() calls given the predictability and the need to get only ~60ns ahead for that usage. I didn't look into that because I was trying to prove things about read_stream.c, not get involved in another project :-D Here ends my science experiment report, which I'm dropping here just in case others see useful ideas here. The main thing I learned about the read stream API is that it'd be nice to be able to reset the stream but preserve the distance (something that came up on the streaming sequential scan thread for a different reason), to deal with cases where look-ahead opportunities come in bursts but you want a longer lived stream than I used here. That is the reason the patch creates and destroys temporary streams in a loop; doh. It also provides an interesting case study for what speculative random look-ahead support might need to look like.
This reminds me of a prototype I wrote earlier, see https://github.com/pgvector/pgvector/pull/386, 1st commit. It reorganizes HnswSearchLayer() so that it in iteration, it first collects all the neighbors to visit, and then visits them, somewhat similar to your patch.
-- Heikki Linnakangas Neon (https://neon.tech)
