למה אינדקס מיושר-סמנטית?

מה קורה כשמזהה הוא ידע, לא כתובת

כתובת לא יודעת כלום

כדי למצוא את Yi Sun-sin במסד נתונים, אתה צריך מזהה.

ב-Wikidata, המזהה של Yi Sun-sin הוא Q8492.

המספר הזה מצביע על Yi Sun-sin. אבל המחרוזת Q8492 עצמה לא יודעת כלום.

היא לא יודעת אם מדובר באדם או בבניין. היא לא יודעת אם מדובר בקוריאני או באזרח צרפתי. היא לא יודעת אם זו דמות מהמאה ה-16 או מהמאה ה-21. היא לא יודעת אם הוא חי או מת.

Q8492 היא כתובת. דוור שמחלק דואר אין לו מושג מה כתוב בתוך המעטפה. הוא פשוט מסתכל על הכתובת שעל המעטפה ומוסר.

UUID זהה. 550e8400-e29b-41d4-a716-446655440000. 128 ביט של מספרים אקראיים. ייחודי רק כדי למנוע התנגשויות – הוא לא אומר לך כלום על מה שהוא מתייחס אליו.

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

צריך לעקוב כדי לדעת

למה זו בעיה?

נניח שאתה רוצה למצוא “פילוסוף גבר בעל אזרחות גרמנית שנולד במאה ה-19.”

במסד נתונים מסורתי, כך זה עובד:

1. Filter persons table where gender = 'male'
2. JOIN with nationalities table and filter country = 'Germany'
3. JOIN with birth_dates table and filter year BETWEEN 1800 AND 1899
4. JOIN with occupations table and filter occupation = 'philosopher'

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

למה זה כל כך מורכב?

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

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

מה אם המזהה כבר ידע?

נהפוך את ההנחה.

מה אם המזהה עצמו הכיל את המידע החיוני?

מה אם, פשוט על ידי הסתכלות על המזהה, יכולת לדעת אם הוא מתייחס לאדם, מאיזו מדינה הוא, לאיזו תקופה הוא שייך, ואיך הוא מסווג?

כדי למצוא “פילוסוף גרמני גבר מהמאה ה-19,” JOIN-ים הופכים למיותרים.

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

זהו הרעיון המרכזי של אינדקס מיושר-סמנטית.

יישור משמעות לתוך המזהה

SIDX (Semantically-Aligned Index) הוא מזהה בן 64 ביט.

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

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

הביטים הבאים מכילים מידע סיווגי. אם זה אדם, איזו תקופה? איזה אזור?

הביטים התחתונים נושאים מידע ספציפי יותר ויותר.

העיקרון המרכזי הוא:

סדר הביטים הוא סדר חשיבות המידע.

הסיווג הבסיסי ביותר למעלה, ההבחנות הדקות ביותר למטה.

זהו לא מיון בלבד. זו פילוסופיית עיצוב.

ממיליארד לעשרת אלפים, במעבר אחד

הכוח המעשי של SIDX מתגלה במספרים.

WMS מכיל מיליארד ישויות. ה-SIDX של כל ישות הוא 64 ביט. גודל כולל: מיליארד x 8 בתים = 8 GB.

8 GB אלה נכנסים לזיכרון במלואם.

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

mask   = 0xFF00_0000_0000_0000  (upper 8 bits: type + region)
target = 0x8100_0000_0000_0000  (human + East Asia)

for each sidx in 1_billion:
    if (sidx & mask) == target:
        add to candidates

פעולה זו ניתנת למקבול עם SIMD. עם AVX-512, משווים 8 SIDX-ים בו-זמנית בפקודה אחת. סריקת מיליארד רשומות: כ-12 מילישניות.

על GPU? פחות ממילישנייה.

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

אפס JOIN-ים. אפס מעברים על עצי אינדקס. רק AND ביטי אחד.

למה 64 ביט מספיקים

בהתחלה, חשבתי שצריך מרחב גדול יותר.

32 בתים (256 ביט). וקטור FP16 בן 32 ממדים. ניסיתי לדחוס כל מאפיין מרכזי של ישות לתוך המזהה. אם הוא אדם, מגדר, אזרחות, תקופה, מקצוע, אזור, סטטוס חיים, נתיב סיווג…

אבל אז הבנתי משהו.

המזהה לא צריך לדעת הכל.

הוא רק צריך לצמצם מיליארד רשומות לעשרת אלפים. WMS מטפל בשאר.

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

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

ו-64 ביט = ארבע מילים בנות 16 ביט. הם זורמים באופן טבעי בתוך זרם. מזהה של 32 בתים היה מכביד על הזרם, אבל SIDX של 64 ביט קל ומהיר.

הידרדרות חיננית: משמעות שורדת גם כשביטים נקטעים

יתרון נוסף של יישור סמנטי הוא מאפייני ההידרדרות שלו.

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

Full 64 bits:  "Yi Sun-sin, 16th-century Joseon naval commander"
48 bits:       "16th-century Joseon military officer"
32 bits:       "16th-century East Asian human"
16 bits:       "Human"
8 bits:        "Physical entity"

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

זהו מימוש ברמת הביטים של עקרון “ההידרדרות החיננית.”

גם אם הפרעת רשת מעבירה רק נתונים חלקיים, המערכת יודעת “אני לא יודע בדיוק מי זה, אבל זה לפחות סיפור על אדם” ויכולה להמשיך להסיק.

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

שאילתה הופכת למזהה

האפשרות המסקרנת ביותר שאינדקס מיושר-סמנטית פותח היא זו: שאילתה בשפה טבעית ניתנת להמרה ל-SIDX זמני.

משתמש שואל: “מי היה הגנרל שהביס את הצי היפני במלחמת אימג’ין?”

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

SIDX זמני זה סורק את מיליארד ה-SIDX-ים ב-WMS. ישויות שדפוסי הביטים שלהן הכי דומים עולות כמועמדות. Yi Sun-sin, Won Gyun, Gwon Yul, Yi Eok-gi…

הצלבת מידע מפורט מול מועמדים אלה מניבה את התשובה הסופית.

זה מאחד חיפוש וקישור ישויות למנגנון אחד. אין צורך במנוע חיפוש נפרד. אין צורך בצינור NER (Named Entity Recognition) נפרד. השוואת SIDX אחת היא כל מה שנדרש.

למה לא B-Tree?

מסדי נתונים מסורתיים משתמשים באינדקסי B-Tree.

B-Tree-ים מצטיינים במציאת ערך ספציפי בנתונים ממוינים ב-O(log n). ל"מצא Q8492," הם אופטימליים.

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

סריקה ממצה עם SIDX + SIMD נוקטת גישה שונה מהיסוד.

אם B-Tree הוא ספר טלפונים שעונה במהירות “מי גר בכתובת הזו,” סריקת SIDX היא פרופילינג שעונה במהירות “למי יש את המאפיינים האלה.”

אופי השאלה שונה, ולכן גם מבנה הנתונים האופטימלי שונה.

WMS לא משתמש ב-B-Tree-ים. הוא טוען מיליארד SIDX-ים לזיכרון ומבצע סריקה ממצה עם מסכות ביטים SIMD.

פשוט. כוח גס. מהיר.

חוכמתו של הפמן

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

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

ב-SIDX, מידע הסיווג הנדרש בתדירות הגבוהה ביותר תופס את הביטים העליונים, ופרטים שנדרשים לעתים נדירות תופסים את הביטים התחתונים.

אותו עיקרון שולט בקידומות סוגי הפקטות של שפה זו. Tiny Verb Edge בתדירות הגבוהה ביותר מקבל את הקידומת הקצרה ביותר. Event6 Edge בתדירות נמוכה מקבל קידומת ארוכה יותר.

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

סיכום

מזהה מסורתי הוא כתובת. כתובת לא יודעת כלום.

1. כשהמזהה לא נושא משמעות, צריך לעקוב אחריו לנתונים בכל פעם. זהו JOIN.
2. ארבעה JOIN-ים על פני מיליארד רשומות זה איטי.
3. SIDX מקודד משמעות ישירות לתוך המזהה דרך יישור סמנטי.
4. AND ביטי אחד מצמצם מיליארד רשומות לעשרת אלפים. אפס JOIN-ים.
5. 64 ביט מספיקים. המזהה לא צריך לדעת הכל – הוא רק צריך לצמצם את המועמדים.
6. כיוון שהמידע החשוב ביותר תופס את הביטים העליונים, המשמעות המרכזית שורדת גם כשביטים נקטעים.
7. המרת שאילתה בשפה טבעית ל-SIDX זמני הופכת חיפוש לפעולה וקטורית.

ברגע שמזהה מפסיק להיות כתובת והופך לידע, הכללים של מסד הנתונים משתנים.