‏سریع‌تر کردن درج داده تو SQLite با مرتب‌سازی قبل از insert

نویسنده تو پست قبلی نشون داده بود که تصادفی بودن UUID4 چه‌قدر روی سرعت درج تو SQLite اثر می‌ذاره و UUID7 چه‌طور کمک می‌کنه. حالا سراغ حالتیه که اصلاً نمی‌تونی از UUID7 استفاده کنی؛ مثلاً برای توکن نشست که نباید اطلاعات لو بده. اینجا یه شناسه‌ی تصادفی ۱۶۰ بیتی (۲۰ بایت) با SecureRandom ساخته می‌شه که عملاً هیچ ترتیبی نداره.

مشکل از ساختار درخت B+ می‌آد. به گفته‌ی نویسنده ویژگی اصلی این درخت اینه که مرتبه، پس نوشتن پشت‌سرهم و ترتیب‌دار سریعه. ولی داده‌ی تصادفی دقیقاً برعکس عمل می‌کنه: صفحه‌ها رو می‌کوبه، باعث شکستن صفحه (page split) و متعادل‌سازی دوباره‌ی درخت می‌شه. نتیجه‌ش هم می‌شه حدود صد هزار درج در ثانیه که خیلی کنده.

نکته‌ی کلیدی اینه که داده‌ها همین الانش هم دسته‌ای (batch) درج می‌شن. پس نویسنده می‌گه چرا قبل از درج، خود دسته رو مرتب نکنیم؟ برای این کار به یه راه سریع برای مقایسه‌ی شناسه‌های تصادفی نیاز داریم. به‌جای این‌که کل ۲۰ بایت رو مقایسه کنیم، فقط ۸ بایت اولش رو برمی‌داریم و به یه long تبدیل می‌کنیم. این مقایسه باید بدون علامت (unsigned) و Big Endian باشه تا با ترتیب blob خود SQLite (که با memcmp() انجام می‌شه) جور دربیاد.

مقایسه‌گرش این‌شکلیه:

(defn bytes->long [^bytes bytes]
  (-> (ByteBuffer/wrap bytes 0 8)
    (ByteBuffer/.getLong 0)))

(defn byte-compare [a b]
  (Long/compareUnsigned
    (bytes->long a)
    (bytes->long b)))

بعد کافیه قبل از درج، کل دسته‌ی یک‌میلیونی با همین byte-compare مرتب بشه و بعد توی جدول WITHOUT ROWID ریخته بشه. نتیجه‌ی جالبش اینه که با وجود سرباری که خود مرتب‌سازی داره، سرعت کل کار حدود ۲ تا ۳ برابر بهتر می‌شه.

جمع‌بندی نویسنده اینه که دسته‌ای کردن داده‌ها در کنار سریع‌تر شدن خودِ درج، یه در دیگه هم باز می‌کنه: بهینه‌سازی‌هایی مثل مرتب‌سازی قبل از insert که وقتی با داده‌ی نامرتب سروکار داری حسابی به کارت می‌آد.

نکات کلیدی:

• داده‌ی تصادفی به‌عنوان کلید اصلی، درخت B+ رو با page split و متعادل‌سازی مجدد کند می‌کنه
• چون درج‌ها دسته‌ای‌ان، می‌شه قبل از insert کل دسته رو مرتب کرد
• برای مقایسه‌ی سریع فقط ۸ بایت اول به long تبدیل می‌شه، با مقایسه‌ی unsigned و Big Endian تا با ترتیب blob در SQLite جور باشه
• نتیجه: سرعت درج حدود ۲ تا ۳ برابر بیشتر، با وجود سربار مرتب‌سازی