MIME-Version: 1.0
From: Thomas Munro <thomas.munro@gmail.com>
Date: Tue, 11 Jun 2024 16:53:41 +1200
Message-ID: <CA+hUKGJ_7NKd46nx1wbyXWriuZSNzsTfm+rhEuvU6nxZi3-KVw@mail.gmail.com>
Subject: Trying out read streams in pgvector (an extension)
To: pgsql-hackers <pgsql-hackers@postgresql.org>
Content-Type: multipart/mixed; boundary="000000000000f8881e061a960e65"
Archived-At: <https://www.postgresql.org/message-id/CA%2BhUKGJ_7NKd46nx1wbyXWriuZSNzsTfm%2BrhEuvU6nxZi3-KVw%40mail.gmail.com>
Precedence: bulk

--000000000000f8881e061a960e65
Content-Type: text/plain; charset="UTF-8"

Hi,

I was looking around for an exotic index type to try the experience of
streamifying an extension, ie out-of-core code.  I am totally new to
pgvector, but since everyone keeps talking about it, I could not avoid
picking up some basic facts in the pgconf.dev hallway track, and
understood that its scans have some degree of known-order access
predictability, and then also some degree of fuzzy-predictable
order-not-yet-determined access too.  It's also quite random in the
I/O sense.

Here's a toy to streamify the known-order part.  I think for the fuzzy
part that links those parts together, maybe there is some way to guess
when it's a reasonable time to speculatively prefetch the lowest order
stuff in the pairing heap, and then deal with it if you're wrong, but
I didn't try that...

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...).
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!

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.

[1] https://www.postgresql.org/message-id/flat/CA%2BhUKGKNUMnqubrrz8pRBdEM8vHeSCZcNq7iqERmkt6zPtpA3g%40mail.gmail.com

=== setup ====

create extension vector;

create or replace function random_vector(dimensions int)
returns vector language sql
begin atomic;
  select array_agg(random())::vector
    from generate_series(1, dimensions);
end;

create table t (id serial, embedding vector(6));

insert into t (embedding)
select random_vector(6)
  from generate_series(1, 1000000);

set maintenance_work_mem = '2GB';

create index on t using hnsw(embedding vector_l2_ops);

=== test of a hot search, assuming repeated ===

select embedding <-> '[0.5,0.5,0.5,0.5,0.5,0.5]'::vector
  from t
 where embedding <-> '[0.5,0.5,0.5,0.5,0.5,0.5]'::vector < 0.2
 order by 1 limit 20;

=== test of a cold search, assuming empty caches ===

create or replace function test()
returns void
language plpgsql as
$$
declare
  my_vec vector(6) := random_vector(6);
begin
  perform embedding <-> my_vec
     from t
    where embedding <-> my_vec < 0.2
    order by 1 limit 20;
end;
$$;

select test();

(Make sure you remember to set effective_io_concurrency to an
interesting number if you want to generate a lot of overlapping
fadvise calls.)

--000000000000f8881e061a960e65
Content-Type: application/octet-stream; 
	name="0001-XXX-toy-use-of-read-stream-API.patch"
Content-Disposition: attachment; 
	filename="0001-XXX-toy-use-of-read-stream-API.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_lx9w2rkj0>
X-Attachment-Id: f_lx9w2rkj0

RnJvbSAzNDRjYjc3NThkNTI1OTQzOTJlOTU1ZWZlYjMzYzMyY2VkZmNiNDdhIE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBUaG9tYXMgTXVucm8gPHRob21hcy5tdW5yb0BnbWFpbC5jb20+
CkRhdGU6IFR1ZSwgMTEgSnVuIDIwMjQgMTQ6MzI6NDcgKzEyMDAKU3ViamVjdDogW1BBVENIXSBY
WFggdG95IHVzZSBvZiByZWFkIHN0cmVhbSBBUEkKCi0tLQogc3JjL2huc3cuaCAgICAgIHwgIDEg
Kwogc3JjL2huc3d1dGlscy5jIHwgOTMgKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysr
KysrKysrKysrKysrKysrKwogMiBmaWxlcyBjaGFuZ2VkLCA5NCBpbnNlcnRpb25zKCspCgpkaWZm
IC0tZ2l0IGEvc3JjL2huc3cuaCBiL3NyYy9obnN3LmgKaW5kZXggNDgwYWQ5Zi4uZTczODI0MSAx
MDA2NDQKLS0tIGEvc3JjL2huc3cuaAorKysgYi9zcmMvaG5zdy5oCkBAIC0xMzYsNiArMTM2LDcg
QEAgc3RydWN0IEhuc3dFbGVtZW50RGF0YQogCXVpbnQ4CQlkZWxldGVkOwogCXVpbnQzMgkJaGFz
aDsKIAlIbnN3TmVpZ2hib3JzUHRyIG5laWdoYm9yczsKKwlCdWZmZXIJCWJ1ZmZlcjsKIAlCbG9j
a051bWJlciBibGtubzsKIAlPZmZzZXROdW1iZXIgb2Zmbm87CiAJT2Zmc2V0TnVtYmVyIG5laWdo
Ym9yT2Zmbm87CmRpZmYgLS1naXQgYS9zcmMvaG5zd3V0aWxzLmMgYi9zcmMvaG5zd3V0aWxzLmMK
aW5kZXggZDNiYTkxMS4uYjlhZGRmZiAxMDA2NDQKLS0tIGEvc3JjL2huc3d1dGlscy5jCisrKyBi
L3NyYy9obnN3dXRpbHMuYwpAQCAtMTQsNiArMTQsMTAgQEAKICNpbmNsdWRlICJ1dGlscy9tZW1k
ZWJ1Zy5oIgogI2luY2x1ZGUgInV0aWxzL3JlbC5oIgogCisjaWYgUEdfVkVSU0lPTl9OVU0gPj0g
MTcwMDAwCisjaW5jbHVkZSAic3RvcmFnZS9yZWFkX3N0cmVhbS5oIgorI2VuZGlmCisKICNpZiBQ
R19WRVJTSU9OX05VTSA+PSAxMzAwMDAKICNpbmNsdWRlICJjb21tb24vaGFzaGZuLmgiCiAjZWxz
ZQpAQCAtMjc4LDYgKzI4Miw5IEBAIEhuc3dJbml0RWxlbWVudEZyb21CbG9jayhCbG9ja051bWJl
ciBibGtubywgT2Zmc2V0TnVtYmVyIG9mZm5vKQogCUhuc3dFbGVtZW50IGVsZW1lbnQgPSBwYWxs
b2Moc2l6ZW9mKEhuc3dFbGVtZW50RGF0YSkpOwogCWNoYXIJICAgKmJhc2UgPSBOVUxMOwogCisj
aWYgUEdfVkVSU0lPTl9OVU0gPj0gMTcwMDAwCisJZWxlbWVudC0+YnVmZmVyID0gSW52YWxpZEJ1
ZmZlcjsKKyNlbmRpZgogCWVsZW1lbnQtPmJsa25vID0gYmxrbm87CiAJZWxlbWVudC0+b2Zmbm8g
PSBvZmZubzsKIAlIbnN3UHRyU3RvcmUoYmFzZSwgZWxlbWVudC0+bmVpZ2hib3JzLCAoSG5zd05l
aWdoYm9yQXJyYXlQdHIgKikgTlVMTCk7CkBAIC01NTIsNyArNTU5LDIwIEBAIEhuc3dMb2FkRWxl
bWVudChIbnN3RWxlbWVudCBlbGVtZW50LCBmbG9hdCAqZGlzdGFuY2UsIERhdHVtICpxLCBSZWxh
dGlvbiBpbmRleCwKIAlIbnN3RWxlbWVudFR1cGxlIGV0dXA7CiAKIAkvKiBSZWFkIHZlY3RvciAq
LworI2lmIFBHX1ZFUlNJT05fTlVNID49IDE3MDAwMAorCWlmIChlbGVtZW50LT5idWZmZXIgIT0g
SW52YWxpZEJ1ZmZlcikKKwl7CisJCS8qIEJ1ZmZlciBwaW5uZWQgYWxyZWFkeS4gKi8KKwkJYnVm
ID0gZWxlbWVudC0+YnVmZmVyOworCQlBc3NlcnQoQnVmZmVyR2V0QmxvY2tOdW1iZXIoYnVmKSA9
PSBlbGVtZW50LT5ibGtubyk7CisJfQorCWVsc2UKKwl7CisJCWJ1ZiA9IFJlYWRCdWZmZXIoaW5k
ZXgsIGVsZW1lbnQtPmJsa25vKTsKKwl9CisjZWxzZQogCWJ1ZiA9IFJlYWRCdWZmZXIoaW5kZXgs
IGVsZW1lbnQtPmJsa25vKTsKKyNlbmRpZgogCUxvY2tCdWZmZXIoYnVmLCBCVUZGRVJfTE9DS19T
SEFSRSk7CiAJcGFnZSA9IEJ1ZmZlckdldFBhZ2UoYnVmKTsKIApAQCAtNzE0LDYgKzczNCwyOCBA
QCBDb3VudEVsZW1lbnQoY2hhciAqYmFzZSwgSG5zd0VsZW1lbnQgc2tpcEVsZW1lbnQsIEhuc3dD
YW5kaWRhdGUgKiBoYykKIAlyZXR1cm4gZS0+aGVhcHRpZHNMZW5ndGggIT0gMDsKIH0KIAorI2lm
IFBHX1ZFUlNJT05fTlVNID49IDE3MDAwMAordHlwZWRlZiBzdHJ1Y3QgSG5zd1NlYXJjaExheWVy
TmV4dEJsb2NrRGF0YSB7CisJY2hhcgkgICAqYmFzZTsKKwlIbnN3Q2FuZGlkYXRlICoqaXRlbXM7
CisJaW50CQkJbml0ZW1zOworCWludAkJCWk7Cit9IEhuc3dTZWFyY2hMYXllck5leHRCbG9ja0Rh
dGE7CisKK3N0YXRpYyBCbG9ja051bWJlcgorSG5zd1NlYXJjaExheWVyTmV4dEJsb2NrKFJlYWRT
dHJlYW0gKnN0cmVhbSwgdm9pZCAqY2FsbGJhY2tfZGF0YSwgdm9pZCAqcGVyX2J1ZmZlcl9kYXRh
KQoreworCUhuc3dTZWFyY2hMYXllck5leHRCbG9ja0RhdGEgKmRhdGEgPSBjYWxsYmFja19kYXRh
OworCUhuc3dFbGVtZW50IGhjZTsKKworCWlmIChkYXRhLT5pID09IGRhdGEtPm5pdGVtcykKKwkJ
cmV0dXJuIEludmFsaWRCbG9ja051bWJlcjsKKworCWhjZSA9IEhuc3dQdHJBY2Nlc3MoZGF0YS0+
YmFzZSwgZGF0YS0+aXRlbXNbZGF0YS0+aSsrXS0+ZWxlbWVudCk7CisJcmV0dXJuIGhjZS0+Ymxr
bm87Cit9CisjZW5kaWYKKwogLyoKICAqIEFsZ29yaXRobSAyIGZyb20gcGFwZXIKICAqLwpAQCAt
NzI5LDYgKzc3MSwxMSBAQCBIbnN3U2VhcmNoTGF5ZXIoY2hhciAqYmFzZSwgRGF0dW0gcSwgTGlz
dCAqZXAsIGludCBlZiwgaW50IGxjLCBSZWxhdGlvbiBpbmRleCwgRgogCUhuc3dOZWlnaGJvckFy
cmF5ICpuZWlnaGJvcmhvb2REYXRhID0gTlVMTDsKIAlTaXplCQluZWlnaGJvcmhvb2RTaXplOwog
CisjaWYgUEdfVkVSU0lPTl9OVU0gPj0gMTcwMDAwCisJUmVhZFN0cmVhbSAqc3RyZWFtOworCUhu
c3dTZWFyY2hMYXllck5leHRCbG9ja0RhdGEgc3RyZWFtX2NhbGxiYWNrX2RhdGE7CisjZW5kaWYK
KwogCUluaXRWaXNpdGVkKGJhc2UsICZ2LCBpbmRleCwgZWYsIG0pOwogCiAJLyogQ3JlYXRlIGxv
Y2FsIG1lbW9yeSBmb3IgbmVpZ2hib3Job29kIGlmIG5lZWRlZCAqLwpAQCAtNzY0LDYgKzgxMSw4
IEBAIEhuc3dTZWFyY2hMYXllcihjaGFyICpiYXNlLCBEYXR1bSBxLCBMaXN0ICplcCwgaW50IGVm
LCBpbnQgbGMsIFJlbGF0aW9uIGluZGV4LCBGCiAJCUhuc3dDYW5kaWRhdGUgKmMgPSAoKEhuc3dQ
YWlyaW5nSGVhcE5vZGUgKikgcGFpcmluZ2hlYXBfcmVtb3ZlX2ZpcnN0KEMpKS0+aW5uZXI7CiAJ
CUhuc3dDYW5kaWRhdGUgKmYgPSAoKEhuc3dQYWlyaW5nSGVhcE5vZGUgKikgcGFpcmluZ2hlYXBf
Zmlyc3QoVykpLT5pbm5lcjsKIAkJSG5zd0VsZW1lbnQgY0VsZW1lbnQ7CisJCUhuc3dDYW5kaWRh
dGUgKml0ZW1zW0hOU1dfTUFYX1NJWkVdOworCQlpbnQgbml0ZW1zOwogCiAJCWlmIChjLT5kaXN0
YW5jZSA+IGYtPmRpc3RhbmNlKQogCQkJYnJlYWs7CkBAIC03ODUsNiArODM0LDggQEAgSG5zd1Nl
YXJjaExheWVyKGNoYXIgKmJhc2UsIERhdHVtIHEsIExpc3QgKmVwLCBpbnQgZWYsIGludCBsYywg
UmVsYXRpb24gaW5kZXgsIEYKIAkJCW5laWdoYm9yaG9vZCA9IG5laWdoYm9yaG9vZERhdGE7CiAJ
CX0KIAorCQkvKiBCdWlsZCBhIGxpc3Qgb2YgaW5kZXhlcyBvZiBuZWlnaGJvcnMgdG8gdmlzaXQu
ICovCisJCW5pdGVtcyA9IDA7CiAJCWZvciAoaW50IGkgPSAwOyBpIDwgbmVpZ2hib3Job29kLT5s
ZW5ndGg7IGkrKykKIAkJewogCQkJSG5zd0NhbmRpZGF0ZSAqZSA9ICZuZWlnaGJvcmhvb2QtPml0
ZW1zW2ldOwpAQCAtNzkzLDYgKzg0NCwzOCBAQCBIbnN3U2VhcmNoTGF5ZXIoY2hhciAqYmFzZSwg
RGF0dW0gcSwgTGlzdCAqZXAsIGludCBlZiwgaW50IGxjLCBSZWxhdGlvbiBpbmRleCwgRgogCQkJ
QWRkVG9WaXNpdGVkKGJhc2UsICZ2LCBlLCBpbmRleCwgJnZpc2l0ZWQpOwogCiAJCQlpZiAoIXZp
c2l0ZWQpCisJCQkJaXRlbXNbbml0ZW1zKytdID0gZTsKKwkJfQorCisjaWYgUEdfVkVSU0lPTl9O
VU0gPj0gMTcwMDAwCisJCXN0cmVhbV9jYWxsYmFja19kYXRhLmJhc2UgPSBiYXNlOworCQlzdHJl
YW1fY2FsbGJhY2tfZGF0YS5pdGVtcyA9IGl0ZW1zOworCQlzdHJlYW1fY2FsbGJhY2tfZGF0YS5u
aXRlbXMgPSBuaXRlbXM7CisJCXN0cmVhbV9jYWxsYmFja19kYXRhLmkgPSAwOworCisJCS8qCisJ
CSAqIFhYWCBGb3IgdGhpcyBxdWljay1hbmQtZGlydHkgaGFjaywgd2UnbGwgdXNlIGEgdGVtcG9y
YXJ5IHN0cmVhbSBmb3IKKwkJICogZWFjaCBzZXQgb2YgbmVpZ2hib3JzIHdlIHZpc2l0Li4uICBT
aG91bGQgcmVhbGx5IHJlLXVzZSBhIHN0cmVhbSwKKwkJICogYW5kIHJlc2V0IGl0IGFmdGVyIHdl
IGhpdCBzdGFsbCBwb2ludHMgdGhhdCBuZWVkIG1vcmUgZGF0YSB0byBsb29rCisJCSAqIGZ1cnRo
ZXIgYWhlYWQuCisJCSAqLworCQlpZiAoaW5kZXgpCisJCQlzdHJlYW0gPSByZWFkX3N0cmVhbV9i
ZWdpbl9yZWxhdGlvbihSRUFEX1NUUkVBTV9GVUxMLAorCQkJCQkJCQkJCQkJTlVMTCwKKwkJCQkJ
CQkJCQkJCWluZGV4LAorCQkJCQkJCQkJCQkJTUFJTl9GT1JLTlVNLAorCQkJCQkJCQkJCQkJSG5z
d1NlYXJjaExheWVyTmV4dEJsb2NrLAorCQkJCQkJCQkJCQkJJnN0cmVhbV9jYWxsYmFja19kYXRh
LAorCQkJCQkJCQkJCQkJMCk7CisJCWVsc2UKKwkJCXN0cmVhbSA9IE5VTEw7CisjZW5kaWYKKwor
CQkvKiBWaXNpdCB0aGVtLiAqLworCQlmb3IgKGludCBpID0gMDsgaSA8IG5pdGVtczsgaSsrKQor
CQl7CisJCQlIbnN3Q2FuZGlkYXRlICplID0gaXRlbXNbaV07CisKIAkJCXsKIAkJCQlmbG9hdAkJ
ZURpc3RhbmNlOwogCQkJCUhuc3dFbGVtZW50IGVFbGVtZW50ID0gSG5zd1B0ckFjY2VzcyhiYXNl
LCBlLT5lbGVtZW50KTsKQEAgLTgwMiw3ICs4ODUsMTMgQEAgSG5zd1NlYXJjaExheWVyKGNoYXIg
KmJhc2UsIERhdHVtIHEsIExpc3QgKmVwLCBpbnQgZWYsIGludCBsYywgUmVsYXRpb24gaW5kZXgs
IEYKIAkJCQlpZiAoaW5kZXggPT0gTlVMTCkKIAkJCQkJZURpc3RhbmNlID0gR2V0Q2FuZGlkYXRl
RGlzdGFuY2UoYmFzZSwgZSwgcSwgcHJvY2luZm8sIGNvbGxhdGlvbik7CiAJCQkJZWxzZQorCQkJ
CXsKKyNpZiBQR19WRVJTSU9OX05VTSA+PSAxNzAwMDAKKwkJCQkJaWYgKHN0cmVhbSkKKwkJCQkJ
CWVFbGVtZW50LT5idWZmZXIgPSByZWFkX3N0cmVhbV9uZXh0X2J1ZmZlcihzdHJlYW0sIE5VTEwp
OworI2VuZGlmCiAJCQkJCUhuc3dMb2FkRWxlbWVudChlRWxlbWVudCwgJmVEaXN0YW5jZSwgJnEs
IGluZGV4LCBwcm9jaW5mbywgY29sbGF0aW9uLCBpbnNlcnRpbmcsIHdsZW4gPj0gZWYgPyAmZi0+
ZGlzdGFuY2UgOiBOVUxMKTsKKwkJCQl9CiAKIAkJCQlpZiAoZURpc3RhbmNlIDwgZi0+ZGlzdGFu
Y2UgfHwgd2xlbiA8IGVmKQogCQkJCXsKQEAgLTgzOCw2ICs5MjcsMTAgQEAgSG5zd1NlYXJjaExh
eWVyKGNoYXIgKmJhc2UsIERhdHVtIHEsIExpc3QgKmVwLCBpbnQgZWYsIGludCBsYywgUmVsYXRp
b24gaW5kZXgsIEYKIAkJCQl9CiAJCQl9CiAJCX0KKyNpZiBQR19WRVJTSU9OX05VTSA+PSAxNzAw
MDAKKwkJaWYgKHN0cmVhbSkKKwkJCXJlYWRfc3RyZWFtX2VuZChzdHJlYW0pOworI2VuZGlmCiAJ
fQogCiAJLyogQWRkIGVhY2ggZWxlbWVudCBvZiBXIHRvIHcgKi8KLS0gCjIuNDUuMQoK
--000000000000f8881e061a960e65--