mukles.
All posts
  • PostgreSQL
  • Database
  • Backend

PostgreSQL Internals, Part 3: Index কীভাবে কাজ করে

B-Tree index ভেতরে কীভাবে সাজানো থাকে, Index Scan, Index Only Scan আর Bitmap Scan কখন কাজে লাগে, আর composite index-এ column order কেন এত গুরুত্বপূর্ণ।

Md Mukles Ali13 min read

এটা PostgreSQL Internals সিরিজের Part 3। Part 1 · Part 2 · Part 3 · Part 4 · Part 5

Part 1-এ আমরা দেখেছি PostgreSQL-এর table আসলে একটা heap: 8 KB-এর page-এর সারি, যার ভেতরে tuple রাখা থাকে, আর প্রতিটা tuple-কে খুঁজে পাওয়া যায় তার CTID দিয়ে, মানে (block number, line pointer)। Part 2-এ দেখেছি প্রতিটা tuple-এর header-এ xmin/xmax থাকে, আর snapshot ঠিক করে কোন version কার কাছে visible।

এই পর্বে এই সবকিছু একসাথে কাজে লাগবে। প্রশ্নটা সহজ: একটা নির্দিষ্ট row PostgreSQL দ্রুত খুঁজে পায় কীভাবে?

সমস্যা: index ছাড়া খোঁজা মানে সব page পড়া

ধরা যাক users table-এ 10 লাখ row আছে, আর আমরা চালালাম:

SELECT *
FROM users
WHERE email = 'mukles@gmail.com';

email column-এ কোনো index নেই। PostgreSQL জানে না mukles@gmail.com কোন page-এ আছে। Heap তো email বা id অনুযায়ী sorted না। তাই একটাই উপায় আছে: প্রথম page থেকে শেষ page পর্যন্ত সব tuple পড়ে condition মিলিয়ে দেখা।

Heap

Page 0    → সব tuple check
Page 1    → সব tuple check
Page 2    → সব tuple check
...
Page 9999 → সব tuple check

এটাকে বলে Seq Scan (sequential scan)। আমাদের দরকার মাত্র একটা row, অথচ পড়তে হচ্ছে পুরো table।

Index-এর কাজ হলো value থেকে সরাসরি tuple-এর location বের করে দেওয়া, যাতে পুরো heap পড়তে না হয়।

Index আর Heap আলাদা জিনিস

CREATE INDEX idx_users_email
ON users(email);

প্রথমে একটা জিনিস পরিষ্কার থাকা দরকার: index table-এর ভেতরে থাকে না। এটা নিজের page নিয়ে আলাদা একটা physical structure। Index-এর প্রতিটা entry-তে মূলত দুটো জিনিস থাকে:

indexed value  +  heap tuple-এর location (TID)

এই TID আর Part 1-এর CTID একই ধারণা: heap-এর কোন page-এর কোন line pointer।

B-Tree Index                       Heap
─────────────────────────          ──────────
a@gmail.com      → (0,1)   ───→    Page 0, LP 1
b@gmail.com      → (2,4)   ───→    Page 2, LP 4
mukles@gmail.com → (5,3)   ───→    Page 5, LP 3
z@gmail.com      → (9,7)   ───→    Page 9, LP 7

তাহলে query-টা এখন এভাবে চলতে পারে:

'mukles@gmail.com'
        ↓
   B-Tree Index
        ↓
   TID = (5,3)
        ↓
  Heap Page 5
        ↓
 Line Pointer 3
        ↓
     Tuple

কিন্তু একটা প্রশ্ন থেকে যায়। Index-এও তো 10 লাখ entry। PostgreSQL যদি index-এর ভেতরেও একটা একটা করে entry মিলিয়ে দেখে, তাহলে লাভ কী? এখানেই B-Tree-এর আসল কৌশল।

B-Tree: একটা sorted directory

B-Tree-কে একটা sorted directory হিসেবে ভাবা যায়। Binary search-এর মতো প্রতিটা ধাপে খোঁজার জায়গা ছোট হয়ে আসে, তবে এটা page-ভিত্তিক, কারণ database disk থেকে page ধরে পড়ে। B-Tree-ও 8 KB page দিয়েই তৈরি, আর page-গুলো তিন ধরনের ভূমিকায় থাকে:

                       ROOT PAGE
                  ┌────────────────┐
                  │   [ G | N ]    │
                  └──┬────┬────┬───┘
            < G      │    │    │     ≥ N
         ┌───────────┘    │    └────────────┐
         ▼                ▼ G–N             ▼
    INTERNAL          INTERNAL          INTERNAL
  ┌───────────┐    ┌─────────────┐    ┌───────────┐
  │  [C | E]  │    │ [I | K | M] │    │  [R | T]  │
  └─┬───┬───┬─┘    └─┬──┬───┬──┬─┘    └─┬───┬───┬─┘
    ▼   ▼   ▼         ▼  ▼  ▼  ▼        ▼   ▼   ▼

                     LEAF PAGES
  [a..] [c..] [e..]  ... [m..] ...  [r..] [t..]
     ⇄     ⇄     ⇄          ⇄          ⇄

Root page

Root-এ কোনো row-এর data থাকে না। এখানে থাকে কিছু boundary key আর প্রতিটা range-এর জন্য নিচের page-এর pointer। Root শুধু বলে দেয়: "কোন দিকে যেতে হবে?"

আমরা খুঁজছি mukles@gmail.com। Root-এ boundary G আর N। যেহেতু G ≤ m < N, তাই PostgreSQL শুধু মাঝের branch-এ নামে।

< G     ❌ বাদ
G – N   ✅ এখানে যাও
≥ N     ❌ বাদ

এক comparison-এ index-এর বিশাল একটা অংশ বাদ পড়ে গেল।

Internal page

মাঝের branch-এর internal page-এ আরও সূক্ষ্ম boundary: I | K | M। m পড়ে M-এর পরের range-এ, তাই আবার একটা branch বেছে নিচে নামা। আবার অনেক data বাদ।

বড় index-এ এরকম internal level একাধিক থাকতে পারে। আর ছোট index-এ root নিজেই leaf হতে পারে।

Leaf page

শেষে পৌঁছানো যায় leaf page-এ। আসল index entry, মানে value → TID, এখানেই থাকে, sorted অবস্থায়:

Leaf Page
┌──────────────────────────────────┐
│ martin@gmail.com   → (10,2)      │
│ mike@gmail.com     → (52,7)      │
│ mukles@gmail.com   → (83,4)  ✅  │
│ munna@gmail.com    → (91,2)      │
└──────────────────────────────────┘

(83,4) পেয়ে গেলে বাকিটা Part 1-এর চেনা পথ: heap-এর page 83, line pointer 4, তারপর tuple।

WHERE id = 847293 খোঁজার পুরো পথ:

flowchart TD
  R["Root page<br/>কোন range?"] --> I["Internal page<br/>আরও ছোট range"]
  I --> L["Leaf page<br/>key = 847293 → TID (5021, 7)"]
  L -->|TID| H["Heap page 5021<br/>item 7 = আসল row"]
  H --> V{"MVCC visible?"}
  V -->|হ্যাঁ| OUT(["Row ফেরত"])
  V -->|না| SKIP(["বাদ"])

কেন এটা এত দ্রুত

প্রতিটা page-এ শত শত key ধরে, তাই tree খুব চওড়া কিন্তু খুব কম উঁচু হয়। কয়েক মিলিয়ন row-এর index-এও সাধারণত root থেকে leaf পর্যন্ত মাত্র ৩–৪টা page পড়লেই চলে। 10 লাখ entry একটা একটা করে মেলানোর দরকার পড়ে না।

ব্যাপারটা dictionary-তে শব্দ খোঁজার মতো। PostgreSQL শব্দটা খুঁজতে কেউ Aardvark থেকে পড়া শুরু করে না। Dictionary sorted, তাই সরাসরি P-এর কাছে চলে যায়।

Range query-তেও কাজে লাগে

Leaf page-গুলো sorted, আর পাশের leaf page-এর সাথে link করা থাকে (ডায়াগ্রামের ⇄)। তাই range query-তে PostgreSQL প্রথম matching entry পর্যন্ত tree বেয়ে নামে, তারপর leaf level-এ পাশাপাশি হাঁটতে থাকে:

WHERE id > 500
WHERE created_at BETWEEN '2026-08-01' AND '2026-08-31'

একই কারণে ORDER BY email-এর মতো query-তেও B-Tree index আলাদা sort ছাড়াই sorted output দিতে পারে।

Index Scan

উপরের পুরো যাত্রাটাই হলো Index Scan:

Index-এ খোঁজা (Root → Internal → Leaf)
        ↓
TID পাওয়া
        ↓
Heap page-এ যাওয়া
        ↓
Tuple পড়া (আর visibility check)

একাধিক row match করলে PostgreSQL leaf-এ পরের entry নেয়, আবার heap-এ যায়, এভাবে চলতে থাকে।

এখানে একটা গুরুত্বপূর্ণ detail আছে: index entry-তে xmin/xmax থাকে না। Index জানে না কোন tuple version কোন snapshot-এর কাছে visible। তাই Index Scan-এ heap tuple পড়ার সময়েই MVCC visibility check হয় (Part 2-এর snapshot rule অনুযায়ী)। পরের অংশটা বুঝতে এই detail-টা লাগবে।

Index Only Scan

এবার একটু অন্য query:

SELECT email
FROM users
WHERE email = 'mukles@gmail.com';

আমাদের দরকার শুধু email, আর সেটা index-এর leaf entry-তেই আছে। তাহলে heap-এ যাওয়ার দরকার কী?

SELECT *      → id, name, created_at সব লাগবে → heap-এ যেতেই হবে → Index Scan
SELECT email  → দরকারি সব column index-এই আছে → Index Only Scan সম্ভব

যখন query-র দরকারি সব column index-এর মধ্যেই থাকে, PostgreSQL heap না ছুঁয়ে শুধু index থেকে result দিতে পারে। এটাই Index Only Scan।

কিন্তু visibility-র কী হবে?

এখানেই সমস্যা। আগেই বললাম index-এ MVCC তথ্য নেই। Index-এ mukles@gmail.com → (8,4) আছে, কিন্তু (8,4)-এর tuple-টা হয়তো কোনো transaction delete করে commit করে দিয়েছে, অথবা এমন transaction insert করেছে যেটা এখনো commit হয়নি। Heap-এ না গেলে PostgreSQL এটা জানবে কীভাবে?

প্রতিবার heap-এ গিয়ে xmin/xmax দেখলে তো Index Only Scan-এর পুরো লাভটাই চলে যায়।

Visibility Map

এর সমাধান হলো Visibility Map (VM)। প্রতিটা table-এর সাথে PostgreSQL একটা ছোট আলাদা file রাখে, যেখানে heap-এর প্রতিটা page-এর জন্য একটা bit থাকে: এই page কি all-visible?

Visibility Map

Page 0 → all-visible     ✅
Page 1 → all-visible     ✅
Page 2 → not all-visible ❌
Page 3 → all-visible     ✅

All-visible মানে এই page-এর প্রতিটা tuple সব transaction-এর কাছে visible। এখানে কোনো dead tuple নেই, কোনো uncommitted change নেই। তাই এই page-এর tuple-এর জন্য আলাদা করে visibility যাচাই করতে হয় না।

এখন Index Only Scan এভাবে চলে:

Index → mukles@gmail.com, TID (8,4)
              ↓
     VM: Page 8 all-visible?
        │
        ├─ হ্যাঁ ✅ → heap skip, index থেকেই result
        │
        └─ না  ❌ → Heap Page 8-এ গিয়ে tuple-এর visibility check

অর্থাৎ নাম Index Only Scan হলেও, page all-visible না হলে PostgreSQL-কে heap-এ যেতেই হয়।

EXPLAIN ANALYZE-এ "Heap Fetches"

এই heap visit কতবার হলো, সেটা EXPLAIN ANALYZE সরাসরি দেখায় (output সংক্ষেপিত):

Index Only Scan using idx_users_email on users
  Index Cond: (email = 'mukles@gmail.com'::text)
  Heap Fetches: 0
  • Heap Fetches: 0 মানে VM দিয়েই সব কাজ হয়ে গেছে, heap একবারও লাগেনি। আদর্শ অবস্থা।
  • Heap Fetches: 5000 মানে index থেকে data পাওয়ার পরেও 5,000 বার heap-এ গিয়ে visibility যাচাই করতে হয়েছে। বেশি কাজ, বেশি I/O-এর সম্ভাবনা।

তবে শুধু এই সংখ্যা দেখেই query slow বলা যায় না। মোট কত row, page cache-এ আছে কিনা, এসবও ব্যাপার।

VACUUM-এর সাথে সম্পর্ক

Visibility Map-এর bit কে set করে? মূলত VACUUM (আর autovacuum)। VACUUM page পরিষ্কার করার পর যদি দেখে সব tuple সবার কাছে visible, তাহলে সেই page all-visible mark করে। আবার কোনো INSERT, UPDATE বা DELETE ওই page-এ হাত দিলে bit-টা clear হয়ে যায়।

VACUUM চলে
   ↓
বেশি page all-visible হয়
   ↓
Index Only Scan-এ Heap Fetches কমে
   ↓
কম I/O

তাই যে table-এ খুব বেশি write হয় আর VACUUM পিছিয়ে থাকে, সেখানে Index Only Scan প্রত্যাশামতো লাভ দেয় না। VACUUM-এর বাকি কাজ Part 2-এ আছে।

ছোট একটা tip: query-তে index-এর key-র বাইরে কোনো extra column লাগলে CREATE INDEX ... ON users(email) INCLUDE (name) দিয়ে সেই column-টা leaf-এ রাখা যায়। এতে Index Only Scan-এর সুযোগ বাড়ে।

Bitmap Index Scan + Bitmap Heap Scan

Index Scan অল্প row-এর জন্য দারুণ। কিন্তু অনেক row match করলে কী হয়?

CREATE INDEX idx_orders_status ON orders(status);

SELECT *
FROM orders
WHERE status = 'PENDING';

ধরা যাক orders-এ 10 লাখ row, তার মধ্যে 1 লাখ PENDING।

Index Scan-এর সমস্যা: random heap access

Index থেকে TID আসে status-এর order-এ, heap-এর physical order-এ না:

PENDING → (100,5)
PENDING → (2,3)
PENDING → (500,7)
PENDING → (2,8)
PENDING → (100,9)
PENDING → (700,1)
...

প্রতিটা TID-এর জন্য সঙ্গে সঙ্গে heap-এ গেলে:

Page 100 → Page 2 → Page 500 → Page 2 → Page 100 → Page 700 ...

Heap-এ এলোমেলো লাফালাফি হয়, আর একই page (যেমন 2, 100) বারবার পড়তে হতে পারে। 1 লাখ row-এর জন্য এটা খুব ব্যয়বহুল।

Bitmap-এর idea

PostgreSQL তখন কাজটা দুই ধাপে ভাগ করে।

ধাপ ১ — Bitmap Index Scan: Index থেকে সব matching TID আগে জড়ো করে একটা bitmap বানায়। Bitmap-টা heap page অনুযায়ী সাজানো থাকে।

Bitmap (page order-এ)

Page 2   → tuple 3, 8
Page 100 → tuple 5, 9
Page 500 → tuple 7
Page 700 → tuple 1

ধাপ ২ — Bitmap Heap Scan: এবার heap page-গুলো physical order-এ একবার করে পড়ে:

Page 2   → tuple 3, 8
Page 100 → tuple 5, 9
Page 500 → tuple 7
Page 700 → tuple 1

TID-গুলো page অনুযায়ী sort করে প্রতিটা heap page একবারই visit করা হয়, আর access-টা এলোমেলোর বদলে প্রায় sequential হয়ে যায়।

তাই EXPLAIN-এ এই দুটো node সাধারণত জোড়ায় দেখা যায়:

Bitmap Heap Scan on orders
  Recheck Cond: (status = 'PENDING'::text)
  ->  Bitmap Index Scan on idx_orders_status
        Index Cond: (status = 'PENDING'::text)

ভেতরের node ঠিক করে "কোন কোন page লাগবে", আর বাইরের node "সেই page-গুলো দক্ষভাবে পড়ে"।

দুটো ছোট কিন্তু কাজের detail:

  • Match অনেক বেশি হলে bitmap memory-তে (work_mem) না ধরলে সেটা lossy হয়ে যায়। তখন tuple-এর বদলে শুধু page মনে রাখা হয়, আর heap-এ গিয়ে condition আবার মেলানো হয়। Recheck Cond সেই কাজটাই করে।
  • একাধিক index-এর bitmap একসাথে মেলানো যায় (BitmapAnd / BitmapOr)। যেমন WHERE status = 'PENDING' OR user_id = 10 হলে দুটো আলাদা index একসাথে কাজে লাগানো যায়।

Seq Scan কখন জেতে?

একটা সাধারণ ভুল ধারণা হলো "index থাকলেই PostgreSQL সেটা use করবে।" বাস্তবে তা না।

SELECT *
FROM users
WHERE is_active = true;

ধরা যাক 1 কোটি row-এর মধ্যে 90 লাখ is_active = true, আর is_active-এ index আছে। Index দিয়ে 90 লাখ TID বের করে বারবার heap-এ যাওয়ার চেয়ে পুরো table একবার শুরু থেকে শেষ পর্যন্ত পড়া অনেক সস্তা। কারণ sequential read random read-এর চেয়ে দ্রুত, আর প্রায় সব page তো পড়তেই হবে।

উল্টো দিকে:

SELECT * FROM users WHERE id = 10;

1 কোটির মধ্যে মাত্র ১টা row। এখানে Index Scan স্পষ্টভাবে ভালো: কয়েকটা index page আর একটা heap page পড়লেই কাজ শেষ। Bitmap বানানোর বাড়তি কাজেরও দরকার নেই।

একটা মোটামুটি intuition:

1,000,000 rows-এর table

খুব কম row match (যেমন 1)          → Index Scan
মাঝারি/অনেক row match (যেমন 1 লাখ) → Bitmap Index + Heap Scan
table-এর বড় অংশ match (যেমন 8 লাখ) → Seq Scan

এগুলো fixed rule না। Planner statistics দেখে প্রতিটা plan-এর cost estimate করে, আর সবচেয়ে সস্তাটা বেছে নেয়। কত row match করবে (selectivity), table-এর আকার, row কত চওড়া, আর heap-এ data index order-এর সাথে কতটা মিলিয়ে সাজানো (correlation), সবকিছুই এই হিসাবে ঢোকে। Planner কীভাবে এই সিদ্ধান্ত নেয়, সেটা Part 4-এ query lifecycle-এর অংশ হিসেবে দেখব।

Planner মোটামুটি এভাবে ভাবে (আসল সিদ্ধান্ত cost হিসাব করে, এটা শুধু অনুভূতি দেওয়ার জন্য):

flowchart TD
  Q(["WHERE condition"]) --> IX{"ব্যবহারযোগ্য index আছে?"}
  IX -->|না| SEQ["Seq Scan"]
  IX -->|হ্যাঁ| SEL{"কত শতাংশ row লাগবে?"}
  SEL -->|"খুব কম (কয়েকটা)"| IS["Index Scan"]
  SEL -->|"মাঝামাঝি"| BS["Bitmap Index Scan<br/>+ Bitmap Heap Scan"]
  SEL -->|"বেশিরভাগ"| SEQ
  IS --> COV{"সব column index-এ আছে<br/>আর page all-visible?"}
  COV -->|হ্যাঁ| IOS["Index Only Scan"]

Composite Index আর Leftmost Prefix

CREATE INDEX idx_orders
ON orders(user_id, status, created_at);

এটা তিনটা আলাদা index না। এটা একটাই B-Tree, যার key হলো তিনটা column-এর combination (user_id, status, created_at)।

কীভাবে sorted থাকে

Sort হয় dictionary-র মতো: প্রথমে user_id দিয়ে, user_id সমান হলে status দিয়ে, সেটাও সমান হলে created_at দিয়ে।

user_id   status      created_at
--------------------------------
1         CANCELLED   Aug 01
1         PENDING     Aug 01
1         PENDING     Aug 05
1         PENDING     Aug 10
2         CANCELLED   Aug 02
2         PENDING     Aug 03
2         PENDING     Aug 07
3         PENDING     Aug 01

এবার দেখা যাক বিভিন্ন query এই structure-এর সাথে কতটা মেলে।

WHERE user_id = 1

user_id = 1-এর সব entry পাশাপাশি আছে। Tree বেয়ে নেমে একটা contiguous range পড়লেই হলো।

WHERE user_id = 1 AND status = 'PENDING'

আরও সরু range: [1, PENDING, *], সেটাও পাশাপাশি।

WHERE user_id = 1
  AND status = 'PENDING'
  AND created_at >= '2026-08-05'

সবচেয়ে সরু: [1, PENDING, Aug 05] থেকে শুরু করে [1, PENDING, ...] শেষ হওয়া পর্যন্ত। এটা B-Tree-এর জন্য একদম স্বাভাবিক।

(user_id, status, created_at)
    ↑        ↑          ↑
 equality  equality    range

Leftmost prefix rule

Index (A, B, C) হলে:

A             ✅ ভালোভাবে কাজে লাগে
A + B         ✅
A + B + C     ✅

B             ⚠️ সাধারণত দুর্বল
C             ⚠️
B + C         ⚠️

কারণ B-Tree প্রথমে A দিয়ে sorted। শুধু WHERE status = 'PENDING' দিলে PENDING entry-গুলো এক জায়গায় থাকে না, প্রতিটা user_id-এর ভেতরে ছড়িয়ে থাকে:

[1, PENDING, ...]  ...  [2, PENDING, ...]  ...  [3, PENDING, ...]  ...

Tree বেয়ে নেমে একটা range পড়ার সুযোগ এখানে নেই। Composite index শুরুর (leftmost) column থেকে শুরু করে পরপর যতগুলো column-এ condition আছে, সেই prefix দিয়েই খোঁজার জায়গা ছোট করতে পারে।

তবে "কখনোই use করবে না" বলাও ঠিক না। Planner চাইলে পুরো index scan করে status filter করতে পারে, যদি সেটা table scan-এর চেয়ে সস্তা হয়। আর PostgreSQL 18 থেকে B-Tree skip scan আছে: leading column-এ distinct value কম হলে PostgreSQL প্রতিটা user_id-এর জন্য আলাদা করে লাফিয়ে লাফিয়ে খুঁজতে পারে। তবু এটা ঠিকমতো design করা index-এর বিকল্প না।

একইভাবে range condition-এর পরের column খোঁজার জায়গা ছোট করতে পারে না। যেমন (user_id, created_at, status) index-এ created_at-এ range দিলে status আর tree navigation-এ সাহায্য করে না, শুধু filter হিসেবে কাজ করে। এই কারণেই সাধারণ নিয়ম হলো equality column আগে, range column পরে।

Design rule

Composite index-এর column order table-এর column order দেখে ঠিক হয় না, query-র access pattern দেখে ঠিক হয়। Index design করার আগে প্রশ্ন করতে হয়:

কোন query সবচেয়ে বেশি চলে?
      ↓
কোন column-এ equality?
      ↓
কোন column-এ range?
      ↓
কোন ORDER BY লাগবে?
      ↓
তারপর column order ঠিক করো

Index-এর একটা খরচও আছে। প্রতিটা INSERT আর বেশিরভাগ UPDATE-এ index-ও update করতে হয়। কখন UPDATE নতুন index entry ছাড়াই হয়ে যায় (HOT update), সেটা Part 2-এ আছে।

নিজেকে যাচাই করো

  1. Index Only Scan-এর plan-এ Heap Fetches: 5000 দেখা গেল। কেন এমন হলো, আর কী করলে সংখ্যাটা কমতে পারে?
  2. (user_id, status, created_at) index-এ কোন query সবচেয়ে ভালো মেলে: (A) user_id = 10 AND status = 'PENDING' AND created_at >= '2026-08-01', (B) status = 'PENDING' AND created_at >= '2026-08-01', নাকি (C) created_at >= '2026-08-01'?
  3. 10 লাখ row-এর মধ্যে 1 লাখ row match করে। Planner কেন Index Scan-এর বদলে Bitmap Heap Scan বেছে নিতে পারে?

উত্তর: (1) Index entry-তে visibility তথ্য থাকে না। যে page-গুলো Visibility Map-এ all-visible mark করা নেই, সেগুলোর জন্য heap-এ গিয়ে tuple-এর visibility দেখতে হয়েছে। VACUUM (বা ঠিকমতো tune করা autovacuum) চালালে বেশি page all-visible হবে, আর heap fetch কমবে। (2) A, কারণ এটা leftmost prefix মেনে দুটো equality আর তারপর একটা range দেয়। B আর C leading column user_id বাদ দেয়। (3) Index Scan প্রতিটা TID-এর জন্য এলোমেলোভাবে heap page পড়ে, একই page বারবারও পড়তে পারে। Bitmap Heap Scan TID-গুলো page অনুযায়ী সাজিয়ে প্রতিটা page একবার, প্রায় sequential order-এ পড়ে।

সারসংক্ষেপ আর পরের পর্বে

  • Index heap থেকে আলাদা structure, যার leaf entry হলো value → TID।
  • B-Tree হলো root → internal → leaf, page দিয়ে তৈরি একটা sorted directory। প্রতিটা level-এ খোঁজার জায়গা ছোট হয়, তাই কয়েকটা page পড়েই leaf-এ পৌঁছানো যায়।
  • Index Scan মানে index থেকে TID নিয়ে heap-এ যাওয়া। Index Only Scan heap এড়াতে পারে, কিন্তু শুধু all-visible page-এর ক্ষেত্রে। Heap Fetches দেখায় কতবার heap-এ যেতে হয়েছে।
  • Bitmap Scan TID জড়ো করে page order-এ heap পড়ে, যা অনেক row match করলে কাজে লাগে।
  • Table-এর বড় অংশ লাগলে Seq Scan-ই সস্তা। শেষ সিদ্ধান্ত নেয় cost-based planner।
  • Composite index leftmost prefix মেনে চলে: equality আগে, range পরে।

এতক্ষণ আমরা দেখলাম data disk-এ কীভাবে থাকে আর কীভাবে খুঁজে পাওয়া যায়। Part 4-এ এক ধাপ পিছিয়ে বড় ছবিটা দেখব: একটা connection এলে PostgreSQL কোন process দিয়ে সেটা handle করে, shared buffers কী, আর একটা SQL query parser থেকে planner হয়ে executor পর্যন্ত কীভাবে যায়।

Working on something similar?

I'm happy to talk through architecture, AI features or production issues.

Email me →More posts