الگوریتم مرتب‌سازی اوراکل آزاد شد
خلاصهٔ کامل‌تر
به نوشته‌ی این مقاله، پتنت الگوریتمی که اوراکل برای مرتب‌سازی ستون‌های جدول ساخته بود سال ۲۰۲۴ به بیست‌سالگی رسید و خودبه‌خود منقضی شد. اسم الگوریتم Orasort ـه و پتنتش به نام Mark Callaghan ثبت شده بود. حالا که رفته توی دامنه عمومی، هر پروژه‌ای می‌تونه بدون دردسر حقوقی ازش استفاده کنه.
برای اینکه بفهمیم چرا مهمه، اول باید ببینیم مرتب‌سازی قدیمی چطور کار می‌کرد. دیتابیس دو رشته رو کاراکتر به کاراکتر، یعنی یک بایت یک بایت، با هم می‌سنجید. برای Apple و Amazon کار توی کاراکتر دوم تموم می‌شد، ولی برای دو مقدار مثل «Apple is good» و «Apple is bad» مقایسه تا نزدیک آخر رشته ادامه داشت و کلی سیکل CPU می‌سوزوند.
ترفند Orasort استفاده از رجیسترهای CPU ـه. یک رجیستر معمولاً ۸ بایت جا داره، پس به جای یک بایت، ۸ بایت اول هر دو رشته رو می‌کشه بیرون و هر کدوم رو به یک عدد صحیح ۶۴ بیتی تبدیل می‌کنه. بعد فقط یک مقایسه‌ی عددی لازمه. اگه تکلیف همون‌جا روشن شد کار تمومه، وگرنه می‌ره سراغ ۸ بایت بعدی. یعنی به جای هشت مقایسه، یکی.
مقاله می‌گه توی عمل اوراکل رکوردها رو کامل توی حافظه نمی‌ریزه؛ فقط کلید و شناسه‌ی هر رکورد رو توی یک ناحیه‌ی مرتب‌سازی داخل RAM می‌چینه. اگه تعداد رکوردها میلیونی باشه، داده رو تکه‌تکه روی دیسک نگه می‌داره و تکه‌ها رو یکی‌یکی میاره بالا. نوشتن هم آسنکرون و تدریجیه: همزمان با اجرای Orasort می‌نویسه و ادغام نهایی آخر کار روی دیسک انجام می‌گیره.
به گفته‌ی نویسنده، آزاد شدن پتنت دو تا برنده‌ی مشخص داره. اول دیتابیس‌های متن‌باز مثل MySQL و PostgreSQL که Orasort رو یکپارچه کردن و دارن روش آزمایش می‌کنن، دوم شرکت‌های ابری که چون سیکل CPU کمتری خرج میشه، هزینه‌ی عملیاتی‌شون میاد پایین.
نکات کلیدی:
- پتنت Orasort سال ۲۰۲۴ بعد از ۲۰ سال منقضی شد و به دامنه عمومی رفت
- پتنت به نام Mark Callaghan ثبت شده بود
- مقایسه به جای ۱ بایت روی ۸ بایت انجام می‌گیره: دو رشته به عدد ۶۴ بیتی تبدیل می‌شن
- ادعای مقاله اینه که مرتب‌سازی تا ۵ برابر سریع‌تر شده
- MySQL و PostgreSQL الگوریتم رو یکپارچه کردن و در حال آزمایشن
