ביצוע אחזור יעיל של k התוצאות המובילות

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

יצירת אינדקסים של חיפושים להתאמות k המובילות

כדי להגדיר אינדקס חיפוש להתאמה של k התוצאות המובילות, משתמשים ב-ORDER BY כדי להזמין את אינדקס החיפוש לפי עמודה ספציפית. השאילתות צריכות לכלול פסקה ORDER BY שתואמת בדיוק לסדר המיון של אינדקס החיפוש (כולל כיוון עולה לעומת כיוון יורד) ופסקה LIMIT שמבקשת שהשאילתה תיפסק אחרי מציאת k שורות תואמות.

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

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

לדוגמה, נניח שיש טבלה עם הסכימה הבאה:

GoogleSQL 

CREATE TABLE Albums (
  AlbumId STRING(MAX) NOT NULL,
  RecordTimestamp INT64 NOT NULL,
  ReleaseTimestamp INT64 NOT NULL,
  ListenTimestamp INT64 NOT NULL,
  AlbumTitle STRING(MAX),
  AlbumTitle_Tokens TOKENLIST AS (TOKENIZE_FULLTEXT(AlbumTitle)) HIDDEN
) PRIMARY KEY(AlbumId);

CREATE SEARCH INDEX AlbumsRecordTimestampIndex
ON Albums(AlbumTitle_Tokens, SingerId_Tokens)
STORING (ListenTimestamp)
ORDER BY RecordTimestamp DESC

CREATE SEARCH INDEX AlbumsReleaseTimestampIndex
ON Albums(AlbumTitle_Tokens)
STORING (ListenTimestamp)
ORDER BY ReleaseTimestamp DESC

PostgreSQL 

CREATE TABLE albums (
  albumid character varying NOT NULL,
  recordtimestamp bigint NOT NULL,
  releasetimestamp bigint NOT NULL,
  listentimestamp bigint NOT NULL,
  albumtitle character varying,
  albumtitle_tokens spanner.tokenlist
      GENERATED ALWAYS AS (spanner.tokenize_fulltext(albumtitle)) VIRTUAL HIDDEN,
PRIMARY KEY(albumid));

CREATE SEARCH INDEX albumsrecordtimestampindex
ON Albums(albumtitle_tokens, singerid_tokens)
INCLUDE (listentimestamp)
ORDER BY recordtimestamp DESC

CREATE SEARCH INDEX albumsreleasetimestampindex
ON Albums(albumtitle_tokens)
INCLUDE (listentimestamp)
ORDER BY releasetimestamp DESC

חיפוש באינדקסים של שאילתות כדי למצוא את k ההתאמות המובילות

כמו שצוין קודם, השאילתות צריכות לכלול פסקה ORDER BY שתואמת בדיוק לסדר המיון של אינדקס החיפוש (כולל כיוון המיון – עולה או יורד) ופסקה LIMIT שמבקשת שהשאילתה תיפסק אחרי שהמערכת תמצא k שורות תואמות.

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

  • השאילתה הזו יעילה מאוד. הוא בוחר את האינדקס AlbumsRecordTimestampIndex. גם אם יש הרבה אלבומים עם המילה happy, השאילתה סורקת רק מספר קטן של שורות:

    GoogleSQL 

    SELECT AlbumId
FROM Albums
WHERE SEARCH(AlbumTitle_Tokens, 'happy')
ORDER BY RecordTimestamp DESC
LIMIT 10

    PostgreSQL 

    SELECT albumid
FROM albums
WHERE spanner.search(albumtitle_tokens, 'happy')
ORDER BY recordtimestamp DESC
LIMIT 10

  • אותה שאילתה, שמבקשת סדר מיון לפי ReleaseTimestamp בסדר יורד, משתמשת באינדקס AlbumsReleaseTimestampIndex והיא יעילה באותה מידה:

    GoogleSQL 

    SELECT AlbumId
FROM Albums
WHERE SEARCH(AlbumTitle_Tokens, 'happy')
ORDER BY ReleaseTimestamp DESC
LIMIT 10

    PostgreSQL 

    SELECT albumid
FROM albums
WHERE spanner.search(albumtitle_tokens, 'happy')
ORDER BY releasetimestamp DESC
LIMIT 10

  • שאילתה שמבקשת סדר מיון לפי ListenTimestamp לא מבצעת שאילתת top-k ביעילות. הפונקציה צריכה לאחזר את כל האלבומים התואמים, למיין אותם לפי ListenTimestamp, ולהחזיר את 10 האלבומים הראשונים. שאילתה כזו צורכת יותר משאבים אם יש מספר גדול של מסמכים שמכילים את המונח 'happy'.

    GoogleSQL 

    SELECT AlbumId
FROM Albums
WHERE SEARCH(AlbumTitle_Tokens, 'happy')
ORDER BY ListenTimestamp DESC
LIMIT 10

    PostgreSQL 

    SELECT albumid
FROM albums
WHERE spanner.search(albumtitle_tokens, 'happy')
ORDER BY listentimestamp DESC
LIMIT 10

  • באופן דומה, שאילתה לא תפעל ביעילות אם היא מבקשת שהתוצאות יסודרו לפי העמודה RecordTimestamp בסדר עולה. הוא סורק את כל השורות עם המילה happy, למרות שיש LIMIT.

    GoogleSQL 

    SELECT AlbumId
FROM Albums
WHERE SEARCH(AlbumTitle_Tokens, 'happy')
ORDER BY RecordTimestamp ASC
LIMIT 10

    PostgreSQL 

    SELECT albumid
FROM albums
WHERE spanner.search(albumtitle_tokens, 'happy')
ORDER BY recordtimestamp ASC
LIMIT 10

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