benwtrent commented on PR #14085: URL: https://github.com/apache/lucene/pull/14085#issuecomment-2591197302
I updated my branch further. Got some interesting results which indicate that our graph exploration is slightly too expensive (vint reading and graph seek end up dominating the cost), but still ends up faster with nicer recall behavior than baseline: 1M vectors Candidate: Note the weirdness where visited is low, but latency is high, this is due to graph serialization costs (vint and binary search to find nsw offsets). But even with this weirdness, it ends up faster than baseline at comparable recall. ``` recall latency (ms) nDoc topK fanout maxConn beamWidth visited index s index docs/s index size (MB) selectivity vec disk (MB) vec RAM (MB) 0.457 0.394 1000000 100 0 16 100 543 0.00 Infinity 3976.06 0.001 3906.250 3906.250 0.617 4.128 1000000 100 0 16 100 1169 0.00 Infinity 3976.06 0.005 3906.250 3906.250 0.704 4.460 1000000 100 0 16 100 1119 0.00 Infinity 3976.06 0.01 3906.250 3906.250 0.856 4.426 1000000 100 0 16 100 3018 0.00 Infinity 3976.06 0.05 3906.250 3906.250 0.860 3.279 1000000 100 0 16 100 3190 0.00 Infinity 3976.06 0.10 3906.250 3906.250 0.856 2.868 1000000 100 0 16 100 3280 0.00 Infinity 3976.06 0.20 3906.250 3906.250 0.844 2.595 1000000 100 0 16 100 3341 0.00 Infinity 3976.06 0.30 3906.250 3906.250 0.846 2.375 1000000 100 0 16 100 3277 0.00 Infinity 3976.06 0.40 3906.250 3906.250 0.848 2.125 1000000 100 0 16 100 3127 0.00 Infinity 3976.06 0.50 3906.250 3906.250 0.852 1.913 1000000 100 0 16 100 2926 0.00 Infinity 3976.06 0.60 3906.250 3906.250 0.855 1.674 1000000 100 0 16 100 2669 0.00 Infinity 3976.06 0.70 3906.250 3906.250 0.858 1.503 1000000 100 0 16 100 2357 0.00 Infinity 3976.06 0.80 3906.250 3906.250 0.866 1.242 1000000 100 0 16 100 2009 0.00 Infinity 3976.06 0.90 3906.250 3906.250 0.870 1.198 1000000 100 0 16 100 1931 0.00 Infinity 3976.06 0.95 3906.250 3906.250 1.000 0.613 1000000 100 250 16 100 1082 0.00 Infinity 3976.06 0.001 3906.250 3906.250 0.830 13.153 1000000 100 250 16 100 2159 0.00 Infinity 3976.06 0.005 3906.250 3906.250 0.869 15.463 1000000 100 250 16 100 3083 0.00 Infinity 3976.06 0.01 3906.250 3906.250 0.943 13.776 1000000 100 250 16 100 8378 0.00 Infinity 3976.06 0.05 3906.250 3906.250 0.952 10.126 1000000 100 250 16 100 8947 0.00 Infinity 3976.06 0.10 3906.250 3906.250 0.957 7.990 1000000 100 250 16 100 9164 0.00 Infinity 3976.06 0.20 3906.250 3906.250 0.958 6.964 1000000 100 250 16 100 9239 0.00 Infinity 3976.06 0.30 3906.250 3906.250 0.960 6.533 1000000 100 250 16 100 9077 0.00 Infinity 3976.06 0.40 3906.250 3906.250 0.961 5.836 1000000 100 250 16 100 8666 0.00 Infinity 3976.06 0.50 3906.250 3906.250 0.963 5.671 1000000 100 250 16 100 8117 0.00 Infinity 3976.06 0.60 3906.250 3906.250 0.965 4.923 1000000 100 250 16 100 7348 0.00 Infinity 3976.06 0.70 3906.250 3906.250 0.966 4.151 1000000 100 250 16 100 6374 0.00 Infinity 3976.06 0.80 3906.250 3906.250 0.969 3.323 1000000 100 250 16 100 5392 0.00 Infinity 3976.06 0.90 3906.250 3906.250 0.970 3.188 1000000 100 250 16 100 5212 0.00 Infinity 3976.06 0.95 3906.250 3906.250 ``` Baseline: ``` recall latency (ms) nDoc topK fanout maxConn beamWidth visited index s index docs/s index size (MB) selectivity vec disk (MB) vec RAM (MB) 1.000 1.041 1000000 100 0 16 100 1955 0.00 Infinity 3976.06 0.001 3906.250 3906.250 1.000 5.594 1000000 100 0 16 100 9699 0.00 Infinity 3976.06 0.005 3906.250 3906.250 1.000 12.979 1000000 100 0 16 100 19847 0.00 Infinity 3976.06 0.01 3906.250 3906.250 0.956 15.219 1000000 100 0 16 100 22052 0.00 Infinity 3976.06 0.05 3906.250 3906.250 0.950 8.020 1000000 100 0 16 100 12591 0.00 Infinity 3976.06 0.10 3906.250 3906.250 0.936 4.343 1000000 100 0 16 100 7148 0.00 Infinity 3976.06 0.20 3906.250 3906.250 0.926 3.095 1000000 100 0 16 100 5202 0.00 Infinity 3976.06 0.30 3906.250 3906.250 0.917 2.280 1000000 100 0 16 100 4077 0.00 Infinity 3976.06 0.40 3906.250 3906.250 0.907 1.944 1000000 100 0 16 100 3401 0.00 Infinity 3976.06 0.50 3906.250 3906.250 0.899 1.750 1000000 100 0 16 100 2951 0.00 Infinity 3976.06 0.60 3906.250 3906.250 0.892 1.547 1000000 100 0 16 100 2626 0.00 Infinity 3976.06 0.70 3906.250 3906.250 0.887 1.414 1000000 100 0 16 100 2376 0.00 Infinity 3976.06 0.80 3906.250 3906.250 0.883 1.277 1000000 100 0 16 100 2154 0.00 Infinity 3976.06 0.90 3906.250 3906.250 0.879 1.221 1000000 100 0 16 100 2061 0.00 Infinity 3976.06 0.95 3906.250 3906.250 1.000 1.091 1000000 100 250 16 100 1955 0.00 Infinity 3976.06 0.001 3906.250 3906.250 1.000 5.649 1000000 100 250 16 100 9699 0.00 Infinity 3976.06 0.005 3906.250 3906.250 1.000 13.369 1000000 100 250 16 100 19847 0.00 Infinity 3976.06 0.01 3906.250 3906.250 0.999 57.741 1000000 100 250 16 100 90785 0.00 Infinity 3976.06 0.05 3906.250 3906.250 0.991 25.507 1000000 100 250 16 100 35212 0.00 Infinity 3976.06 0.10 3906.250 3906.250 0.988 13.688 1000000 100 250 16 100 19755 0.00 Infinity 3976.06 0.20 3906.250 3906.250 0.985 9.582 1000000 100 250 16 100 14228 0.00 Infinity 3976.06 0.30 3906.250 3906.250 0.984 7.421 1000000 100 250 16 100 11239 0.00 Infinity 3976.06 0.40 3906.250 3906.250 0.982 5.938 1000000 100 250 16 100 9366 0.00 Infinity 3976.06 0.50 3906.250 3906.250 0.980 5.067 1000000 100 250 16 100 8080 0.00 Infinity 3976.06 0.60 3906.250 3906.250 0.978 4.419 1000000 100 250 16 100 7147 0.00 Infinity 3976.06 0.70 3906.250 3906.250 0.976 3.970 1000000 100 250 16 100 6443 0.00 Infinity 3976.06 0.80 3906.250 3906.250 0.975 3.587 1000000 100 250 16 100 5843 0.00 Infinity 3976.06 0.90 3906.250 3906.250 0.974 3.394 1000000 100 250 16 100 5587 0.00 Infinity 3976.06 0.95 3906.250 3906.250 ``` -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org