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


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

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

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

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

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

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

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 משווה שורות בין שני טבלאות. אם הטבלאות גדולות, הוא עובר על אינדקס; אם אין אינדקס, הוא מבצע סריקה מלאה. עם מיליארד רשומות, התהליך הזה לוקח שניות עד עשרות שניות.

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

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

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


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

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

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

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

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

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

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


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

SIDX (Semantically-Aligned Index) הוא מחקר שמטרתו לבנות מזהה כזה. בדקדוק של GEUL כבר יש מקום ל-Reference שמצביע על יעד באמצעות SIDX (GEUL-SIDX). אבל הרוחב ושיטת ההקצאה טרם הוכרעו. הם ייקבעו לפי סטטיסטיקות שימוש מצטברות. להלן, לשם ההסבר, נשתמש ב-64 ביטים כדוגמה.

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

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

הביטים הבאים נושאים מידע סיווגי. אם זה אדם — מאיזו תקופה? מאיזה אזור?

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

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

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

הסיווג היסודי ביותר בראש, ההבחנות הדקות ביותר בתחתית.

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


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

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

נניח שיש מיליארד ישויות, לכל אחת SIDX בן 64 ביטים. נפח כולל: מיליארד × 8 בתים = 8GB.

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

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

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. המגבלה אינה החישוב אלא רוחב הפס של הזיכרון. במדידה מקדימה עבור SILK, סריקה במסכה של 100 מיליון חתימות בנות 128 ביטים (1.6GB) ארכה כ-27 אלפיות שנייה ב-8 תהליכוני Go. באותו קצב, מיליארד SIDX בני 64 ביטים (8GB) ייקחו מעט יותר מ-0.1 שנייה.

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

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


כמה רחב הוא צריך להיות?

בהתחלה חשבתי שנדרש מרחב גדול יותר.

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

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

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

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

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

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

אבל זו עדיין השערה. GEUL אינה קובעת את הרוחב ליד שולחן כתיבה. בין מועמדים כמו 4 WORD (64 ביטים) ו-16 WORD, ההכרעה תהיה לפי סטטיסטיקות שימוש אמיתיות. עד אז מצביעים על יעדים במזהים שניתנים לפי הסדר, ולאחר הקצאת SIDX מקשרים את שני המזהים כאותו יעד.


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

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

כיוון שביטים של 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. ישויות שדפוסי הביטים שלהן הדומים ביותר עולות כמועמדות. יי סון-סין, וון גיון, גוון יול, יי אוק-גי…

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

חיפוש וקישור ישויות (entity linking) יכולים להפוך למנגנון אחד. בלי מנוע חיפוש נפרד, בלי צנרת NER (זיהוי ישויות בעלות שם) נפרדת, בהשוואת SIDX אחת.


למה לא B-Tree?

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

B-Tree מצטיין במציאת ערך מסוים בנתונים ממוינים ב-O(log n). עבור “מצא את Q50184” הוא אופטימלי.

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

סריקה מלאה של SIDX + SIMD היא גישה אחרת.

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

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

סוג שאילתהB-Treeסריקת SIDX
חיפוש לפי מזהה מסויםO(log n), אופטימלימיותר (נפתר בגיבוב)
סינון בתנאים מורכביםדורש JOIN, איטיAND ביטי אחד, מהיר
חיפוש ישויות דומותבלתי אפשריאפשרי לפי דמיון ביטים
הכנסהO(log n), איזון מחדשO(1), הוספה
מורכבות מימושגבוההנמוכה

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

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


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

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

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

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

הקצאת Codec בדקדוק של GEUL הולכת לפי אותו עיקרון. פורמטים ששכיחותם אושרה מקבלים קוד ישיר קצר בתוך ה-TAG WORD, ופורמטים נדירים עוברים לפורמטי Issuer עם TAG הרחבה.

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


סיכום

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

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

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