Index আর query performance — composite, covering index আর EXPLAIN

১ · ডেটা বাড়লে খোঁজার খরচ — full scan বনাম index

পর্ব ১৯-এ দেখেছেন storage engine ডিস্কে ডেটা কীভাবে সাজায়, পর্ব ২০-এ বেছেছেন ডেটাবেসের ধরন। এই পর্বের প্রশ্ন নকশার স্তরের: কোন query-র জন্য কোন index, তার দাম কত, আর ডেটা ১০০ গুণ বাড়লেও query দ্রুত রাখা যায় কীভাবে। B+ tree-র গঠন আর plan-এর লাইন ধরে খুঁটিনাটি আছে DBMS কোর্সের Index — B+ tree, hash আর bitmap আর Index ডিজাইন — composite, covering আর EXPLAIN পর্বে।

পুরো পর্বে একটি উদাহরণ সাথে থাকবে: একটি অনলাইন খাবার ও মুদি-ডেলিভারি সেবা (কাল্পনিক)। orders টেবিলে প্রতিটি অর্ডারের গ্রাহক (customer), দোকান (merchant), অবস্থা (status), সময় (created_at), টাকার অঙ্ক আর ডেলিভারির ফোন নম্বর। গ্রাহক app-এ নিজের অর্ডার-ইতিহাস দেখেন, দোকানের ড্যাশবোর্ডে অপেক্ষমাণ অর্ডার আসে, আর support desk ফোনের শেষ চার অঙ্ক দিয়ে অর্ডার খোঁজে।

হিসাবটি সংখ্যায় — ১০ কোটি সারি

ডেটাবেস ডিস্ক থেকে সারি একটা একটা করে পড়ে না, পড়ে page ধরে — কয়েক KB-র একটি খণ্ড (PostgreSQL-এ ডিফল্টে 8 KB, MySQL InnoDB-তে 16 KB, SQLite-এ 4 KB; সংস্করণ আর সেটিংভেদে আলাদা)। ধরা যাক টেবিলে N = ১০^৮ (১০ কোটি) সারি, প্রতিটি প্রায় ১৬০ byte, তাই 8 KB-র একটি page-এ প্রায় ৫০টি সারি ধরে।

• Full scan: N ÷ ৫০ = ২০,০০,০০০ page — প্রায় ১৬ GB. SSD থেকে টানা সেকেন্ডে ~১ GB পড়া গেলে (ধরা যাক) প্রায় ১৬ সেকেন্ড। ডেটা দ্বিগুণ হলে সময়ও দ্বিগুণ — খরচ O(N).
• B-tree index: প্রতিটি page একটি node, আর একটি node-এ কয়েকশো key ধরে — এই সংখ্যাকে বলে fan-out. ধরা যাক f = ৩০০. মূল (root) থেকে পাতা (leaf) পর্যন্ত h স্তর পেরোলে সর্বোচ্চ f^hটি key পৌঁছানো যায়। দরকার f^h ≥ N, অর্থাৎ h ≥ log_f N = ln N ÷ ln f. এখানে ৩০০^৩ = ২.৭ × ১০^৭ < ১০^৮ ≤ ৩০০^৪, তাই h = ৪. একটি সারি পেতে ৪টি index page আর টেবিলের ১টি page — মোট ৫টি, ২০ লাখের জায়গায়। খরচ O(log N).
• বৃদ্ধির হার: ডেটা ১০০ গুণ বাড়লে উচ্চতা বাড়ে log_৩০০ ১০০ ≈ ০.৮ স্তর — বড়জোর একটি page বেশি। আর মূল আর মাঝের স্তরগুলো সাধারণত memory-তে (buffer pool-এ) থাকে, তাই বাস্তবে ডিস্কে যায় মাত্র ১–২টি পড়া।

একটি query ডেটাবেসের ভেতরে কোন পথে যায়, ছবিতে:

এবার একটি ছোট cost model চালিয়ে দেখুন — কয়েক মাপের টেবিলে কত page লাগে, কখন index হেরে যায়, আর প্রতিটি নতুন index লেখায় কত দাম যোগ করে। সব সংখ্যা ধরে নেওয়া (comment-এ লেখা), মাপা নয়:

// Index cost model: pages a query touches, and the price of k secondary indexes.
// Assumed (not measured): 8 KB pages, 50 rows per table page, B-tree fan-out 300,
// SSD: one random page ~0.1 ms, sequential reading ~1 GB/s (~0.008 ms per page).
const ROWS_PER_PAGE = 50, FANOUT = 300, RAND_MS = 0.1, SEQ_MS = 0.008, PAGE_B = 8192;
function height(n) {                        // B-tree levels, root to leaf, for n entries
  let pages = Math.ceil(n / FANOUT), h = 1;
  while (pages > 1) { pages = Math.ceil(pages / FANOUT); h++; }
  return h;
}
const f = x => x.toLocaleString("en-US");
const t = m => m < 1e3 ? m.toFixed(1) + " ms" : m < 6e4 ? (m / 1e3).toFixed(1) + " s" : (m / 6e4).toFixed(1) + " min";
console.log("A) one lookup or a 20-row range: full scan vs B-tree");
console.log("          rows  h     scan pages  scan time  point  20 rows  covering");
for (const n of [1e4, 1e6, 1e8, 1e10]) {
  const h = height(n), scan = Math.ceil(n / ROWS_PER_PAGE);
  console.log(f(n).padStart(14) + String(h).padStart(3) + f(scan).padStart(15) + t(scan * SEQ_MS).padStart(11) +
              String(h + 1).padStart(7) + String(h + 20).padStart(9) + String(h).padStart(10));
}
const N = 1e8, H = height(N), SCAN = N / ROWS_PER_PAGE;
console.log("\nB) N = 100,000,000: when does the index lose? (k matching rows, not covering)");
for (const k of [1e3, 1e5, 1e6, 1e7]) {
  const pages = H + Math.ceil(k / FANOUT) - 1 + k;   // index leaves + one random table page per row
  const idx = pages * RAND_MS, scan = SCAN * SEQ_MS;
  console.log(("k = " + f(k)).padEnd(15) + (k / N * 100 + "%").padEnd(7) + "index " + t(idx).padStart(8) +
              "   scan " + t(scan).padStart(6) + "   -> " + (idx < scan ? "index" : "scan"));
}
console.log("break-even k ~ " + f(Math.round(SCAN * SEQ_MS / RAND_MS)) + " rows");
const tableGB = SCAN * PAGE_B / 1e9, indexGB = Math.ceil(N / FANOUT) * PAGE_B / 1e9;
console.log("\nC) write price at N = 100,000,000 (table " + tableGB.toFixed(1) + " GB, one index ~" + indexGB.toFixed(1) + " GB)");
console.log("indexes  structures written per INSERT  path pages  disk");
for (const k of [0, 1, 3, 5]) {
  console.log(String(k).padStart(7) + String(1 + k).padStart(32) + String((1 + k) * H).padStart(12) +
              ((tableGB + k * indexGB).toFixed(1) + " GB").padStart(9));
}

A) one lookup or a 20-row range: full scan vs B-tree
          rows  h     scan pages  scan time  point  20 rows  covering
        10,000  2            200     1.6 ms      3       22         2
     1,000,000  3         20,000   160.0 ms      4       23         3
   100,000,000  4      2,000,000     16.0 s      5       24         4
10,000,000,000  5    200,000,000   26.7 min      6       25         5

B) N = 100,000,000: when does the index lose? (k matching rows, not covering)
k = 1,000      0.001% index 100.7 ms   scan 16.0 s   -> index
k = 100,000    0.1%   index   10.0 s   scan 16.0 s   -> index
k = 1,000,000  1%     index  1.7 min   scan 16.0 s   -> scan
k = 10,000,000 10%    index 16.7 min   scan 16.0 s   -> scan
break-even k ~ 160,000 rows

C) write price at N = 100,000,000 (table 16.4 GB, one index ~2.7 GB)
indexes  structures written per INSERT  path pages  disk
      0                               1           4  16.4 GB
      1                               2           8  19.1 GB
      3                               4          16  24.6 GB
      5                               6          24  30.0 GB

২ · Index-এর ধরন — নকশার চোখে একটি মানচিত্র

নকশার আলোচনায় একটি index-এর বিষয়ে তিনটি প্রশ্নই আসল: কী দিয়ে সাজানো, কোন প্রশ্নের উত্তর দেয়, আর কোন প্রশ্নে অচল. ভেতরের গঠন আলাদা পর্বের বিষয়; এখানে একটি মানচিত্র:

Clustered বনাম secondary — নকশার ফল। InnoDB-তে টেবিল primary key-এর ক্রমে সাজানো, তাই primary key-এর range একটানা page-এ পড়ে, আর প্রতিটি secondary entry-তে primary key থাকে। তাই primary key ছোট রাখুন — ১৬ byte-এর এলোমেলো UUID প্রতিটি secondary index-কে মোটা করে, আর গাছের এলোমেলো জায়গায় ঢুকে page split বাড়ায় (সময়-ক্রমের ID পর্ব ২৩-এ)। PostgreSQL-এ টেবিল heap; CLUSTER একবার সাজায়, পরের লেখায় সেই ক্রম থাকে না।

Hash বনাম B-tree. Hash index শুধু “ঠিক এই key” প্রশ্নে দ্রুত; “গত সাত দিনের অর্ডার” বা “নতুন আগে” পারে না। তাই relational ডেটাবেসে ডিফল্ট B-tree. PostgreSQL-এ hash index আছে (সংস্করণ ১০ থেকে crash-safe); InnoDB-তে নিজে hash index বানানো যায় না; ভেতরে একটি adaptive hash index নিজে থেকে তৈরি হতে পারে (ডিফল্টে চালু না বন্ধ, তা সংস্করণভেদে আলাদা)। পুরো ডেটাবেসটাই hash-এ সাজানো key-value store-এর কথা পর্ব ২০-এ।

Unique index — গতি নয়, নিয়ম। “আগে খুঁজে দেখি, না থাকলে INSERT” — দুটি অনুরোধ একসাথে এলে দুজনেই “নেই” দেখে, আর দুটি সারি ঢোকে; ব্যাংকের দুই কাউন্টারে একই চেক একসাথে জমা নেওয়ার মতো। সমাধান ডেটাবেসকেই বিচারক বানানো: UNIQUE (customer_id, idem_key) থাকলে দ্বিতীয় INSERT ব্যর্থ হয়, বা ON CONFLICT DO NOTHING-এ বাদ যায়। পর্ব ০৮-এর idempotency key এর ওপরই দাঁড়িয়ে; delivery semantics পর্ব ৩৪-এ।

-- composite + covering: search by (customer_id, created_at), carry status and amount in the leaves
CREATE INDEX idx_orders_cust_time ON orders (customer_id, created_at) INCLUDE (status, amount);
-- partial: only the ~6% of rows that are still pending
CREATE INDEX idx_orders_pending ON orders (merchant_id, created_at) WHERE status = 'pending';
-- expression: the query must say lower(email) exactly
CREATE INDEX idx_users_email_lower ON users (lower(email));
-- unique as a rule: one order per (customer, idempotency key)
CREATE UNIQUE INDEX uq_orders_idem ON orders (customer_id, idem_key);
-- hash: equality only
CREATE INDEX idx_sessions_token ON sessions USING hash (token);

৩ · Composite index আর leftmost-prefix নিয়ম

আসল query-তে সাধারণত একাধিক শর্ত: “গ্রাহক ৪২-এর অর্ডার, নতুন আগে”। এর জন্য একাধিক কলামের একটিই index — composite index. পর্ব ০৬-এ composite key (board, year, roll) দেখেছিলেন: তিনটি দিলে সরাসরি একটি সারি, শুধু roll দিলে পুরো টেবিল। এখানে নিয়মটিকে নকশার হাতিয়ার বানাব।

নিচে (customer_id, created_at) index-এর ১০টি entry — সাজানো ক্রমে, যেমন leaf page-এ থাকে। চারটি প্রশ্নে কতগুলো entry পড়তে হয়, ধাপে ধাপে দেখুন:

এবার ৫০,০০০ সারির আসল টেবিলে একই পরীক্ষা। প্রতিটি এডিটরের শুরুতে নিচের নমুনা ডেটাবেস তৈরি হয়ে যায় (“নমুনা ডেটাবেস” খুলে দেখতে পারেন): recursive CTE দিয়ে ১ থেকে ৫০,০০০ পর্যন্ত i, আর ভাগশেষের সূত্রে মান — ৫,০০০ গ্রাহকের প্রত্যেকের ঠিক ১০টি অর্ডার, ২০০টি দোকান, প্রতি ৭ মিনিটে একটি অর্ডার (২০২৬-এর জানুয়ারি থেকে আগস্টের শেষ), আর প্রায় ৬% pending. এটি single-node SQLite — query plan আর ফল দেখায়, সময় মাপে না; বহু যন্ত্রে ভাগ করা ডেটাবেসের আচরণও দেখায় না। EXPLAIN QUERY PLAN query না চালিয়েই পথটি বলে।

-- Before: no secondary index at all
EXPLAIN QUERY PLAN
SELECT order_id, created_at, amount FROM orders
WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 3;

CREATE INDEX idx_cust_time ON orders(customer_id, created_at);

-- (a) customer_id only, sorted by the second column
EXPLAIN QUERY PLAN
SELECT order_id, created_at, amount FROM orders
WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 3;
-- (b) customer_id = ? and a range on created_at
EXPLAIN QUERY PLAN
SELECT order_id, amount FROM orders
WHERE customer_id = 42 AND created_at >= '2026-06-01';
-- (c) created_at alone: the leading column is missing
EXPLAIN QUERY PLAN
SELECT order_id, amount FROM orders WHERE created_at >= '2026-08-31';

SELECT order_id, created_at, amount FROM orders
WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 3;

(a) SEARCH orders USING INDEX idx_cust_time (customer_id=?)
(b) SEARCH orders USING INDEX idx_cust_time (customer_id=? AND created_at>?)
(c) SCAN orders

৪ · Covering index — টেবিলে না গিয়ে উত্তর

অংশ ১-এর হিসাবে ২০টি সারির range-এ page লেগেছিল h + ২০. কারণ secondary index-এর entry-তে থাকে শুধু key আর সারির ঠিকানা। Query যদি amount-ও চায়, প্রতিটি entry থেকে টেবিলে যেতে হয় — table lookup, সাধারণত এলোমেলো জায়গায় একটি করে page. আর query-র দরকারি সব কলাম index-এই থাকলে টেবিলে যাওয়ার দরকারই নেই — এটাই covering index. Plan-এ SQLite লেখে USING COVERING INDEX, PostgreSQL লেখে Index Only Scan, MySQL-এর Extra কলামে Using index.

CREATE INDEX idx_cust_time ON orders(customer_id, created_at);
-- 1) The history page wants time and amount
EXPLAIN QUERY PLAN
SELECT created_at, amount FROM orders
WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;
-- 2) Put amount into the index too: the query needs nothing else
CREATE INDEX idx_cust_time_amt ON orders(customer_id, created_at, amount);
EXPLAIN QUERY PLAN
SELECT created_at, amount FROM orders
WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;
-- 3) SELECT * needs every column again
EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;
-- 4) A shop dashboard: count and total per status
EXPLAIN QUERY PLAN
SELECT status, COUNT(*), SUM(amount) FROM orders WHERE merchant_id = 7 GROUP BY status;
CREATE INDEX idx_merch_status_amt ON orders(merchant_id, status, amount);
EXPLAIN QUERY PLAN
SELECT status, COUNT(*), SUM(amount) FROM orders WHERE merchant_id = 7 GROUP BY status;
SELECT status, COUNT(*) AS n, SUM(amount) AS taka FROM orders
WHERE merchant_id = 7 GROUP BY status;

1) SEARCH orders USING INDEX idx_cust_time (customer_id=?)
2) SEARCH orders USING COVERING INDEX idx_cust_time_amt (customer_id=?)
3) SEARCH orders USING INDEX idx_cust_time (customer_id=?)
4) SCAN orders
   USE TEMP B-TREE FOR GROUP BY
   SEARCH orders USING COVERING INDEX idx_merch_status_amt (merchant_id=?)

PostgreSQL (১১ থেকে) আর SQL Server-এ আরও পরিষ্কার উপায় INCLUDE: বাড়তি কলাম শুধু leaf-এ বসে, key-তে নয় — গাছের মাঝের স্তর সরু থাকে, আর unique-এর নিয়মেও সেগুলো গোনা হয় না। InnoDB-তে প্রতিটি secondary entry-তে primary key থাকে, তাই primary key-এর কলাম চাওয়া query অনেক সময় এমনিই covering. PostgreSQL-এ সারিটি সবার কাছে দৃশ্যমান কি না, তা থাকে visibility map-এ (MVCC, পর্ব ২৪); সদ্য বদলানো page-এর জন্য Index Only Scan-কেও টেবিলে যেতে হয় — plan-এর Heap Fetches-এ দেখা যায়, আর VACUUM সেটি কমায়।

৫ · Access pattern থেকে index — query-র তালিকা ধরে নকশা

“কোন কলামে index দেব?” প্রশ্নটি ভুল দিক থেকে শুরু। সঠিক প্রশ্ন: “কোন query, কত ঘনঘন, কত দ্রুত চাই?” পর্ব ০৬-এর নকশার ধাপে data model-এর পাশেই এই তালিকা লেখা হয় — প্রতিটি access pattern-এর জন্য query-র রূপ, আনুমানিক QPS আর latency-র লক্ষ্য (পর্ব ০২)। তারপর পাঁচটি ধাপ:

1. কলাম তিন ভাগে: সমতার শর্ত (=, ছোট IN), range বা sort-এর কলাম, আর শুধু ফেরত দেওয়ার কলাম।
2. ক্রম: সমতার কলাম আগে, তারপর range বা sort; ঘনঘন চলা হলে শেষে ফেরতের কলাম, যাতে index covering হয়।
3. মেলানো: একটির prefix আরেকটির কাজ করলে আলাদা index নয়; দ্বৈত আর অব্যবহৃত index মুছুন।
4. দাম গোনা: প্রতি INSERT-এ কয়টি কাঠামো, আকার কত, লেখার QPS কত।
5. যাচাই: আসল মাপের ডেটায় EXPLAIN, deploy-এর পর প্রতিটি query-র p99.

ধাপ ২-এর একটি সূক্ষ্মতা। Range আর sort একই কলামে হলে — “গত সাত দিনের অর্ডার, নতুন আগে” — দ্বিধা নেই। আলাদা কলামে হলে — WHERE merchant_id = ? AND amount > 1000 ORDER BY created_at — (merchant_id, amount, created_at) কম entry পড়ে কিন্তু আলাদা sort লাগে; (merchant_id, created_at, amount) sort বাঁচায় আর LIMIT পেয়েই থামে, কিন্তু বেশি entry পেরোয়। MongoDB-র নির্দেশিকা এজন্য “Equality, Sort, Range” (ESR) ক্রমের পরামর্শ দেয়। কোনটি জিতবে, তা মেলা সারি আর LIMIT-এর ওপর নির্ভর করে — মেপে দেখুন।

এবার উদাহরণের সেবায় তিনটি access pattern থেকে index বাছাই, ধাপে ধাপে (QPS-গুলো ধরে নেওয়া):

স্টেপারের নকশা নমুনা টেবিলে যাচাই করুন। P3-এর জন্য idem_key কলাম যোগ করা হলো; শেষে একই অনুরোধ দুবার আসে, যেমন timeout-এর পর app আবার পাঠালে হয়:

-- P1: a customer's history, newest first
CREATE INDEX idx_cust_time ON orders(customer_id, created_at);
-- P2: a shop's queue of pending orders (about 6% of rows), oldest first
CREATE INDEX idx_pending ON orders(merchant_id, created_at) WHERE status = 'pending';
-- P3: retry-safe order creation
ALTER TABLE orders ADD COLUMN idem_key TEXT;
CREATE UNIQUE INDEX uq_cust_key ON orders(customer_id, idem_key);

EXPLAIN QUERY PLAN SELECT order_id, created_at, amount FROM orders
WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;
EXPLAIN QUERY PLAN SELECT order_id, created_at FROM orders
WHERE merchant_id = 7 AND status = 'pending' ORDER BY created_at;
SELECT order_id, created_at FROM orders
WHERE merchant_id = 7 AND status = 'pending' ORDER BY created_at LIMIT 3;

-- The app timed out and sent the same order again (the server made a new order_id)
INSERT INTO orders VALUES (50001, 42, 7, 'pending', '2026-09-01 02:00:00', 650,
  '01304398618', 'K-7a1f') ON CONFLICT DO NOTHING;
INSERT INTO orders VALUES (50002, 42, 7, 'pending', '2026-09-01 02:00:05', 650,
  '01304398618', 'K-7a1f') ON CONFLICT DO NOTHING;
SELECT order_id, idem_key FROM orders WHERE customer_id = 42 AND idem_key = 'K-7a1f';

লেখার দাম — write amplification, জায়গা আর bloat

অংশ ১-এর অংশ C মনে করুন: k-টি secondary index মানে প্রতি INSERT-এ k + ১টি কাঠামো লেখা — write amplification. সাথে আরও দাম:

• UPDATE: index-এর কলাম বদলালে সেই index-এ পুরোনো entry মুছে নতুন বসানো। PostgreSQL-এ সারির নতুন সংস্করণ প্রায়ই নতুন জায়গায় লেখা হয়, তাই কলাম না বদলালেও সব index-এ নতুন entry লাগতে পারে — ব্যতিক্রম HOT update (সংস্করণ ৮.৩ থেকে)।
• জায়গা আর memory: ১০ কোটি সারিতে একটি সরু index প্রায় ২.৭ GB (অংশ ১-এর মডেল); সব index memory-র জন্য একে অপরের সাথে লড়ে।
• Index bloat: মোছা-বদলানো entry-র ফাঁকা জায়গা, আর page split-এর পর আধা-খালি page. এলোমেলো key (যেমন UUIDv4) নতুন entry গাছের সবখানে ছড়ায়; সময়-ক্রমের key ডান প্রান্তে জমে। প্রতিকার: PostgreSQL-এ VACUUM আর REINDEX CONCURRENTLY (১২ থেকে), MySQL-এ OPTIMIZE TABLE.
• চালু সিস্টেমে বানানো: বড় টেবিলে সাধারণ CREATE INDEX লেখা আটকে রাখতে পারে; PostgreSQL-এ CREATE INDEX CONCURRENTLY, InnoDB-তে online DDL — ধীর, কিন্তু লেখা চলে। Zero-downtime migration পর্ব ৫৩-এ।

৬ · Query plan পড়া — EXPLAIN, selectivity আর optimiser-এর সিদ্ধান্ত

Index বানালেই ডেটাবেস সেটি ব্যবহার করবে, এমন নয়। সিদ্ধান্ত নেয় query optimizer — সম্ভাব্য পথগুলোর খরচ অনুমান করে সবচেয়ে সস্তাটি বাছে। বাছাই করা পথটির নাম query plan, আর দেখার কমান্ড EXPLAIN. PostgreSQL-এর EXPLAIN ANALYZE query-টি সত্যিই চালিয়ে অনুমানের পাশে আসল সময় আর আসল সারির সংখ্যা বসায় (UPDATE বা DELETE-এ তাই transaction-এর ভেতরে চালিয়ে ROLLBACK করুন); MySQL ৮.০.১৮ থেকে EXPLAIN ANALYZE আছে। একই ধারণার তিন ভাষা:

নামগুলো সংস্করণভেদে কিছুটা আলাদা; লাইন ধরে পড়ার নিয়ম DBMS কোর্সের Index ডিজাইন পর্বে। নকশাকারের চারটি প্রশ্নই যথেষ্ট: পুরো টেবিল নাকি index? অনুমিত আর আসল সারি কাছাকাছি কি না? আলাদা sort আছে কি না? কতগুলো সারি পড়ে কতগুলো ফেরত — PostgreSQL-এর Rows Removed by Filter বড় হলে index ঠিক কাজ করছে না।

Selectivity আর cardinality

একটি কলামের cardinality হলো তাতে কতগুলো ভিন্ন মান; একটি শর্তের selectivity হলো শর্তটি মোট সারির কত ভাগ রাখে। নমুনা টেবিলে customer_id-এর cardinality ৫,০০০, তাই customer_id = 42 রাখে ৫০,০০০-এর ১০টি — ০.০২%, চমৎকার। status-এর cardinality ৩, আর status = 'delivered' রাখে ৪২,৭৮০টি — প্রায় ৮৬%. অংশ ১-এর অংশ B বলেছিল: এত সারি এলোমেলো table lookup-এ আনার চেয়ে টানা scan সস্তা, তাই PostgreSQL-এর মতো cost-based optimizer এমন শর্তে সাধারণত Seq Scan বাছে। SQLite-এর planner সরলতর — এই টেবিলে status-এ index বানিয়ে ANALYZE চালানোর পরও (statistics-এ 50000 16667) সে status = 'delivered'-এ index-ই নিয়েছে। আচরণ ডেটাবেসভেদে আলাদা; নিজের ডেটাবেসে plan দেখে নিন।

Optimizer index উপেক্ষা করলে কারণ সাধারণত এগুলোর একটি:

• মিল অনেক বেশি (কম selectivity), বা টেবিল ছোট — scan সত্যিই সস্তা।
• পুরোনো statistics: লাখো সারি আমদানির পর অনুমান ভুল — ANALYZE চালান।
• শর্ত index-এর ভাষায় লেখা নয়: ফাংশন, টাইপ, শুরুর wildcard, আলাদা কলামে OR — অংশ ৭।
• মানভেদে আলাদা ছবি: একটি বড় দোকানের অর্ডার মোটের ৪০% হলে একই query ছোট দোকানে দ্রুত, বড়টিতে ধীর (hot key); prepared statement-এর সাধারণ plan সব মানে সমান ভালো নাও হতে পারে।

সব মিলিয়ে একটি ধীর query সারানোর পথ — ১০ কোটি সারির টেবিলে (ধরা যাক)। Plan-এর লেখা নমুনা টেবিলে SQLite-এ যাচাই করা; page আর সময় অংশ ১-এর মডেল থেকে:

৭ · Index ভেস্তে দেওয়ার চেনা ভুল

Index আছে, অথচ plan বলছে SCAN — এর সবচেয়ে সাধারণ কারণ query-র লেখা। Index-এ সাজানো আছে কলামের মান; শর্ত যদি মানটিকে বদলে তারপর মেলায়, সাজানো ক্রম কাজে লাগে না। যে শর্ত index ব্যবহার করতে পারে, তাকে বলে sargable. প্রথম দুটি ভুল আর তাদের সারানো রূপ:

CREATE INDEX idx_created ON orders(created_at);
CREATE INDEX idx_phone   ON orders(delivery_phone);
-- 1) A function wrapped around the indexed column
EXPLAIN QUERY PLAN SELECT order_id, amount FROM orders
WHERE date(created_at) = '2026-03-15';
-- Fixed: a half-open range on the bare column
EXPLAIN QUERY PLAN SELECT order_id, amount FROM orders
WHERE created_at >= '2026-03-15' AND created_at < '2026-03-16';
SELECT COUNT(*) AS by_function FROM orders WHERE date(created_at) = '2026-03-15';
SELECT COUNT(*) AS by_range FROM orders
WHERE created_at >= '2026-03-15' AND created_at < '2026-03-16';
-- 2) Leading wildcard: the support desk types the last 4 digits
EXPLAIN QUERY PLAN SELECT order_id, amount FROM orders
WHERE delivery_phone LIKE '%8618';
-- Fixed: index exactly the expression the query asks for
CREATE INDEX idx_phone_last4 ON orders(substr(delivery_phone, -4));
EXPLAIN QUERY PLAN SELECT order_id, amount FROM orders
WHERE substr(delivery_phone, -4) = '8618';
SELECT COUNT(*) AS by_last4 FROM orders WHERE substr(delivery_phone, -4) = '8618';

আরও তিনটি পরিচিত ফাঁদ — হিসাব, টাইপ আর OR:

CREATE INDEX idx_cust ON orders(customer_id);
-- 3) Arithmetic on the column
EXPLAIN QUERY PLAN SELECT order_id, amount FROM orders WHERE customer_id + 0 = 42;
-- 4) A text literal for an INTEGER column
EXPLAIN QUERY PLAN SELECT order_id, amount FROM orders WHERE customer_id = '42';
-- 5) OR across two columns, only one of them indexed
EXPLAIN QUERY PLAN SELECT order_id, amount FROM orders
WHERE customer_id = 42 OR merchant_id = 7;
CREATE INDEX idx_merch ON orders(merchant_id);
EXPLAIN QUERY PLAN SELECT order_id, amount FROM orders
WHERE customer_id = 42 OR merchant_id = 7;
SELECT COUNT(*) AS n FROM orders WHERE customer_id = 42 OR merchant_id = 7;

N+1 মনে রাখার মতো: ৫০টি অর্ডারের প্রতিটির দোকানের নাম আলাদা query-তে আনলে ৫১টি round trip — ০.৫ ms করে হলেও শুধু যাতায়াতে ২৫ ms-এর বেশি। ORM প্রায়ই নিঃশব্দে এটি করে; slow-query log-এ প্রতিটি query দ্রুত, অথচ পাতা ধীর।

৮ · ভাগ করা ডেটাবেসে secondary index — local বনাম global

ডেটা একটি যন্ত্রে না ধরলে টেবিল ভাগ হয় কয়েকটি partition বা shard-এ (পর্ব ২৩)। ধরা যাক orders ভাগ হয়েছে customer_id-এর hash দিয়ে ৮ ভাগে — partition key customer_id. গ্রাহকের ইতিহাস (P1) তাই একটি partition-এই মেটে। কিন্তু দোকানের ড্যাশবোর্ড খোঁজে merchant_id দিয়ে, আর দোকান ৭-এর অর্ডার আটটি partition-এই ছড়ানো। Secondary index তাহলে থাকবে কোথায়? দুটি উত্তর:

দুই পথের দাম সংখ্যায় দেখুন। ধরে নেওয়া হলো: একটি call সাধারণত ২–৪ ms, কিন্তু ০.৫% ক্ষেত্রে ৬০ ms (garbage collection-এর বিরতি, compaction ইত্যাদি); আর global index-এর async হালনাগাদের দেরি গড়ে ৫০ ms-এর exponential বণ্টনে। Seed-যুক্ত PRNG, তাই প্রতিবার একই ফল:

// Orders split into 8 partitions by customer_id. Query: "merchant 7's latest 20 orders".
// LOCAL index : each partition indexes only its own rows -> ask all 8, merge (scatter-gather).
// GLOBAL index: partitioned by merchant_id -> one partition answers (covering), updated async.
// Assumed latency of one call: 2-4 ms, but 60 ms with probability 0.5% (GC pause, compaction).
function mulberry32(a) {
  return () => { a |= 0; a = a + 0x6D2B79F5 | 0; let t = Math.imul(a ^ a >>> 15, 1 | a);
    t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t; return ((t ^ t >>> 14) >>> 0) / 4294967296; };
}
const rnd = mulberry32(21), P = 8, SLOW = 0.005, TRIALS = 20000;
const call = () => rnd() < SLOW ? 60 : 2 + 2 * rnd();
const pct = (a, q) => [...a].sort((x, y) => x - y)[Math.ceil(q * a.length) - 1];
const local = [], global = [];
for (let i = 0; i < TRIALS; i++) {
  let worst = 0;
  for (let s = 0; s < P; s++) worst = Math.max(worst, call());   // wait for the slowest partition
  local.push(worst + 1);                                          // + ~1 ms to merge 8 x 20 rows
  global.push(call());
}
const row = (name, a, calls) => console.log(name.padEnd(14) + String(calls).padStart(5) +
  pct(a, 0.5).toFixed(1).padStart(9) + pct(a, 0.99).toFixed(1).padStart(9) +
  (a.filter(x => x >= 60).length / TRIALS * 100).toFixed(2).padStart(9) + "%");
console.log("READ          calls  p50 ms   p99 ms   >=60 ms");
row("local index", local, P);
row("global index", global, 1);
console.log("theory: P(at least one slow of " + P + ") = 1 - 0.995^8 = " + ((1 - (1 - SLOW) ** P) * 100).toFixed(2) + "%");
// WRITE: local index lives in the same partition and the same transaction -> never stale.
// Global index entry is applied later; assumed lag ~ exponential, mean 50 ms.
console.log("\nWRITE then READ via global index after t ms: share that misses the new order");
for (const t of [10, 100, 500]) {
  let miss = 0;
  for (let i = 0; i < TRIALS; i++) if (-50 * Math.log(1 - rnd()) > t) miss++;
  console.log(("t = " + t + " ms").padEnd(12) + "simulated " + (miss / TRIALS * 100).toFixed(1).padStart(5) +
              "%   formula e^(-t/50) " + (Math.exp(-t / 50) * 100).toFixed(1).padStart(5) + "%");
}

READ          calls  p50 ms   p99 ms   >=60 ms
local index       8      4.8     61.0     3.97%
global index      1      3.0      4.0     0.50%
theory: P(at least one slow of 8) = 1 - 0.995^8 = 3.93%

WRITE then READ via global index after t ms: share that misses the new order
t = 10 ms   simulated  81.8%   formula e^(-t/50)  81.9%
t = 100 ms  simulated  13.4%   formula e^(-t/50)  13.5%
t = 500 ms  simulated   0.0%   formula e^(-t/50)   0.0%

বাস্তবের সিস্টেমে দুই পথই দেখা যায় (প্রকাশিত ডকুমেন্টেশন অনুযায়ী, লেখার সময়ে; খুঁটিনাটি সংস্করণভেদে আলাদা):

• Amazon DynamoDB: local secondary index একই partition key-তে থাকে, strongly consistent read চলে, কিন্তু টেবিল বানানোর সময়েই ঘোষণা করতে হয়; global secondary index-এর আলাদা partition key, আর তার read শুধু eventually consistent.
• Cassandra আর Elasticsearch: secondary index বা প্রতিটি shard-এর inverted index local; partition key ছাড়া query বহু node-এ যায়। MongoDB-র sharded cluster-এও shard key ছাড়া query সব shard-এ পাঠানো হয়।
• Google Spanner: secondary index global, একই transaction-এ হালনাগাদ — পড়া নিখুঁত, কিন্তু প্রতিটি লেখায় একাধিক অংশের commit-এর দাম।
• PostgreSQL-এর partitioned table: index প্রতিটি partition-এ local, আর unique constraint-এ partition key-এর সব কলাম থাকতে হয়। তাই user_id দিয়ে ভাগ করা টেবিলে email সব জায়গায় অনন্য রাখতে আলাদা lookup টেবিল (email → user_id) লাগে — হাতে বানানো global index, outbox বা change stream দিয়ে মেলানো (পর্ব ২৫, ৩৩)।

৯ · Index-এর বাইরে query performance

সঠিক index প্রথম হাতিয়ার, শেষ নয়। লাখো সারির যোগফল, বহু partition জুড়ে join, বা এক যন্ত্রের সামর্থ্যের বাইরের পড়ার চাপ — তখন নকশার পরের ধাপগুলো:

Materialized view: PostgreSQL-এ REFRESH MATERIALIZED VIEW পুরো ফল নতুন করে হিসাব করে; CONCURRENTLY দিলে পড়া আটকায় না, তবে view-এ একটি unique index লাগে। MySQL-এ লেখার সময়ে নিজস্ব materialized view নেই — summary টেবিল আর job দিয়ে কাজ চালানো হয়।

মাপার নিয়ম। Query-কে আক্ষরিক মান বাদ দিয়ে এক ছাঁচে আনুন — WHERE merchant_id = ? — তারপর দুটি তালিকা: মোট সময় (চলার সংখ্যা × গড়) ধরে, আর p99 ধরে। PostgreSQL-এর pg_stat_statements প্রতিটি ছাঁচের চলার সংখ্যা আর গড় সময় রাখে, log_min_duration_statement ধীর query log-এ লেখে; MySQL-এ slow query log আর long_query_time. Percentile আসে metric-এর histogram বা trace থেকে (observability, পর্ব ৫০)। আর query-প্রতি সময়সীমা (statement_timeout) রাখুন, যাতে একটি ভুল query পুরো ডেটাবেস আটকে না দেয় (পর্ব ১৮)।

১০ · AI-এর যুগে index আর query tuning

“Query ধীর, index বলে দাও” — AI কয়েক সেকেন্ডে একটি CREATE INDEX লিখে দেয়। কিন্তু সে আপনার ডেটার মাপ, মানের বণ্টন আর লেখার হার জানে না, আর প্রায়ই plan না দেখেই উত্তর দেয়। চেনা ভুলগুলো:

AI-এর দেওয়া index চালু করার আগে — চেকলিস্ট

• প্রতিটি index-এর পেছনে একটি নির্দিষ্ট query, তার QPS আর latency-র লক্ষ্য আছে
• আসল মাপের ডেটায় EXPLAIN (বা EXPLAIN ANALYZE)-এ আগে আর পরের plan দেখেছি
• কলামের ক্রম leftmost prefix আর “সমতা আগে, তারপর range বা sort” নিয়মে মিলিয়েছি
• লেখার দাম, আকার আর দ্বৈত (prefix) index নিজে হিসাব করেছি
• বড় টেবিলে লেখা না আটকে বানানোর উপায় আর rollback ঠিক করেছি; বৈশিষ্ট্যগুলো অফিশিয়াল ডকুমেন্টেশনে মিলিয়েছি
• deploy-এর পর সেই query-র p99 আর INSERT-এর latency মেপেছি; লাভ না হলে index মুছেছি