انواع index در پستگرس

مقدمه

کلمه پایگاه داده در این مطلب به پایگاه داده‌های رابطه(RDBMS) اشاره دارد.

استفاده از index باعث نشانه‌گذاری و پیدا کردن سریع‌تر رکوردها پایگاه‌داده ما خواهد شد. به صورت پیشفرض وقتی یک ستونی دارای index نباشد، به هنگام جستجوی بر اساس اون ستون، پایگاه‌داده شروع به بررسی تک‌تک مقادیر اون ستون در سطرهای جدول می‌کنه، که طبیعتا با افزایش حجم داده‌های جدول این جستجو روز به روز کندتر میشه. برای همین منظور توسعه دهندگان پایگاه‌داده‌ها با معرفی index گذاری سعی در رفع این مشکل کردند. از اونجایی که postgresql هم یکی از پایگاه‌داده‌های محبوبه و استفاده زیادی دارد، چه بهتر که با انواع مختلف ایندکس(index) گذاری تو این پایگاه داده بیشتر آشنا بشیم.

انواع indexها

به طور کلی postgres دارای ۶ نوع ایندکس‌گذاری می‌باشد.

• B-Tree
• GIN
• GiST
• Brin
• Hash
• SPGiST
• Bloom(in contrib)

که ما با سه‌تای آخری کاری نداریم!!

B-Tree Index

این ایندکس‌گذاری، معروف‌ترین نوع ایندکس‌گذاری می‌باشد که اکثر پایگاه‌داده‌ها نیز از آن پشتیبانی می‌کنند. اما رعایت بعضی موارد باعث استفاده بهتر از این ایندکس‌گذاری ‌می‌شود. احتمالا با خودتون میگین که رعایت چی؟ ایندکسه دیگه، میزاری تموم میشه میره. آیا چیزی به اسم partial index رو شنیدین؟ این موراد چیزایی که باعث میشه ما ایندکس‌گذاری بهتری داشته باشیم.

نحوه ساخت B-Tree در postgres:

در واقع B-Tree یک درخت متوازن هستش که تعداد بچه های یک والد می‌تونه بیشتر از ۲ باشه(درخت دودویی نیست) و این باعث میشه که عمق درخت کمتر باشه. درضمن فاصله همه‌ی برگ‌ها از ریشه هم به یک اندازه‌ست(بازهم دوباره یعنی مثل درخت دودویی(binary) نیست). اما هر گره این درخت شامل چه چیزهاییه:

توی پستگرس هرچیزی توی یک چیزی به اسم page ذخیره میشه و اندازه این page هم ۸ کیلوبایته. به عنوان مثال هر کدوم از گره‌های درخت هم توی یک page ذخیره میشه. بسته به موارد مختلف توی page چیزهای مختلفی ذخیره میشه که این موارد برای درخت B-Tree شامل سه تا مورد میشه:

۱− شماره بلاک(برای pointer)

۲− بیشترین مقدار اون گره(high key)

۳− مقادیر(items)

مورد یک که هیچی یک عدده و محل رو نشون میده.

مورد دوم، هر گره بیشترین مقداری که توی خودش(زیردرخت خودش) داره رو اینجا ذخیره می‌کنه تا بر اساس این مقدار بررسی بشه که چیزی که دنبالیشم توی اینجا هست یا بریم سراغ بعدی؟ گره آخر هم این مقدار رو نداره.

مورد سوم شامل یک لیست از مقادیر هستش که هر مقدار دوتا عنصر توی خودش داره: یکی value که مقدار چیزیه که ایندکسش کردیم و دومی اشاره‌گر(pointer) که اگر والد باشه به بچه اشاره می‌کنه(در واقع به page اون بچه) و اگر برگ باشه به محل واقعی اون سطر اشاره می‌کنه.

Normal Index

توی این مورد ایندکس روی همه مقادیر اون ستون در همه سطرها اعمال میشه. بخوایم هم تعریف کنیم این طوری عمل می‌کنیم:

CREATE INDEX [index_name] ON [table_name](column_name_list)
ex:
یک ایندکس روی یک ستون
CREATE INDEX user_phone_idx ON users(phone);
 یک ایندکس برای چند ستون باشه
CREATE INDEX user_full_name_idx ON users(first_name, last_name);

توی جنگو(django) به این شکل عمل می‌کنیم:

class Meta:
    indexes = [
       models.Index(fields=['phone'], name='user_phone_idx')
    ]
یا اگر بخوایم روی چند تا ستون داشته باشیم:
class Meta:
    indexes = [
        models.Index(fields=['first_name', 'last_name'], name='user_full_name_idx')
    ]

دو تا نکته درباره ایندکس روی چند فیلد:
۱) اولین ستون رو میشه مثل ایندکس گذاری روی تک ستون فرض کرد، چون موقع ایندکس‌گذاری چند ستونه، اولین ستون مرتب‌شده(ordered) هستش و این یعنی مثل ایندکس روی ستون میشه باهاش رفتار کرد.
توی مثال بالا، الان ستون first_name انگار خودش به تنهایی هم ایندکس‌گذاری شده. پس توی ایندکس‌گذاری چند ستونه، حواستون باشه که چه ستونی رو اول انتخاب می‌کنید، و ستونی که بیشترین سرچ رو دارین رو اول بذارین. به این کار استفاده مجدد(reuse) هم میگن. در واقع اگر یک ایندکس چند ستونه داریم و یک ایندکس تنها برای ستون اولِ اون چندتایی، به خاطر ایندکس چندتایی، می‌تونیم اون ایندکس تنهایی رو برداریم.
۲) حواستون باشه که موقع کوئری زدن هم تا جایی که ممکنه، بر اساس ستون اول فیلتر رو انجام بدیم، نتیجه بهتر(سریع‌تر) می‌گیریم.

Partial index

این نوع ایندکس یک شرط هم داریم. یعنی میگیم توی فلان ستون اون سطرهایی که فلان شرط رو دارن رو ایندکس کن(توی ایندکس عادی همه سطرها بودن اینجا براساس شرط). با یک مثال موضوع رو بهتر متوجه میشیم:

CREATE INDEX [index_name] ON [table_name](columns_name_list) where [condition];
Ex:
CREATE INDEX active_users_partial_idx ON users(is_active) where is_active = 1; 

بخوایم توی جنگو این کار رو انجام بدیم هم داریم:

class Meta:
     indexes = [
        models.Index(
             fields=['is_active'], name='active_users_partial_idx', condition=Q(is_active=True)
        )
     ]

ایندکس بخشی(partial index) زمانی به درد می‌خوره که اکثر کوئری‌ها روی یک سری سطر با یک سری شرایط خاص انجام میشه، به عنوان مثال:

اگر برای مدل users یک فیلد برای مشخص کردن کاربران فعال و غیرفعال داشته باشیم، معمولا موقع جستجو، نتیجه بر اساس کاربران فعال فیلتر میشه، پس ایندکس‌گذاری روی این کاربران بهتره. شاید بپرسین که چرا روی همه کاربران ایندکس نزاریم و آورده این ایندکس نسبی(partial index) چیه؟ جواب اینکه هر چی تعداد رکوردها بیشتر بشه، حجم ایندکس هم بزرگتر میشه و این باعث میشه پیدا کردن و رسیدن به رکورد بیشتر طول بکشه ولی ایندکس نسبی(partial index) چون بر اساس اون شرایط خاص انجام میشه حجم کوچک‌تری داره و در نتیجه سریع‌تر جواب میده.

Unique index

با این ایندکس دیگه مقدار تکراری برای اون فیلد نخواهیم داشت و همه مقادیر اون ستون با اون یکی‌ها متفاوته. مثلا چیزی مثل کدملی یا ایمیل.

CREATE UNIQUE INDEX [index_name] ON [table_name](column_name_list)
ex: یک ایندکس روی
CREATE UNIQUE INDEX user_email_unique_idx ON users(email);

توی جنگو برای ساختن این نوع ایندکس موقع تعریف اون فیلد عبارت unique=True رو پاس میدیم.

phone = models.charfield(max_lenght=11, unique=True)

Partial unique index

این نوع ایندکس باعث میشه که بر اساس یک شرطی تکراری بودن مقادیر بررسی بشه. مثلا میگیم ایمیل unique باشه ولی فقط برای سطرهایی که بعد از سال ۱۴۰۰ ساخته شدند. این مورد برای soft delete هم جوابه. از اونجایی هم ایندکس کوچک‌تری داریم، در نتیجه موقع insert سرعت بیشتری خواهیم داشت. چون موارد کمتری برای تکراری بودن مقدار، بررسی می‌شوند.

برای ساخت این ایندکس داریم:

CREATE UNIQUE INDEX [index_name] ON [table_name](column_name_list) WHERE [condition]
Ex:
CREATE UNIQUE INDEX user_email_unique_partial_idx ON users(email) where created_at > '2021-03-20'; 

Django:

class Meta:
      indexes = [
         models.UniqueConstraint(
              fields=['email'],
              name='user_email_unique_partial_idx',
              condition=Q(created_at__gt='2021-03-20')
         )
     ]

GIN Index(General Inverted iNdex)

این ایندکس برای آرایه‌ها، json و tsvector(از tsvector برای full text سرچ استفاده میشه) مورد استفاده قرار می‌گیرد.

این ایندکس برای چیزهایی مثل، آیا این آرایه شامل این عنصر هستش یا نه یا این آرایه بخشی از اون آرایه هستش یا نه و ... کاربرد دارد(توی پستگرس این عملیات با عملگرهای @> , &&, @@@ انجام می‌شوند). برای همین هم برای full text خوبه، چون دائما از پایگاه داده می‌پرسیم، آیا این متن توی اون متن هست؟ این کلمه چطور؟ و چیزایی مثل این.

برای ساختن این ایندکس داریم:

CREATE INDEX [index_name] ON [table_name] USING GIN (column)
CREATE INDEX article_fulltext_gin_idx ON article USING GIN(content);

Django:

from django.contrib.postgres.indexes import GinIndex
class Article(models.Model):
     ...
    class Meta:
           indexes = [GinIndex(fields=['content'])]

نحوه کار این ایندکس:

به عنوال مثال اگر یک ستون که شامل آرایه‌ست رو ایندکس گذاری کنیم، Gin این طوری عمل می‌کنه که هر عنصر آرایه رو میاد جدا می‌کنه و یک entry براش در نظر می‌گیره و البته مقدار این entry یکتا(unique) هستش. یعنی اگر یک عنصر از یک آرایه توی آرایه دیگه هم وجود داشته(مثلا مقدار ۴ توی دو تا آرایه سطر یا همون آرایه متفاوت باشه)، میاد و از entry قبلی استفاده می‌کنه. این entryها هم به یک سری برگ(leaf) اشاره می‌کنند که اونا هم یک سری اشاره‌گر(pointer) به سطرها هستند. از اونجایی هم که برگ یک page هستش و ممکنه سایز یک page برای همه اشاره‌گر ها کوچک باشه(یعنی یک عنصر تو سطرهای مختلف خیلی تکرار شده باشه)، در این صورت از یک چیزی به اسم post tree استفاده میشه(یعنی اون برگ به post tree اشاره می‌کنه).

نمای کلی این حرفا میشه، تصویر پایین:

به طور خلاصه Gin:
۱− برای آرایه‌ها، json و tsvector مفیده
۲− یک درخت متعادله(balanced)
۳− به جای ایندکس کردن کل مقدار ستون(کل آرایه)، تک تک مقادیر رو ایندکس می‌کنه.
۴− هر مقدار این درخت یکتاست(unique)

GiST Index(GeneralIzed Search Tree)

نکته‌ای که در رابطه با GiST وجود داره، اینکه که GiST یک ایندکس نیست و یک فریم‌ورک به حساب میاد!! احتمالا الان براتون سوال پیش اومده که این جمله یعنی چی(حق هم دارین)؟ ما می‌تونیم ایندکس خودمون برای data typeهای مختلف بنویسیم(اگر دوست و حوصله داشته باشیم)! یک لیست از توابع هستش که باید پیاده سازی بشن و تامام، ما یک ایندکس داریم. البته باید توجه داشته باشیم که به نکات این ایندکس باید توجه داشته باشیم وگرنه یک ایندکس بد رو پیاده سازی کنیم که نه تنها سرعت رو برای ما به ارمغان نیورده، بلکه بدترش کرده!!

بزارین با یک مثال موضوع رو شفاف‌تر کنیم. ما یک رکورد که اطلاعات مربوط به که یک دایره رو برای ما فراهم می‌کنه و یک رکورد هم داریم که یک مستطیل رو به ما میده(اینکه ما یک همچنین چیزی داریم خودش عجیب‌تر به نظر میاد)!!! طبیعتا ما نمی‌تونیم این دوتا رو با هم مقایسه کنیم(نهایتش می‌تونیم سوال کنیم، این دوتا نوعش‌شون با هم یکیه یا نه)، اما می‌تونیم سوالاتی مثل اینکه آیا این دایره توی این مستطیله یا نه رو بپرسیم یا مثلا آيا دایره نزدیک مستطیله یا نه؟ یا اگر بخواهیم یک مثال بهتری داشته باشیم می‌تونیم به سراغ موارد جغرافیایی بریم. چون این جنس سوال‌ها توی موارد جغرافیایی زیاد پرسیده میشه(آیا این لوکیشن توی فلان منطقه‌ست؟ فلان منطقه توی کدوم شهره؟ چه مناطق دیگه‌ای نزدیکه این منطقه داریم؟). به طور کلی این ایندکس برای چیزهای overlap طور خوبه(جغرافیایی، آرایه‌ها و range و ...).

نکته آخر درمورد GiST اینکه ما از اون برای full text search هم می‌تونیم استفاده کنیم، ولی اینکه کی بریم سراغ GIN و کی بریم سراغ GiST، سوالیه که تو این پست بهش جواب نمیدیم، شاید یک پست دیگه یا شاید هیچ وقت(به نظرم خودتون برین سراغش و مطالعه کنید بهتر باشه)!!!
نحوه ایجاد این ایندکس:

CREATE INDEX [index_name] ON [table_name] USING GIST (column);
CREATE INDEX article_aaa_gist_idx ON article USING GIST(aaa);

Django:

from django.contrib.postgres.indexes import GistIndex
class Article(models.Model):
      ...
     class Meta:
            indexes = [GistIndex(fields=['aaa'])]

الان احتمالا دارین میگین که چی شد؟ ما گفته بودیم یک فریم‌ورک و ایناست و توابعی رو پیاده‌سازی کنیم و ... پس اونا کو؟ جواب این سوال اینکه خود پستگرس یک پیاه‌سازی‌هایی برای data typeهای موجود انجام داده که ما می‌تونیم از اونا استفاده کنیم.

BRIN Index(Block Rang INdex)

همین اول کار بهتون میگم که این ایندکس اصلا تشکیل درخت نمیده!! اینکه محل فیزیکی ذخیره یک رکورد با یک رکورد بعدی با هم تفاوت داشته باشن، یک موضوع کاملا عادیه. اما اگر ما یک تیبل داشته باشیم که رایت زیاد داره و به ندرت هم اپدیت میشه این جور مواقع محل فیزیکی سطرهای جدول، توی دیسک هم کنار هم قرار داره و اینجاست که BRIN می‌تونه کمک کننده باشه. چرا؟ چون یک ایندکس با حجم بسیار کوچک درست می‌کنه و گشتن ایندکس با حجم کوچک خیلی سریعه. در واقع توی B-Tree ما به اجرای هر سطر یک page(منظورم page پستگرس هستش که قبلا تو همین پست بهش اشاره کردیم) داریم و طبیعتا هرچی سایز جدولمون بزرگتر بشه این درخت سایزش بیشتر میشه و در نهایت سرعت پیدا کردن می‌تونه کندتر بشه. اما BRIN میاد و به صورت یک بازه‌ای از بلاک‌ها کار می‌کنه. به صورت دقیق‌تر بخوایم بگیم چیزی که ذخیره می‌کنه اینجوریه که میگه این بازه از مقادیر توی این بلاک‌هاست، برو فلان و اونجا دنبالش بگرد(محل دقیق رو به ما نمیگه)! خوبی این مورد توی جدول‌های خیلی بزرگ به خوبی عمل میکنه چون ایندکس کوچک داریم. اما باید حواسمون باشه که چیزی که داریم ایندکس می‌کنیم بازه مقادیر خیلی عجیب غریبی نداشته باشه که یک حجم خوبی از رکوردهارو شامل بشه و به فنا بریم.

نحوه تعریف

CREATE INDEX [index_name] ON [table_name] USING BRIN (column);
CREATE INDEX article_created_at_idx ON article USING GIST(created_at);

Django:

from django.contrib.postgres.indexes import BrinIndex
class Article(models.Model):
      ...
     class Meta:
            indexes = [BrinIndex(fields=['created_at'])]

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

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

نکته۱: کلا این ایندکس چیزهای افزایشی خوبه(مثلا اگر کلید اصلی جدولمون افزایشیه و خیلی هم بزرگه).

نکته ۲: اگر ما سطرهای جدول رو پاک کنیم و عملیات vacuum رو انجام بدیم دیگه این ایندکس زیاد خوب عمل نمی‌کنه.

SP GiST(Space Partitioning GiST)

این مورد هم مثل GiST در واقع یک فریم‌ورک هستش و طبیعتا یک سری تفاوت‌هایی با GiST دارد. اینکه چطوری کار می‌کنه و ... متاسفانه در لحظه که دارم این مقاله رو می‌نویسم هنوز نرسیدم برم بررسی کنم. شاید تو آینده این بخش آپدیت کنم. یک عکس از بلاگ alibaba-cloud پیدا کردم که از همون استفاده می‌کنم، لینک مطلب زیر عکس هستش، نمیدونم چقدر خوب توضیح داده.

نحوه تعریف:

CREATE INDEX [index_name] ON [table_name] USING SPGIST (column);
CREATE INDEX article_aaa_gist_idx ON article USING SPGIST(aaa);

Django:

from django.contrib.postgres.indexes import SpGistIndex
class Article(models.Model):
      ...
     class Meta:
            indexes = [SpGistIndex(fields=['aaa'])]

Hash Index

از روی اسمش میشه یک چیزهایی رو حدس زد، به هش(درهم‌سازی) و hash table ربط داره. نکته مهم این ایندکس اینه که تا نسخه ۱۰ پستگرس زیاد چیز خوبی نبود و از نسخه ۱۰ به بعد stable شد.

هر مقدار به یک هش کد ۳۲ بیتی تبدیل میشه و این موضوع خودش رو توی مواردی که مقدار خیلی بزرگ هستش به خوبی نشون میده(b-tree کل مقدار رو توی خودش ذخیره می‌کنه و بنابراین برای مواردی که سایز بزرگی دارن مناسب نیست. درمورد TOAST توی پستگرس یک سرچی بزنید). شکل کلی این ایندکس اینطوریه:

نکته درمورد هش ایندکس اینکه اگر تصادم(collision) داشته باشیم، توی یک خونه از باکت داریمشون. توی عکس بالا John Smith و Sandra Dee این وضعیت رو دارند.

نحوه تعریف:

CREATE INDEX [index_name] ON [table_name] USING HASH (column);
CREATE INDEX article_aaa_gist_idx ON article USING HASH(aaa);

Django:

from django.contrib.postgres.indexes import HashIndex
class Article(models.Model):
      ...
     class Meta:
            indexes = [HashIndex(fields=['name'])]

Bloom Index

به صورت رسمی نداریمش با extension میشه نصب کرد! شبیه هش هستش ولی با کمی متفاوت. برای ایندکس کردن چند ستونی مناسبه و برای این مورد سرعت خوبی هم داره. این جوریه که همه مقادیر اون ستون‌هارو میگیره و هش می‌کنه. بر خلافه B-Tree که ستون اول توی چند ستونی مهمه اینجا اینطوری نیست.

برای اینکه یک دید کلی هم داشته باشیم به این شکل تعریف میشه:

CREATE INDEX [index_name] ON [table_name] USING BLOOM (columns) WITH (length= , col1=, col2= , col3=);
CREATE INDEX a_simple_idx_ ON sample_table USING BLOOM (country, city, region, zipcode) WITH (length=80 , col1=7, col2=7 , col3=7, col4=7);

اینکه این عدد چطوری انتخاب میشه یک فرمول داره به این شکل m = −nlog2p / ln 2. اینکه چطوری اعداد به دست میاد رو از این لینک و برای توضیحات بیشتر این لینک رو بخونید!

همین! لبخند بزنین لطفا :)

منابع:

• https://www.youtube.com/watch?v=Xv0NFozBIbM&ab_channel=PostgresOpen
• https://www.youtube.com/watch?v=ncwqtsjlSBE&ab_channel=DjangoConUS