PostgreSQL Internals, Part 1: Heap, Page আর Tuple

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

বেশিরভাগ backend developer PostgreSQL-কে চেনে query দিয়ে। SELECT, JOIN, WHERE লিখি, result আসে। কিন্তু একসময় প্রশ্ন আসে, একই query কেন কখনো 2 ms নেয় আর কখনো 2 সেকেন্ড? Index দিলে কেন fast হয়? অনেক UPDATE-এর পরে table কেন ফুলে যায়?

এই প্রশ্নগুলোর উত্তর query-র ভাষায় পাওয়া যায় না। পাওয়া যায় PostgreSQL-এর ভিতরে, অর্থাৎ data কীভাবে disk-এ রাখা আছে সেখানে। Storage বুঝলে index, MVCC, VACUUM, সবকিছু একটা আরেকটার সাথে জুড়ে যায়। তাই এই সিরিজ শুরু হচ্ছে একদম নিচ থেকে: একটা table physically দেখতে কেমন।

এই পর্বে আমরা দেখব:

Table
  ↓
Heap
  ↓
Page (8 KB)
  ↓
Line Pointer
  ↓
Tuple
  └── বড় value? → TOAST

Table আসলে disk-এ কী?

ধরা যাক একটা সাধারণ table:

CREATE TABLE users (
  id    BIGINT,
  name  TEXT,
  email TEXT
);

আমরা logically এটাকে spreadsheet-এর মতো দেখি:

users
┌────┬────────┬───────────────────┐
│ id │ name   │ email             │
├────┼────────┼───────────────────┤
│ 1  │ Mukles │ m@example.com     │
│ 2  │ Rahim  │ r@example.com     │
│ 3  │ Karim  │ k@example.com     │
└────┴────────┴───────────────────┘

কিন্তু disk-এ PostgreSQL এভাবে rows আর columns-এর grid রাখে না। Physical দিক থেকে ব্যাপারটা এরকম:

users table
    ↓
Heap file
    ↓
┌──────────┐
│ Page 0   │  8 KB
├──────────┤
│ Page 1   │  8 KB
├──────────┤
│ Page 2   │  8 KB
├──────────┤
│ ...      │
└──────────┘

Heap কী?

PostgreSQL-এর সাধারণ table-এর storage-কে বলা হয় heap। এখানে heap মানে JavaScript বা C-এর memory heap না, আবার heap data structure (priority queue) ও না।

Heap হলো table-এর rows রাখার physical storage, যেটা অনেকগুলো সমান মাপের page দিয়ে তৈরি। "Heap" নামটা এসেছে "স্তূপ" অর্থে: rows কোনো নির্দিষ্ট order-এ সাজানো থাকে না, যেখানে জায়গা আছে সেখানে রাখা হয়। এই কথাটা একটু পরে আবার আসবে।

Page কী?

PostgreSQL disk থেকে একটা একটা row আলাদা করে পড়ে না। Storage-কে fixed-size page (বা block) হিসেবে manage করে। Default page size:

8 KB = 8192 bytes

Disk থেকে পড়া, memory-তে cache করা (shared buffers), আবার disk-এ লেখা, সবকিছু হয় page ধরে। একটা row লাগলেও PostgreSQL পুরো 8 KB page-টা নিয়ে আসে।

Tuple কী?

PostgreSQL-এর ভাষায় row-এর physical রূপকে বলা হয় tuple। আরও নির্দিষ্ট করে বললে, tuple হলো একটা row-এর একটা version। একটা logical row-এর একাধিক tuple থাকতে পারে, কেন সেটা নিচে দেখব।

তাহলে সম্পর্কটা দাঁড়াল:

Table  → logical ধারণা
Heap   → table-এর physical storage
Page   → heap-এর 8 KB-এর একেকটা টুকরা
Tuple  → page-এর ভিতরে রাখা row version

এই চার স্তরের সম্পর্কটাই PostgreSQL internals-এর ভিত্তি।

Index না থাকলে query কেন সব page পড়ে?

ধরা যাক users table-এ 10 লাখ row আছে, প্রতি page-এ মোটামুটি 100টা করে, অর্থাৎ প্রায় 10,000 page। email-এ কোনো index নেই।

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

PostgreSQL-এর কাছে এমন কোনো তালিকা নেই যেটা বলে দেয়:

❌ mukles@example.com → Page 9999

সে শুধু জানে table-এর 10,000টা page আছে। কোন page-এ এই email আছে, সেটা জানার কোনো উপায় নেই। তাই তাকে প্রথম থেকে শুরু করতে হবে:

Page 0    → প্রতিটা tuple check → মিলল না
Page 1    → প্রতিটা tuple check → মিলল না
Page 2    → প্রতিটা tuple check → মিলল না
...
Page 9999 → প্রতিটা tuple check → মিলল ✅

এটাই Sequential Scan। EXPLAIN চালালে দেখা যাবে:

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

Seq Scan on users  (cost=0.00..22500.00 rows=1 width=...)
  Filter: (email = 'mukles@example.com'::text)

একটা জিনিস খেয়াল রাখার মতো: match পেলেও Seq Scan সাধারণত থামে না। PostgreSQL জানে না email unique কিনা, আরও row মিলতে পারে। তাই LIMIT না থাকলে শেষ page পর্যন্ত পড়তে হয়। Index ছাড়া cost-টা table-এর মোট page সংখ্যার সমানুপাতিক, row যেখানেই থাকুক।

Index এখানে একটা directory-র কাজ করে। সে বলে দেয় কোন value কোন physical location-এ আছে:

email index
┌──────────────────────────────────┐
│ a@example.com      → (12, 4)     │
│ b@example.com      → (873, 1)    │
│ mukles@example.com → (9999, 37)  │
└──────────────────────────────────┘
                 ↓
         Heap Page 9999
                 ↓
               Tuple

ওই (9999, 37) জিনিসটা কী, সেটাই এই পর্বের মূল আলোচনা। Index-এর ভিতরটা আমরা দেখব Part 3-এ।

দুটো পথ পাশাপাশি:

flowchart LR
  Q(["WHERE email = 'm@example.com'"]) --> HAS{"email-এ index আছে?"}
  HAS -->|না| SEQ["Seq Scan<br/>Page 0 → 1 → 2 → … → 9999<br/>প্রতিটা tuple check"]
  HAS -->|হ্যাঁ| IDX["Index lookup<br/>key → CTID"]
  IDX --> ONE["শুধু দরকারি heap page পড়ো"]
  SEQ --> R(["Row"])
  ONE --> R

Page-এর ভিতরে কী থাকে?

একটা 8 KB page-এর ভিতরে শুধু rows থাকে না। Simplified layout:

           PostgreSQL Page (8 KB)
┌────────────────────────────────────┐
│ Page Header (24 bytes)             │
├────────────────────────────────────┤
│ LP 1 │ LP 2 │ LP 3 │ →             │  ← line pointers সামনে থেকে বাড়ে
│                                    │
│            FREE SPACE              │
│                                    │
│               ← │ Tuple 3 │        │  ← tuples পিছন থেকে বাড়ে
│ Tuple 2         │ Tuple 1          │
└────────────────────────────────────┘

চারটা অংশ:

১. Page Header

Page-এর শুরুতে ছোট একটা header থাকে। এতে page manage করার metadata থাকে, যেমন free space কোথায় শুরু আর কোথায় শেষ (pd_lower, pd_upper), page-এর শেষ পরিবর্তনের WAL position, checksum ইত্যাদি। Details মুখস্থ করার দরকার নেই, header হলো page-টা চালানোর হিসাবের খাতা।

২. Line Pointers

Header-এর ঠিক পরে থাকে line pointer (documentation-এ বলা হয় item identifier)-এর একটা array। প্রতিটা line pointer 4 bytes, আর তাতে লেখা থাকে একটা tuple page-এর ঠিক কোন offset-এ আছে এবং তার length কত।

LP #1 ───────────→ Tuple A (offset 8000)
LP #2 ───────────→ Tuple B (offset 7900)
LP #3 ───────────→ Tuple C (offset 7810)

৩. Tuples

আসল row data page-এর শেষ দিক থেকে শুরু করে পিছনের দিকে জমা হয়। প্রতিটা tuple-এর আবার দুটো অংশ:

Tuple
┌──────────────────────────────┐
│ Tuple Header (~23 bytes)     │ ← xmin, xmax, t_ctid, flags ...
├──────────────────────────────┤
│ 1 │ Mukles │ m@example.com   │ ← আসল column values
└──────────────────────────────┘

অর্থাৎ একটা tuple শুধু আমাদের column values না, সাথে PostgreSQL-এর নিজস্ব metadata-ও। এই header-এর xmin আর xmax দিয়েই MVCC কাজ করে, সেটা Part 2-এর বিষয়।

৪. Free Space

Line pointers সামনে থেকে বাড়ে, tuples পিছন থেকে। মাঝখানের ফাঁকা অংশটাই free space। দুই দিক মিলে গেলে page full, নতুন tuple আর এখানে ঢুকবে না।

Line pointer কেন দরকার?

সরাসরি "tuple আছে byte 7532-এ" না বলে মাঝখানে একটা layer রাখার কারণ হলো, page-এর ভিতরে tuple-এর physical position বদলাতে পারে।

ধরা যাক কিছু পুরোনো tuple মুছে যাওয়ার পর PostgreSQL page-টা compact করল, অর্থাৎ বাকি tuples সরিয়ে ফাঁকা জায়গাগুলো একসাথে করল:

আগে:   LP #1 ──→ Tuple A (offset 7000)
পরে:   LP #1 ──→ Tuple A (offset 7400)

Tuple সরেছে, কিন্তু শুধু line pointer-এর ভিতরের offset update হয়েছে। বাইরে থেকে কেউ যদি "Page 0-এর LP #1" হিসেবে tuple-টাকে চেনে, তার কাছে কিছুই বদলায়নি। Line pointer page-এর ভিতরের নড়াচড়া বাইরের দুনিয়া থেকে লুকিয়ে রাখে। এই বাইরের দুনিয়ার সবচেয়ে বড় সদস্য হলো index।

CTID: tuple-এর ঠিকানা

এখন একটা tuple-কে পুরো table-এর মধ্যে অনন্যভাবে চিনতে দুটো তথ্য লাগে: কোন page, আর সেই page-এর কোন line pointer। এই জোড়াটাই CTID (tuple identifier)।

ctid = (5, 3)
        │  │
        │  └── line pointer / item number 3
        │
        └───── block (page) number 5

পড়ার নিয়ম:

CTID (5, 3)
   ↓
Page 5
   ↓
Line Pointer #3
   ↓
Tuple

একটা সূক্ষ্ম কিন্তু জরুরি বিষয়: 3 সরাসরি tuple না, এটা line pointer-এর নম্বর। Tuple কোথায় আছে সেটা ওই line pointer বলে দেয়।

ctid প্রতিটা table-এর একটা hidden system column, চাইলেই দেখা যায়:

SELECT ctid, * FROM users;

 ctid  | id |  name
-------+----+--------
 (0,1) |  1 | Mukles
 (0,2) |  2 | Rahim
 (0,3) |  3 | Karim

(0,2) মানে Page 0-এর 2 নম্বর line pointer যে tuple-কে দেখাচ্ছে।

CTID ধরে একটা row পর্যন্ত পৌঁছানোর পথ:

flowchart LR
  I["Index entry<br/>key = 42"] -->|"CTID (5, 3)"| P["Heap page 5"]
  P --> LP["Line pointer 3<br/>offset + length"]
  LP --> T["Tuple<br/>আসল row"]

CTID কী কাজে লাগে?

সবচেয়ে বড় কাজ: B-Tree সহ PostgreSQL-এর index গুলো value-এর পাশে CTID রাখে। Index থেকে CTID পেলে PostgreSQL সরাসরি সেই page পড়ে, সেই line pointer ধরে tuple-এ পৌঁছে যায়। উপরের (9999, 37) ছিল ঠিক এটাই। আর line pointer আছে বলেই page compact হলেও index-কে update করতে হয় না।

CTID দিয়ে সরাসরি query-ও করা যায়, তখন plan-এ দেখা যায় Tid Scan:

SELECT * FROM users WHERE ctid = '(0,2)';

তবে CTID একটা physical location, permanent row ID না। UPDATE বা VACUUM FULL-এর পরে একই row-এর CTID বদলে যেতে পারে। তাই application-এ কখনো CTID store করে পরে row খোঁজার জন্য ব্যবহার করা উচিত না, সে কাজ primary key-এর।

Page-এর ভিতরটা নিজের চোখে দেখা

যারা আরও গভীরে দেখতে চান, pageinspect extension (superuser লাগে) দিয়ে একটা page-এর line pointers সরাসরি পড়া যায়:

CREATE EXTENSION pageinspect;

SELECT lp, lp_off, lp_len, t_xmin, t_xmax, t_ctid
FROM heap_page_items(get_raw_page('users', 0));

 lp | lp_off | lp_len | t_xmin | t_xmax | t_ctid
----+--------+--------+--------+--------+--------
  1 |   8128 |     63 |    750 |      0 | (0,1)
  2 |   8064 |     62 |    751 |      0 | (0,2)
  3 |   8000 |     62 |    752 |      0 | (0,3)

lp_off কমছে, অর্থাৎ tuples সত্যিই page-এর শেষ দিক থেকে সামনের দিকে জমা হচ্ছে।

Heap ordered না

এখন একটা স্বাভাবিক প্রশ্ন:

INSERT INTO users VALUES (1, 'Mukles', 'm@example.com');

PostgreSQL কি id = 1 দেখে row-টাকে Page 0-তে রাখতে বাধ্য?

না। Heap-এ rows কোনো column অনুযায়ী sorted থাকে না। নতুন tuple রাখার সময় PostgreSQL দেখে কোন page-এ যথেষ্ট free space আছে (এর জন্য প্রতিটা table-এর একটা Free Space Map থাকে), আর সেখানেই রাখে। কোথাও জায়গা না থাকলে table-এর শেষে নতুন page যোগ হয়।

Page 0 → id 1, 2, 3, 57, 912 ...
Page 1 → id 4, 5, 300, 8 ...
Page 2 → id 6, 7, 1044 ...

শুরুতে নতুন table-এ insert করলে rows প্রায় insert order-এ থাকে, তাই মনে হতে পারে heap sorted। কিন্তু DELETE, UPDATE আর VACUUM-এর পর পুরোনো page-এর খালি জায়গায় নতুন rows ঢুকতে থাকে, order ভেঙে যায়।

এর দুটো বাস্তব ফল আছে:

• ORDER BY ছাড়া SELECT-এর result-এর order-এর কোনো guarantee নেই। আজ যে order-এ আসছে, কাল সেই order-এ নাও আসতে পারে।
• "id দিয়ে sorted আছে, তাই PostgreSQL সরাসরি জায়গাটা বের করে ফেলবে" ভাবাটা ভুল। Sorted structure চাইলে সেটা index, heap না।

UPDATE আসলে নতুন tuple বানায়

Storage-এর একটা আচরণ এখনই জেনে রাখা দরকার, কারণ এটা পরের প্রায় সব পর্বে ফিরে আসবে। PostgreSQL-এ UPDATE পুরোনো tuple overwrite করে না, বরং row-এর একটা নতুন version, অর্থাৎ নতুন tuple লেখে।

Page 0

LP #2 ──→ Mukles       ← OLD version, ctid (0,2)
LP #4 ──→ Mukles Ali   ← NEW version, ctid (0,4)

পুরোনো tuple-এর header-এ xmax বসে যায় (কোন transaction এটাকে শেষ করল), আর তার t_ctid নতুন version-এর দিকে point করে। Page-এ জায়গা থাকলে নতুন version একই page-এ নতুন line pointer পায়, না থাকলে অন্য page-এ চলে যায়, যেমন (1,1)। দুই ক্ষেত্রেই CTID বদলায়, কারণ কিছুক্ষণ পুরোনো আর নতুন দুটো version-ই physically থাকতে হয়: অন্য কোনো চলমান transaction-এর হয়তো এখনো পুরোনোটা দেখা দরকার। কোন transaction কোন version দেখবে, আর পুরোনো version কখন পরিষ্কার হয়, সেটাই MVCC আর VACUUM, যা আমরা Part 2-এ বিস্তারিত দেখব।

TOAST: বড় value কোথায় যায়?

এখন একটা সমস্যা। Page মাত্র 8 KB, আর একটা tuple কখনো দুই page জুড়ে ছড়িয়ে থাকতে পারে না। তাহলে এই table-এ 10 MB-এর একটা article রাখলে কী হবে?

CREATE TABLE articles (
  id      BIGSERIAL,
  title   TEXT,
  content TEXT
);

এখানেই আসে TOAST: The Oversized-Attribute Storage Technique।

TOAST পুরো row-কে না, row-এর বড় variable-length column value-কে আলাদা করে সামলায়। দুটো কৌশল আছে:

1. Compression: value-টা compress করে tuple-এর ভিতরেই রাখা (default pglz, PostgreSQL 14 থেকে চাইলে lz4)।
2. Out-of-line storage: value-টা ছোট ছোট chunk-এ (প্রায় 2 KB করে) ভেঙে একটা আলাদা TOAST table-এ রাখা, আর main tuple-এ শুধু একটা ছোট pointer রাখা।

Main Heap Page
┌────────────────────────────┐
│ Tuple                      │
│ id      = 1                │
│ title   = PostgreSQL...    │
│ content = TOAST pointer ─────────┐
└────────────────────────────┘     │
                                   ↓
                     pg_toast.pg_toast_<oid>
                     ┌────────────────────┐
                     │ chunk 1            │
                     │ chunk 2            │
                     │ chunk 3            │
                     │ ...                │
                     └────────────────────┘

TOAST কখন শুরু হয়?

অনেকে ভাবেন tuple 8 KB পার হলে TOAST শুরু হয়। আসলে threshold অনেক কম। কোনো tuple মোটামুটি 2 KB-এর বেশি হলে (TOAST_TUPLE_THRESHOLD, যাতে একটা page-এ অন্তত চারটা tuple ধরে) PostgreSQL কাজ শুরু করে: প্রথমে বড় TOAST-able column গুলো compress করার চেষ্টা করে, তাতেও tuple প্রায় 2 KB-এর নিচে না নামলে সেগুলো একে একে out-of-line সরায়।

কয়েকটা গুরুত্বপূর্ণ নিয়ম:

• শুধু variable-length type (TEXT, VARCHAR, BYTEA, JSONB, array ইত্যাদি) TOAST-able। INTEGER, BIGINT, TIMESTAMP-এর মতো fixed-size type কখনো TOAST হয় না।
• ছোট value main tuple-এই থাকে। কলামের type TEXT দেখেই বলা যায় না যে data TOAST table-এ আছে।
• Main heap-এ tuple সবসময় থাকে। বাইরে যায় শুধু বড় value গুলো, তাদের জায়গায় থাকে pointer।
• প্রতিটা column-এর একটা storage strategy থাকে (PLAIN, MAIN, EXTERNAL, EXTENDED), TEXT-এর default EXTENDED, মানে compression আর out-of-line দুটোই চলবে। একটা TOAST-ed value সর্বোচ্চ 1 GB পর্যন্ত হতে পারে।

Application-এর দিক থেকে এগুলো পুরোপুরি transparent:

SELECT content FROM articles WHERE id = 1;

PostgreSQL নিজেই chunk গুলো জোড়া লাগিয়ে, decompress করে পুরো value ফেরত দেয়। TOAST table-এর সাথে manually join করতে হয় না।

TOAST-এর performance দিক

TOAST-এর একটা লুকানো সুবিধা আছে:

SELECT id, title FROM articles;

এখানে content select করা হয়নি, তাই PostgreSQL TOAST table ছুঁয়েও দেখে না। Main heap-এর tuple গুলো ছোট থাকায় একটা page-এ অনেক বেশি tuple ধরে, ফলে Seq Scan-এও কম page পড়তে হয়। বড় column বাদ দিয়ে query করলে TOAST-এর কারণে সেটা সত্যিই সস্তা হয়।

উল্টো দিকটাও মনে রাখা দরকার: SELECT * লিখলে প্রতিটা row-এর জন্য TOAST chunk পড়া আর decompress করার খরচ যোগ হয়। বড় TEXT বা JSONB column থাকা table-এ দরকারি column-গুলোই select করা ভালো অভ্যাস।

পুরো ছবি একসাথে

Table
  ↓
Heap  (ordered না, free space যেখানে সেখানে tuple)
  ↓
Pages (8 KB করে)
  ├── Page Header
  ├── Line Pointers ──┐
  ├── Free Space      │  CTID = (page, line pointer)
  └── Tuples ←────────┘
        ├── Header (xmin, xmax, t_ctid ...)
        └── Column data
              └── বড় variable-length value?
                       ↓
                     TOAST (compress / out-of-line)

সংক্ষেপে:

• Table disk-এ একটা heap, যা 8 KB page-এর সমষ্টি।
• Page-এর ভিতরে header, line pointers, free space আর tuples।
• CTID = (block number, line pointer number), একটা tuple version-এর physical ঠিকানা, permanent ID না।
• Index CTID রাখে বলেই সরাসরি tuple-এ পৌঁছাতে পারে; index না থাকলে Seq Scan-এ সব page পড়তে হয়।
• Heap sorted না, ORDER BY ছাড়া order-এর guarantee নেই।
• বড় column value TOAST-এ যায়, পুরো row না।

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

1. ctid = (12, 5) হলে 12 আর 5 কী বোঝায়, আর 5 কি সরাসরি tuple?
2. UPDATE users SET name = 'X' WHERE id = 1; চালানোর পরে কি row-টার CTID একই থাকবে?
3. একটা row-তে 3 MB-এর একটা TEXT value আছে। PostgreSQL কি পুরো row TOAST table-এ পাঠাবে?

উত্তর: (1) 12 হলো block বা page number, 5 হলো সেই page-এর line pointer নম্বর; tuple-টা কোথায় আছে সেটা line pointer #5 বলে দেয়, তাই 5 নিজে tuple না। (2) না, UPDATE একটা নতুন tuple version বানায়, যেটা নতুন line pointer পায় (একই page বা অন্য page-এ), তাই CTID বদলে যায়। (3) না, শুধু ওই বড় column value-টা compress হয়ে বা chunk আকারে TOAST table-এ যায়; main heap-এ tuple থেকে যায়, তাতে value-টার জায়গায় একটা pointer থাকে।

পরের পর্বে

আমরা দেখলাম UPDATE পুরোনো tuple রেখে দিয়ে নতুন একটা লেখে, ফলে একই row-এর একাধিক version একসাথে page-এ থাকতে পারে। তাহলে একটা SELECT কীভাবে ঠিক করে কোন version দেখাবে? আর পুরোনো version গুলো কে, কখন পরিষ্কার করে? এর উত্তর Part 2: MVCC আর VACUUM-এ, যেখানে tuple header-এর xmin, xmax আর snapshot নিয়ে কথা হবে।