آوند — داده: SQL، مدل‌سازی و تحلیل برای تصمیم

فصل ۳ از ۸

پیشرفت ترم
۰٪

در این فصل چه یاد می‌گیری#

یک خط SQL می‌نویسیم و همان پرسشِ دو فصلِ قبل — که SCAN events می‌گرفت — SEARCH می‌شود. جواب همان ۱۱٬۴۲۱ می‌ماند و زمانش، در اجرای همین فصل، از حدودِ ۳۵ میلی‌ثانیه به کمتر از نیم میلی‌ثانیه می‌رسد.

بعد سراغِ چیزی می‌رویم که در بیشترِ آموزش‌ها گفته نمی‌شود: قیمتش. پایگاه دادهٔ ما با ۴٬۸۸۶ صفحه شروع می‌کند و با چهار index به ۱۳٬۵۶۱ صفحه می‌رسد — یعنی indexها بیشتر از خودِ داده جا می‌گیرند. و نوشتنِ ۲۰٬۰۰۰ سطرِ تازه، با همان چهار index، چند برابر کندتر می‌شود.

درختی که از یک ریشه به دو شاخه و از هر شاخه به دو شاخهٔ دیگر می‌رسد و کنارش یک ستونِ بلند از خانه‌های پشتِ سرِ هم

آخر این فصل می‌توانی:

  • با CREATE INDEX یک index بسازی و اثرش را با دو عدد و یک نقشه نشان بدهی
  • بگویی چرا ده برابر شدنِ داده، جست‌وجو را ده برابر کند نمی‌کند
  • index چندستونی بسازی و بگویی چرا ترتیبِ ستون‌ها همه‌چیز است
  • index روی یک عبارت بسازی
  • هزینهٔ حجم و هزینهٔ نوشتن را اندازه بگیری، نه حدس بزنی

قبل از شروع#

از فصلِ ۲: SCAN و SEARCH و USING COVERING INDEX و خواندنِ نقشهٔ اجرا. از فصلِ ۱: timed و پهنای نوسان.

دانه‌بندی: یک سطر از events یک رویداد است، و همهٔ عددهای این فصل روی همان ۴۰۰٬۰۰۰ سطر گرفته می‌شوند.

📓 نوت‌بوک: نوت‌بوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

جدول تعدادِ سطر زمانِ ساخت
events ۴۰۰٬۰۰۰ چند ثانیه
books ۴۰٬۰۰۰ کمتر از یک ثانیه
members ۱۲٬۰۰۰ آنی
branches ۸ آنی

۱. چرا نصف کردن، از اول تا آخر خواندن را می‌بَرد#

یک index یک نسخهٔ مرتب‌شده از یک ستون است، به‌علاوهٔ اشاره‌ای به سطرِ اصلی. تمامِ ارزشش از همان یک کلمه می‌آید: مرتب.

روی چیزی که مرتب است می‌شود نصف کرد. یک فهرستِ هزارتایی، و یک عددِ گمشده:

values = list(range(1, 1001))
target = 837
low, high, steps = 0, len(values) - 1, 0

while low <= high:
    steps += 1
    middle = (low + high) // 2
    if values[middle] == target:
        break
    if values[middle] < target:
        low = middle + 1
    else:
        high = middle - 1

print("اندازهٔ فهرست:", len(values))
print("پیدا شد در گامِ:", steps)
اندازهٔ فهرست: 1000
پیدا شد در گامِ: 9

نُه گام برای هزار عدد. اگر از اول تا آخر می‌خواندی، به‌طورِ متوسط پانصد گام لازم داشتی.

و نکتهٔ اصلی این نیست که نُه از پانصد کمتر است؛ این است که این عدد با بزرگ شدنِ فهرست تقریباً بزرگ نمی‌شود:

import math

for rows in (1_000, 400_000, 40_000_000):
    print(f"{rows:>12,} سطر → حداکثر {math.ceil(math.log2(rows)):>2} گام")
       1,000 سطر → حداکثر 10 گام
     400,000 سطر → حداکثر 19 گام
  40,000,000 سطر → حداکثر 26 گام

داده چهل‌هزار برابر شد و گام‌ها از ۱۰ به ۲۶ رسیدند. این همان چیزی است که یک index می‌خرد، و ساختارِ درونی‌اش — یک درختِ چندشاخه به نامِ B-tree — دقیقاً برای همین ساخته شده: هر مراجعه، بازهٔ باقی‌مانده را چند برابر کوچک می‌کند.

🌱 ریشه‌اش کجاست: عددی که با چند برابر شدنِ ورودی فقط چند واحد بالا می‌رود، اسمِ ریاضی دارد: لگاریتم. لگاریتم می‌پرسد «چند بار باید نصف کنم تا به یک برسم؟» و جوابش برای هزار می‌شود ۱۰ و برای چهل میلیون می‌شود ۲۶. اگر می‌خواهی این وارونهٔ توان را از پایه ببینی، ریشه ترمِ ۴ فصل ۸ دقیقاً همین است.

۲. CREATE INDEX، و دو عددی که ادعا را ثابت می‌کنند#

همان پرسشِ ماهِ سومِ فصلِ ۱. اول جواب و اندازهٔ فایل را ثبت می‌کنیم، قبل از هر تغییری:

SQL_MONTH = """
    SELECT COUNT(*) AS n
    FROM events
    WHERE happened_at >= ? AND happened_at < ?
"""
MONTH = ("2022-03-01", "2022-04-01")

before_answer = int(q(SQL_MONTH, MONTH).iloc[0, 0])
before_pages = con.execute("PRAGMA page_count").fetchone()[0]
before_ms = timed(SQL_MONTH, MONTH)

con.execute("CREATE INDEX idx_events_time ON events(happened_at)")
con.commit()

after_answer = int(q(SQL_MONTH, MONTH).iloc[0, 0])
after_pages = con.execute("PRAGMA page_count").fetchone()[0]
after_ms = timed(SQL_MONTH, MONTH)

print("پاسخ قبل :", before_answer)
print("پاسخ بعد :", after_answer)
print("صفحه‌های فایل قبل:", before_pages)
print("صفحه‌های فایل بعد:", after_pages)
print("صفحه‌هایی که این index گرفت:", after_pages - before_pages)
پاسخ قبل : 11421
پاسخ بعد : 11421
صفحه‌های فایل قبل: 4886
صفحه‌های فایل بعد: 7623
صفحه‌هایی که این index گرفت: 2737
show_plan(SQL_MONTH, MONTH)
print()
print("زمان قبل:", before_ms, "میلی‌ثانیه")
print("زمان بعد:", after_ms, "میلی‌ثانیه")
print("نسبت    :", round(before_ms / after_ms, 1), "برابر")
 id  parent                                                                               detail
  3       0 SEARCH events USING COVERING INDEX idx_events_time (happened_at>? AND happened_at<?)

زمان قبل: 35.4 میلی‌ثانیه
زمان بعد: 0.4 میلی‌ثانیه
نسبت    : 88.5 برابر

سه چیزی که این ترم می‌خواهد، هر سه اینجاست: زمانِ قبل، زمانِ بعد، و نقشهٔ اجرا. SCAN events شد SEARCH events USING COVERING INDEX، و پاسخ عوض نشد.

و عددِ چهارمی هم هست که کمتر کسی گزارشش می‌کند: این index بیش از نصفِ حجمِ کلِ پایگاه داده جا گرفت — ۲٬۷۳۷ صفحه در برابرِ ۴٬۸۸۶ صفحهٔ دادهٔ اصلی.

✅ چک کن: «پاسخ قبل» و «پاسخ بعد» باید دقیقاً برابر باشند. اگر نبودند، index مقصر نیست — پرسش یا داده را عوض کرده‌ای. یک index هرگز جوابِ یک پرسش را عوض نمی‌کند؛ فقط راهِ رسیدن به آن را عوض می‌کند.

۳. covering index: وقتی اصلاً به جدول سر نمی‌زند#

فصلِ قبل دیدیم که کلمهٔ COVERING یعنی همه‌چیزِ لازم داخلِ خودِ index بود. حالا اندازه‌اش می‌گیریم. این پرسش علاوه بر تاریخ، ستونِ days را هم می‌خواهد که در idx_events_time نیست:

SUM_YEAR = """
    SELECT COUNT(*) AS n, SUM(days) AS total
    FROM events
    WHERE happened_at >= ? AND happened_at < ?
"""
YEAR = ("2022-01-01", "2023-01-01")

print(q(SUM_YEAR, YEAR))
partial_ms = timed(SUM_YEAR, YEAR)
pages_before = con.execute("PRAGMA page_count").fetchone()[0]

con.execute("CREATE INDEX idx_events_time_days ON events(happened_at, days)")
con.commit()

covering_ms = timed(SUM_YEAR, YEAR)
pages_after = con.execute("PRAGMA page_count").fetchone()[0]
print("همان پاسخ بعد از index دوم:")
print(q(SUM_YEAR, YEAR))
print("صفحه‌هایی که index دوم گرفت:", pages_after - pages_before)
        n    total
0  133169  2733912
همان پاسخ بعد از index دوم:
        n    total
0  133169  2733912
صفحه‌هایی که index دوم گرفت: 2938
show_plan(SUM_YEAR, YEAR)
print()
print("با index تاریخ تنها  :", partial_ms, "میلی‌ثانیه")
print("با index تاریخ و days:", covering_ms, "میلی‌ثانیه")
 id  parent                                                                                    detail
  3       0 SEARCH events USING COVERING INDEX idx_events_time_days (happened_at>? AND happened_at<?)

با index تاریخ تنها  : 17.78 میلی‌ثانیه
با index تاریخ و days: 10.63 میلی‌ثانیه

کمی کمتر از دو برابر بهتر — و دو هزار و نهصد و سی‌وهشت صفحهٔ دیگر خرج شد.

دلیلش ساده است: در حالتِ اول، پایگاه داده برای هر یک از ۱۳۳٬۱۶۹ سطر دو مراجعه می‌کرد — یکی به index و یکی به خودِ جدول تا days را بردارد. در حالتِ دوم days هم داخلِ index است، پس مراجعهٔ دوم حذف شد.

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

۴. index چندستونی، و اینکه ترتیب همه‌چیز است#

یک index روی دو ستون مثلِ یک دفترچهٔ تلفن است که اول با نامِ خانوادگی و بعد با نام مرتب شده. با نامِ خانوادگی می‌شود سریع پیدا کرد؛ با نامِ کوچکِ تنها هیچ کمکی نمی‌کند.

BY_BOOK = "SELECT COUNT(*) AS n FROM events WHERE book_id = ?"
print("رویدادهای کتاب ۱۷:", int(q(BY_BOOK, (17,)).iloc[0, 0]))

con.execute("CREATE INDEX idx_wrong_order ON events(kind, book_id)")
con.commit()
wrong_ms = timed(BY_BOOK, (17,))
show_plan(BY_BOOK, (17,))

con.execute("DROP INDEX idx_wrong_order")
con.execute("CREATE INDEX idx_events_book ON events(book_id, kind)")
con.commit()
right_ms = timed(BY_BOOK, (17,))
print()
show_plan(BY_BOOK, (17,))
print()
print("index(kind, book_id):", wrong_ms, "میلی‌ثانیه")
print("index(book_id, kind):", right_ms, "میلی‌ثانیه")
رویدادهای کتاب ۱۷: 16
 id  parent                                           detail
  3       0 SCAN events USING COVERING INDEX idx_wrong_order

 id  parent                                                         detail
  3       0 SEARCH events USING COVERING INDEX idx_events_book (book_id=?)

index(kind, book_id): 14.31 میلی‌ثانیه
index(book_id, kind): 0.06 میلی‌ثانیه

دو index روی دقیقاً همان دو ستون، و صدها برابر اختلاف.

نقشه دلیلش را می‌گوید: با ترتیبِ اول، SQLite مجبور شد کلِ index را SCAN کند — چون book_id ستونِ دوم است و بدونِ دانستنِ kind نمی‌شود در آن پرید. با ترتیبِ دوم، SEARCH گرفت.

قاعده‌ای که از این درمی‌آید: ستونی که با = فیلتر می‌شود، اول. و اگر پرسش‌های مختلفی داری که هرکدام یک ستونِ متفاوت را فیلتر می‌کنند، یک index چندستونی جوابِ همه‌شان نیست.

۵. index روی یک عبارت#

گاهی فیلترِ تو روی خودِ ستون نیست، روی یک محاسبه روی آن است. SQLite می‌گذارد index را روی همان محاسبه بسازی:

BY_MONTH_TEXT = "SELECT COUNT(*) AS n FROM events WHERE substr(happened_at, 1, 7) = ?"
print("رویدادهای همان ماه، این بار با substr:",
      int(q(BY_MONTH_TEXT, ("2022-03",)).iloc[0, 0]))

expr_before = timed(BY_MONTH_TEXT, ("2022-03",))
show_plan(BY_MONTH_TEXT, ("2022-03",))

con.execute("CREATE INDEX idx_events_month ON events(substr(happened_at, 1, 7))")
con.commit()
expr_after = timed(BY_MONTH_TEXT, ("2022-03",))
print()
show_plan(BY_MONTH_TEXT, ("2022-03",))
print()
print("قبل:", expr_before, "| بعد:", expr_after,
      "| نسبت:", round(expr_before / expr_after, 1))
رویدادهای همان ماه، این بار با substr: 11421
 id  parent                                           detail
  3       0 SCAN events USING COVERING INDEX idx_events_time

 id  parent                                                detail
  4       0 SEARCH events USING INDEX idx_events_month (<expr>=?)

قبل: 34.45 | بعد: 0.52 | نسبت: 66.2

دقتِ لازم در سطرِ اولِ نقشه: قبل از ساختنِ index عبارتی، پرسش SCAN گرفت در حالی که idx_events_time روی همان ستون وجود داشت. یعنی آن index هیچ کمکی نکرد. جوابِ هر دو حالت همان ۱۱٬۴۲۱ است — همان عددی که در بخشِ ۲ با یک پرسشِ کاملاً متفاوت گرفتیم.

این مهم‌ترین نکتهٔ این بخش است و کلِ فصلِ بعد را می‌سازد: داشتنِ index روی یک ستون تضمین نمی‌کند که استفاده شود.

۶. قیمتِ اول: حجم#

چهار index ساختیم. حالا صورت‌حساب:

print(q("""
    SELECT name FROM sqlite_master
    WHERE type = ? AND name NOT LIKE 'sqlite_%'
    ORDER BY name
""", ("index",)))
print()
total_pages = con.execute("PRAGMA page_count").fetchone()[0]
page_size = con.execute("PRAGMA page_size").fetchone()[0]
print("صفحه‌های اول فصل :", before_pages)
print("صفحه‌های الان    :", total_pages)
print("سهم index‌ها     :", total_pages - before_pages, "صفحه")
print("اندازهٔ هر صفحه   :", page_size, "بایت")
                   name
0       idx_events_book
1      idx_events_month
2       idx_events_time
3  idx_events_time_days

صفحه‌های اول فصل : 4886
صفحه‌های الان    : 13561
سهم index‌ها     : 8675 صفحه
اندازهٔ هر صفحه   : 4096 بایت

۸٬۶۷۵ صفحهٔ index روی ۴٬۸۸۶ صفحهٔ داده. یعنی فایلی که ساختیم بیشتر از آنکه داده باشد، index است.

این لزوماً بد نیست — ولی یک تصمیم است، و تصمیمی که عددش را ندیده باشی تصمیم نیست.

۷. قیمتِ دوم: نوشتن#

هر index باید هر بار که سطری اضافه می‌شود به‌روز شود. پس ۲۰٬۰۰۰ سطر را دو جا می‌نویسیم: یک جدولِ خالیِ بدونِ index، و همین events که چهار index دارد.

sample = con.execute("""
    SELECT book_id, member_id, happened_at, kind, days
    FROM events ORDER BY id LIMIT 20000
""").fetchall()
new_rows = [(400000 + number,) + row for number, row in enumerate(sample, start=1)]

con.executescript("""
    DROP TABLE IF EXISTS events_plain;
    CREATE TABLE events_plain (
        id          INTEGER PRIMARY KEY,
        book_id     INTEGER NOT NULL,
        member_id   INTEGER NOT NULL,
        happened_at TEXT    NOT NULL,
        kind        TEXT    NOT NULL,
        days        INTEGER NOT NULL
    );
""")
con.commit()

start = time.perf_counter()
con.executemany("INSERT INTO events_plain VALUES (?, ?, ?, ?, ?, ?)", new_rows)
con.commit()
plain_ms = (time.perf_counter() - start) * 1000

start = time.perf_counter()
con.executemany("INSERT INTO events VALUES (?, ?, ?, ?, ?, ?)", new_rows)
con.commit()
indexed_ms = (time.perf_counter() - start) * 1000

print("سطرهای جدولِ بدون index:", int(q("SELECT COUNT(*) AS n FROM events_plain").iloc[0, 0]))
print("سطرهای events بعد از درج:", int(q("SELECT COUNT(*) AS n FROM events").iloc[0, 0]))
con.execute("DELETE FROM events WHERE id > 400000")
con.commit()
print("سطرهای events بعد از پاک‌سازی:", int(q("SELECT COUNT(*) AS n FROM events").iloc[0, 0]))
سطرهای جدولِ بدون index: 20000
سطرهای events بعد از درج: 420000
سطرهای events بعد از پاک‌سازی: 400000
print("درج در جدولِ بدون index:", round(plain_ms, 1), "میلی‌ثانیه")
print("درج در جدولِ چهار index:", round(indexed_ms, 1), "میلی‌ثانیه")
print("نسبت                  :", round(indexed_ms / plain_ms, 1), "برابر")
درج در جدولِ بدون index: 39.0 میلی‌ثانیه
درج در جدولِ چهار index: 707.7 میلی‌ثانیه
نسبت                  : 18.2 برابر

همان ۲۰٬۰۰۰ سطر، بیش از ده برابر گران‌تر. ولی همهٔ این نسبت سهمِ index نیست: events کلیدِ خارجی دارد و events_plain ندارد. سهمِ indexها حدودِ پنج برابر است، و دلیلش دقیقاً همان چیزی است که خواندن را سریع کرد: هر index باید مرتب بماند، پس هر سطرِ تازه باید در چهار درختِ جداگانه سرِ جای درستش نشانده شود.

پس معاملهٔ index این است: خواندن ارزان‌تر، نوشتن گران‌تر، فایل بزرگ‌تر. جدولی که روزی یک بار پر می‌شود و هزار بار خوانده می‌شود، معاملهٔ خوبی است. جدولی که هر ثانیه صد سطر می‌گیرد و هفته‌ای یک بار گزارش می‌دهد، معاملهٔ بدی.

🔧 اگر کار نکرد: اگر سلولِ بخشِ ۲ را دو بار اجرا کنی، بارِ دوم این را می‌گیری:

try:
    con.execute("CREATE INDEX idx_events_time ON events(happened_at)")
except Exception as error:
    print(type(error).__module__ + "." + type(error).__name__)
    print(error)
sqlite3.OperationalError
index idx_events_time already exists

رفعش CREATE INDEX IF NOT EXISTS است — همان IF NOT EXISTS که در ترمِ ۴ برای جدول‌ها دیدی. در یک اسکریپتِ مهاجرت این تقریباً همیشه شکلِ درست است، چون اسکریپتی که فقط یک بار قابلِ اجراست، اسکریپتِ خرابی است.

📏 اندازه بگیر: یک سطر یعنی چه؟ در events یک رویداد؛ در جدولِ sqlite_master یک index؛ و در شمارشِ صفحه‌ها یک صفحهٔ ۴٬۰۹۶ بایتی از فایل. با کدام شمارشِ دوم سنجیدی؟ با سه‌تا: پاسخِ پرسشِ بخشِ ۲ قبل و بعد از ساختنِ index دقیقاً همان ۱۱٬۴۲۱ ماند؛ ۱۳۳٬۱۶۹ و ۲٬۷۳۳٬۹۱۲ در بخشِ ۳ قبل و بعد از index دوم یکی بودند؛ و شمارشِ سطرهای events بعد از درج و بعد از پاک‌سازی به ۴۰۰٬۰۰۰ برگشت. چه کسی از قلم افتاد؟ ۲۶۶٬۸۳۱ رویدادی که خارجِ سالِ اول‌اند و در هیچ‌کدام از عددهای بخشِ ۳ نیستند — و در سمتِ هزینه، زمانِ ساختِ خودِ index، که ما اصلاً اندازه‌اش نگرفتیم و برای جدولِ صدمیلیونی مسئلهٔ اصلی است.

🤖 از دستیارت بپرس: «چرا یک index خواندن را سریع و نوشتن را کند می‌کند؟» بعد این را بپرس: «اگر روی هر ستونِ یک جدول یک index بسازم چه می‌شود؟» — جوابِ درست دستِ‌کم سه هزینه را می‌شمارد: حجم، کند شدنِ هر INSERT و UPDATE، و اینکه بیشترِ آن indexها هرگز استفاده نمی‌شوند. اگر جواب گفت «مشکلی ندارد، فقط جا می‌گیرد»، با نسبتِ درجِ بخشِ ۷ ردش کن.

واژه‌های تازهٔ این فصل#

کلمه تلفظ به حروف فارسی یعنی چه
index ایندکس نسخهٔ مرتب‌شدهٔ یک ستون، به‌علاوهٔ اشاره به سطرِ اصلی
B-tree بی‌تری درختِ چندشاخه‌ای که index با آن ساخته می‌شود
composite index کامپوزیت ایندکس index روی چند ستون، که ترتیبِ ستون‌هایش معنا دارد
expression index اکسپرشن ایندکس index روی یک محاسبه، نه روی خودِ ستون
page پیج صفحه؛ واحدِ ثابتِ ذخیره‌سازی در فایلِ پایگاه داده
write amplification رایت امپلیفیکیشن گران‌تر شدنِ هر نوشتن به‌خاطرِ ساختارهایی که باید به‌روز بمانند

تمرین‌ها

اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.

در فصل بعد#

این فصل نشان داد یک index چه می‌کند. بخشِ ۵ ولی یک چیزِ نگران‌کننده هم نشان داد: idx_events_time روی ستونِ happened_at بود، پرسش هم روی happened_at فیلتر می‌کرد، و نقشه گفت SCAN.

فصلِ بعد کلِ خانوادهٔ این حالت‌هاست: indexی که هست، درست ساخته شده، و کار نمی‌کند. از جمله بدترین حالتِ ممکن — پرسشی که نقشه‌اش SEARCH ... USING INDEX است، ظاهرش بی‌عیب است، و جوابش یک جدولِ خالی است در حالی که سطرِ موردِ نظر همان‌جا در جدول نشسته.

به آخر این فصل رسیدی!

اگر ساختی و جواب داد، این دکمه مال توست.