Skip to content

Instantly share code, notes, and snippets.

@cutecutecat

cutecutecat/README.md

Last active June 25, 2025 06:19
Show Gist options
  • Save cutecutecat/1ca66f896be8290e5360b8fabf8879b6 to your computer and use it in GitHub Desktop.
Save cutecutecat/1ca66f896be8290e5360b8fabf8879b6 to your computer and use it in GitHub Desktop.
Download ZIP
LAION-400m benchmark
Raw
README.md

How to use the LAION-400m benchmark scripts

Preset

  • Machine G: with nvidia GPU, such like A10 to build external K-means, with minimum hardware requirements:
    • at least 120GB memory
  • Machine D: An instance like i7ie.2xlarge to do the benchmark, with minimum hardware requirements:
    • at least 4000G NVME SSD
    • at least 64GB memory
    • at least 8 vcpus

Python environment on machine G:

conda install numpy pytorch::faiss-gpu tqdm

Python environment on machine D:

conda install conda-forge::pgvector-python numpy conda-forge::psycopg tqdm
# or
pip install pgvector numpy psycopg tqdm

Benchmark

# Step 1 - download dataset - on both machine G and D
python download.py

# Step 2 - train k-means - on machine G
# Time: About 1 day. Consider using the `screen` command to avoid interruptions.
python train.py -g # with GPU
python train.py # without GPU

# Step 3 - Copy centroids.npy from machine G to machine D
aws s3 cp centroids.npy s3://...
aws s3 cp s3://... centroids.npy

# You can destroy machine G now.

# Step 4 - Init VectorChord - on machine D
sudo apt-get install lvm2
sudo pvcreate /dev/nvme1n1 /dev/nvme2n1
sudo vgcreate myvg /dev/nvme1n1 /dev/nvme2n1
sudo lvcreate -L 4000G -n mylv myvg
sudo mkfs.xfs /dev/myvg/mylv
sudo mkdir -p /data
sudo mount /dev/myvg/mylv /data
docker run \
  --name vectorchord \
  -e POSTGRES_PASSWORD=123 \
  -p 5432:5432 \
  -v /data/pg:/var/lib/postgresql/data \
  -d ghcr.io/tensorchord/vchord-postgres:pg17-v0.4.3
PGPASSWORD=123 psql -U postgres -h localhost -c "ALTER SYSTEM SET shared_buffers = '48GB'; ALTER SYSTEM SET max_worker_processes = 16;"
CONTAINER_ID=$(docker ps -q -f "name=vectorchord")
docker stop $CONTAINER_ID && docker start $CONTAINER_ID

# Step 5 - Insert data to table and build index - on machine D
# Time: About 2 days. Consider using the `screen` command to avoid interruptions.
python index.py -c centroids.npy

# Step 6 - Run experiments - on machine D
./all_exps.sh "$CONTAINER_ID" > result.txt

Result

nprob epsilon cold QPS warm QPS recall
10 0.8 18.50 114.13 0.8188
100 0.8 10.19 48.56 0.9194
100 1.0 7.04 41.75 0.9326
200 1.0 5.84 28.37 0.9410
400 1.5 2.04 7.90 0.9582
500 1.5 1.97 3.54 0.9602
800 1.9 0.90 1.11 0.9638
Raw
all_exps.sh
CONTAINER_ID=$1
docker stop $CONTAINER_ID && docker start $CONTAINER_ID && sudo sh -c "sync; echo 1 > /proc/sys/vm/drop_caches"
sleep 10
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 10 --epsilon 0.8
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 10 --epsilon 0.8
docker stop $CONTAINER_ID && docker start $CONTAINER_ID && sudo sh -c "sync; echo 1 > /proc/sys/vm/drop_caches"
sleep 10
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 100 --epsilon 0.8
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 100 --epsilon 0.8
docker stop $CONTAINER_ID && docker start $CONTAINER_ID && sudo sh -c "sync; echo 1 > /proc/sys/vm/drop_caches"
sleep 10
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 100 --epsilon 1.0
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 100 --epsilon 1.0
docker stop $CONTAINER_ID && docker start $CONTAINER_ID && sudo sh -c "sync; echo 1 > /proc/sys/vm/drop_caches"
sleep 10
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 200 --epsilon 1.0
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 200 --epsilon 1.0
docker stop $CONTAINER_ID && docker start $CONTAINER_ID && sudo sh -c "sync; echo 1 > /proc/sys/vm/drop_caches"
sleep 10
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 400 --epsilon 1.5
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 400 --epsilon 1.5
docker stop $CONTAINER_ID && docker start $CONTAINER_ID && sudo sh -c "sync; echo 1 > /proc/sys/vm/drop_caches"
sleep 10
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 500 --epsilon 1.5
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 500 --epsilon 1.5
docker stop $CONTAINER_ID && docker start $CONTAINER_ID && sudo sh -c "sync; echo 1 > /proc/sys/vm/drop_caches"
sleep 10
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 800 --epsilon 1.9
python bench.py -n laion --url postgres://postgres:123@localhost:5432/postgres -m cos --nprob 800 --epsilon 1.9
Raw
bench.py
full_scan_result = [
[89825391, 368490947, 333089524, 185403414, 7296653, 204973778, 196913901, 339163574, 254816544, 193173014, 381632317, 267482536, 185627420, 211487955, 131135693, 157753473, 96636665, 64841409, 179523861, 139380960, 239780863, 95724227, 316193996, 361955937, 91825839, 137004252, 322096240, 135551629, 32990356, 375797830, 6527218, 359998002, 246276917, 191897499, 155369525, 345362669, 356311131, 396176685, 69862403, 172949282, 272964900, 370807692, 284917388, 76780935, 400521363, 542194, 218296105, 178870, 380979757],
[386595919, 61896664, 8804336, 226182034, 45680863, 224607560, 222954424, 333114034, 287227481, 393571334, 96987956, 273745471, 319573622, 44402572, 304778692, 92459314, 57630966, 183428709, 195846562, 291069973, 373888894, 243076067, 111181705, 167077000, 326282059, 372604960, 267549550, 216225398, 84645442, 127368047, 31692739, 84909776, 103071729, 107175218, 369345381, 226800161, 259191341, 162039980, 282781361, 225601361, 158355696, 58402180, 348550243, 356304637, 236265172, 33615656, 293375092, 371428749, 311613661, 108937926],
[352859737, 15110696, 5907798, 299079279, 346880649, 52038496, 405135433, 104690663, 186209629, 294040729, 235668171, 137199934, 2, 119236794, 139868546, 70673321, 223960805, 86304631, 158485952, 117079292, 404617456, 234961502, 26504678, 367830357, 222477011, 27390120, 367303435, 160433634, 395882117, 268180181, 266678951, 65230456, 74069285, 317428888, 62522869, 260495709, 280007342, 264787650, 227186152, 22588546, 225693090, 311396784, 246786095, 249180726, 74588159, 397199254, 229529051, 257407783, 181496253, 400805006],
[3, 396528020, 335118222, 198329387, 94173194, 375766430, 69591016, 32929508, 270294079, 117523601, 328540614, 356871093, 327302781, 207721546, 184630088, 399097699, 187864492, 259418738, 330546590, 150740186, 151479290, 165660259, 89606222, 100574011, 165062673, 172484899, 124224240, 15184919, 49730827, 293292370, 82474979, 391585764, 114037971, 308311047, 72383794, 226009204, 390626889, 51886471, 133955156, 375262082, 288903630, 385540974, 75996960, 140129010, 41495610, 256333290, 333091119, 96165513, 362971750, 209937499],
[253645220, 4, 251671117, 158575783, 287898580, 255142386, 315185707, 32747019, 105753987, 256299810, 330140298, 110547061, 209267716, 172524582, 208686576, 108286799, 331051819, 163951958, 241386205, 108179910, 36826419, 5046308, 31060701, 121552376, 102038495, 353264526, 216574610, 132648397, 284487217, 63617410, 316676817, 28552319, 258540308, 89960311, 136703052, 105022918, 15453412, 395458484, 359814322, 403448302, 287835163, 354802928, 398412757, 110569313, 187094121, 398848238, 388618741, 356369149, 313524082, 257076606],
[5, 31924199, 242522846, 13213298, 253202138, 254803667, 24871821, 246828057, 12880676, 276131820, 62034269, 114904797, 265284073, 223057454, 219172319, 361267378, 386935190, 110072696, 172131446, 16850322, 375660870, 32985695, 320256139, 218421908, 231632409, 311395491, 257009790, 362010033, 241108317, 383337704, 340408577, 267891821, 400165473, 213829929, 61633819, 59536922, 300273332, 313124645, 255384370, 209904530, 51717321, 6394207, 382995122, 280246811, 269796150, 172722481, 379484002, 86491039, 379189297, 97988749],
[6, 317168225, 338193279, 323426330, 84235862, 166963272, 31610485, 268114518, 158918136, 150450759, 198978417, 114844146, 308388124, 401404966, 319979439, 230036870, 391517942, 328938353, 161679097, 158826240, 296481218, 401552373, 79076320, 361703777, 102730662, 7030980, 252821767, 250014887, 331526495, 33841512, 204640255, 136314736, 113562701, 6505311, 86287354, 207657747, 357311320, 131713453, 328641803, 320395689, 345153685, 348800124, 71696224, 157458177, 109656213, 14066105, 322324082, 305622902, 331222285, 341964583],
[7, 294342452, 305603252, 11401761, 260228847, 45135685, 193250525, 337468755, 334128620, 276570718, 234520399, 382130738, 192606343, 202815125, 366715191, 108543066, 100334472, 100908860, 109408027, 51351491, 4664771, 154770027, 90640921, 330630325, 225569154, 318024565, 80758542, 250439620, 272683280, 336023050, 203943167, 67189361, 87619310, 72758746, 295089605, 361114625, 9172954, 183961745, 173362577, 49474478, 240262504, 102258143, 291293567, 166925666, 326299249, 260148766, 206700829, 301294458, 388218750, 400110635],
[8, 219226493, 178667124, 371894036, 85605845, 394311881, 329089527, 27708256, 301154557, 339304395, 20708733, 306295849, 96406272, 138982826, 270719666, 142889313, 64349465, 66288005, 136684898, 346195138, 66053767, 302879603, 327695599, 99526499, 112797698, 2937310, 117042926, 274341528, 244229355, 345901420, 212351187, 347100168, 28682687, 18180095, 52639958, 172128647, 315732102, 231906686, 13707269, 39048848, 169123569, 120102617, 204034936, 241228473, 181984535, 136068828, 170556680, 368200078, 13436475, 300972204],
[9, 175082350, 201461204, 35422778, 97559473, 42814362, 94226538, 134850207, 111292357, 265350914, 65954578, 14321501, 309240287, 289407429, 124114154, 159146000, 255628740, 216155962, 47083197, 384586861, 81503603, 183710790, 21487524, 134083198, 82399651, 144375559, 13461831, 301746762, 158644339, 26942335, 150082192, 267783872, 383737190, 333341579, 105338520, 276008417, 277106050, 191159067, 343032162, 34205677, 5319826, 352904356, 225185014, 301509581, 378861770, 325549553, 158420161, 224875457, 99344795, 217933670],
[10, 308501075, 40592790, 371341147, 399589536, 290702753, 59274997, 149893132, 82041629, 313411587, 137574909, 210360883, 253598047, 140327062, 353239091, 273424957, 134778384, 95735710, 167217336, 379549383, 250157417, 73112825, 44648852, 240687272, 114081006, 1183042, 340581374, 129738781, 154545848, 374924333, 274304390, 283596239, 217975848, 397111489, 152562393, 398812138, 285731311, 116397828, 379110890, 218361338, 3875899, 108307337, 235568364, 46027787, 77017448, 273029369, 271848854, 168309042, 114932780, 8254894],
[11, 401525033, 232341082, 247459076, 324694412, 15778080, 57112937, 212266021, 280686933, 92915083, 64606942, 404356142, 46088553, 74300586, 338976034, 116122545, 15421795, 232369738, 277514696, 252915679, 260960192, 148195040, 378905151, 242603251, 234219090, 89635182, 199391144, 356025235, 311331236, 185486422, 385810325, 292692393, 244395992, 146735974, 245221390, 292985927, 327357012, 326009797, 298414485, 177645444, 174154027, 188153867, 230037366, 399304934, 75572065, 286487757, 206923432, 110290160, 344971559, 54472764],
[329161253, 399005949, 81569969, 45944723, 44154539, 111319449, 159544860, 105829573, 315116507, 364923709, 129690990, 326974851, 112065701, 138266847, 299620377, 124880622, 127737363, 124903794, 90269291, 93121030, 289017890, 97942465, 229456602, 363457170, 39439707, 226210622, 41742887, 226125034, 147487557, 12, 240399146, 98386710, 88773062, 219903412, 50495274, 149458244, 258191511, 320325433, 33387201, 312399645, 40151882, 344875374, 49379185, 33332641, 185704524, 196746792, 312548420, 127595017, 87110597, 245860396],
[13, 202738056, 275621710, 220808423, 257200453, 208478554, 129154879, 384685359, 262020155, 4597337, 299875941, 154344805, 37745033, 109648314, 276787685, 209670576, 292794681, 155327523, 367057828, 30925771, 312055616, 285101315, 104124017, 342712879, 329752718, 141223853, 361328781, 232842563, 138884717, 107087294, 115874127, 142754019, 286245298, 84135848, 292018809, 398333287, 33775169, 367947336, 295954937, 132606514, 112972057, 87015022, 57263104, 318088348, 57716432, 192924126, 68741027, 223922899, 130518931, 116192813],
[14, 170252444, 34168997, 198789024, 37628345, 78557183, 381175487, 263391020, 177231752, 355040248, 161710936, 322976732, 28694333, 47005503, 142703592, 229426779, 240977410, 22551701, 110053681, 354747947, 76215958, 336694614, 324168257, 56692148, 79839202, 62873558, 53543287, 265403153, 259645096, 5541521, 201321970, 319726560, 1079742, 378337634, 321468033, 76079009, 152959201, 47816871, 16726887, 208703802, 223532774, 302110990, 406880474, 103059282, 88055822, 356225278, 172177817, 46539541, 403009940, 43061426],
[15, 328755815, 52820044, 117248686, 232479990, 351334598, 84187753, 367925821, 60532098, 392231952, 199564546, 205159020, 210125312, 177756828, 149098548, 174404641, 187869793, 93653874, 6941280, 145637980, 211246166, 31172982, 239106922, 196740662, 245139158, 183181825, 55027629, 261038572, 228515118, 97894082, 163136223, 13365716, 100800717, 134784240, 53127246, 153219867, 362869301, 357794603, 215583862, 43381751, 352762999, 334274039, 154048320, 225100098, 82863855, 6564180, 250995997, 215108650, 137578122, 190998177],
[16, 153091867, 2218778, 267831143, 20402452, 180871366, 47265329, 213528374, 180699331, 305571250, 293921044, 21620776, 267941494, 103208680, 315340287, 100535991, 233245818, 111243105, 95127000, 320060318, 71618509, 29449993, 104355875, 151636558, 95035941, 355657781, 252771330, 349451846, 381046875, 357229155, 117483070, 175044879, 341818648, 75021716, 346969544, 114717831, 260730904, 345005115, 319180270, 94530164, 369225042, 12894223, 69113514, 277414670, 188991176, 294022706, 101505928, 323623782, 280040467, 286479406],
[17, 156149640, 271519920, 262465425, 295926413, 51852787, 292071356, 42786302, 391291188, 210143593, 55791373, 15319489, 309410897, 181431624, 120005332, 198715116, 130293508, 13017162, 228186720, 125108759, 101956507, 321817284, 100687565, 323045184, 175126499, 134483338, 400197599, 126444795, 167693271, 10861485, 87637618, 196255791, 378692076, 379498594, 267782739, 393086599, 240082575, 89312867, 121749436, 312068468, 126622090, 188264859, 236049927, 343526647, 230876960, 329887746, 38271256, 266533749, 82194983, 97986075],
[18, 311330292, 359043315, 54426451, 182861700, 185482442, 130287364, 365483233, 305894764, 144880104, 38979313, 156248019, 181980969, 254262149, 152211605, 172715285, 314597050, 5059164, 389658071, 260120365, 347288812, 198405493, 285743550, 225974015, 351390578, 181524338, 402307985, 351802554, 375488415, 620114, 284856422, 378585041, 117239834, 131299711, 186842429, 58466770, 387306971, 379919041, 67413123, 195837473, 365943427, 260783789, 386746906, 25723525, 58781406, 366162864, 148133501, 183860827, 94614669, 30796908],
[19, 38795914, 138660259, 302468749, 185934565, 368090426, 303075748, 140797703, 150535300, 147746630, 41292575, 309471127, 166287919, 392695889, 359101590, 142344054, 60638595, 122523522, 185506708, 137837740, 141121295, 247297150, 214234092, 212237785, 348838037, 174776429, 197176600, 77675600, 227589025, 125139430, 338911323, 254720794, 157599663, 160802413, 20911765, 165787314, 30168515, 260599434, 243172305, 11264708, 367782556, 302229394, 350316812, 34765885, 333560874, 195421276, 118667101, 156829789, 72944091, 210181107],
[20, 175015687, 363331199, 101797674, 113044583, 233452616, 72956349, 165989066, 365855894, 396053251, 129525844, 305584564, 7249258, 272735925, 197232790, 226224482, 193522940, 2145432, 93790621, 106449844, 39397148, 40504049, 338501573, 295240975, 231522963, 337430288, 343100884, 392459961, 218358837, 273998601, 406511461, 370712912, 231366897, 323359163, 92860384, 92093355, 85979647, 268557646, 258569758, 163331079, 33112310, 248307986, 40678541, 118735156, 84706780, 298486311, 335573739, 401393021, 234534676, 225180563],
[21, 160936721, 401944253, 233157394, 168481266, 56162418, 293720803, 39538593, 111074026, 347358351, 237271922, 240290680, 285637297, 392379996, 125750194, 6389859, 186794688, 375559979, 212422664, 139699573, 52663452, 234858831, 337794410, 136938643, 291317636, 247141304, 70677270, 380112406, 97966199, 72363735, 285219960, 275896634, 7732477, 214489345, 352764726, 284616901, 383168837, 80673158, 135909635, 405763657, 285004950, 37583619, 77982767, 334867977, 13509699, 89534410, 281835549, 8761853, 49840052, 328377818],
[241315896, 22, 260417198, 161184744, 139475965, 90410982, 18812928, 244601742, 379062832, 149030624, 103628435, 172115511, 126982137, 196116829, 56252992, 299671140, 142106773, 239109795, 8781350, 270908736, 148153436, 38772418, 275924337, 23200476, 404632069, 18970257, 205172004, 18721317, 315423349, 287190126, 297283434, 261457913, 23030039, 353384809, 344403814, 82453629, 309465197, 244996164, 388628438, 98958719, 13956615, 30667054, 135364006, 399149261, 111731374, 12041460, 82476670, 282809381, 340905801, 163923602],
[23, 215668855, 190032465, 147278305, 211384163, 398350335, 68965230, 34257810, 69780236, 18503729, 321419759, 316489381, 152267689, 385713975, 21500358, 280141880, 288516517, 126543529, 148296286, 287215437, 92124925, 117474014, 309626508, 228286126, 119551364, 368439696, 321899998, 76064736, 160467585, 150833302, 39181255, 161635012, 33756116, 117732351, 119626574, 14469275, 371197996, 140168394, 248881097, 27756864, 312586936, 134709063, 8277247, 378389296, 344980723, 89552624, 272750927, 371658820, 360847361, 140607054],
[31537034, 226998126, 261663817, 24, 87219559, 172964081, 141430748, 172784745, 335040289, 2776955, 104958584, 327349329, 290874641, 210701311, 364159444, 198407987, 262314875, 342207948, 306885331, 70825879, 96571099, 201318548, 219530101, 57446342, 323004159, 144500230, 8938693, 164596604, 302995512, 93135134, 12708846, 56551520, 262242577, 304175739, 168060425, 108155124, 180268168, 345362901, 194933971, 192512734, 150740473, 402041095, 256051518, 220512356, 260641660, 180365418, 179109995, 71613394, 380018515, 175054981],
[25, 335405053, 382819738, 176820501, 263794717, 83364774, 407211077, 278343874, 31828653, 6989463, 177827023, 400003024, 144758072, 234990985, 248384421, 148098066, 239433415, 331207977, 17096052, 22517213, 244436804, 13703309, 103323133, 62434583, 107954851, 190213066, 353345339, 120342121, 7961329, 160602923, 136109932, 200408711, 198454173, 116764442, 308247471, 112042171, 391724573, 401867790, 199919102, 170772037, 152378845, 176043967, 79417792, 74376689, 144831169, 283482532, 74989743, 93259263, 344948585, 126241076],
[26, 343732430, 14699163, 359530987, 359397088, 28788739, 391498376, 357356336, 342825391, 57419551, 138032876, 44609078, 250446543, 210282222, 227107202, 326549182, 70920643, 223307704, 397361799, 362162755, 9463779, 18882838, 347249979, 373776073, 91359065, 149571888, 2160737, 153515721, 197910794, 148727190, 117335805, 70876664, 358626227, 357962265, 273717991, 323213569, 122087013, 239338757, 262136709, 193821967, 277385571, 366310480, 83076958, 106317211, 395302784, 303942003, 389475430, 205676184, 324386073, 215514843],
[247467601, 27, 200768133, 313637586, 392973543, 181236263, 88506105, 342475, 284828586, 236772134, 387238262, 127951694, 382759224, 285545220, 148558851, 127704971, 283772260, 316554757, 166695097, 155101962, 219469380, 242224248, 131335219, 44140300, 291612364, 98579196, 86448243, 239653086, 212489036, 97717710, 141465231, 205136079, 128531254, 373833643, 109767610, 192330216, 48253706, 250710051, 207321357, 197718858, 314165654, 174612347, 205515958, 182881281, 154525882, 272691678, 390866594, 283043391, 352274791, 268720504],
[383846758, 28, 288273247, 333639905, 197153868, 375933760, 84449970, 288095849, 244746483, 5607044, 186900905, 115124893, 198121039, 321437966, 102942702, 247195295, 207792318, 347242994, 95631220, 291434203, 136410185, 392283510, 106964943, 62377321, 282530555, 193464107, 62809257, 370962321, 102827482, 276033545, 45358715, 88082979, 74104600, 375498579, 281033520, 380620944, 279014188, 7917445, 131588156, 331920882, 318217767, 236565287, 65890050, 370366663, 49094904, 110511048, 217994085, 7288115, 63507623, 259470076],
[29, 4616975, 171134314, 66781547, 272136865, 31461216, 268567423, 321571023, 2150223, 387391326, 173498932, 70662694, 179899662, 19839317, 58437597, 159184690, 106625922, 56691815, 152670626, 216204444, 166051629, 368152719, 399613259, 134720983, 402011974, 70079601, 110308082, 210044881, 123252618, 302517550, 204093626, 369694951, 190492580, 3834817, 210764342, 345715374, 332133304, 257783357, 362233060, 61148736, 135079340, 243901641, 114856367, 270968858, 71795801, 104567668, 147405701, 199146767, 251473465, 539925],
[30, 26098841, 213910620, 363020093, 276302439, 23726722, 180525711, 263651666, 224709761, 393251015, 295973023, 43916058, 129817571, 382013160, 400355887, 147356220, 43344577, 23638578, 92452314, 235275594, 136995510, 237950572, 136846787, 361480134, 285233065, 142115599, 338221037, 342697371, 347492977, 261065716, 51014186, 218720069, 327789701, 274622945, 394280501, 17664458, 397671865, 193486113, 252139629, 146387385, 5446527, 166841563, 156579448, 204555205, 279531289, 135141161, 329556574, 397147086, 387755781, 331436360],
[31, 369893125, 290209381, 159831162, 109625535, 164753081, 338013799, 319424607, 13918733, 265059267, 118264167, 384841122, 402373248, 22307691, 396971892, 217043629, 162553057, 206520911, 310556344, 376717959, 24503828, 360836822, 183529808, 108020336, 207743288, 250988065, 163825658, 13902414, 202942806, 281694659, 208169345, 74727250, 108858612, 136828916, 219852132, 317754315, 58210295, 388514829, 254359316, 246031017, 174451451, 185946907, 1947974, 365415038, 17664568, 167534947, 324703982, 138218052, 123762568, 96554217],
[32, 163758170, 301088720, 133417845, 18819067, 246244995, 159688259, 336487251, 178304152, 114151074, 182800979, 99497909, 259184262, 75758726, 196230886, 249022379, 108914904, 117121011, 284203430, 102472299, 183250517, 3095470, 148745449, 214059075, 265012253, 169444621, 237235477, 118301244, 89730771, 403244776, 100615291, 49210768, 137271972, 86518209, 344849738, 372266765, 179793468, 274727399, 118553030, 281317627, 268653979, 398900945, 148067816, 16670724, 209639416, 126543054, 224342254, 83515054, 400346524, 71503681],
[33, 269051771, 84917195, 196410136, 287785176, 262088947, 70928903, 351723298, 182491537, 1525733, 11146151, 379468002, 82639501, 83326932, 370028954, 370464123, 111051954, 283705110, 117702725, 127232475, 379770465, 266744235, 73210943, 160643034, 136302992, 278693086, 357027583, 240960458, 113117036, 370057920, 373900633, 73676331, 23983927, 203673727, 31862922, 82335263, 269976283, 214423609, 354926633, 278419572, 289593206, 307648967, 251868086, 308231482, 44648487, 402047806, 328069853, 356401670, 351825782, 289773055],
[34, 197315466, 56184037, 291666789, 246848494, 31036068, 399819841, 96577548, 387260240, 294552357, 231515789, 393595258, 334198039, 319211201, 111466179, 210610469, 2485097, 164789983, 7124142, 275333250, 234965827, 54049384, 155315810, 234038399, 18389676, 140946145, 38545519, 83149897, 30136066, 180692295, 245292535, 244721527, 379707379, 27222164, 98641871, 375970781, 144615717, 99372600, 301698883, 157900804, 290528526, 329485493, 232285000, 393230420, 246225461, 398439208, 378108612, 21056283, 57087400, 211275829],
[35, 297105840, 371081719, 199652794, 230741873, 226645768, 312477752, 310891960, 385549520, 112511195, 124166156, 41656995, 392450001, 236585740, 328664040, 289600429, 76774426, 291899295, 179551798, 29322270, 13641452, 330157364, 217573002, 107647352, 235706465, 811232, 81412390, 75450129, 21253012, 126273519, 176758314, 189709534, 78584174, 299092279, 98672138, 261883932, 26331107, 340854146, 343733827, 379481031, 44592285, 337909004, 161925677, 146143291, 371629663, 381836805, 250031120, 151344291, 95366681, 312866390],
[390343390, 243915090, 36, 333717562, 82520629, 396995049, 176044087, 390354731, 324028784, 20618204, 23988430, 202972476, 131726788, 348255494, 212933372, 264902837, 363920231, 330510799, 280788697, 398904683, 50464239, 393470773, 287873254, 125387372, 277437278, 54645646, 229604793, 44287094, 67436483, 366712432, 154700998, 365032567, 129879860, 386636764, 22668051, 215337184, 219584067, 83446142, 55947246, 13537371, 190181947, 108306366, 402161761, 37296214, 278166493, 267950269, 174145521, 287341096, 176066054, 238663981],
[37, 239334448, 127147420, 49513507, 57283018, 202803786, 91545163, 67390643, 345785282, 246127580, 379358289, 352121153, 329650579, 334029263, 32291445, 234257790, 261917156, 327412741, 162657836, 7528469, 26785580, 349427386, 222176396, 386379349, 347855496, 253772691, 63917437, 354283961, 317225549, 142142867, 95032618, 235428869, 346289748, 210528566, 281458369, 309330291, 163690299, 203383045, 375911581, 63617404, 264607836, 10744090, 39125026, 62924958, 256416939, 400483971, 277681547, 121667385, 216131965, 236443076],
[38, 101321444, 204894488, 101225713, 109778122, 34315047, 58037465, 6958918, 194112256, 124943861, 210896010, 341232905, 255575579, 75492439, 264665156, 191213688, 332990311, 66014112, 319040454, 192784222, 315658817, 289843281, 289789682, 53220613, 331974375, 215751892, 332679522, 212892857, 350342673, 199030281, 2477889, 229725916, 247549794, 371445859, 404790958, 44400186, 218282892, 60763836, 334153507, 274264155, 246746817, 58119681, 83221663, 326426423, 146768840, 232397376, 130442185, 166493940, 192033459, 112198042],
[39, 113279023, 360951962, 52626422, 91603156, 160370621, 223729384, 104863414, 193033932, 399575589, 193956068, 361193367, 35637767, 388279069, 374960825, 391221896, 262757310, 167966391, 114428283, 154946710, 277239068, 386349103, 278930731, 227181457, 154366791, 382580937, 266530597, 130066058, 366824472, 247491855, 246013950, 103138344, 308108706, 27254729, 151944777, 363343025, 25573860, 192480185, 71329532, 112486822, 14899167, 256248670, 366463200, 17052181, 84331827, 363079766, 79221061, 285200034, 362030109, 170207241],
[27013016, 182711815, 40, 320290766, 190920154, 313066966, 93781512, 240917628, 286029782, 351393692, 309745447, 50466460, 370319433, 205517053, 92902621, 27845601, 277224359, 166003579, 333241105, 144440167, 191598478, 131801941, 321351116, 350709846, 180728853, 159235629, 295499961, 82869287, 235395520, 333249105, 111391257, 403426263, 334865390, 31138668, 129316781, 298591179, 353070814, 17467089, 363833315, 29265379, 41652368, 258334195, 135422954, 22671919, 116376018, 101479202, 396076486, 253786754, 43271613, 262507887],
[41, 375332374, 37508762, 103769588, 348544794, 277367518, 359862707, 91713943, 230556424, 385837536, 345993323, 231238890, 208481663, 115309279, 332836170, 295532028, 14600439, 219619527, 291198542, 234142547, 137570605, 180368095, 105651408, 122818450, 164498635, 329657189, 376239231, 72722826, 122049215, 198833684, 375265266, 402236057, 279375731, 287596817, 164852880, 158897304, 236854333, 97891390, 94718870, 267737596, 12380704, 298555295, 314505546, 252720837, 321939618, 38946622, 381438046, 394190178, 77250270, 327586849],
[42, 46636198, 152992083, 357847910, 378076085, 100337596, 80081992, 298097275, 325712028, 257516383, 120770005, 347763737, 8339244, 152920050, 286135082, 287605202, 7144967, 405240848, 347023384, 229408047, 163893621, 140929139, 45728281, 250855125, 212739440, 108589430, 241398595, 154144146, 141883125, 337953364, 345930790, 171403683, 200553397, 269271035, 96055080, 23575621, 208564240, 306557053, 53421031, 16334330, 106732612, 363334136, 81865775, 243091501, 199773326, 368152532, 190479602, 385710882, 21344944, 347027076],
[43, 201180149, 129612401, 46770367, 393730251, 401418595, 6091332, 282063235, 405305627, 322827451, 302857601, 61359479, 189419144, 82215644, 231911522, 176922489, 32969265, 19085558, 93452637, 343405613, 357371422, 107921485, 97134414, 120178424, 232713194, 299821805, 390627262, 325757916, 42733630, 264045112, 163728842, 33777965, 82243566, 27959720, 358257707, 66833781, 392931332, 286187629, 255007221, 158956480, 324226859, 263720117, 84474973, 183016215, 334788087, 79068855, 362751633, 310485250, 358547643, 266463503],
[44, 228204579, 282078859, 116216943, 324695157, 60186332, 163072728, 164588476, 135777082, 98347235, 26158174, 364096562, 101751512, 220395134, 134288601, 212448354, 18617167, 50389256, 241139517, 27951858, 314404367, 255546560, 389448989, 7224812, 137569474, 74117456, 388796888, 81366194, 130055044, 82407316, 165874195, 315154377, 184641707, 155499026, 70513283, 367536700, 262726216, 141672532, 131064993, 200638270, 26158096, 396395898, 273852323, 328183504, 249813294, 300265510, 259777420, 95489282, 120769890, 244740114],
[45, 173307504, 147055863, 304699349, 241781947, 379077919, 208968674, 338876141, 292547759, 319056511, 376738679, 344834976, 92531592, 157472676, 378809011, 15664709, 75415666, 52796961, 97554587, 384894653, 293478307, 97868851, 194195051, 357811967, 246241800, 339920571, 73803181, 36689780, 261583077, 404093414, 380962291, 385608738, 125343310, 279088592, 59258171, 387683397, 138910112, 306442231, 152895408, 192072571, 124081950, 97359844, 328921582, 349164981, 373281595, 30354217, 181895517, 183315714, 353915067, 52907487],
[46, 26313971, 253038896, 230986335, 316143930, 149934723, 116079917, 288557768, 141745688, 187040395, 243013175, 85492903, 288432308, 333422022, 619402, 26910891, 33636413, 329092098, 134482753, 18101486, 335369514, 318322962, 279158352, 56530937, 181309585, 75265628, 205834674, 126449849, 368764823, 177742274, 176312776, 232585550, 303370433, 350186380, 263615624, 96026340, 296092882, 30240256, 244314191, 397783512, 162308577, 87835175, 167712956, 239372633, 238332248, 83396308, 156942842, 339303566, 61330081, 124574091],
[47, 112132117, 79738650, 109457438, 77686799, 267665402, 267452969, 256321938, 71720803, 7893713, 248991700, 175495440, 108069773, 323143153, 313060418, 71564099, 163054738, 342609157, 109758866, 35162097, 148945832, 30923667, 172493625, 72857649, 155477334, 137321359, 75459688, 24966741, 96733616, 293731702, 369702711, 55392063, 233402825, 229923363, 386258516, 346856941, 252778668, 59802612, 285864914, 392548703, 329585646, 393301455, 192145032, 143944863, 294326918, 245599964, 135234360, 346105441, 209474763, 387970824],
[48, 366165420, 259134603, 215206408, 41482188, 172402174, 224362224, 328069817, 193416465, 77609417, 341125527, 316458858, 298958655, 223531072, 305279321, 368890707, 366268706, 308172275, 49049175, 247490930, 129979601, 127965933, 145318197, 288707405, 130554712, 292411261, 262987494, 370180326, 149258360, 257131969, 224503019, 306752756, 273523798, 43555962, 49006338, 356784701, 125864116, 269149689, 210096759, 348351927, 241864911, 405840374, 209788168, 78961636, 111048454, 361869353, 317677359, 156168835, 211219395, 145980581],
[49, 147531410, 97926052, 48692395, 373956353, 81494585, 167017765, 138171910, 185997494, 389242413, 120070237, 58872304, 86662011, 286278306, 134391875, 327786327, 275295057, 290783600, 1024970, 33120194, 338162965, 145760300, 208508065, 123760320, 404635726, 191733500, 329431895, 373700696, 386174615, 332687779, 371915181, 387678719, 345434365, 108055315, 25003614, 375018151, 238271890, 337575559, 251389616, 205164561, 266188912, 397666857, 320127897, 64424979, 396625639, 1107371, 129376769, 115655575, 160173119, 89800398],
[50, 338473093, 64383824, 199082714, 90183747, 338048217, 294705435, 261914896, 189603741, 320676135, 147393575, 101278107, 282378328, 73688864, 247200716, 18079339, 239406096, 171393625, 197603874, 92402841, 165263910, 336861373, 56082718, 195599067, 1456228, 245619666, 168317700, 275981393, 378441154, 91212625, 406325826, 200099111, 129678537, 26647179, 387120467, 182708652, 218542387, 118940795, 371599991, 287835564, 192408431, 148002274, 282468598, 353006884, 280300785, 91528183, 312764342, 316700022, 48491310, 271719465],
[129464184, 269772990, 314379589, 51, 116106694, 223627647, 301485134, 90457125, 115800492, 405321591, 387840017, 13926955, 290731159, 230296645, 237162427, 71902800, 286941431, 18738436, 19757636, 227111402, 360588996, 180737920, 104361572, 336957815, 381744565, 131315743, 166006085, 78710933, 31575773, 158786290, 350660648, 36526412, 86600480, 135951337, 308614700, 278546924, 295847132, 99853362, 336292793, 127037532, 305546544, 301581376, 343993670, 252033019, 394624119, 13382011, 222945651, 90304799, 208910320, 208607003],
[52, 161983025, 181516358, 177325746, 395149934, 73459397, 93352661, 44336265, 88759784, 375100140, 233032003, 298718707, 33900189, 288231064, 287503906, 312087721, 404842256, 292105570, 50275408, 214290776, 207274879, 97102724, 146980040, 314288619, 9692781, 137861385, 254704636, 126884385, 297221224, 82380546, 151117449, 45604187, 331588677, 155730207, 115249102, 401853540, 311501720, 151161509, 364799714, 123667303, 295495002, 287857168, 393445300, 116203135, 146906150, 319961147, 213046802, 29617858, 71587737, 292411216],
[53, 196478545, 274158600, 125152400, 316188530, 370361824, 74327142, 155157299, 183046169, 345461026, 871007, 96048225, 366628672, 80797246, 157951927, 77399436, 309829240, 36531052, 51413249, 231323026, 126483975, 28090124, 398683108, 160647802, 286192911, 369686149, 393585549, 10366500, 360003154, 376435426, 86620400, 383421755, 149644135, 131483831, 260167020, 189023047, 358834379, 131222598, 347107788, 191892468, 5283405, 144665660, 274598950, 244746216, 248920721, 281778688, 26607670, 97332326, 211272971, 23874644],
[54, 239130963, 346116568, 182516658, 9402055, 120082065, 82764307, 186749676, 257767878, 207163385, 12225525, 146075466, 189030043, 27002235, 134196750, 153759585, 152016679, 166595653, 154349231, 356715931, 163928654, 200029790, 253643317, 184832443, 378015838, 25513753, 40676143, 297114925, 349987187, 13089206, 273030502, 103067649, 40320133, 6723526, 12636858, 37023630, 5211437, 50319433, 363001499, 317309875, 137078094, 123421303, 484902, 258258030, 132478011, 345453966, 184074950, 43638969, 85408293, 76050519],
[55, 267623494, 84170794, 278344203, 207292099, 243726106, 365985761, 246374378, 333534973, 42573636, 158334075, 130658411, 30894051, 46921738, 275136254, 259253871, 207451378, 406412408, 244939745, 171524376, 218210205, 367049556, 139084349, 263372871, 338837436, 184570512, 191552056, 303414487, 255534322, 23865063, 68763401, 202459924, 171521446, 168103744, 58322981, 28033462, 255096467, 225202884, 283563860, 91978177, 383011544, 186833292, 391545741, 361158381, 230204626, 398304154, 198874174, 182667084, 256577662, 129508785],
[56, 207459611, 66787802, 220713549, 324044541, 404893255, 201631778, 309162209, 85710011, 256287051, 335428165, 197054800, 37451212, 122622615, 44133670, 140332477, 132887680, 7918111, 343514053, 358903265, 300419969, 144047625, 8998966, 80729822, 359976823, 60434433, 394234963, 163370668, 232119669, 130606891, 345551536, 245823572, 222088162, 132255616, 400406669, 329459145, 378764435, 367168867, 111079193, 343007399, 192166680, 267404868, 142804665, 168557046, 47463813, 96230795, 245478638, 95144344, 169144337, 102606686],
[57, 320145736, 288682800, 125896682, 362580579, 74819121, 3752588, 182346832, 182057952, 218437232, 312154515, 56907201, 299901983, 221312514, 4685627, 147639725, 244393145, 318539671, 54914450, 33701037, 27915262, 144376132, 281730527, 35461393, 274343089, 35033531, 33933221, 369631636, 155443872, 349605893, 233600810, 165404987, 313763248, 53803150, 402940341, 54481786, 100712473, 264542125, 124048265, 273458484, 167229230, 216756032, 22181500, 23532283, 328172761, 241481662, 219554668, 61911982, 215370004, 237136679],
[58, 131997189, 356667403, 278508897, 347256594, 182267794, 7857184, 110424376, 16918466, 56232353, 395582845, 10073508, 30588586, 257338940, 389260344, 236315576, 265060251, 294184864, 304347057, 59642225, 6417008, 174969015, 141161585, 106908358, 138738603, 291628763, 401437296, 355011016, 182041083, 387002553, 38345339, 125768424, 50630479, 112672457, 330797162, 265221591, 373848853, 53975422, 362480434, 37072726, 3392447, 18992926, 255123631, 75704859, 182346420, 221088606, 154460897, 212132153, 193631882, 313699199],
[59, 216240843, 269350672, 301049703, 297145021, 135396543, 188004619, 319747257, 229943909, 74982009, 358970298, 6410513, 170231390, 280709791, 188160207, 234957539, 56094374, 300408146, 17491800, 168415013, 322412582, 61253386, 27574582, 259144699, 222023645, 261435267, 265743361, 254791448, 73580150, 208741191, 73473991, 128528390, 397056090, 117079785, 395285341, 386807150, 233754770, 214896763, 81063127, 386710478, 152958676, 98401648, 229470967, 281372607, 3468381, 164018196, 206863279, 64750153, 363971750, 39013748],
[175274846, 60, 361973494, 77871795, 247801494, 24618694, 259180360, 275683313, 41639195, 11635473, 111329552, 321266763, 349288620, 191532198, 284338096, 262675322, 363831574, 383396843, 246109349, 143750515, 145296438, 124325290, 156570646, 291828099, 355961922, 333311437, 5706772, 275116829, 43378406, 359226193, 273822653, 171334115, 233532641, 376247428, 67506002, 345775008, 305662423, 60516713, 387128826, 109439017, 96477369, 337156803, 229559511, 74453636, 251721348, 116784899, 196025304, 21015241, 173006473, 384399474],
[61, 369623017, 124437283, 319659549, 19612205, 331968533, 164227257, 182570384, 195772121, 310487168, 157440278, 336681204, 132479886, 215920319, 160627221, 155640071, 155597937, 137061332, 97402763, 70598844, 321029297, 94835726, 147044991, 5527542, 85552473, 270116226, 173170080, 103289565, 364657135, 271773682, 395986389, 213520340, 97466619, 107949616, 113316051, 372440928, 28975045, 223113526, 148671570, 314660410, 360391588, 39579962, 123027940, 123338891, 211656399, 383957311, 203770395, 328526097, 406160843, 111858748],
[62, 230074334, 33815835, 372996411, 146487603, 374544131, 208251060, 26439458, 242175387, 62004667, 346437636, 382931119, 389771471, 394220371, 386594669, 295178899, 110138439, 61883704, 41803284, 386868753, 295123644, 291275506, 69202435, 14255182, 247925563, 48133533, 279546100, 80213111, 230557503, 242002322, 331882619, 223446333, 220149770, 384824788, 84081002, 392083392, 353065208, 380653300, 79879864, 393842065, 287316946, 177179303, 142619284, 7691019, 275660631, 58955543, 238747493, 267769923, 174599802, 109788754],
[5656556, 63, 81162177, 315230966, 371546633, 119079283, 179176987, 252004188, 318198543, 169524457, 373998058, 280532428, 285129852, 181129607, 372590974, 18221204, 68885623, 354831141, 360715392, 10143518, 341299496, 165835271, 252036880, 70432793, 92802067, 44767091, 260473157, 133665556, 320695433, 264912680, 321367410, 363241538, 243466362, 205612779, 207319430, 340646606, 228171484, 276203051, 44376905, 294449240, 250723624, 172925279, 266762785, 337669545, 7840349, 71112055, 383413466, 24294360, 210789410, 46530296],
[64, 314732348, 56927683, 39178185, 168354321, 250321510, 320369263, 203790769, 172403163, 296434456, 116967202, 172486054, 173254558, 267994452, 225260055, 171989560, 150251155, 60105936, 285854974, 60072031, 67980075, 286864195, 54307804, 273998034, 394479376, 39248433, 203746200, 145475030, 199546552, 309481076, 164377736, 269105470, 241760215, 179749725, 265821117, 187158686, 191621341, 250568562, 127540387, 95739467, 377785005, 344416702, 345138132, 29421135, 353723724, 20716422, 199811320, 21815625, 318562479, 131252275],
[65, 284469322, 142712515, 324561556, 59309615, 92833250, 11458077, 339300861, 353655362, 119976236, 181226256, 296881332, 292616202, 160064160, 20344961, 97504919, 392002391, 325199746, 376878194, 137202114, 159210485, 178478804, 84639583, 42390862, 349542862, 179232377, 91424268, 59693389, 248170310, 94207668, 30290331, 1811430, 43400292, 396986897, 358847251, 128196496, 13818809, 290323397, 100946026, 112465203, 32856266, 3654757, 181232542, 373087166, 93693095, 7400050, 109194407, 174525597, 226459426, 335048029],
[66, 214923567, 405660182, 272462327, 361092635, 43752596, 74259462, 12902609, 126047566, 171277529, 368867227, 390496667, 165196314, 236779249, 404034525, 89067667, 100928892, 210982425, 152980906, 292029566, 11382513, 38271907, 314525781, 143127168, 333215711, 342349608, 166842499, 277700599, 31072624, 131249219, 154365629, 276358553, 394736913, 83840863, 123275476, 292300731, 40852173, 338909551, 70247862, 369589227, 200054978, 61344430, 198745035, 15394093, 69067110, 157844342, 28530088, 78323967, 185072434, 61037884],
[67, 35482621, 149022535, 252299517, 171524964, 247483555, 68528017, 361998540, 121829508, 45992049, 394822685, 125309258, 242164654, 337221430, 118733668, 159006509, 15187861, 257542577, 295844317, 209343722, 266935086, 240607757, 238831239, 40024464, 282814544, 371722387, 250016952, 158604760, 11156664, 189940164, 60945065, 243184930, 83296345, 41856588, 253757690, 3429376, 85834877, 322539273, 42057985, 406898632, 189675288, 72891320, 127527568, 338481714, 363733339, 368310527, 310234571, 200260141, 86768914, 213175326],
[68, 339724756, 103730432, 362957436, 291759714, 318798933, 217352353, 347565404, 14756870, 350267148, 57760478, 194550720, 55934215, 140006006, 155901987, 269641809, 305372150, 301892221, 129709846, 91780786, 321450149, 391517071, 49564001, 162350903, 17475432, 392977426, 5817703, 302905444, 273206333, 313038361, 17128731, 105243022, 208047910, 313226655, 233374114, 352199439, 315045953, 128637501, 317888033, 268246893, 324008396, 380627938, 346074113, 33262967, 83441226, 146003995, 41936299, 406325112, 120681007, 388705462],
[69, 360529240, 124348569, 56864184, 2341178, 341128280, 218794540, 346980704, 71822160, 194731022, 251090488, 45653077, 236178592, 89074857, 348228238, 77482920, 245104547, 396494097, 171358450, 353224866, 269238388, 59235540, 330044289, 248012394, 319720108, 113086467, 59707689, 194255129, 177057450, 233081441, 365542306, 365776204, 124912826, 232982681, 209592576, 5944306, 64621405, 67081515, 229520714, 159988885, 354539602, 311847730, 165445594, 322348527, 45933783, 40694361, 237531237, 163837530, 42692863, 275951530],
[70, 199052062, 134189332, 398424418, 260574784, 263972641, 52114801, 144905053, 60020007, 335819028, 82422642, 387699459, 201890703, 356757748, 87419144, 85467493, 180634740, 185232377, 162447656, 149852555, 32530371, 26120920, 55128887, 343265796, 11495797, 325977756, 276660186, 163273802, 144875541, 403775708, 337136196, 81632009, 54522570, 92422859, 59086037, 398370169, 335587589, 353305782, 259228996, 274260940, 244910200, 235561891, 101600145, 232393511, 16830510, 12942177, 252068799, 136253970, 7289035, 83006886],
[231555871, 71, 235296573, 32783280, 332895898, 125203011, 334414202, 388793625, 158138208, 383462685, 274590998, 12218565, 314622189, 262420949, 247568678, 254480387, 343179870, 78342823, 36886246, 270845954, 223310068, 257190420, 215420187, 63366243, 267066276, 229892065, 302036223, 179978434, 333782699, 196078551, 340531864, 167708173, 90184597, 10268574, 307256521, 373572154, 180567229, 100305804, 372388104, 359475740, 177327838, 121287273, 220899356, 188584382, 42165366, 5395750, 283457579, 183479222, 398655233, 154972271],
[72, 16186958, 203208074, 292667875, 291949485, 158293367, 328691173, 4582322, 56765965, 384547489, 44672033, 84986739, 281207456, 130742066, 283923842, 354702352, 4745250, 342687646, 7790241, 124861314, 343580173, 10187203, 215752046, 377237905, 186033336, 191250664, 354116458, 263683857, 92163965, 188652533, 63422930, 163890396, 247003151, 294817709, 131240997, 288209923, 64474351, 212427008, 109387650, 114168783, 54815819, 362563126, 125954340, 244094712, 12311972, 28696554, 97895255, 293798988, 274840736, 113606732],
[73, 35896811, 283431665, 146728874, 102940357, 322221336, 305113738, 262062990, 295785077, 250117642, 51806331, 5755030, 187545104, 401449241, 151901845, 222840227, 204463774, 189235608, 96936762, 323376289, 248522236, 225092403, 174224659, 320351693, 380963410, 161687603, 172638609, 159109676, 293862019, 41036544, 64193603, 154328547, 140323767, 223565545, 391772819, 202543263, 48695445, 17481248, 188767509, 15934982, 145313881, 125285508, 127550751, 106859740, 50860612, 46140001, 88676498, 14979930, 363663021, 160262887],
[74, 111119071, 158378631, 210403678, 59441083, 115362268, 16314523, 20414735, 376403968, 289342196, 341164686, 36722905, 132514238, 76563616, 343638612, 400682474, 100724468, 119925507, 220211291, 121741602, 146376122, 194705487, 401754314, 255296608, 190709006, 89269874, 230322721, 356276307, 180859437, 292815598, 242940840, 292217080, 40527676, 388243409, 392304005, 6200097, 101526721, 75465045, 134796317, 22473399, 127791698, 168844112, 2938461, 226351683, 123005995, 145106434, 243030943, 95467133, 267958419, 356986559],
[75, 233496154, 394921612, 27802506, 293861797, 96034796, 144580762, 123893914, 155789434, 166991756, 352184768, 405078062, 290227831, 200325803, 85674441, 311238079, 391353932, 380717628, 284269536, 158960340, 393397944, 207322599, 336962010, 334691334, 139194871, 194908726, 298842475, 390722649, 392450464, 99216479, 64705203, 272207946, 60349250, 311378672, 27008546, 151334228, 277402685, 76350435, 74628850, 311208458, 246502174, 259500431, 8958573, 108367841, 378446973, 402512433, 74403165, 194179703, 368407663, 177564273],
[76, 297073134, 224961690, 9806789, 371848607, 406651955, 108055487, 225557143, 302233277, 145925943, 205363577, 12193557, 36940029, 345956986, 207752896, 112551020, 254555588, 165558394, 127155513, 143149341, 257863584, 214149415, 60844355, 335494908, 38813974, 205163822, 243664800, 289442757, 6971959, 191917872, 3308840, 76445751, 372210833, 364259894, 148944628, 373508134, 169181425, 252889683, 122422176, 288700721, 91278154, 172257700, 257596330, 19366411, 6615139, 177284342, 171863737, 16779627, 103125315, 386480888],
[77, 257995895, 55813685, 232126630, 294380927, 30806948, 288693762, 288601278, 303682648, 111619903, 343191203, 81286917, 241208768, 310146891, 298693239, 125121972, 83833724, 360079884, 294506449, 406266542, 107987427, 49075805, 386490529, 336113760, 354946236, 74312887, 36020200, 245872012, 159151099, 24281828, 43911798, 44264138, 116468450, 72464886, 225579343, 204183110, 27411197, 155925835, 129011113, 113420075, 59613625, 49269938, 262876647, 96764445, 106274530, 114296811, 162776654, 125912276, 316456487, 215780080],
[350750323, 128108932, 287964409, 335070387, 78, 305155237, 401859155, 79716779, 134226652, 146630645, 209996672, 286626588, 347146825, 398102289, 107865015, 186988851, 221803183, 238714021, 369524979, 313165062, 42354159, 351674808, 237481636, 229976582, 42309048, 253688384, 266493607, 159865199, 20608063, 226977602, 96077420, 48231301, 389799982, 245108331, 140156420, 279772306, 144973212, 174628651, 176692785, 400530923, 372979118, 328525346, 84056203, 303688084, 99816247, 403819441, 211374680, 197538840, 137682542, 320391492],
[79, 202484593, 314238863, 328085168, 110275679, 285211976, 16793035, 338222149, 89901052, 362263304, 266168105, 97288100, 9279648, 92680793, 113935941, 167194721, 172181302, 149453693, 332318268, 32441726, 126628306, 276715963, 27281789, 213520844, 218976788, 295548263, 6995273, 122098782, 369329180, 215294427, 5587897, 245776403, 148064874, 185911392, 292375019, 363313991, 343952728, 147387328, 107801994, 192101823, 283922800, 65990919, 33824197, 230202682, 165926568, 229724189, 213152081, 240424007, 183018925, 48019365],
[80, 54049602, 306421914, 228755580, 222355508, 400872705, 188226071, 235836596, 187866937, 150986915, 218496402, 264061150, 121643366, 93402545, 391690159, 248010545, 277714159, 325008057, 66045396, 269131237, 40771047, 207156728, 245407488, 212059376, 338852354, 299382651, 57451260, 124373813, 94346619, 354487316, 341138887, 172035459, 56609301, 367317756, 13835238, 124676973, 265187716, 143974218, 121530590, 20933148, 129994265, 100424695, 265199132, 225901689, 378828734, 194948146, 24984527, 199831523, 217844581, 201905219],
[393484298, 32547500, 81, 184599498, 264228648, 108863705, 303622759, 363371883, 4993634, 215171867, 240061150, 226743446, 250657698, 304538302, 140480189, 382102813, 169647076, 203628997, 231779197, 272192618, 352606646, 178664473, 187032633, 333912617, 259433836, 102240322, 155415899, 275545003, 377669207, 382012089, 60248969, 285989981, 158038661, 111876595, 356818876, 113266226, 157630074, 227048257, 307499015, 385949441, 73049980, 4028091, 327992997, 252177981, 6289612, 93252031, 221809806, 376986298, 337663154, 102445883],
[82, 167367425, 85799020, 228680636, 202118487, 68565648, 91858244, 145895144, 225644094, 361468332, 151932349, 139604153, 95463822, 296529427, 13772921, 386747418, 72312046, 207139744, 49192313, 53362085, 60022513, 129666860, 28523516, 91545248, 308663533, 139372006, 335052718, 133468604, 388061254, 259685883, 355453903, 404836164, 166495100, 81677438, 184134410, 115759889, 319048355, 193584217, 343074400, 112827085, 362250830, 253630974, 241037619, 194154463, 255346809, 22196641, 340405163, 119463525, 286738555, 243056155],
[83, 351194678, 260931137, 220785960, 374084135, 387251973, 125957757, 263069290, 194890687, 129357238, 165984405, 339747005, 22789247, 101408472, 146166103, 274881334, 400659636, 9165809, 374757531, 64209836, 157808365, 38302763, 187204206, 117128568, 25925171, 193960893, 331842638, 382406378, 232135837, 176506286, 186165861, 233710710, 147730830, 344931137, 170817013, 200295566, 37257216, 307697411, 231188123, 351041234, 11513970, 72216989, 62911141, 355965860, 221515937, 200354965, 16633560, 36039552, 313767604, 263137165],
[84, 25566838, 83900545, 81290442, 23543384, 8631509, 19564764, 182767087, 256737653, 89946060, 333148984, 189088170, 90604792, 61219509, 350437290, 334131802, 190537617, 395570715, 330346349, 235335777, 138046858, 252688626, 300455776, 240477787, 359189980, 323188038, 122127468, 248251293, 138271491, 147021639, 347698853, 333722806, 165820550, 77900237, 130726187, 280509208, 84464276, 220089222, 7450392, 351750045, 352704193, 34090519, 236363483, 229243289, 174297051, 388847136, 235113490, 170915446, 186877357, 207749741],
[85, 95630030, 402220658, 398594194, 43661535, 260292186, 154599594, 341780013, 376328797, 71187547, 159859434, 129304261, 304436353, 57892782, 139784349, 2156903, 397079518, 245599844, 220243606, 298599077, 24421891, 220349026, 346941884, 55858301, 205796815, 238001524, 128856318, 222463052, 163056528, 225320873, 343774017, 392214951, 207349167, 378020061, 236839218, 316035633, 242741640, 269828297, 138366464, 301591896, 184975444, 135451295, 291349168, 264222176, 387490428, 241655112, 164061925, 2282996, 403615714, 344786636],
[86, 159015251, 393298812, 298896924, 331428255, 33687453, 370251997, 266070069, 41176228, 398922496, 199922573, 286792923, 81226403, 333001648, 197714047, 378346507, 302449264, 137045409, 278101862, 138682971, 399291674, 393260229, 234991474, 39230262, 58323225, 273863947, 335783760, 76403086, 403579766, 270710718, 315159670, 368776904, 108337164, 188553931, 105719090, 266156060, 144750139, 63241662, 278502910, 139325124, 336274873, 104273360, 370094686, 276040585, 11446447, 304298669, 112491380, 268204311, 59241745, 325656000],
[87, 401899954, 308448810, 366987655, 279333549, 382114700, 197090441, 257715393, 323396283, 129750541, 321803708, 399968681, 6764967, 93035696, 241885598, 198602801, 39537048, 197232873, 28556090, 311978389, 181311372, 136258083, 161969826, 370827024, 314175143, 12315817, 8257609, 367834198, 105324167, 212545180, 59628109, 251478504, 56090906, 153459236, 239233825, 90542668, 279910515, 141188874, 258420188, 94588681, 202825980, 74977996, 361479964, 127783529, 39999373, 78258357, 355399138, 150649141, 320994837, 261550835],
[88, 317657675, 402729284, 121553666, 75808997, 299222777, 377653476, 130936849, 189185337, 165248906, 251910329, 55710904, 96197013, 278842057, 139593787, 326611684, 345215182, 125178939, 71559758, 155400593, 32446951, 245512910, 347508612, 380103074, 280376682, 103549118, 90435103, 209736147, 1017535, 183231223, 406720892, 239225441, 245362345, 229236566, 214537390, 139491116, 213129161, 282221350, 345700529, 368667875, 273137348, 291272401, 76878737, 275932050, 176016094, 314370421, 44779369, 104759491, 398740860, 380377046],
[89, 103532558, 204417910, 162139661, 113602222, 351297031, 1232469, 74179440, 129143994, 52493695, 234156640, 48603000, 164588869, 263478918, 129619413, 173608082, 295481408, 172433146, 9323577, 43530745, 126382564, 259369047, 271750681, 56561891, 23509345, 320376101, 346830230, 145219833, 199210832, 103953764, 162617478, 125617909, 304841448, 171451135, 288597351, 397253375, 399383320, 293551849, 70006193, 339262629, 197748142, 259857162, 272401130, 276637258, 261392879, 266322961, 25125188, 321610868, 295080796, 35214212],
[90, 285343019, 100968656, 224536557, 152665400, 158023759, 197556778, 291620179, 325804543, 174979682, 207991060, 80313119, 136842755, 197572553, 101220876, 31351347, 101082215, 172363835, 46784046, 311923455, 269902893, 154885935, 79720095, 63655184, 283521261, 251555999, 163975870, 73399296, 4114560, 10441080, 222045214, 242007278, 53326351, 368013913, 6108294, 205455783, 70084122, 64254900, 99076342, 136207504, 16797882, 27580198, 144925954, 398327639, 103982929, 11162495, 371152176, 73527979, 133383042, 82476513],
[91, 187136381, 375874780, 187228529, 214616467, 1572613, 162563194, 140185834, 149977623, 52240025, 190483011, 177227166, 219937090, 9678302, 262672494, 82838954, 394086916, 184669671, 406111131, 48330510, 275544278, 293647131, 35698369, 341823496, 84985194, 56537364, 100703039, 343925276, 174760934, 155888396, 39583414, 356007562, 160177391, 264449608, 332758322, 37779135, 71240619, 29812322, 266592776, 283218417, 385805660, 10005033, 249018801, 252620535, 265412013, 287161863, 156883546, 86795623, 276224002, 51966484],
[92, 120013404, 60998095, 70423988, 155325746, 258870266, 113044637, 278807199, 247174548, 181280487, 81052858, 268200036, 32960114, 31148047, 18097172, 257698073, 397424730, 151326620, 112344215, 54378133, 290339088, 213203545, 63737895, 149272513, 197019401, 405817435, 380950418, 29286259, 384123307, 205940761, 182676488, 206926617, 231875295, 310305757, 38733159, 11134298, 296469975, 32071865, 149419950, 158343803, 259068017, 289229574, 73326103, 136618986, 24318208, 386424259, 386572620, 133244347, 23114784, 242580],
[93, 194226865, 131364580, 321910162, 388653108, 366055223, 24424188, 93297585, 270142769, 73764656, 46777981, 353636507, 261073197, 18554705, 284986202, 271667082, 182172376, 243852055, 1353781, 209638494, 11385673, 405615655, 238580424, 132975192, 185711527, 299328541, 217101649, 84155603, 105576399, 181320222, 302777033, 146124821, 84550022, 314673592, 199975564, 231573807, 173787281, 185339006, 48204476, 278674622, 335354634, 16413506, 171346836, 355498489, 251635720, 151994510, 400826743, 108899978, 340868470, 144978814],
[94, 350036406, 40226254, 158434758, 171193062, 13183146, 130717901, 25829822, 202941838, 244706426, 400924501, 341520742, 65036095, 214008566, 40769589, 405921677, 232934370, 314876255, 186525619, 383612822, 401157738, 39941328, 44905384, 356308662, 316599204, 96575974, 126043903, 114965675, 239070557, 384872906, 118035819, 127231596, 141447522, 134611323, 367493047, 156873830, 60242309, 288720759, 155910953, 256239546, 63799278, 5181267, 151358023, 48292202, 203154498, 59065221, 1137815, 196995992, 164689359, 277006602],
[324972082, 95, 356948864, 50386966, 55731671, 141509406, 52734714, 4595437, 178990996, 267208691, 111803896, 303503098, 377317268, 95143701, 130014111, 389945003, 140435179, 357113798, 315986839, 361791093, 216768936, 191956650, 313183637, 169872171, 27352512, 217294784, 35093167, 155423619, 305017538, 396975754, 216390841, 268804534, 354211183, 196027869, 257046709, 148426488, 75818880, 293905659, 384859819, 11741408, 373875512, 394677978, 187859294, 407086436, 151486469, 331683229, 357625957, 23404706, 56325332, 179278846],
[96, 322269386, 16336199, 238861569, 47190474, 107325420, 191159336, 391792564, 295730472, 358885893, 304561849, 98069342, 113020191, 354458313, 251926613, 330444636, 18955792, 346165519, 203697847, 224639385, 34571149, 323998486, 78903277, 341957239, 83074015, 319037359, 201422963, 110612236, 66213895, 352245751, 56739050, 4989946, 397724493, 251435553, 303769980, 406112511, 195230519, 177645164, 117489828, 146222205, 124298447, 68554439, 306362009, 115957583, 263444001, 40810269, 245282714, 49016832, 75345947, 113825294],
[97, 378226508, 223178422, 287369206, 359746277, 321397635, 204113285, 111651960, 294999848, 164547940, 269065893, 275977314, 266677870, 353316247, 330909322, 227513076, 159439903, 86902437, 136520385, 49492346, 84271956, 218015912, 241320085, 370454665, 326142136, 385844100, 310962956, 308521983, 303011501, 146585644, 74124428, 100068772, 268983251, 71269100, 308216554, 193180787, 377496563, 27168472, 4243093, 276021008, 325397276, 178534695, 393029525, 289548219, 48428512, 300573937, 66032905, 119891657, 392699122, 255120938],
[98, 137803405, 216176974, 300846555, 96909077, 154559038, 228655860, 391932843, 181926920, 406731549, 303986740, 172068691, 178051968, 33683503, 200038090, 88739345, 97890766, 242314379, 161757306, 66639432, 103625668, 49435366, 169768112, 185067489, 145582525, 18512392, 61371651, 402819176, 209285333, 147379985, 403150404, 222006258, 352836094, 134159774, 194313754, 404068951, 292356986, 378985176, 7239039, 281217998, 63726854, 366842015, 298044403, 150137345, 288635565, 262703491, 150248616, 120962412, 91346375, 225784889],
[99, 197837191, 161481305, 110391286, 207667247, 193602197, 322637391, 274895237, 200179002, 6259654, 279864206, 245226320, 305182890, 237501300, 140497833, 343463433, 141884629, 153944055, 217042298, 300107265, 328836658, 129884692, 387235795, 373159720, 369821023, 69865559, 340061371, 339371793, 184108602, 362770800, 250655952, 152473606, 321350527, 173557493, 268332271, 349684634, 330322764, 23829410, 195283790, 272424848, 183483959, 26985412, 292828332, 26407235, 230512678, 2693126, 265209501, 257432702, 67403625, 53253459],
]
import time
import argparse
from tqdm import tqdm
import multiprocessing as mp
import numpy as np
import psycopg
from pgvector.psycopg import register_vector
def build_arg_parse():
parser = argparse.ArgumentParser()
parser.add_argument(
"-m",
"--metric",
help="Metric to pick, in l2 or cos",
choices=["l2", "cos", "dot"],
default="l2",
)
parser.add_argument("-n", "--name", help="Dataset name, like: sift", required=True)
parser.add_argument(
"--url",
help="url, like `postgresql://postgres:123@localhost:5432/postgres`",
required=True,
)
parser.add_argument(
"-t", "--top", help="Dimension", type=int, choices=[10, 50], default=50
)
parser.add_argument(
"--nprob", help="argument probes for query", default=100, type=int
)
parser.add_argument(
"--epsilon", help="argument epsilon for query", type=float, default=1.0
)
parser.add_argument(
"--processes", help="Number of parallel processes to use", type=int, default=1
)
return parser
def create_connection(url, nprob, epsilon):
keepalive_kwargs = {
"keepalives": 1,
"keepalives_idle": 30,
"keepalives_interval": 5,
"keepalives_count": 5,
}
conn = psycopg.connect(
conninfo=url,
dbname="postgres",
autocommit=True,
**keepalive_kwargs,
)
try:
conn.execute("CREATE EXTENSION IF NOT EXISTS vector")
conn.execute("CREATE EXTENSION IF NOT EXISTS vchord")
except Exception:
pass
# Tuning
conn.execute("SET jit=false")
conn.execute("SET effective_io_concurrency=200")
conn.execute(f"SET vchordrq.probes={nprob}")
conn.execute(f"SET vchordrq.epsilon={epsilon}")
try:
conn.execute(f"SELECT vchordrq_prewarm('{args.name}_embedding_idx'::regclass)")
except Exception:
pass
register_vector(conn)
return conn
def calculate_metrics(all_results, k, m, num_processes=1):
"""Calculate recall, QPS, and latency percentiles from results"""
hits, latencies = zip(*all_results)
total_time = sum(latencies)
total_hits = sum(hits)
recall = total_hits / (k * m * num_processes)
qps = (m * num_processes) / total_time
# Calculate latency percentiles (in milliseconds)
latencies_ms = np.array(latencies) * 1000
p50 = np.percentile(latencies_ms, 50)
p99 = np.percentile(latencies_ms, 99)
return recall, qps, p50, p99
def sequential_bench(name, test, answer, metric_ops, conn, top):
"""Original sequential benchmark implementation with latency tracking"""
m = test.shape[0]
results = []
pbar = tqdm(enumerate(test), total=m)
for i, query in pbar:
start = time.perf_counter()
result = conn.execute(
f"SELECT id FROM {name} ORDER BY embedding {metric_ops} %s LIMIT {top}",
(query,),
).fetchall()
end = time.perf_counter()
query_time = end - start
hit = len(set([p[0] for p in result[:top]]) & set(answer[i][:top]))
results.append((hit, query_time))
# Update progress bar with running metrics
curr_results = results[: i + 1]
curr_recall, curr_qps, curr_p50, _ = calculate_metrics(curr_results, top, i + 1)
pbar.set_description(
f"recall: {curr_recall:.4f} QPS: {curr_qps:.2f} P50: {curr_p50:.2f}ms"
)
# Calculate final metrics
recall, qps, p50, p99 = calculate_metrics(results, top, m)
print(f"Top: {top}")
print(f" Recall: {recall:.4f}")
print(f" QPS: {qps:.2f}")
print(f" P50 latency: {p50:.2f}ms")
print(f" P99 latency: {p99:.2f}ms")
NUMBER_OF_PARTS = 409
def read_npy_files():
idx = 0
uploaded = 0
while idx <= NUMBER_OF_PARTS:
data = np.load(f"data/laion/img_emb_{idx}.npy")
for row in data:
yield uploaded, row.reshape(-1)
uploaded += 1
del row
idx += 1
if __name__ == "__main__":
parser = build_arg_parse()
args = parser.parse_args()
print(args)
data = np.load(f"data/laion/img_emb_0.npy")
test = data[:100, :]
if args.metric == "l2":
metric_ops = "<->"
elif args.metric == "cos":
metric_ops = "<=>"
elif args.metric == "dot":
metric_ops = "<#>"
else:
raise ValueError
conn = create_connection(args.url, args.nprob, args.epsilon)
sequential_bench(args.name, test, full_scan_result, metric_ops, conn, args.top)
Raw
download.py
import os
NUMBER_OF_PARTS = 409
CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
DATA_DIR = os.path.join(CURRENT_DIR, "data")
def get_img_emb_url(part: int) -> str:
return f"https://deploy.laion.ai/8f83b608504d46bb81708ec86e912220/embeddings/img_emb/img_emb_{part}.npy"
def get_metadata_url(part: int) -> str:
return f"https://deploy.laion.ai/8f83b608504d46bb81708ec86e912220/embeddings/metadata/metadata_{part}.parquet"
def local_img_emb_path(part: int) -> str:
return os.path.join(DATA_DIR, "laion", f"img_emb_{part}.npy")
def local_metadata_path(part: int) -> str:
return os.path.join(DATA_DIR, "laion", f"metadata_{part}.parquet")
def download_file(url: str, path: str):
print(f"Downloading {url} to {path}")
if not os.path.exists(path):
os.system(f"wget {url} -O {path}")
def download(idx: int):
# download files
download_file(get_img_emb_url(idx), local_img_emb_path(idx))
download_file(get_metadata_url(idx), local_metadata_path(idx))
def download_all(limit):
idx = 0
os.makedirs(os.path.join(DATA_DIR, "laion"), exist_ok=True)
while idx <= limit:
embedding_path = local_img_emb_path(idx)
if os.path.exists(embedding_path):
print(f"File {embedding_path} exist，skip download")
else:
download(idx)
idx += 1
def main():
download_all(NUMBER_OF_PARTS)
if __name__ == "__main__":
main()
Raw
index.py
import asyncio
from time import perf_counter
import argparse
import psycopg
from pgvector.psycopg import register_vector_async
import numpy as np
from tqdm import tqdm
KEEPALIVE_KWARGS = {
"keepalives": 1,
"keepalives_idle": 30,
"keepalives_interval": 5,
"keepalives_count": 5,
}
CHUNKS = 10
def build_arg_parse():
parser = argparse.ArgumentParser(description="Build index with K-means centroids")
parser.add_argument(
"-m",
"--metric",
help="Distance metric",
default="cos",
choices=["l2", "cos", "dot"],
)
parser.add_argument(
"-n", "--name", help="Dataset name, like: sift", required=False, default="laion"
)
parser.add_argument(
"--url",
help="url, like `postgresql://postgres:123@localhost:5432/postgres`",
required=True,
)
parser.add_argument(
"-d", "--dim", help="Dimension", type=int, required=False, default=512
)
parser.add_argument(
"--num", help="Numbers", type=int, required=False, default=400_000_000
)
parser.add_argument(
"-w",
"--workers",
help="Workers to build index",
type=int,
required=False,
default=16,
)
# External build
parser.add_argument(
"-c", "--centroids", help="K-means centroids file", required=True
)
return parser
def get_ivf_ops_config(metric, workers, name=None):
assert name is not None
external_centroids_cfg = """
[build.external]
table = 'public.{name}_centroids'
"""
if metric == "l2":
metric_ops = "halfvec_l2_ops"
config = "residual_quantization = true"
elif metric == "cos":
metric_ops = "halfvec_cosine_ops"
config = "residual_quantization = false"
elif metric == "dot":
metric_ops = "halfvec_ip_ops"
config = "residual_quantization = false"
else:
raise ValueError
build_config = external_centroids_cfg.format(name=name)
return metric_ops, "\n".join([config, build_config])
async def create_connection(url):
conn = await psycopg.AsyncConnection.connect(
conninfo=url,
dbname="postgres",
autocommit=True,
**KEEPALIVE_KWARGS,
)
await conn.execute("CREATE EXTENSION IF NOT EXISTS vector")
await conn.execute("CREATE EXTENSION IF NOT EXISTS vchord")
await register_vector_async(conn)
return conn
async def add_centroids(conn, name, centroids):
n, dim = centroids.shape
root = np.mean(centroids, axis=0)
await conn.execute(f"DROP TABLE IF EXISTS public.{name}_centroids")
await conn.execute(
f"CREATE TABLE public.{name}_centroids (id integer, parent integer, vector vector({dim}))"
)
async with conn.cursor().copy(
f"COPY public.{name}_centroids (id, parent, vector) FROM STDIN WITH (FORMAT BINARY)"
) as copy:
copy.set_types(["integer", "integer", "vector"])
await copy.write_row((0, None, root))
for i, centroid in tqdm(enumerate(centroids), desc="Adding centroids", total=n):
await copy.write_row((i + 1, 0, centroid))
while conn.pgconn.flush() == 1:
await asyncio.sleep(0)
async def add_embeddings(conn, name, dim, n, iterator, workers):
await conn.execute(f"DROP TABLE IF EXISTS {name}")
await conn.execute(f"CREATE TABLE {name} (id integer, embedding halfvec({dim}))")
await conn.execute(f"ALTER TABLE {name} SET (parallel_workers = {workers})")
pbar = tqdm(desc="Adding embeddings", total=n)
async with conn.cursor().copy(
f"COPY {name} (id, embedding) FROM STDIN WITH (FORMAT BINARY)"
) as copy:
for i, vec in iterator:
copy.set_types(["integer", "halfvec"])
await copy.write_row((i, vec.astype(np.float16)))
while conn.pgconn.flush() == 1:
await asyncio.sleep(0)
pbar.update(1)
pbar.close()
async def build_index(
conn, name, workers, metric_ops, ivf_config, finish: asyncio.Event
):
start_time = perf_counter()
await conn.execute(f"SET max_parallel_maintenance_workers TO {workers}")
await conn.execute(f"SET max_parallel_workers TO {workers}")
await conn.execute(
f"CREATE INDEX {name}_embedding_idx ON {name} USING vchordrq (embedding {metric_ops}) WITH (options = $${ivf_config}$$)"
)
print(f"Index build time: {perf_counter() - start_time:.2f}s")
finish.set()
async def monitor_index_build(conn, finish: asyncio.Event):
async with conn.cursor() as acur:
blocks_total = None
while blocks_total is None:
await asyncio.sleep(1)
await acur.execute("SELECT blocks_total FROM pg_stat_progress_create_index")
blocks_total = await acur.fetchone()
total = 0 if blocks_total is None else blocks_total[0]
pbar = tqdm(smoothing=0.0, total=total, desc="Building index")
while True:
if finish.is_set():
pbar.update(pbar.total - pbar.n)
return
await acur.execute("SELECT blocks_done FROM pg_stat_progress_create_index")
blocks_done = await acur.fetchone()
done = 0 if blocks_done is None else blocks_done[0]
pbar.update(done - pbar.n)
await asyncio.sleep(1)
pbar.close()
NUMBER_OF_PARTS = 409
def read_npy_files():
idx = 0
uploaded = 0
while idx <= NUMBER_OF_PARTS:
data = np.load(f"data/laion/img_emb_{idx}.npy")
for row in data:
yield uploaded, row.reshape(-1)
uploaded += 1
del row
idx += 1
async def main(args):
iterator = read_npy_files()
conn = await create_connection(args.url)
if args.centroids:
centroids = np.load(args.centroids, allow_pickle=False)
await add_centroids(conn, args.name, centroids)
metric_ops, ivf_config = get_ivf_ops_config(args.metric, args.workers, args.name)
await add_embeddings(conn, args.name, args.dim, args.num, iterator, args.workers)
index_finish = asyncio.Event()
# Need a separate connection for monitor process
monitor_conn = await create_connection(args.url)
monitor_task = monitor_index_build(
monitor_conn,
index_finish,
)
index_task = build_index(
conn,
args.name,
args.workers,
metric_ops,
ivf_config,
index_finish,
)
await asyncio.gather(index_task, monitor_task)
if __name__ == "__main__":
parser = build_arg_parse()
args = parser.parse_args()
print(args)
asyncio.run(main(args))
Raw
train.py
import os
import random
from time import perf_counter
import argparse
from pathlib import Path
from sys import version_info
from tqdm import tqdm
from numpy import linalg as LA
if version_info >= (3, 12):
raise RuntimeError("h5py doesn't support 3.12")
from faiss import Kmeans
import numpy as np
DEFAULT_LISTS = 160000
N_ITER = 25
CHUNKS = 10
SEED = 42
MAX_POINTS_PER_CLUSTER = 256
def build_arg_parse():
parser = argparse.ArgumentParser(description="Train K-means centroids")
parser.add_argument("-o", "--output", help="output filepath", required=False, default='centroids.npy')
parser.add_argument("-t", "--total", type=int, required=False, default=400_000_000)
parser.add_argument(
"--lists",
help="Number of centroids",
type=int,
required=False,
default=DEFAULT_LISTS,
)
parser.add_argument(
"--niter", help="number of iterations", type=int, default=N_ITER
)
parser.add_argument("-m", "--metric", choices=["l2", "cos", "dot"], default="cos")
parser.add_argument(
"-g", "--gpu", help="enable GPU for KMeans", action="store_true"
)
return parser
def sample_vectors(iterator, sample_size, total_size, chunk_size=10000000):
probability = sample_size / total_size
result = []
chunk_count = 0
file_paths = []
with tqdm(total=total_size, desc="Processing vectors", mininterval=1) as pbar:
for vector in iterator:
if random.random() < probability:
result.append(vector)
if len(result) >= sample_size:
break
if len(result) >= chunk_size:
chunk_file = f"sampled_chunk_{chunk_count}.npy"
np.save(chunk_file, np.stack(result))
file_paths.append(chunk_file)
result = []
chunk_count += 1
pbar.update(1)
if result:
chunk_file = f"sampled_chunk_{chunk_count}.npy"
np.save(chunk_file, np.stack(result))
file_paths.append(chunk_file)
return file_paths
def kmeans_cluster(
data_iter,
size,
k,
niter,
metric,
gpu=False,
):
dim = 512
sample_vectors(data_iter, MAX_POINTS_PER_CLUSTER * args.lists, size)
files = sorted([f for f in os.listdir('.') if f.startswith('sampled_chunk')])
train = []
for file in tqdm(files):
chunk = np.load(file)
train.append(chunk)
train = np.vstack(train).reshape(-1, dim)
print(train.shape)
if metric == "cos":
train = train / LA.norm(train, axis=1, keepdims=True)
kmeans = Kmeans(
dim, k, gpu=gpu, verbose=True, niter=niter, seed=SEED, spherical=metric != "l2"
)
kmeans.train(train)
return kmeans.centroids
def read_npy_files(file_pattern):
files = sorted([f for f in os.listdir('data') if f.endswith('.npy') and f.startswith(file_pattern)])
for file in files:
data = np.load(os.path.join('data', file))
for row in data:
yield row.reshape(1, -1)
del row
if __name__ == "__main__":
parser = build_arg_parse()
args = parser.parse_args()
print(args)
file_pattern = 'img_emb'
iterator = read_npy_files(file_pattern)
start_time = perf_counter()
centroids = kmeans_cluster(
iterator,
args.total,
args.lists,
args.niter,
args.metric,
args.gpu
)
print(
f"K-means (k=({args.lists})): {perf_counter() - start_time:.2f}s"
)
np.save(Path(args.output), centroids, allow_pickle=False)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment