لماذا الفهرس المحاذي دلالياً؟

ماذا يحدث عندما يكون المعرّف معرفة، لا عنواناً

العنوان لا يعرف شيئاً

للعثور على يي سون شين في قاعدة بيانات، تحتاج إلى معرّف.

في Wikidata، معرّف يي سون شين هو Q8492.

هذا الرقم يشير إلى يي سون شين. لكن السلسلة Q8492 نفسها لا تعرف شيئاً.

لا تعرف ما إذا كان شخصاً أم مبنى. لا تعرف ما إذا كان كورياً أم مواطناً فرنسياً. لا تعرف ما إذا كان شخصية من القرن السادس عشر أم الحادي والعشرين. لا تعرف ما إذا كان حياً أم ميتاً.

Q8492 هو عنوان. ساعي البريد الذي يوصل الرسائل لا يعرف ما هو مكتوب داخل المغلف. إنه ببساطة ينظر إلى العنوان على المغلف ويوصّل.

UUID كذلك. 550e8400-e29b-41d4-a716-446655440000. 128 بت من الأرقام العشوائية. فريد فقط لتجنب التصادمات – لا يخبرك بشيء عما يشير إليه.

على مدى الخمسين سنة الماضية، عملت معرّفات قواعد البيانات بهذه الطريقة. المعرّف هو عنوان، ولمعرفة أي شيء، يجب أن تتبع ذلك العنوان وتقرأ البيانات.

يجب أن تتبعه لتعرف

لماذا هذه مشكلة؟

لنفترض أنك تريد العثور على “فيلسوف ذكر من جنسية ألمانية وُلد في القرن التاسع عشر.”

في قاعدة بيانات تقليدية، يعمل الأمر هكذا:

1. تصفية جدول الأشخاص حيث الجنس = 'ذكر'
2. JOIN مع جدول الجنسيات وتصفية الدولة = 'ألمانيا'
3. JOIN مع جدول تواريخ الميلاد وتصفية السنة بين 1800 و1899
4. JOIN مع جدول المهن وتصفية المهنة = 'فيلسوف'

أربع عمليات JOIN. كل JOIN تقارن الصفوف بين جدولين. إذا كانت الجداول كبيرة، تجتاز فهرساً؛ إذا لم يكن هناك فهرس، تقوم بمسح كامل. مع مليار سجل، تستغرق هذه العملية ثوانٍ إلى عشرات الثواني.

لماذا هي بهذا التعقيد؟

لأن المعرّف لا يعرف شيئاً. بالنظر إلى Q8492، لا يمكنك معرفة ما إذا كان ألمانياً أم كورياً، لذا يجب أن تذهب إلى جدول آخر لاسترجاع تلك المعلومة.

لكل سؤال، يجب أن تتبع ما يشير إليه المعرّف. هذه هي التكلفة التي ظلت قواعد البيانات تدفعها لخمسين سنة.

ماذا لو كان المعرّف يعرف مسبقاً؟

لنقلب الفرضية.

ماذا لو كان المعرّف نفسه يحتوي على المعلومات الأساسية؟

ماذا لو أمكنك، بمجرد النظر إلى المعرّف، أن تعرف ما إذا كان يشير إلى إنسان، ومن أي بلد، ومن أي حقبة، وكيف يُصنَّف؟

للعثور على “فيلسوف ألماني ذكر من القرن التاسع عشر”، تصبح عمليات JOIN غير ضرورية.

بمسح مليار معرّف، يمكنك تحديد ما إذا كان كل منها مطابقاً فوراً بفحص بتاته.

هذه هي الفكرة الجوهرية وراء الفهرس المحاذي دلالياً.

محاذاة المعنى في المعرّف

SIDX (الفهرس المحاذي دلالياً) هو معرّف من 64 بت.

هذه الـ 64 بت ليست أرقاماً عشوائية. يُخصَّص معنى لموضع كل بت.

البتات العليا تحمل أهم المعلومات. ما نوع هذا الكيان؟ شخص، مكان، حدث، مفهوم؟

البتات التالية تحمل معلومات التصنيف. إذا كان شخصاً، من أي حقبة؟ من أي منطقة؟

البتات السفلية تحمل معلومات أكثر تحديداً بالتدريج.

المبدأ الأساسي هو:

ترتيب البتات هو ترتيب أهمية المعلومات.

أهم تصنيف في الأعلى، أدق التمييزات في الأسفل.

هذا ليس مجرد ترتيب. هذه فلسفة تصميم.

من مليار إلى عشرة آلاف، في مرور واحد

القوة العملية لـ SIDX تظهر في الأرقام.

WMS يحتوي على مليار كيان. SIDX لكل كيان هو 64 بت. الحجم الكلي: 1 مليار × 8 بايت = 8 غيغابايت.

هذه الـ 8 غيغابايت تسع بالكامل في الذاكرة.

تريد العثور على “كيانات من نوع إنسان وأصلها من شرق آسيا.” البتات العليا تحتوي على علامة “إنسان” ورمز “شرق آسيا”، لذا يمكنك التصفية بقناع بتات واحد.

mask   = 0xFF00_0000_0000_0000  (البتات العليا 8: النوع + المنطقة)
target = 0x8100_0000_0000_0000  (إنسان + شرق آسيا)

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

هذه العملية تتوازى مع SIMD. مع AVX-512، تقارن 8 معرّفات SIDX في آن واحد بتعليمة واحدة. مسح مليار إدخال: تقريباً 12 مللي ثانية.

على GPU؟ أقل من 1 مللي ثانية.

مليار سجل تضيّقت إلى عشرة آلاف. تصفية العشرة آلاف المتبقية بالتفصيل فورية.

صفر JOIN. صفر اجتياز شجرة فهرس. مجرد عملية AND بتية واحدة.

لماذا 64 بت كافية

في البداية، ظننت أن فضاءً أكبر مطلوب.

32 بايت (256 بت). متجه FP16 من 32 بُعداً. حاولت حشر كل سمة أساسية لكيان في المعرّف. هل هو إنسان، جنسه، جنسيته، حقبته، مهنته، منطقته، حالته الحياتية، مسار تصنيفه…

لكنني أدركت شيئاً.

المعرّف لا يحتاج أن يعرف كل شيء.

يحتاج فقط أن يضيّق مليار سجل إلى عشرة آلاف. WMS يتولى الباقي.

فكّر فيه كنقطة تفتيش. عند بوابة رسوم طريق سريع، لتحديد أن “هذه المركبة متجهة نحو مقاطعة غيونغي” من لوحة الترخيص، لا تحتاج أن تعرف ما هو محمّل في الصندوق.

64 بت كافية. استخدم البتات العليا لالتقاط النوع والتصنيف العام، والبتات السفلية للتصنيف الأدق. 64 بت أكثر من كافية لتضييق مليار سجل إلى عشرة آلاف.

و64 بت = أربع كلمات 16 بت. تتدفق بشكل طبيعي داخل التدفق. معرّف 32 بايت يجعل التدفق ثقيلاً، لكن SIDX من 64 بت خفيف وسريع.

التدهور الرشيق: المعنى يبقى حتى عند اقتطاع البتات

قوة أخرى للمحاذاة الدلالية هي خصائص التدهور.

لأن بتات SIDX مرتبة من الأهم إلى الأقل أهمية، حتى إذا تلفت البتات السفلية أو اقتُطعت، تُحفظ المعلومات الأساسية في البتات العليا.

64 بت كاملة:  "يي سون شين، قائد بحري من مملكة جوسون في القرن 16"
48 بت:         "ضابط عسكري من جوسون في القرن 16"
32 بت:         "إنسان من شرق آسيا في القرن 16"
16 بت:         "إنسان"
8 بتات:        "كيان مادي"

كلما اقتُطعت المعلومات، تُفقد الخصوصية، لكن التصنيف الأساسي يبقى حتى النهاية.

هذا تطبيق على مستوى البتات لمبدأ “التدهور الرشيق”.

حتى لو وصلت بيانات جزئية فقط بسبب انقطاع الشبكة، يعرف النظام “لا أعرف بالضبط من هذا، لكنها على الأقل قصة عن إنسان” ويمكنه متابعة الاستدلال.

خطوط عريضة ضبابية أفضل من الصمت التام. فهم جزئي أفضل من فشل كامل.

الاستعلام يصبح معرّفاً

الإمكانية الأكثر إثارة التي يفتحها الفهرسة المحاذية دلالياً هي: يمكن تحويل استعلام بلغة طبيعية إلى SIDX مؤقت.

يسأل مستخدم: “من كان القائد الذي هزم البحرية اليابانية خلال حرب إمجين؟”

يحلل المشفّر هذا السؤال. إنسان. شرق آسيا. القرن السادس عشر. متعلق بالعسكرية. تجميع هذه السمات في بتات يُنتج SIDX مؤقتاً.

هذا الـ SIDX المؤقت يمسح مليار SIDX في WMS. الكيانات التي أنماط بتاتها أكثر تشابهاً ترتفع كمرشحين. يي سون شين، وون غيون، غوون يول، يي أوك غي…

مطابقة المعلومات التفصيلية مع هؤلاء المرشحين تعطي الإجابة النهائية.

هذا يوحّد البحث وربط الكيانات في آلية واحدة. لا حاجة لمحرك بحث منفصل. لا حاجة لخط أنابيب NER (التعرف على الكيانات المسمّاة) منفصل. مقارنة SIDX واحدة هي كل ما يلزم.

لماذا ليس B-Tree؟

قواعد البيانات التقليدية تستخدم فهارس B-Tree.

B-Trees تتفوق في العثور على قيمة محددة في بيانات مرتبة بـ O(log n). لـ “ابحث عن Q8492”، هي الأمثل.

لكن لـ “ابحث عن جميع الكيانات من نوع إنسان وأصلها من شرق آسيا”، هي ضعيفة. عمليات البحث بشروط مركبة تتطلب تقاطع فهارس متعددة، وتكلفة التقاطع تنمو بشكل حاد مع حجم البيانات.

SIDX + مسح SIMD الشامل يتبع نهجاً مختلفاً جذرياً.

إذا كان B-Tree دليل هاتف يجيب بسرعة عن “من يسكن في هذا العنوان”، فإن مسح SIDX هو تنميط يجيب بسرعة عن “من لديه هذه الخصائص.”

طبيعة السؤال تختلف، وكذلك بنية البيانات المثلى.

WMS لا يستخدم B-Trees. يحمّل مليار SIDX في الذاكرة ويجري مسحاً شاملاً بأقنعة بتات SIMD.

بسيط. قوة غاشمة. سريع.

حكمة هوفمان

بنية تخصيص البتات في SIDX تتبع مبدأ ترميز هوفمان.

في ترميز هوفمان، الرموز المتكررة بكثرة تحصل على رموز أقصر، والرموز النادرة تحصل على رموز أطول.

في SIDX، معلومات التصنيف الأكثر حاجة تشغل البتات العليا، والتفاصيل النادرة الحاجة تشغل البتات السفلية.

نفس المبدأ يحكم بادئات أنواع الحزم في هذه اللغة. Tiny Verb Edge الأعلى تكراراً يحصل على أقصر بادئة. Event6 Edge المنخفض التكرار يحصل على بادئة أطول.

حكمة هوفمان تسري عبر كل طبقة من هذا التصميم. لا يُهدر بت واحد. أقل تكلفة لأهم شيء.

ملخص

المعرّف التقليدي هو عنوان. العنوان لا يعرف شيئاً.

1. عندما لا يحمل المعرّف معنى، يجب أن تتبعه إلى البيانات في كل مرة. هذا هو JOIN.
2. أربع عمليات JOIN عبر مليار سجل بطيئة.
3. SIDX يشفّر المعنى مباشرة في المعرّف من خلال المحاذاة الدلالية.
4. عملية AND بقناع بتات واحدة تضيّق مليار سجل إلى عشرة آلاف. صفر JOIN.
5. 64 بت كافية. المعرّف لا يحتاج أن يعرف كل شيء – يحتاج فقط أن يضيّق المرشحين.
6. لأن أهم المعلومات تشغل البتات العليا، يبقى المعنى الأساسي حتى عند اقتطاع البتات.
7. تحويل استعلام بلغة طبيعية إلى SIDX مؤقت يحوّل البحث إلى عملية متجهية.

في اللحظة التي يتوقف فيها المعرّف عن كونه عنواناً ويصبح معرفة، تتغير قواعد قاعدة البيانات.