HNSW: איך חיפוש וקטורי מתפקד בקנה מידה של מיליוני embeddings

מאת צוות מדיה דיל · 27.06.2026 · טכנולוגיה · 5 דק׳

Approximate Nearest Neighbor מול Brute Force k-NN, גרף רב-שכבתי, פרמטרי ef_construction ו-ef_search, pgvector, Pinecone, Weaviate ו-Qdrant.

למצוא את עשרת הווקטורים הכי דומים לשאילתה מתוך אוסף של מיליון embeddings בעזרת brute force — לחשב מרחק בין השאילתה לכל וקטור בודד ולמיין — עובד מצוין על אלף וקטורים ומתפרק לגמרי על עשרות מיליונים, כי הזמן גדל ליניארית עם גודל האוסף וכל בקשת חיפוש הופכת לסריקה מלאה. Approximate Nearest Neighbor מוותר במכוון על דיוק מוחלט תמורת מהירות שכמעט לא תלויה בגודל האוסף, ו-HNSW הוא האלגוריתם שהפך לתקן דה-פקטו לבעיה הזו. הוא ניצב היום מאחורי כמעט כל מנוע חיפוש סמנטי, מ-RAG פשוט ועד מערכות המלצה בקנה מידה תעשייתי.

Brute Force ולמה הוא לא סקיילי

חיפוש מדויק (exact k-NN) מבטיח למצוא בדיוק את השכנים הקרובים ביותר, אבל המחיר הוא סריקה של כל וקטור באוסף בכל שאילתה — סיבוכיות O(n). על מיליון וקטורים בממד 768 זה כבר עשרות עד מאות מילישניות לשאילתה בודדת, ועל מאה מיליון וקטורים זה הופך ללא שמיש בזמן אמת, גם עם חומרה חזקה ומקבול מלא. ברוב האפליקציות בפועל — המלצות, חיפוש סמנטי, RAG — התוצאה ה-99.5% הכי קרובה טובה באותה מידה כמו התוצאה המדויקת ב-100%, כך שהוויתור על דיוק מוחלט הוא עסקה משתלמת, במיוחד כשההבדל בפועל בין exact ל-approximate מסתכם בכמה מקומות בדירוג שמשתמש קצה כמעט אף פעם לא ישים לב אליהם.

איך HNSW בנוי: גרף רב-שכבתי

Hierarchical Navigable Small World בונה גרף שבו כל וקטור הוא צומת, מחובר לשכנים הקרובים לו יחסית. המבנה מאורגן בשכבות: השכבה העליונה דלילה עם קפיצות ארוכות בין אזורים רחוקים באוסף, ושכבות נמוכות יותר צפופות יותר עד לשכבה התחתונה שמכילה את כל הווקטורים עם קשרים מקומיים בלבד — דומה במבנה לרעיון של skip list. חיפוש מתחיל מלמעלה, קופץ מהר בין אזורים רחוקים, ויורד שכבה-שכבה תוך צמצום הדרגתי של המרחק לתוצאה, במקום לבדוק כל צומת בגרף. כל שכבה למעשה מסננת את מרחב החיפוש עוד לפני שמגיעים לשכבה התחתונה, כך שמספר הצמתים שבאמת נבדקים בכל שאילתה קטן משמעותית ממספר הווקטורים הכולל באוסף.

Trade-off בין דיוק למהירות

שני פרמטרים עיקריים שולטים על האיזון: ef_construction קובע כמה מועמדים נבדקים בזמן בניית הגרף (יותר — גרף איכותי יותר אבל בנייה איטית יותר), ו-ef_search קובע כמה מועמדים נבדקים בזמן חיפוש (יותר — recall גבוה יותר אבל שאילתה איטית יותר). אין ערך "נכון" קבוע — אפליקציה שמוכנה להקריב עשרות מילישניות נוספות לתמורת recall של 99% במקום 95% פשוט מעלה את ef_search, בלי לבנות מחדש את האינדקס כולו.

שימוש בפועל: pgvector ומנועים ייעודיים

pgvector, ההרחבה של חיפוש וקטורי ב-Postgres, תומכת ב-HNSW כאחת מאפשרויות האינדוקס לצד IVFFlat, ומאפשרת לשלב חיפוש סמנטי בתוך אותו מסד נתונים טרנזקציוני בלי מערכת נפרדת. מנועים ייעודיים כמו Pinecone, Weaviate או Qdrant לוקחים את אותו אלגוריתם ומוסיפים לו תשתית מבוזרת — sharding אוטומטי, replication, וניהול memory מותאם לגרפי HNSW ענקיים שלא נכנסים במכונה בודדת.

מגבלות: זיכרון ועדכונים

גרף HNSW חי כולו בזיכרון לביצועים טובים, כך שאוסף של מאות מיליוני וקטורים בממד גבוה דורש RAM משמעותי — זה לרוב הגורם המגביל בפועל, לא זמן החישוב. מחיקת וקטור מהגרף גם בעייתית יותר מהוספה, כי היא עלולה לשבור קשרים שצמתים אחרים תלויים בהם, ולכן מימושים רבים מסמנים וקטור כ"נמחק" ומנקים אותו רק בבנייה מחדש תקופתית של האינדקס במקום מחיקה מיידית.

בונים מערכת חיפוש סמנטי שצריכה לסקייל למיליוני וקטורים? נשמח לעזור לכם בוואטסאפ.

תגיות: HNSW · Vector Search · Approximate Nearest Neighbor · pgvector · Embeddings · ANN

← חזרה לבלוג · צור קשר