مستوى المقال: محترف. يفترض إنك تعرف الـ embeddings والبحث الدلالي، وعايز تفهم إزاي قاعدة البيانات الشعاعية بتلاقي أقرب جار في ملايين المتجهات في أقل من مللي ثانية.
بحث المتجهات في الملايين: HNSW وأقرب جار
لو البحث الدلالي عندك بياخد 200 مللي ثانية على مليون متجه والـ CPU مش مشغول، المشكلة مش في السيرفر. المشكلة إنك بتقارن كل متجه بكل متجه في كل استعلام. الحل اسمه HNSW، وبينزّل الزمن ده لأقل من مللي ثانية بدقة قريبة من 99%.
المشكلة باختصار
خزّنت مليون مقال كـ embeddings، كل واحد متجه بطول 768 رقم. المستخدم بيبعت سؤال، بتحوّله لمتجه، وعايز أقرب 10 متجهات ليه. الطريقة المباشرة: احسب المسافة بين متجه السؤال وكل المليون. ده اسمه البحث الشامل (brute-force) وتعقيده O(n·d): مليون متجه × 768 بُعد = حوالي 768 مليون عملية ضرب وجمع لكل استعلام. على نواة واحدة ده بيتراوح بين 80 و150 مللي ثانية. اضربها في 500 مستخدم في الثانية، وهتحتاج أسطولًا من الخوادم لمهمة المفروض تخلص في لمح البصر.
الفكرة قبل العلم: البحث في ملعب
تخيّل إنك عايز تلاقي صاحبك في ملعب فيه 80 ألف متفرج. الطريقة الغبية إنك تبص في وش كل واحد لحد ما تلاقيه. الطريقة الذكية: تسأل حد "صاحبي في القطاع الشمالي" فتقفز للقطاع ده، وبعدين "في الصف العلوي" فتقرّب أكتر، وبعدين تمشي بين الكراسي القريبة بس. كل خطوة بتقصّ مساحة البحث لجزء صغير. انت بتضحّي بضمانة إنك أكيد هتلاقيه بأقصر مسار، مقابل إنك توصل أسرع بمراحل. ده بالظبط اللي بيعمله HNSW.
HNSW علميًا: رسم بياني متعدد الطبقات
اسمه الكامل Hierarchical Navigable Small World. هو رسم بياني (graph) كل عقدة فيه متجه، والحواف بتربط كل متجه بجيرانه الأقرب. الحيلة إنه متعدد الطبقات: الطبقة القاعدية (Layer 0) فيها كل المتجهات وكثيفة الروابط. كل طبقة أعلى فيها عينة أقل بكثير، بس بحواف أطول تقفز مسافات كبيرة في الفضاء.
البحث بيبدأ من نقطة دخول ثابتة في أعلى طبقة، وبيمشي ناحية العقدة الأقرب لمتجه السؤال باستخدام القفزات الطويلة. أول ما يعجز عن التقريب أكتر في الطبقة دي، بينزل طبقة تحت ويكرّر. النتيجة إن عدد العُقد اللي بيزورها بيتناسب مع لوغاريتم عدد المتجهات، مش مع العدد نفسه. يعني الفرق بين مليون خطوة و20 خطوة تقريبًا.
الكود: قِس الفرق بنفسك
مكتبة hnswlib بتنفّذ الخوارزمية دي بكفاءة. الكود ده يبني فهرسًا على 500 ألف متجه ويقارن زمن HNSW بالبحث الشامل:
import hnswlib, numpy as np, time
dim, n = 768, 500_000
data = np.random.rand(n, dim).astype(np.float32)
q = np.random.rand(dim).astype(np.float32)
# 1) البحث الشامل: أساس المقارنة
t = time.perf_counter()
dists = np.linalg.norm(data - q, axis=1)
brute_top = set(np.argsort(dists)[:10])
print(f"brute-force: {(time.perf_counter()-t)*1000:.1f} ms")
# 2) بناء فهرس HNSW مرة واحدة
index = hnswlib.Index(space='l2', dim=dim)
index.init_index(max_elements=n, ef_construction=200, M=16)
index.add_items(data) # يُبنى مرة، ثم يُعاد استخدامه
index.set_ef(100) # ef_search: يتحكم في الدقة مقابل السرعة
# 3) الاستعلام
t = time.perf_counter()
labels, _ = index.knn_query(q, k=10)
print(f"HNSW: {(time.perf_counter()-t)*1000:.3f} ms")
recall = len(brute_top & set(labels[0])) / 10
print(f"recall@10: {recall:.2f}")
على جهاز عادي بتطلع أرقام في حدود: البحث الشامل حوالي 110 مللي ثانية، وHNSW حوالي 0.6 مللي ثانية — أي أسرع بقرابة 180 ضعفًا — مع recall@10 ≈ 0.98. يعني 98% من أقرب 10 نتائج فعلية بترجع صح.
المعاملات الثلاثة اللي بتحكم كل حاجة
- M: عدد الحواف لكل عقدة. أكبر = دقة أعلى وذاكرة أكبر. القيمة 16 جيدة لأغلب الحالات، و32–64 للأبعاد العالية.
- ef_construction: جودة البناء. أكبر = فهرس أدق لكن بناء أبطأ. 200 نقطة انطلاق معقولة.
- ef_search: يُضبط وقت الاستعلام. ارفعه تكسب دقة وتخسر سرعة. هو الوحيد اللي تقدر تغيّره من غير إعادة بناء.
الـ trade-offs بصراحة
HNSW مش سحر ببلاش. الذاكرة هي الثمن الأكبر: مع d=768 وM=16، كل متجه بياخد تقريبًا 768×4 بايت للبيانات + حوالي 128 بايت للحواف ≈ 3.2 كيلوبايت. يعني مليون متجه ≈ 3.2 جيجابايت RAM، والفهرس لازم يقعد في الذاكرة كلها للأداء ده. الافتراض هنا إن عندك ذاكرة تكفي؛ لو مش متوفرة، فكّر في التكميم (مثل IVF+PQ في FAISS) اللي بيضغط المتجهات مقابل دقة أقل. كمان البناء مش رخيص: بناء فهرس على 500 ألف متجه بياخد دقائق، والحذف الفعلي مش مدعوم بسلاسة — بتعمل tombstone وتعيد البناء دوريًا.
متى لا تستخدم HNSW
لو عندك أقل من ~10 آلاف متجه، البحث الشامل هيخلص في أقل من مللي ثانية أصلًا، وHNSW هيزوّد تعقيدًا بلا فايدة. لو بياناتك بتتغير بسرعة (إضافة وحذف مستمر)، إدارة الفهرس هتوجعك. ولو الذاكرة عندك محدودة والدقة المطلقة مش شرط، فهرس مبني على القرص زي DiskANN أو IVF مضغوط أنسب. الافتراض اللي HNSW مبني عليه: بيانات شبه ثابتة، ذاكرة كافية، وحاجة لدقة عالية بزمن منخفض.
الخطوة التالية
لو بتستخدم PostgreSQL، فعّل امتداد pgvector وأنشئ فهرسًا واحدًا: CREATE INDEX ON items USING hnsw (embedding vector_l2_ops) WITH (m = 16, ef_construction = 200); ثم قِس EXPLAIN ANALYZE على استعلام قبل وبعد. لو الزمن نزل من مئات المللي ثانية لأجزاء منها، الفهرس شغّال. لو مفيش فرق، غالبًا الاستعلام مش بيستخدم الفهرس — تأكد إنك بتستخدم عامل المسافة نفسه (<->) في الـ ORDER BY.
المصادر
- Malkov, Y. & Yashunin, D. (2018). "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs". IEEE TPAMI — arXiv:1603.09320.
- hnswlib — التنفيذ المرجعي: github.com/nmslib/hnswlib
- FAISS — توثيق فِهارس Facebook AI: github.com/facebookresearch/faiss/wiki
- pgvector — توثيق فهرس HNSW في PostgreSQL: github.com/pgvector/pgvector
- ANN-Benchmarks — مقارنات دقة/سرعة موثّقة: ann-benchmarks.com