بهینه سازی کوئری Order By RAND

اگر با لاراول و ORM‌اش Eloquent آشنا باشید، حتما با متد inRandomOrder هم آشنا هستید. کاری که این متد انجام میده، اضافه کردن این عبارت به انتهای کوئری شماست.

&quotyour query&quot order by rand()

حالا تصور کنید که یک اپلیکیشن برای قرعه‌کشی نوشتید و از بین هزاران رکورد پایگاه داده، قراره به صورت اتفاقی ۳ رکورد انتخاب کنید. کوئری شما به این شکل در میاد.

&quotyour query&quot order by rand() limit 3

قبل از اینکه بفهمیم همچین کوئری چه مشکلاتی پیش میاره و چطور میشه بهینه‌سازی‌اش کرد، اول بهتره بفهمیم که خود MySQL این کوئری رو چطور اجرا میکنه. پایگاه‌های داده در زمینه بهینه‌سازی کوئری‌های که بهشون برای اجرا کردن میدید خیلی خوب عمل میکنند ولی خب بهرحال اونها هم محدودیت‌های خودشون رو دارند. علاوه بر این ما اینجا میخوایم چند مقدار تصادفی رو انتخاب کنیم و ازونجایی که پایگاه داده برای همچین کوئری، بهینه‌سازی خاصی نداره، در واقع در دنیای SQL این یک Anti-pattern محسوب میشه.

حالا بریم ببینیم پایگاه داده برای مرتب کردن سطرها در حالت تصادفی چیکار میکنه:

۱- تمام سطرهایی که با شرایط کوئری شما (شامل where ها و group by ها و ...) match هستند رو توی حافظه Load میکنه.

۲- به هر کدوم از این سطرها یک عدد تصادفی اختصاص میده.

۳- تمام سطرها رو بر اساس این عدد تصادفی مرتب میکنه.

۴- تعداد سطرهایی که بهش توی عبارت Limit گفتید رو بهتون برمیگردونه.

اگر سطرهای کمی توی جدول داشته باشید، اینکار برای پایگاه داده خیلی آسونه. ولی هر چقدر تعدادشون بیشتر بشه، به همون اندازه هم اینکار غیربهینه‌تر میشه. هر چند باز هم بخش Load داده‌ها در حافظه حتی اگر جدول بزرگی داشته باشید، باز هم میتونه سریع باشه ولی مرتب کردن اونها کار سختی هست. علاوه بر این هر پایگاه داده‌ای محدودیتی در حجم داده‌ای داره که قراره مرتب بشه.

بعنوان مثال برای mysql و در سیستم‌عامل لینوکس این مقدار اگر اشتباه نکنم باید ۲۵۶ کیلوبایت باشه. البته میشه این عدد رو بیشتر کرد ولی مزایا معایب خاص خودش رو داره. خب پس اگر قرار باشه داده‌هایی با حجم بیشتر از عدد بالا رو مرتب کنید، MySQL مجبور میشه از دیسک هم بعنوان حافظه کمکی استفاده کنه که در نتیجه سرعت عملیات رو خیلی پایین میبره.

راهکار اول : Random Offset

یکی از ساده‌ترین کارها اینه که از ستونی استفاده کنیم که اعداد ترتیبی داره. مثلا کلید در پروژه‌های لاراول معمولا ID و از نوع big integer و auto increment هست و کاندیدای خوبی برای راه‌حل ماست. کوئری ما برای انتخاب ۳ سطر تصادفی، از ترکیب ۳ عدد تصادفی که بین اون اعداد ترتیبی پیدا کردیم، استفاده میکنه.

SELECT * FROM table WHERE id IN(
    SELECT floor(random() * (COUNT(*)) + 1) FROM table
    UNION
    SELECT floor(random() * (COUNT(*)) + 1) FROM table
    UNION
    SELECT floor(random() * (COUNT(*)) + 1) FROM table
)

این راهکار ساده‌ست ولی مشکلات خودش رو داره. حدف سطرهایی که حاوی اعداد ترتیبی هستند، منجر به ایجاد gap در فضای اعداد continous ما میشن که باید پر بشند. همینطور نمیشه از شرط استفاده کرد چون بازم باعث به وجود اومدن gap میشه، و البته بعضی سطرها میتونن بیشتر از یکبار در نتایج ظاهر بشند.

راهکار دوم : Random Range

حالا بیاید ایده قبلی رو یکم گسترش بدیم. به جای اینکه مجموعه داده‌ای مون رو مجبور کنیم که هیچ gapی نداشته باشه، میتونیم بگیم برای جستجو بین تمام سطرها از یک نقطه شروع تصادفی استفاده کنه.

SELECT * FROM repositories WHERE id <= (SELECT floor(random() * (COUNT(*)) + 1) FROM repositories) LIMIT 3

این راه‌حل هم مشکلات خاص خودش رو داره. اگر بعضی از سطرهای متوالی رو حذف کنید، شانس سطرهای بعدی برای قرار گرفتن تو نتایج بالاتر میره. همینطور ما اینجا در شرطی که قرار دادیم، واضحا بعضی از سطرها رو از قرار گرفتن در نتایج حذف کردیم و رقابت بین سطرهای بعدی هست.

راه حل

چند وقت پیش با یکی از همکارهام در مورد راه حلی برای حل یک مساله مالی صحبت میکردیم که از الگوریتم k-NN اسم برد. من چیزی در موردش نمیدونستم. برام جالب شد و در موردش خوندم. حالا اینجا میخوایم یک ترفند بزنیم و از این الگوریتم برای حل مساله‌مون استفاده کنیم. کاری که میکنیم چیه؟ MySQL برای کار با GIS از Index های Spatial که اگر بازم اشتباه نکنم از نوع R-Tree هستند استفاده میکنه. کاری به جزییات‌اش نداریم. ما فقط میخوایم روی داده‌های تصادفی‌مون شاخص بگذاریم تا خیلی سریع به داده‌های تصادفی‌مون برسیم.

یک ستون از نوع POINT به جدول اضافه میکنیم و توش رو با مقادیر تصادفی پر میکنیم. روی این ستون Index از نوع Spatial میگذاریم. خب تا اینجا رو اومدیم، بعدش چی؟ حالا کافیه یک نقطه شروع تصادفی انتخاب کنید و با استفاده از k-NN نقاط تصادفی مدنظرتون رو از بین انبوه داده‌ها بکشید بیرون.

متاسفانه ازینجا به بعد مرحله برای MySQL قفل هست و باید فعلا از Postgres استفاده کنید، چون k-NN در MySQL، هنوز پشتیبانی نمیشه. البته باید روی postgres هم از PostGIS استفاده کنید.