חיפוש שכנים קרובים משוערים (ANN) והטמעות של וקטורים לשאילתות

בדף הזה מוסבר איך למצוא את השכנים הקרובים ביותר (ANN) ולשאול הטמעות וקטורים באמצעות פונקציות המרחק של ANN.

כשיש קבוצת נתונים קטנה, אפשר להשתמש ב-K-nearest neighbors (KNN)‎ כדי למצוא את הווקטורים המדויקים של k-nearest. עם זאת, ככל שמערך הנתונים גדל, כך גם זמן האחזור והעלות של חיפוש KNN גדלים. אתם יכולים להשתמש ב-ANN כדי למצוא את k השכנים הקרובים ביותר בקירוב, עם זמן אחזור ועלות נמוכים משמעותית.

בחיפוש ANN, הווקטורים שמוחזרים על ידי k הם לא השכנים הקרובים ביותר האמיתיים של k, כי בחיפוש ANN מחושבים מרחקים משוערים, ויכול להיות שלא כל הווקטורים במערך הנתונים נבדקים. מדי פעם מוחזרים כמה וקטורים שלא נמצאים בין k השכנים הקרובים ביותר. המצב הזה נקרא אובדן שליפה. המידה שבה אובדן ה-recall מקובל עליכם תלויה בתרחיש לדוגמה, אבל ברוב המקרים, אובדן קטן של recall בתמורה לשיפור בביצועים של מסד הנתונים הוא פשרה מקובלת.

למידע נוסף על הפונקציות של מרחק משוער שנתמכות ב-Spanner, עיינו בדפי העזר הבאים של ניב מסד הנתונים:

הטמעות וקטורים של שאילתות

כדי להאיץ חיפושים וקטוריים של השכן הקרוב ביותר (ANN), ב-Spanner משתמשים באינדקס וקטורי. אתם יכולים להשתמש באינדקס וקטורי כדי לשלוח שאילתות להטמעות וקטורים. כדי לשלוח שאילתות להטמעות וקטורים, קודם צריך ליצור אינדקס וקטורים. לאחר מכן, אפשר להשתמש בכל אחת משלוש הפונקציות של המרחק המשוער כדי למצוא את ה-ANN.

אלה ההגבלות שחלות כשמשתמשים בפונקציות של מרחק משוער:

  • פונקציית המרחק המשוער צריכה לחשב את המרחק בין עמודת הטמעה לבין ביטוי קבוע (לדוגמה, פרמטר או ליטרל).
  • צריך להשתמש בפלט של פונקציית המרחק המשוער בסעיף ORDER BY כמפתח המיון היחיד, ולציין LIMIT אחרי ה-ORDER BY.
  • השאילתה חייבת לסנן באופן מפורש שורות שלא נוספו לאינדקס. ברוב המקרים, זה אומר שהשאילתה צריכה לכלול משפט WHERE <column_name> IS NOT NULL שתואם להגדרה של אינדקס הווקטור, אלא אם העמודה כבר מסומנת כ-NOT NULL בהגדרת הטבלה.

רשימה מפורטת של המגבלות מופיעה בדף העזר בנושא פונקציית המרחק המשוער.

דוגמאות

נניח שיש טבלה ב-Documents עם עמודה DocEmbedding של הטמעות טקסט שחושבו מראש מהעמודה DocContents של הבייטים, ועמודה NullableDocEmbedding שמאוכלסת ממקורות אחרים ויכולה להיות null. בשתי עמודות ההטמעה מצוין וקטור באורך 3, שנדרש כדי ליצור אינדקס וקטורי לחיפוש ANN.

GoogleSQL 

CREATE TABLE Documents (
  UserId       INT64 NOT NULL,
  DocId        INT64 NOT NULL,
  Author       STRING(1024),
  DocContents  BYTES(MAX),
  DocEmbedding ARRAY<FLOAT32>(vector_length=>3) NOT NULL,
  NullableDocEmbedding ARRAY<FLOAT32>(vector_length=>3),
  WordCount    INT64
) PRIMARY KEY (UserId, DocId);

PostgreSQL 

CREATE TABLE documents (
  user_id      bigint not null,
  doc_id       bigint not null,
  author       varchar(1024),
  doc_contents bytea,
  doc_embedding float4[] VECTOR LENGTH 3 not null,
  nullable_doc_embedding float4[] VECTOR LENGTH 3,
  word_count   bigint,
  PRIMARY KEY (user_id, doc_id)
);

כדי לחפש את 100 הווקטורים הקרובים ביותר ל-[1.0, 2.0, 3.0], מציינים את אחת מאפשרויות החיפוש הבאות בפונקציית המרחק המשוער:

  • ‫num_leaves_to_search: מספר העלים לחיפוש. הערך חייב להיות מספר שלם חיובי.
  • ‫pct_leaves_to_search: אחוז העלים לחיפוש. הערך חייב להיות מספר מסוג double בין 0.0 ל-100.0 עם נקודה עשרונית מפורשת (לדוגמה, 10.0). יכול להיות שאינדקסים של וקטורים שנוצרו לפני נובמבר 2025 לא יתמכו באפשרות החיפוש הזו.

אי אפשר לציין את שתי האפשרויות באותה פונקציה של מרחק משוער.

אפשרות 1. שימוש באפשרות החיפוש num_leaves_to_search

GoogleSQL 

SELECT DocId
FROM Documents
WHERE WordCount > 1000
ORDER BY APPROX_EUCLIDEAN_DISTANCE(
  ARRAY<FLOAT32>[1.0, 2.0, 3.0], DocEmbedding,
  options => JSON '{"num_leaves_to_search": 10}')
LIMIT 100

PostgreSQL 

SELECT doc_id
FROM documents
WHERE word_count > 1000
ORDER BY spanner.approx_euclidean_distance(
  ARRAY[1.0, 2.0, 3.0]::float4[], doc_embedding,
  options=>jsonb'{"num_leaves_to_search": 10}'
)
LIMIT 100;

אפשרות 2. שימוש באפשרות החיפוש pct_leaves_to_search

GoogleSQL 

SELECT DocId
FROM Documents
WHERE WordCount > 1000
ORDER BY APPROX_EUCLIDEAN_DISTANCE(
  ARRAY<FLOAT32>[1.0, 2.0, 3.0], DocEmbedding,
  options => JSON '{"pct_leaves_to_search": 10.0}')
LIMIT 100

PostgreSQL 

SELECT doc_id
FROM documents
WHERE word_count > 1000
ORDER BY spanner.approx_euclidean_distance(
  ARRAY[1.0, 2.0, 3.0]::float4[], doc_embedding,
  options=>jsonb'{"pct_leaves_to_search": 10.0}'
)
LIMIT 100;

כדי לחפש את 100 הווקטורים הקרובים ביותר להטמעה שנוצרה על ידי ביטוי SQL, משתמשים בתבנית הבאה. בדוגמה הזו, השאילתה מוצאת את המסמכים שהכי דומים להטמעה של UserId = 1 ו-DocId = 1:

GoogleSQL 

WITH emb AS (
  SELECT DocEmbedding AS value
  FROM Documents
  WHERE UserId = 1 AND DocId = 1
  LIMIT 1
)
SELECT DocId
FROM Documents, emb
ORDER BY APPROX_EUCLIDEAN_DISTANCE(
  emb.value, DocEmbedding,
  options => JSON '{"num_leaves_to_search": 10}')
LIMIT 100

PostgreSQL 

SELECT documents.doc_id
FROM
  documents,
  (
    SELECT doc_embedding AS value
    FROM documents
    WHERE user_id = 1 AND doc_id = 1
    LIMIT 1
  ) vector
WHERE documents.doc_embedding IS NOT NULL
ORDER BY spanner.APPROX_EUCLIDEAN_DISTANCE(documents.doc_embedding,
         vector.value, options=>'{"num_leaves_to_search": 10}'::jsonb)
LIMIT 100

אם עמודת ההטמעה יכולה להכיל ערכי null:

GoogleSQL 

SELECT DocId
FROM Documents
WHERE NullableDocEmbedding IS NOT NULL AND WordCount > 1000
ORDER BY APPROX_EUCLIDEAN_DISTANCE(
  ARRAY<FLOAT32>[1.0, 2.0, 3.0], NullableDocEmbedding,
  options => JSON '{"num_leaves_to_search": 10}')
LIMIT 100

PostgreSQL 

SELECT doc_id
FROM documents
WHERE nullable_doc_embedding IS NOT NULL AND word_count > 1000
ORDER BY spanner.approx_euclidean_distance(
  ARRAY[1.0, 2.0, 3.0]::float4[], nullable_doc_embedding,
  options=>jsonb'{"num_leaves_to_search": 10}'
)
LIMIT 100;

הוספת המרחק לתוצאות השאילתה

בדוגמאות הקודמות, המרחק של ה-ANN משמש לסידור תוצאות השאילתה, אבל לא מוצג בתוצאות האלה. כדי להוסיף את המרחק לתוצאות, צריך להציב את פונקציית המרחק בסעיף SELECT ולתת לה שם סודי, ואז להשתמש בשם הסודי הזה כמפתח המיון היחיד בסעיף ORDER BY.

דוגמאות

GoogleSQL 

SELECT DocId,
  APPROX_EUCLIDEAN_DISTANCE(
    ARRAY<FLOAT32>[1.0, 2.0, 3.0], NullableDocEmbedding,
    options => JSON '{"num_leaves_to_search": 10}') AS distance
FROM Documents
WHERE NullableDocEmbedding IS NOT NULL AND WordCount > 1000
ORDER BY distance
LIMIT 100

PostgreSQL 

SELECT doc_id,
  spanner.approx_euclidean_distance(
    ARRAY[1.0, 2.0, 3.0]::float4[], nullable_doc_embedding,
    options=>jsonb'{"num_leaves_to_search": 10}'
  ) AS distance
FROM documents
WHERE nullable_doc_embedding IS NOT NULL AND word_count > 1000
ORDER BY distance
LIMIT 100;

המאמרים הבאים