Vector index — FAISS, approximate nearest neighbor আর vector database

এই পর্বের desktop run: Bangla Wikipedia (Hugging Face dataset wikimedia/wikipedia, snapshot 20231101.bn, লাইসেন্স CC BY-SA) দুটি parquet ফাইলে আছে; দ্বিতীয়টির শুরু থেকে ১৫০ অক্ষরের বেশি লম্বা প্রথম ১,০০,০০০টি অনুচ্ছেদ (প্রতিটি ৬০০ অক্ষরে কাটা) এই পর্বের corpus. Embedding model intfloat/multilingual-e5-small (MIT লাইসেন্স, token ছাড়া নামানো যায়, ৩৮৪ মাত্রা), CPU-তে ৩ thread-এ। লেখার সময়ে version: Python 3.12, torch 2.15.0, sentence-transformers 6.2.0, faiss-cpu 1.15.1, qdrant-client 1.20.0. পাতায় script ছোট করে দেখানো, আউটপুট হুবহু। পাতার চারটি কোড ব্লক আপনার browser-এ চলে (Pyodide), NumPy দিয়ে নিজে লেখা ছোট index. FAISS বা embedding model পাতায় চলে না, তাই সেগুলোর ফল সত্যিকারের run থেকে হুবহু।

১ · নির্ভুল খোঁজার দাম — N × d

বড় পাইকারি বাজারে একটি নির্দিষ্ট মাপের স্ক্রু খুঁজছেন। একটি উপায়: প্রতিটি দোকানে ঢুকে জিজ্ঞেস করা। উত্তর নির্ভুল, কিন্তু ৫০০ দোকান ঘুরতে সারাদিন। অভিজ্ঞ লোক আগে জানেন হার্ডওয়্যারের গলি কোনটি, তারপর শুধু সেই গলির কয়েকটি দোকান দেখেন। মাঝে মাঝে পাশের গলির একটি ভালো দোকান বাদ পড়ে, কিন্তু সময় বাঁচে বহুগুণ। এই পর্বের পুরো বিষয় এই লেনদেন।

পর্ব ৬৭ · Sentence embedding আর semantic search-এ প্রতিটি লেখা একটি vector হয়ে যায়, আর খোঁজা মানে প্রশ্নের vector-এর সবচেয়ে কাছের k-টি vector বের করা (nearest neighbor search). Vector normalise করা থাকলে cosine আর dot product একই ক্রম দেয় (AI-এর ভিত্তি কোর্সের পর্ব ৩৩)। প্রথম vector search আর একটি ছোট FAISS তুলনা AI-এর ভিত্তি কোর্সের পর্ব ৬৯-এ দেখেছেন; এখানে প্রতিটি index-এর ভেতরের অঙ্কে নামব, আর আসল বাংলা embedding-এ মাপব।

সবচেয়ে সরল পথ: প্রশ্ন q-এর সঙ্গে সব N-টি vector-এর dot product, তারপর সেরা k. প্রতিটি dot product-এ d-টি গুণ আর যোগ, তাই প্রতি প্রশ্নে কাজ

খরচ ≈ N × d গুণ-যোগ,   মেমরি = N × d × 4 byte (float32)

এখানে N হলো vector-এর সংখ্যা, d মাত্রা (dimension), আর ৪ হলো একটি float32 সংখ্যার byte. এই পর্বের desktop corpus-এ N = ১,০০,০০০ আর d = ৩৮৪: প্রতি প্রশ্নে ৩,৮৪,০০,০০০ গুণ-যোগ, মেমরি ১,০০,০০০ × ৩৮৪ × ৪ = ১৫,৩৬,০০,০০০ byte = ১৫৩.৬ MB. Run শুরুর আগেই এই হিসাব করে নিশ্চিত হয়েছি যে embedding, তিন-চারটি index আর model একসঙ্গে ৩ GB-এর নিচে থাকবে। এক কোটি vector হলে একই হিসাবে ১৫.৩৬ GB, শুধু কাঁচা vector-এ।

সেরা k বাছতেও পুরো সাজানোর (N log N) দরকার নেই: np.argpartition গড়ে O(N) সময়ে যেকোনো ক্রমে সেরা k আলাদা করে, তারপর শুধু সেই k-টি সাজানো হয় (heap দিয়েও করা যায়, DSA কোর্সের পর্ব ২৩)। নিচের ব্লকে ২০,০০০টি ৬৪-মাত্রার কৃত্রিম, গুচ্ছবদ্ধ vector (৫০টি “বিষয়” ঘিরে ছড়ানো; আসল embedding নয়, কিন্তু আসলের মতো দলে জড়ো) আর ২০০টি প্রশ্ন। সঙ্গে recall@k: নির্ভুল সেরা k-এর কতটি আমাদের পদ্ধতি খুঁজে পেল, তার গড় ভাগ।

import numpy as np
rng = np.random.default_rng(42)
N, d, k = 20000, 64, 10
topics = rng.normal(size=(50, d))                 # ৫০টি "বিষয়" (গুচ্ছের কেন্দ্র)
X = topics[rng.integers(0, 50, N)] + 0.8 * rng.normal(size=(N, d))
X = (X / np.linalg.norm(X, axis=1, keepdims=True)).astype(np.float32)
Q = X[rng.choice(N, 200, replace=False)] + 0.3 * rng.normal(size=(200, d))
Q = (Q / np.linalg.norm(Q, axis=1, keepdims=True)).astype(np.float32)

def knn(Q, X, k):                                  # brute-force: সবার সঙ্গে dot
    S = Q @ X.T                                    # (200, N) score
    part = np.argpartition(-S, k, axis=1)[:, :k]   # O(N): যেকোনো ক্রমে সেরা k
    order = np.argsort(-np.take_along_axis(S, part, 1), axis=1)
    return np.take_along_axis(part, order, 1)

def recall_at_k(found, truth):                     # প্রতি প্রশ্নে মিল / k, তারপর গড়
    return np.mean([len(set(f) & set(t)) / len(t) for f, t in zip(found, truth)])

truth = knn(Q, X, k)
print(f"N={N}, d={d}: প্রতি প্রশ্নে {N*d:,} গুণ-যোগ, {len(Q)} প্রশ্নে {N*d*len(Q):,}")
print(f"X float32: {X.nbytes/1e6:.2f} MB = N × d × 4 byte")

scale = 127 / np.abs(X).max()                      # int8-এ চেপে রাখা
X8 = np.round(X * scale).astype(np.int8)
found8 = knn(Q, X8.astype(np.float32) / scale, k)
print(f"int8 কপি {X8.nbytes/1e6:.2f} MB, recall@10 = {recall_at_k(found8, truth):.3f}")
half = knn(Q, X[: N // 2], k)                      # অর্ধেক ডেটা দেখলে কী হয়
print(f"শুধু অর্ধেক ডেটা দেখে recall@10 = {recall_at_k(half, truth):.3f}")

N=20000, d=64: প্রতি প্রশ্নে 1,280,000 গুণ-যোগ, 200 প্রশ্নে 256,000,000
X float32: 5.12 MB = N × d × 4 byte
int8 কপি 1.28 MB, recall@10 = 0.975
শুধু অর্ধেক ডেটা দেখে recall@10 = 0.521

২ · প্রায়-নিকটতম খোঁজা — তিনটি পরিবার, তিনদিকের লেনদেন

Approximate nearest neighbor (ANN) পদ্ধতিগুলো সব vector দেখে না। বিনিময়ে মাঝে মাঝে প্রকৃত সেরা k-এর কয়েকটি হারায়। প্রতিটি পদ্ধতি তিনটি জিনিসের মধ্যে লেনদেন করে: recall (কতটা নির্ভুল), latency (প্রতি প্রশ্নে কত সময়) আর মেমরি (index কত বড়)। সঙ্গে আরও দুটি খরচ: index বানানোর সময়, আর নতুন vector যোগ করা কতটা সহজ।

এগুলো জোড়াও লাগে: IVF + PQ (IVFPQ) বড় মাপের সবচেয়ে চেনা জুটি, আর HNSW দিয়ে IVF-এর centroid খোঁজাও হয়। পরের তিনটি অংশে প্রতিটি হাতে-কলমে।

৩ · IVF — cell ভাগ আর nprobe

IVF মানে inverted file. নামটি এসেছে text search-এর inverted index থেকে (সিস্টেম ডিজাইন কোর্সের পর্ব ২৭): সেখানে শব্দ থেকে নথির তালিকা, এখানে cell থেকে vector-এর তালিকা। ধাপ দুটি:

• বানানোর সময় (train + add): k-means দিয়ে nlist-টি centroid শেখা (AI-এর ভিত্তি কোর্সের পর্ব ৬৫)। প্রতিটি vector তার সবচেয়ে কাছের centroid-এর তালিকায় যায়। প্রতিটি centroid ঘিরে জায়গাটুকু একটি Voronoi cell.
• খোঁজার সময়: প্রশ্নকে nlist-টি centroid-এর সঙ্গে মেপে কাছের nprobe-টি cell বাছা, তারপর শুধু সেই তালিকাগুলোয় brute-force.

খরচ মোটামুটি nlist + nprobe × N / nlist দূরত্ব (cell সমান মাপের হলে)। N = ১ লাখ, nlist = ১০২৪, nprobe = ১৬ হলে ১০২৪ + ১৬ × ৯৮ ≈ ২,৫৮৬, অর্থাৎ ১ লাখের ৩ ভাগেরও কম। FAISS-এর নির্দেশিকা nlist রাখতে বলে মোটামুটি ৪√N থেকে ১৬√N, আর train-এ ৩০ × nlist থেকে ২৫৬ × nlist-টি vector. নিচের খেলনা উদাহরণে ঝুঁকিটা হাতে দেখুন।

এবার একই চিন্তা ২০,০০০টি vector-এ। k-means হাতে লেখা (scikit-learn-এর KMeans পাতায় একটি অপ্রাসঙ্গিক warning দেয়), nlist = ৬৪, তারপর nprobe বাড়িয়ে recall আর কাজ।

import numpy as np
rng = np.random.default_rng(42)
N, d, k, nlist = 20000, 64, 10, 64
topics = rng.normal(size=(50, d))
X = topics[rng.integers(0, 50, N)] + 0.8 * rng.normal(size=(N, d))
X = (X / np.linalg.norm(X, axis=1, keepdims=True)).astype(np.float32)
Q = X[rng.choice(N, 200, replace=False)] + 0.3 * rng.normal(size=(200, d))
Q = (Q / np.linalg.norm(Q, axis=1, keepdims=True)).astype(np.float32)
truth = np.argsort(-(Q @ X.T), axis=1)[:, :k]      # নির্ভুল উত্তর

# k-means হাতে (scikit-learn-এর KMeans পাতায় অপ্রয়োজনীয় warning দেয়)
C = X[rng.choice(N, nlist, replace=False)].copy()
for it in range(10):
    assign = np.argmax(X @ C.T, axis=1)            # সবচেয়ে কাছের centroid
    for c in range(nlist):
        m = X[assign == c]
        if len(m): C[c] = m.mean(0) / np.linalg.norm(m.mean(0))
lists = [np.where(assign == c)[0] for c in range(nlist)]   # inverted list
sizes = np.array([len(l) for l in lists])
print(f"nlist={nlist}: list-এর আকার min {sizes.min()}, গড় {sizes.mean():.0f}, max {sizes.max()}")

def ivf_search(q, nprobe):
    probe = np.argsort(-(C @ q))[:nprobe]          # ধাপ ১: কাছের nprobe-টি cell
    cand = np.concatenate([lists[c] for c in probe])
    s = X[cand] @ q                                # ধাপ ২: শুধু তাদের ভেতরে
    return cand[np.argsort(-s)[:k]], nlist + len(cand)

for nprobe in [1, 2, 4, 8, 16]:
    res = [ivf_search(q, nprobe) for q in Q]
    rec = np.mean([len(set(f) & set(t)) / k for (f, _), t in zip(res, truth)])
    work = np.mean([w for _, w in res])
    print(f"nprobe={nprobe:2d}  দূরত্ব/প্রশ্ন {work:7.0f} ({work/N:5.1%})  recall@10 {rec:.3f}")

nlist=64: list-এর আকার min 85, গড় 312, max 809
nprobe= 1  দূরত্ব/প্রশ্ন     414 ( 2.1%)  recall@10 0.637
nprobe= 2  দূরত্ব/প্রশ্ন     734 ( 3.7%)  recall@10 0.793
nprobe= 4  দূরত্ব/প্রশ্ন    1377 ( 6.9%)  recall@10 0.904
nprobe= 8  দূরত্ব/প্রশ্ন    2631 (13.2%)  recall@10 0.968
nprobe=16  দূরত্ব/প্রশ্ন    5107 (25.5%)  recall@10 0.990

৪ · Product quantization — ১৫৩৬ byte থেকে ৪৮ byte

IVF সময় বাঁচায়, মেমরি নয়: প্রতিটি vector তখনও পুরো float32-এ থাকে। এক কোটি ৩৮৪-মাত্রার vector মানে ১৫ GB-এর বেশি RAM. Product quantization (PQ) vector-কেই চেপে ছোট করে।

• টুকরো করা: d-মাত্রার vector-কে m-টি সমান টুকরোয় ভাগ, প্রতিটি d/m মাত্রার।
• প্রতি টুকরোয় আলাদা k-means: সাধারণত ২৫৬টি centroid, যাদের তালিকাকে বলে codebook.
• Encode: প্রতিটি টুকরোর জায়গায় শুধু কাছের centroid-এর নম্বর (০–২৫৫), অর্থাৎ ১ byte. পুরো vector = m byte.
• খোঁজা (ADC): প্রশ্ন চাপা হয় না। প্রতি টুকরোয় প্রশ্নের সঙ্গে ২৫৬টি centroid-এর dot product একবার হিসাব করে টেবিল বানানো; তারপর প্রতিটি ডেটা vector-এর score = m-টি টেবিল-ঘর পড়ে যোগ।

দাম কতটা, নিচের ব্লকে দেখুন। ৬৪-মাত্রার vector, m = ১৬ (প্রতি টুকরো ৪ মাত্রা), ২৫৬টি codeword: ২৫৬ byte থেকে ১৬ byte. শেষে একটি প্রচলিত কৌশল: PQ score দিয়ে ১০০টি প্রার্থী, তারপর শুধু সেই ১০০টির আসল vector দিয়ে আবার সাজানো (re-ranking).

import numpy as np
rng = np.random.default_rng(42)
N, d, k, m, ks = 20000, 64, 10, 16, 256             # m টুকরো, প্রতিটিতে 256 codeword
ds = d // m                                        # প্রতি টুকরো 4 মাত্রা
topics = rng.normal(size=(50, d))
X = topics[rng.integers(0, 50, N)] + 0.8 * rng.normal(size=(N, d))
X = (X / np.linalg.norm(X, axis=1, keepdims=True)).astype(np.float32)
Q = X[rng.choice(N, 200, replace=False)] + 0.3 * rng.normal(size=(200, d))
Q = (Q / np.linalg.norm(Q, axis=1, keepdims=True)).astype(np.float32)
truth = np.argsort(-(Q @ X.T), axis=1)[:, :k]
near = lambda A, C: np.argmin((C**2).sum(1) - 2 * A @ C.T, axis=1)   # সবচেয়ে কাছের codeword

books, codes = [], np.empty((N, m), dtype=np.uint8)
train = X[rng.choice(N, 4000, replace=False)]
for j in range(m):                                 # প্রতি টুকরোয় আলাদা k-means
    sub = train[:, j*ds:(j+1)*ds]
    C = sub[rng.choice(len(sub), ks, replace=False)].copy()
    for it in range(6):
        a = near(sub, C)
        for c in np.unique(a): C[c] = sub[a == c].mean(0)
    codes[:, j] = near(X[:, j*ds:(j+1)*ds], C)     # encode: 4টি সংখ্যা → 1 byte
    books.append(C)
Xhat = np.hstack([books[j][codes[:, j]] for j in range(m)])   # decode
print(f"প্রতি vector: float32 {d*4} byte → PQ code {codes[0].nbytes} byte; codebook মোট {m*ks*ds*4/1024:.0f} KiB")
print(f"গড় পুনর্গঠন ভুল ‖x − x̂‖ = {np.linalg.norm(X - Xhat, axis=1).mean():.3f} (‖x‖ = 1)")

def adc(q):                                        # প্রশ্ন আসল, ডেটা code: টেবিল দেখে যোগ
    T = np.stack([books[j] @ q[j*ds:(j+1)*ds] for j in range(m)])   # (m, 256)
    return T[np.arange(m), codes].sum(1)           # প্রতি vector-এ m-টি টেবিল-পড়া
rec = lambda F: np.mean([len(set(f) & set(t)) / k for f, t in zip(F, truth)])
found = [np.argsort(-adc(q))[:k] for q in Q]
short = [np.argsort(-adc(q))[:100] for q in Q]     # PQ দিয়ে 100 প্রার্থী, তারপর আসল vector
rr = [c[np.argsort(-(X[c] @ q))[:k]] for c, q in zip(short, Q)]
print(f"শুধু PQ score: recall@10 {rec(found):.3f};  PQ-তে top-100, আসল vector-এ re-rank: {rec(rr):.3f}")

প্রতি vector: float32 256 byte → PQ code 16 byte; codebook মোট 64 KiB
গড় পুনর্গঠন ভুল ‖x − x̂‖ = 0.296 (‖x‖ = 1)
শুধু PQ score: recall@10 0.478;  PQ-তে top-100, আসল vector-এ re-rank: 0.967

৫ · HNSW — স্তরের graph-এ লোভী হাঁটা

অচেনা শহরে একটি ঠিকানা খুঁজতে আপনি আগে highway ধরে সঠিক এলাকায় যান, তারপর বড় রাস্তা, শেষে গলি। প্রতিটি মোড়ে শুধু জিজ্ঞেস করেন, “কোন দিকে গেলে আরও কাছে?” HNSW (Hierarchical Navigable Small World) এভাবেই কাজ করে। Yury Malkov আর Dmitry Yashunin ২০১৬ সালে arXiv-এ প্রস্তাব করেন (জার্নালে ২০১৮)। এর আগের NSW graph-এ একটিই স্তর ছিল।

• গঠন: প্রতিটি vector একটি node. প্রতিটি node-এর জন্য এলোমেলোভাবে একটি সর্বোচ্চ স্তর বাছা হয় (উঁচু স্তরের সম্ভাবনা জ্যামিতিক হারে কমে), তাই স্তর ০-এ সবাই, ওপরে অল্প কয়েকজন। প্রতিটি স্তরে node তার কাছের কয়েকটির সঙ্গে যুক্ত। Graph-এর গঠন DSA কোর্সের পর্ব ৩৯-এ।
• M: প্রতি node-এ link-এর সংখ্যা (FAISS-এ স্তর ০-এ ২M). বেশি M মানে ভালো recall, কিন্তু বেশি মেমরি আর ধীর build. FAISS নির্দেশিকা: ৪ ≤ M ≤ ৬৪, আর মেমরি প্রতি vector-এ (d × ৪ + M × ২ × ৪) byte.
• efConstruction: বানানোর সময় প্রতিটি নতুন node-এর প্রতিবেশী খুঁজতে কতটি প্রার্থী রাখা হয়। বড় হলে graph ভালো, build ধীর।
• efSearch: খোঁজার সময় স্তর ০-এ কতটি প্রার্থীর তালিকা রাখা হয় (k-এর সমান বা বেশি)। এটিই খোঁজার সময়ের মূল knob, আর index আবার না বানিয়েই বদলানো যায়।

ওপরের স্তরগুলোয় খোঁজা একেবারে লোভী: বর্তমান node-এর প্রতিবেশীদের মধ্যে প্রশ্নের সবচেয়ে কাছেরটিতে যাওয়া, যতক্ষণ কাছে যাওয়া যায়। তারপর এক স্তর নিচে, একই node থেকে শুরু। নিচের stepper-এ efSearch = ১ ধরে (শুধু একটি প্রার্থী) পুরো পথ।

HNSW-এর দুর্বলতাও জানা দরকার। সব vector আর link RAM-এ রাখতে হয়, তাই মেমরি Flat-এর চেয়েও বেশি। মোছা কঠিন: একটি node সরালে graph-এ ফাঁক তৈরি হয়, তাই অনেক ব্যবস্থা আগে “মোছা” চিহ্ন দেয়, পরে graph আবার গোছায়। আর build ধীর, যেটি §৬-এর run-এ মাপা হয়েছে।

৬ · সত্যিকারের run — ১ লাখ বাংলা অনুচ্ছেদে FAISS

খেলনা ডেটা থেকে এবার আসল বাংলা লেখায়। Corpus: Bangla Wikipedia-র ১,০০,০০০টি অনুচ্ছেদ (কীভাবে বাছা হলো, পাতার শুরুতে লেখা)। দুই রকম প্রশ্ন, প্রতিটি ১০০০টি: (ক) প্রবন্ধের শিরোনাম, “query: ” prefix-সহ, যেমন “বাগেরহাট রেলওয়ে স্টেশন” বা “হিমশৈল”; ছোট, আর অনুচ্ছেদের চেহারা থেকে আলাদা। (খ) corpus-এ নেই এমন প্রবন্ধের একটি করে অনুচ্ছেদ, “passage: ” prefix-সহ; ডেটার মতোই দেখতে, যেমন “এই লেখার মতো আরও লেখা দেখাও” ধরনের খোঁজায়। প্রতিটি index-এর recall@10 মাপা Flat-এর নির্ভুল উত্তরের বিপরীতে। সময় মাপা হয়েছে একটি একটি প্রশ্ন করে, এক thread-এ, অনলাইন সেবার মতো।

~/bazarghar-dl$ uv run python embed.py 100000     # সত্যিকারের run, CPU
articles read 71534, used 20807, passages 100000, queries 1000
mean passage chars 359.6
embed 100000 passages on CPU (3 threads): 2417 s, shape (100000, 384), float32, 153.6 MB
~/bazarghar-dl$ uv run python embed2.py
held-out passages 1000 (articles not in corpus), embed 27 s

শুধু embed করতেই CPU-তে ২৪১৭ সেকেন্ড, প্রায় ৪০ মিনিট; index বানানো তার তুলনায় সেকেন্ডের ব্যাপার। Model বদলালে এই খরচ আবার লাগবে (ভাবনার প্রশ্ন ৪)। Index বানানো আর মাপার মূল অংশ:

# মূল অংশ, ছোট করে (সত্যিকারের bench.py থেকে)
flat = faiss.IndexFlatIP(d); flat.add(X)            # নির্ভুল মাপকাঠি
ivf = faiss.IndexIVFFlat(faiss.IndexFlatIP(d), d, 1024, faiss.METRIC_INNER_PRODUCT)
ivf.train(X); ivf.add(X)                            # train = k-means, ১০২৪টি cell
ivf.nprobe = 16
pq = faiss.IndexIVFPQ(faiss.IndexFlatIP(d), d, 1024, 48, 8, faiss.METRIC_INNER_PRODUCT)
ref = faiss.IndexRefineFlat(pq); ref.k_factor = 10  # PQ-তে ১০০ প্রার্থী, আসল vector-এ re-rank
h = faiss.IndexHNSWFlat(d, 32, faiss.METRIC_INNER_PRODUCT)
h.add(X); h.hnsw.efSearch = 256                     # HNSW-এ train নেই
for i in range(len(Q)):                             # এক এক করে প্রশ্ন, faiss.omp_set_num_threads(1)
    I[i] = ix.search(Q[i:i+1], 10)[1][0]
mb = faiss.serialize_index(ix).nbytes / 1e6         # index-এর আকার

~/bazarghar-dl$ uv run python bench.py     # সত্যিকারের run, একবার
Python 3.12.13, numpy 2.5.4, faiss 1.15.1
X (100000, 384) float32 = 153.6 MB; queries: 1000 titles, 1000 held-out passages
Flat      exact        recall@10 title 1.000 passage 1.000 |  8.641 ms/q |  153.6 MB | hit@10 0.931
build IVFFlat nlist=1024: 4.0 s
IVFFlat   nprobe=1     recall@10 title 0.174 passage 0.360 |  0.048 ms/q |  156.0 MB | hit@10 0.241
IVFFlat   nprobe=4     recall@10 title 0.342 passage 0.619 |  0.065 ms/q |  156.0 MB | hit@10 0.399
IVFFlat   nprobe=16    recall@10 title 0.578 passage 0.833 |  0.212 ms/q |  156.0 MB | hit@10 0.573
IVFFlat   nprobe=64    recall@10 title 0.775 passage 0.951 |  0.642 ms/q |  156.0 MB | hit@10 0.711
IVFFlat   nprobe=256   recall@10 title 0.920 passage 0.994 |  2.377 ms/q |  156.0 MB | hit@10 0.834
build IVFPQ m=48 nbits=8 (+refine copy): 35.7 s
IVFPQ     nprobe=16    recall@10 title 0.292 passage 0.392 |  0.120 ms/q |    7.6 MB | hit@10 0.537
IVFPQ     nprobe=64    recall@10 title 0.335 passage 0.403 |  0.274 ms/q |    7.6 MB | hit@10 0.651
IVFPQ+ref np=64 kf=10  recall@10 title 0.650 passage 0.844 |  0.292 ms/q |  161.2 MB | hit@10 0.703
build HNSW M=16 efConstruction=40: 4.4 s
HNSW16    ef=16        recall@10 title 0.507 passage 0.676 |  0.076 ms/q |  168.0 MB | hit@10 0.487
HNSW16    ef=64        recall@10 title 0.734 passage 0.877 |  0.180 ms/q |  168.0 MB | hit@10 0.678
HNSW16    ef=256       recall@10 title 0.885 passage 0.965 |  0.597 ms/q |  168.0 MB | hit@10 0.797
HNSW16    ef=1024      recall@10 title 0.956 passage 0.987 |  2.899 ms/q |  168.0 MB | hit@10 0.872
build HNSW M=32 efConstruction=40: 7.4 s
HNSW32    ef=16        recall@10 title 0.658 passage 0.820 |  0.116 ms/q |  180.8 MB | hit@10 0.615
HNSW32    ef=64        recall@10 title 0.850 passage 0.952 |  0.295 ms/q |  180.8 MB | hit@10 0.772
HNSW32    ef=256       recall@10 title 0.949 passage 0.991 |  0.935 ms/q |  180.8 MB | hit@10 0.865
HNSW32    ef=1024      recall@10 title 0.985 passage 0.999 |  3.979 ms/q |  180.8 MB | hit@10 0.915

এবার সেই ফল (হুবহু, JSON হিসেবে পাতায় রাখা) দিয়ে সিদ্ধান্ত নিন: recall@10 ≥ ০.৯৫ লক্ষ্য হলে কোন সেটিং সবচেয়ে দ্রুত? দুই ধরনের প্রশ্নে আলাদা করে।

import json
import pandas as pd
import matplotlib.pyplot as plt
pd.set_option("display.width", 72)

df = pd.DataFrame(json.load(open("faiss_bench.json")))   # সত্যিকারের run-এর ফল, হুবহু
flat_ms = df.loc[df["index"] == "Flat", "ms"].iloc[0]
for col, name in [("r_title", "শিরোনাম-প্রশ্ন"), ("r_pass", "অনুচ্ছেদ-প্রশ্ন")]:
    ok = df[(df[col] >= 0.95) & (df["index"] != "Flat")].sort_values("ms")
    b = ok.iloc[0]
    print(f"{name}: recall@10 ≥ 0.95 মানে {len(ok)}টি সেটিং; সবচেয়ে দ্রুত "
          f"{b['index']} {b['setting']} ({b[col]}, {b['ms']} ms, Flat-এর {flat_ms / b['ms']:.0f} গুণ)")

print("\nhit@10 (শিরোনামের নিজের প্রবন্ধ top-10-এ), Flat-এর তুলনায়:")
t = df[df["index"].isin(["Flat", "HNSW32"])][["index", "setting", "r_title", "hit"]]
print(t.to_string(index=False))

fig, axes = plt.subplots(1, 2, figsize=(8, 3.6), sharey=True)
for ax, col, title in [(axes[0], "r_title", "short title queries"),
                       (axes[1], "r_pass", "passage-like queries")]:
    for name, g in df[df["index"] != "Flat"].groupby("index"):
        ax.plot(g["ms"], g[col], "o-", label=name, ms=4)
    ax.axhline(0.95, color="gray", ls="--", lw=1)
    ax.axvline(flat_ms, color="black", ls=":", lw=1)
    ax.set_xscale("log"); ax.set_title(title, fontsize=10)
    ax.set_xlabel("ms per query (1 thread)")
axes[0].set_ylabel("recall@10 vs exact")
axes[1].legend(fontsize=7, loc="lower right")
fig.subplots_adjust(wspace=0.08, bottom=0.17)
plt.show()

শিরোনাম-প্রশ্ন: recall@10 ≥ 0.95 মানে 2টি সেটিং; সবচেয়ে দ্রুত HNSW16 ef=1024 (0.956, 2.899 ms, Flat-এর 3 গুণ)
অনুচ্ছেদ-প্রশ্ন: recall@10 ≥ 0.95 মানে 7টি সেটিং; সবচেয়ে দ্রুত HNSW32 ef=64 (0.952, 0.295 ms, Flat-এর 29 গুণ)

hit@10 (শিরোনামের নিজের প্রবন্ধ top-10-এ), Flat-এর তুলনায়:
 index setting  r_title   hit
  Flat   exact    1.000 0.931
HNSW32   ef=16    0.658 0.615
HNSW32   ef=64    0.850 0.772
HNSW32  ef=256    0.949 0.865
HNSW32 ef=1024    0.985 0.915

৭ · Vector database — index-এর চারপাশে যা লাগে

FAISS একটি library: আপনার program-এর ভেতরে, RAM-এ index. Id আর মূল লেখার হিসাব আপনার; ফাইলে রাখতে faiss.write_index; নির্দিষ্ট id-এর মধ্যে খোঁজার ব্যবস্থা (IDSelector) আছে, কিন্তু কোন id কোন জেলার, তা আপনাকেই জানতে হয়। একটি দোকানের হিসাব খাতা যেমন, আর পুরো একটি ব্যাংক যেমন: খাতায় যোগ-বিয়োগ ঠিকই হয়, কিন্তু শাখা, ভল্ট, অডিট আর একাধিক কপি ব্যাংকের কাজ। Vector database index-এর চারপাশে এই কাজগুলো যোগ করে:

• Metadata আর ফিল্টার: প্রতিটি vector-এর পাশে payload (বিষয়, ভাষা, জেলা, অনুমতি), আর খোঁজার সাথেই শর্ত (metadata filtering; pre-filtering আর post-filtering-এর পার্থক্য DBMS কোর্সের পর্ব ৬০-এ)।
• যোগ, হালনাগাদ, মোছা: id ধরে upsert আর delete, index আবার না বানিয়ে।
• Disk-এ থাকা আর recovery: program বন্ধ হলেও ডেটা থাকে, crash-এর পর ফেরে।
• ছড়ানো: বড় ডেটা কয়েকটি সার্ভারে ভাগ (sharding) আর কপি (replication), সিস্টেম ডিজাইন কোর্সের পর্ব ২২-এর মতো।

লেখার সময়ে (নভেম্বর ২০২৬) প্রচলিত কয়েকটি নাম, প্রতিটির নিজের নথি থেকে; পরিবর্তন হতে পারে, আর এটি কোনো র‍্যাংকিং নয়। Qdrant, Chroma, Milvus, Weaviate open-source vector database. pgvector PostgreSQL-এর extension; নথিতে HNSW আর IVFFlat index, আর লেখা আছে যে approximate index-এ ফিল্টার index scan-এর পরে বসে, ০.৮.০ থেকে iterative index scan চালু করা যায়। Elasticsearch আর OpenSearch search engine, যাদের নথিতে vector field-এ approximate kNN খোঁজা আছে। sqlite-vec SQLite-এর ছোট extension, নিজের README অনুযায়ী এখনও v1-এর আগের, তাই বড় বদল প্রত্যাশিত।

হাতে-কলমে দেখতে বাজারঘরের ২০টি হাতে লেখা help নথি (এই পর্বের জন্য বানানো; বাংলা, ইংরেজি আর বাংলিশ মেশানো) Qdrant-এর Python client-এর local mode-এ রাখা হলো। README অনুযায়ী local mode server ছাড়াই একই API চালায়, path দিলে disk-এ রাখে, আর এটি উন্নয়ন, prototype আর পরীক্ষার জন্য; বড় মাপে server mode-এ যেতে বলে। একই e5-small model, প্রশ্নে “query: ”, নথিতে “passage: ”।

# মূল অংশ, ছোট করে (সত্যিকারের vdb_demo.py থেকে)
db = QdrantClient(path="qdrant_db")                  # local mode, disk-এ
db.create_collection("help", vectors_config=models.VectorParams(
    size=384, distance=models.Distance.COSINE))
db.upsert("help", points=[models.PointStruct(id=d["id"], vector=v,
    payload={"topic": d["topic"], "lang": d["lang"], "text": d["text"]})
    for d, v in zip(docs, V)])
hits = db.query_points("help", query=q, limit=3)
f = models.Filter(must=[models.FieldCondition(key="topic",
    match=models.MatchValue(value="payment"))])
hits = db.query_points("help", query=q, query_filter=f, limit=3)
db.delete("help", points_selector=models.PointIdsList(points=[8]))
db.upsert("help", points=[models.PointStruct(id=21, vector=v_new, payload={...})])

~/bazarghar-dl$ uv run python vdb_demo.py create     # সত্যিকারের run
qdrant-client 1.20.0 | docs 40
points: 40
Q: ঢাকায় ডেলিভারি চার্জ কত?  (ফিল্টার নেই)
  bh04 0.920 active   ডেলিভারি চার্জ: ঢাকা সিটি
  bh28 0.918 active   বড় পণ্যের ডেলিভারি
  bh40 0.910 archived ডেলিভারি চার্জ: ঢাকা সিটি (পুরনো)
একই প্রশ্ন, status = active আর category = delivery
  bh04 0.920 active   ডেলিভারি চার্জ: ঢাকা সিটি
  bh28 0.918 active   বড় পণ্যের ডেলিভারি
  bh06 0.910 active   ডেলিভারি চার্জ: অন্যান্য জেলা
bh40 মোছার পর points: 39
~/bazarghar-dl$ uv run python vdb_demo.py reopen     # নতুন process, একই disk ফোল্ডার
disk থেকে আবার খোলা, points: 39
Q: ঢাকায় ডেলিভারি চার্জ কত?  (ফিল্টার নেই)
  bh04 0.920 active   ডেলিভারি চার্জ: ঢাকা সিটি
  bh28 0.918 active   বড় পণ্যের ডেলিভারি
  bh06 0.910 active   ডেলিভারি চার্জ: অন্যান্য জেলা

৮ · কোনটি কখন — একটি সিদ্ধান্তের পথ

কোনো একটি index সব কাজে সেরা নয়। নিচের প্রশ্নগুলো ক্রমে জিজ্ঞেস করুন। সংখ্যাগুলো শুরুর নিয়ম, আইন নয়; শেষ কথা নিজের ডেটায় মাপা recall আর সময়।

1. N কত? কয়েক হাজার থেকে কয়েক লাখ, আর প্রশ্ন কম: Flat (NumPy বা IndexFlatIP). নির্ভুল, train নেই, যোগ-মোছা সহজ।
2. সব vector float32-এ RAM-এ আঁটে, আর কম latency চাই? HNSW. মেমরি প্রতি vector-এ d × ৪ + M × ৮ byte, build ধীর, মোছা ঝামেলার।
3. আঁটে না, বা খরচ কমাতে চান? IVFPQ (প্রয়োজনে re-ranking-সহ), বা float16/int8-এর মতো scalar quantization. nlist ≈ ৪√N থেকে ১৬√N.
4. ডেটা ঘন ঘন বদলায়, ফিল্টার লাগে, একাধিক সার্ভার? শুধু library নয়, একটি vector database বা আপনার চেনা database-এর vector সুবিধা (§৭)।

৯ · AI-এর যুগে — vector search-এর কোড আর দাবি যাচাই

FAISS বা vector database-এর কোড AI assistant কয়েক সেকেন্ডে লিখে দেয়। কোডটি চলবে, ফলও দেবে; ভুল হলে সাধারণত নীরবে কম recall বা ভুল মেট্রিক।

AI-এর লেখা vector index কোডের চেকলিস্ট

• Metric আর normalisation মিলিয়েছি (cosine হলে normalise + inner product)
• শুরুর আগে N × d × 4-এর মেমরি হিসাব করেছি
• Flat-এর বিপরীতে recall@k মেপেছি, আলাদা প্রশ্নে
• nprobe বা efSearch-এর কয়েকটি মানে sweep করে বেছেছি
• Model-এর নাম, version আর prefix index-এর সঙ্গে লেখা আছে
• Library-র method নিজের version-এর নথিতে মিলিয়েছি