ایندکس گذاری در PostgreSQL و Sequelize

مقایسه دفترچه تلفن با index ها

فرض کن توی دفترچه تلفنت دنبال امیر حسین کریمی میگردی. دفترچه تلفن بر اساس حروف الفبا مرتب شده است. پس میای توی حرف ا دنبال امیر حسین میگردی و بعدش توی حرف ک دنبال کریمی میگردی و در نهایت شماره تلفنش رو پیدا می کنی.

ولی اگه دفترچه تلفنت بر اساس حروف الفبا مرتب نشده بود باید از اول تا آخر بگردی. به این مدل جستجو sequential scan میگن. دقیقا مثل دفترچه تلفن دیتا های جدول رو هم باید نظم بدیم تا سرعت جستجو توی جدول بیشتر بشه.

ایندکس ها یه data structure هستن که برای سرعت بیشتر شما باید بهای write بیشتر و نگهداری از حجم دیتا ها رو به جون بخرید.

پس اگه میخوای یه اپلیکیشن بزنی که با دیتابیس کار می کنه خیلی مهمه که مفهوم ایندکس گذاری تو دیتابیس ها رو درک کرده باشی. ایندکس های چی هستن و به چه کاری میان؟ سرعت پاسخ داده شدن برای کوئری هایی که روی دیتابیس میزنی برات مهمه؟ میخوای روی ۱۰ هزار تا محصول مختلف که توی دیتابیس داری سرچ بزنی و کوئری های رنگارنگ (Elasticsearch) بزنی؟ پس این پست رو تا تهش بخون.

ایندکس چیه؟

ایندکس یه نوع database structure هست که سرعت اجرا شدن کوئری ها رو بالا میبره. ایندکس ها یه بیت هستن، دقیقا مثل شماره صفحات یه کتاب. مثلا میخوای تو یه کتاب دنبال کلمات PostgreSQL بگردی، کار ساده تر اینه که یکبار بیای صفحاتی که کلمه PostgreSQL دارن رو یادداشت کنی و بعدا بجای اینکه هر بار توی تک تک صفحات دنبال کلمه PostgreSQL بگردی، بری فقط توی اون صفحات دنبال اون کلمات بگردی.

نکته خیلی مهم

اکثر RDBMS های با شعور برای هر select ای نمیان از index scan استفاده بکنن. به بیان دیگه اگه تو داری یه select ای میزنی که (تقریبا) بیشتر از ۵ - ۱۰ درصد از رکورد های دیتابیس رو میخواد retrieve بکنه RDBMS از sequential scan استفاده میکنه.
چرا؟

چونکه select داره ۵ - ۱۰ درصد از رکورد ها رو بر میگردونه
برای index scan نیاز به چندین عملیات IO به ازای هر رکورد هست. اول رکورد رو توی ایندکس lookup میکنه و بعدش از heap اونو retrieve میکنه.
توی sequential scan به ازای هر رکورد نیاز به یه IO داریم. حتی تو بعضی موارد کمتر، چونکه یه بلوک ممکنه حاوی چندین سطر باشه.
مورد دیگه اینه که sequential scan میتونه چند page رو در یک لحظه درخواست بده و همون جا هم به CPU بگه تا من روی این page ها کار میکنم تو برو chunk بعدی رو fetch بکن.

انواع ایندکس گذاری

ما توی PostgreSQL چندین نوع ایندکس گذاری داریم ولی نوع ایندکسی که برای یه جدول انتخاب می کنی به چند تا فاکتور وابسته هست:

دیتای درون جدول (یعنی encoding اون رکورد چیه و اینکه آیا fix length هست یا نه)
نوع دیتا
چه نوع lookup هایی میخوای بزنی؟

انواع مدل ایندکس گذاری

B-tree
Hash
GiST (Generalized Inverted Search Tree)
SP-GiST (Spaced Partition GiST)
GIN (Generalized Inverted Index)
BRIN (Block Range Indexes)

B-Tree

تو این مدل PostgreSQL یه درخت self-balanced میسازه. ساده تر بگیم، خودش رو میاد sort میکنه. بخش جذابش اینه که این بالانس رو در طی عملیات های حذف، سرچ یا وارد کردن دیتا حفظ میکنه. تویا وضعیت سرعت عملیات اسکن کردن بالا میره، ولی چرا؟

چونکه مجبور نیست صفحات رو به صورت خطی و پشت سر هم اسکن کنه.

این روش ایندکس گذاری برای زمانی خوبه که:

اول جدول و فیلد هاش رو بدست میاری.
طول آن فیلد ثابته (fix length هست)
عملیات ها روی بلوک های زیادی از دیتا قرار هست اجرا بشه.

دستور `CREATE INDEX` به صورت پیشفرض برامون یه B-Tree ایجاد میکنه. وقتی روی یه ستون ایندکس گذاری شده عملگر های مقایسه (>، =>، =، =<, IS NOT NULL, IS NULL, IN, BETWEEN) اعمال میکنی query planner میاد از ایندکس B-Tree استفاده میکنه.

create index index_name on table_name [using method_name]
(
    column_name [asc | decs] [nulls first | nulls last]
)

توی دستور بالا index_name رو خواهشا با معنی بزارید.

متد های ایندکس گذاری مختلفی داریم که شما میتونید بر اساس نیازتون مشخص کنید متد ایندکس گذاری چی باشه. متد پیشفرض btree هست. ولی شما میتونید از: hash ،gist ،gin ،brin و spgist هم استفاده کنید.

نکته بعدی بخشی هست که میگی این ایندکس گذاری شامل چه ستون هایی بشه:

برای مشخص کردن نحوه sort شدن از ASC یا DESC استفاده میشه.
برای اینکه مقادیر null ابتدا لیست بشن از nulls first استفاده میشه و برای بر عکس کردن هم از nulls last
در صورتی که DESC رو انتخاب کرده باشید مقدار nulls first استفاده میشه.
در صورتی که ASC رو انتخاب کرده باشید مقدار nulls last استفاده میشه.

Hash

سرعت lookup این مدل ایندکس خیلی سریع تر از B-Tree هست. ولی یه نکته منفی داره. اونم اینه که مورد استفاده اون محدود به عملگر = هست. البته تو ورژن های ۹ و پایین تر از اون PostgreSQL هش ایندکس ها WAL-logged یا crash-safe نبودن. یعنی اگه سرور ریستارت میشد یا کرش می کرد باید REINDEX میکردی.

در کل این نوع ایندکس گذاری حافظه کمتری نسبت به B-Tree لازم داره. چونکه مسطح هست.

CREATE INDEX the_index_name ON the_table_name USING HASH (the_indexed_column);

GiST

تو شرایطی که مقادیر ذخیره شده تو یه ستون overlap دارن ما از این مدل برای ایندکس گذاری استفاده می کنیم. دو کیس خیلی مشهور اینا هست:

Full-text search
Geometric types

نکته full text search اینه که اجباری در ایندکس گذاری به خاطرش وجود نداره، اما اگه سرچ روی اون ستون به صورت مداوم انجام میشه ایندکس گذاری کردن یه کار خوبه.

البته وقتی از GiST استفاده می کنی یادت باشه که ایندکس گذاری به این روش lossy هست؛ به این معنی که ممکنه مقادیر اشتباهی بر گردونه. اما این معنی رو نمیده که خروجی کوئری اشتباه هست، فقط داره میگه PostgreSQL باید یخورده سخت تر کار کنه تا خروجی رو verify بکنه که درسته.

وقتی داری یه ستونی رو به این صورت ایندکس گذاری می کنی اون ستون میتونه از نوع tsvector یا tsquery باشه.

SP-GiST

دیتا هایی که non-balance هستن رو با درخت های partitioned search میان ایندکس گذاری میکنن. بهترین مثالش شماره تلفن منزل هست:

همه شماره تلفن ها از سمت چپ با ۳ رقم کد استان و بعد سه رقم کد شهرستان و بعد ۴ رقم دیگر که ادامه شماره تلفن هر خط ثابت است. ولی در برخی موارد کد استان (مثلا مشهد) با دو رقم شروع میشه. تو این مورد بالانس از دست رفت.

GIN

توی این مدل ایندکس گذاری، به هر واژه یه ایندکس داده میشه. تو یه لیست فشرده ایندکس هایmatching location ها ذکر شده. این متد ایندکس گذاری برای زمانی خوب هست که ما مقادیر مختلفی تو یه ستون داریم. یعنی data type اون ستون معمولا یکی از موارد زیر هست:

JSONB
Array
Range Types
hStore

مورد کاربردش وقتی هست که دنبال یه text خاص تو یه مشته داکیومنت (تعداد رو زیاد در نظر بگیرید) هستی. مثلا میخوای دنبال اسم مشتری تو جدول مشتری ها، با یه میلیون رکورد بگردی. مثلا کاربر توی input سه حرف اول رو وارد میکنه، حالا می تونی شاهد جادوی GIN باشی. همه ی رکورد هایی که اون سه حرف رو تو خودشون (contains) داشتن بر گردونده میشن. به بیان ساده تر هر کدوم از مقادیر ذخیره شده توی اون ستون خودشون می تونن داده های مجزایی باشن.

نکات مهم:

وقتی داری یه ستونی رو به این صورت ایندکس گذاری می کنی اون ستون باید از نوع tsvector باشه.
وقتی از این متد ایندکس گذاری استفاده می کنی باید از عملگر خودش استفاده بکنی. دیگه عملگر LIKE و wildcard هاش رو فراموش کن

BRIN

در اکثر موارد به جای SP-GiST میتونی از این مدل ایندکس گذاری استفاده بکنی. بهره وری این مدل ایندکس گذاری تو مواردی که datasets زیادی داریم خیلی بیشتر هست. در ضمن هزینه maintenance این مدل ایندکس گذاری از B-Tree خیلی کمتره.

کاربرد این مدل ایندکس گذاری تو مواردی هست که مثل zip code و date. چونکه میتونی از دیتا های unnecessary صرف نظر بکنی.

دیتاست: مجموعه ای از داده ها که توی دیتابیس هست.

GIN VS GiST

سرعت lookup ایندکس GIN سه برابر بیشتر از GiST است.
سرعت ایجاد ایندکس GIN سه برابر بیشتر از GiST هست.
سرعت آپدیت ایندکس GIN یکمی از آپدیت ایندکس GiST کند تر هست. (اما اگه fast update رو غیر فعال کرده باشی این کندی به ۱۰ برابر میرسه. ولی توی GIN ما سرعت آپدیت رو با افزایش دادن مقدار maintenance_work_mem میتونیم زیاد تر بکنیم. در حالی که سرعت آپدیت GiST به این پارامتر حساس نیست)
حجمی که ایندکس GIN نسبت به GiST اشغال میکنه ۲ الی ۳ برابر بیشتر هست.

در کل میشه گفت که GIN برای

دیتا های استاتیک به علت سرعت بالای lookup
اگه تعداد کلمات unique بالای ۱۰۰٫۰۰۰ باشه.

و GiST برای

دیتا های داینامیک که به علت سرعت بالای آپدیت
تعداد کلمات unique اون زیر ۱۰۰٫۰۰۰ باشه

بنچ مارک GiST و GIN (کامل نشده)

شرایط benchmark

۲ تا سرویس PostgreSQL روی داکر با منابع سخت افزاری محدود شده به یه core سی پی یو و یه گیگ رم.
استفاده از پکیج sequelize و pg

لینک repo توی گیت هاب

چند نکته

ایندکس گذاری خودکار: فیلد هایی که به صورت unique یا کلید اصلی تعریف میشن به صورت خودکار ایندکس گذاری میشن. به همین دلیله که سرعت سرچ روی کلید های اصلی این همه بالا هست.
ایندکس گذاری partial: مثلا میخوای با null به صورت یه مقدار برخورد نشه و ایندکس گذاری رو با شعور بکنی. یعنی بر اساس یکسری شرایط ایندکس گذاری بکنی از partial index باید استفاده بکنی

ایجاد ایندکس توی PostgreSQL

ایجاد ایندکس ها توی Sequelize

برای ایندکس گذاری میتونیم به این صورت عمل کنیم:

const { Model, DataTypes } = require('sequelize');
const sequelize = require('./sequelize');
class Product extends Model {}
Product.init(
  {
    id: {
      primaryKey: true,
      type: DataTypes.UUID,
      defaultValue: DataTypes.UUIDV4
    },
    title: {
      type: DataTypes.STRING
    }
  },
  {
    sequelize: sequelize.getSequelize(),
    indexes: [
      {
        fields: ['title']
      },
    ],
  },
);
module.exports = Product;

به این روش شما یه ایندکس B-Tree روی ستون title ایجاد می کنید. برای اینکه دقیقا بگید چه مدل ایندکسی میخواید بزارید باید توی indexes بگید:

indexes: [
    {
        fields: ['title'],
        using: 'gin', // gist, sp-gist, ...
        operator: ''
    },
],

مطالعه بیشتر

مدیوم

منابع

رفرنس، رفرنس