Index — B+ tree, hash আর bitmap

১ · বইয়ের সূচি আর লাইব্রেরির ক্যাটালগ — index কী

পর্ব ৩৯-এ দেখেছেন, টেবিলের সারিগুলো ডিস্কে page-এ ভাগ হয়ে থাকে, আর খরচ মাপা হয় কয়টি page পড়তে হলো তা দিয়ে। এখন প্রশ্ন: WHERE customer_id = 42 লিখলে DBMS কোন page-এ যাবে? কোনো সাহায্য না থাকলে উত্তর একটিই — সবগুলো page পড়ে দেখা।

সংজ্ঞাটি স্পষ্ট করা যাক। Index হলো টেবিলের বাইরে (বা পাশে) রাখা একটি সাজানো কাঠামো, যা একটি search key-এর মান থেকে সেই মানের সারিগুলোর ঠিকানায় নিয়ে যায়। প্রতিটি entry মূলত একটি জোড়া: (key, rid). এখানে record id (rid) হলো সারির ঠিকানা — (page নম্বর, page-এর ভেতরের slot). তিনটি কথা মনে রাখুন:

• Search key আর primary key এক নয়। যেকোনো কলাম বা কলাম-সেটের ওপর index হয়, আর একই key বহু সারিতে থাকতে পারে (একজন গ্রাহকের ১০টি অর্ডার)।
• Index একটি কপি। key-গুলোর সাজানো কপি, যা DBMS প্রতিটি লেখার সাথে নিজে হালনাগাদ রাখে। তাই এটি physical স্তরের বিষয় — যোগ বা মুছলে কোয়েরির ফল বদলায় না, শুধু গতি বদলায় (পর্ব ৩-এর physical data independence).
• একটি টেবিলে অনেকগুলো index থাকতে পারে — ঠিক লাইব্রেরির তিন ক্যাটালগের মতো। কিন্তু সারিগুলো ডিস্কে একটিই ক্রমে সাজানো থাকতে পারে (অংশ ৩)।

এই পর্বের লাইভ SQL-এ বেশির ভাগ সময় একটি বড় টেবিল লাগবে, কারণ ১০টি সারিতে index-এর প্রভাব চোখে পড়ে না। পর্ব ২৫-এর recursive CTE দিয়ে ১০,০০০ সারির একটি orders টেবিল বানানো যাক: order_id (১ থেকে ১০,০০০), customer_id (১ থেকে ১,০০০), order_date (২০২৫ সালের কোনো দিন), amount (টাকা) আর status. মানগুলো সূত্র দিয়ে বানানো, তাই প্রতিবার একই আসে:

CREATE TABLE orders (
  order_id    INTEGER PRIMARY KEY,
  customer_id INTEGER NOT NULL,
  order_date  TEXT NOT NULL,
  amount      INTEGER NOT NULL,
  status      TEXT NOT NULL
);
WITH RECURSIVE seq(n) AS (
  SELECT 1 UNION ALL SELECT n + 1 FROM seq WHERE n < 10000
)
INSERT INTO orders
SELECT n, (n * 37) % 1000 + 1,
       date('2025-01-01', '+' || (n % 365) || ' days'),
       (n * 7919) % 5000 + 100,
       CASE WHEN n % 50 = 0 THEN 'pending'
            WHEN n % 10 = 0 THEN 'cancelled' ELSE 'delivered' END
FROM seq;
SELECT COUNT(*) AS total_rows, COUNT(DISTINCT customer_id) AS customers,
       MIN(order_date) AS first_day, MAX(order_date) AS last_day
FROM orders;
SELECT status, COUNT(*) AS n FROM orders GROUP BY status ORDER BY n DESC;

২ · Index ছাড়া আর index দিয়ে — খরচের হিসাব

একটি বড় টেবিল ধরুন। সংখ্যাগুলো হিসাবের সুবিধার জন্য ধরে নেওয়া, কোনো নির্দিষ্ট প্রতিষ্ঠানের নয়:

• N = ১ কোটি (10⁷) সারি; একটি page-এ ১০০টি সারি, তাই P = ১ লাখ data page.
• page ৮ KB (PostgreSQL-এর ডিফল্ট; InnoDB-তে ১৬ KB). একটি index entry — ৮ বাইটের key, ৬–৮ বাইটের ঠিকানা আর কিছু overhead — মোটামুটি ২০ বাইট। তাই একটি page-এ ৪০০-র মতো entry ধরে; page পুরো ভরা থাকে না বলে কার্যকর fanout F ধরা যাক ২০০ থেকে ৫০০।

Index ছাড়া: WHERE customer_id = 42-এর উত্তর যেকোনো page-এ থাকতে পারে, তাই full table scan — P = ১,০০,০০০ page. key unique হলেও গড়ে অর্ধেক, আর না পেলে সবগুলো।

B+ tree index দিয়ে: গাছের প্রতিটি স্তরে একটি page পড়ে নিচে নামতে হয়। leaf-এ ১ কোটি entry, প্রতিটি leaf-এ ধরুন ২৫০টি — তাই ৪০,০০০ leaf. তার ওপরের স্তরে ৪০,০০০ ÷ ২৫০ = ১৬০টি node, তার ওপরে একটি root. উচ্চতা h = ৩। সাধারণভাবে:

তাহলে একটি সারি পেতে খরচ = hটি index page + ১টি data page = ৪ থেকে ৫টি page, ১ লাখের জায়গায়। আরও ভালো: root আর দ্বিতীয় স্তর মিলে মাত্র কয়েকশো page, যা প্রায় সবসময় buffer pool-এ থাকে। বাস্তবে ডিস্কে যেতে হয় ১–২ বার। আর টেবিল ১০ গুণ বড় হলে h বাড়ে বড়জোর ১।

Range কোয়েরি — যেখানে হিসাব জটিল হয়

“এক সপ্তাহের অর্ডার” ধরনের কোয়েরিতে ধরুন মোট সারির ১%, অর্থাৎ ১ লাখ সারি মেলে। খরচ = h (প্রথম key পর্যন্ত নামা) + মিল থাকা leaf page (১ লাখ ÷ ২৫০ = ৪০০) + data page. শেষ অংশটিই নির্ণায়ক:

শেষ সারিটি অবাক করে: সারিগুলো যদি ডিস্কে ছড়ানো থাকে, প্রতিটি মিলের জন্য আলাদা একটি data page — ১ লাখ random পড়া, যা ১ লাখ sequential পড়ার চেয়েও ধীর। তাই selectivity বড় হলে optimizer জেনেশুনে index ফেলে full scan বেছে নেয় (পর্ব ৪৩)। Index সবসময় জেতে না; জেতে যখন সামান্য কিছু সারি লাগে।

এবার নিজে দেখুন। SQLite-এর EXPLAIN QUERY PLAN কোয়েরি না চালিয়ে বলে দেয় কোন পথে চালাবে। SCAN মানে পুরো টেবিল পড়া, SEARCH … USING INDEX মানে index ধরে খোঁজা:

EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE customer_id = 42;

CREATE INDEX idx_orders_customer ON orders(customer_id);

EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE customer_id = 42;

SELECT order_id, order_date, amount, status
FROM orders WHERE customer_id = 42;

৩ · Index-এর শ্রেণিবিভাগ — চার জোড়া শব্দ

পাঠ্যবই আর পরীক্ষায় চার জোড়া শব্দ বারবার আসে। আগে একটি সতর্কতা: বইভেদে সংজ্ঞা একটু আলাদা। Silberschatz-এর বইয়ে primary index আর clustering index একই; Elmasri–Navathe-এর বইয়ে primary index হলো সাজানো ফাইলের key কলামে, আর clustering index সাজানো ফাইলের non-key কলামে। লিখিত পরীক্ষায় কোন সংজ্ঞা ধরছেন, এক লাইনে বলে নিন।

Sparse index-এর হিসাবটি দেখুন। আমাদের ১ কোটি সারি order_id-এর ক্রমে সাজানো থাকলে dense index-এ ১ কোটি entry, কিন্তু sparse index-এ ১ লাখ — প্রতিটি data page-এর জন্য একটি। key 5,00,123 খুঁজতে sparse index-এ “5,00,123-এর সমান বা ঠিক ছোট” entry পান, সেই page-এ যান, ভেতরে খোঁজেন। কিন্তু secondary index কখনো sparse হতে পারে না: ফাইল অন্য ক্রমে থাকলে “এই page-এর প্রথম key” থেকে পরের key কোথায়, বলা যায় না।

১ লাখ entry-র sparse index-ও প্রায় ২৫০–৫০০ page. তার ওপর আরেকটি sparse index বানালে ১–২টি page — এক page-এই আঁটে। এভাবে স্তরের পর স্তর: multi-level index-এ খোঁজ = স্তরের সংখ্যা = log_F N টি page. ১৯৬০-এর দশকে IBM-এর ISAM ফাইল ঠিক এমন স্থির বহু-স্তরের index ব্যবহার করত; সমস্যা ছিল, নতুন সারি এলে কাঠামো বদলাত না, overflow area-য় জমত আর ধীরে ধীরে ধীর হতো। নিজে নিজে বাড়া-কমা multi-level index — সেটিই B+ tree.

বাস্তব সিস্টেমে কে কোনটি

• MySQL InnoDB: টেবিল নিজেই primary key-এর ওপর একটি clustered B+ tree — leaf-এ পুরো সারি। প্রতিটি secondary index-এর leaf-এ থাকে primary key-এর মান, physical ঠিকানা নয়। তাই secondary দিয়ে খুঁজলে দুটি গাছে নামতে হয়।
• PostgreSQL: টেবিল একটি heap file — কোনো ক্রম নেই; primary key-সহ সব index আলাদা, non-clustered, leaf-এ (page, slot) ঠিকানা। CLUSTER কমান্ড একবার সাজায়, পরের লেখায় ক্রম আর রক্ষা হয় না।
• SQL Server: একটি টেবিলে একটি clustered index (সাধারণত primary key-এ), বাকিগুলো non-clustered. Oracle-এ সাধারণ টেবিল heap, আর clustered রূপের নাম index-organized table.
• SQLite: সাধারণ টেবিল নিজেই rowid-এর ওপর একটি B-tree, সারি থাকে leaf-এ — কার্যত clustered. INTEGER PRIMARY KEY হলো সেই rowid-এরই আরেক নাম।

শেষ কথাটি SQLite নিজেই দেখায়। order_id দিয়ে খুঁজলে কোনো CREATE INDEX লাগে না, কিন্তু amount-এ কোনো index নেই:

EXPLAIN QUERY PLAN SELECT * FROM orders WHERE order_id = 5000;
EXPLAIN QUERY PLAN SELECT * FROM orders WHERE amount = 2500;
SELECT order_id, customer_id, amount FROM orders WHERE order_id = 5000;

৪ · B+ tree-এর গঠন, উচ্চতা আর খোঁজ

B+ tree একটি balanced বহু-শাখার গাছ, যার প্রতিটি node ঠিক একটি page. ধরুন একটি node-এ সর্বোচ্চ mটি child pointer ধরে (order m). নিয়মগুলো:

• Internal node: kটি key আর k + ১টি pointer: P0 K1 P1 K2 P2 … Kk Pk. Pi-এর নিচের সব key Ki ≤ key < Ki+1 মানে। এখানে কোনো সারির ঠিকানা নেই — শুধু পথনির্দেশ।
• Leaf: সাজানো (key, rid) জোড়া, আর পাশের leaf-এর একটি pointer — leaf link. সব leaf মিলে পুরো key-সেটের একটি সাজানো শিকল।
• ভরাটের নিয়ম: root ছাড়া প্রতিটি node অন্তত অর্ধেক ভরা (internal node-এ অন্তত ⌈m/2⌉টি child). root-এ অন্তত ২টি child (যদি root নিজে leaf না হয়)।
• Balance: সব leaf একই গভীরতায়। তাই যেকোনো key-এর খোঁজ ঠিক hটি node পড়ে।

পুরোনো B-tree-এর সাথে পার্থক্য এখানেই: B-tree-এ ভেতরের node-এও key-এর সাথে তথ্য থাকে, তাই কিছু খোঁজ আগেই থামে। কিন্তু ভেতরের node-এ তথ্য রাখলে প্রতি page-এ key কম ধরে, fanout কমে; আর range scan-এ গাছে ওঠানামা করতে হয়। B+ tree ভেতরের node-কে হালকা রাখে, সব তথ্য leaf-এ নামায় — fanout বাড়ে, আর range মানে শুধু leaf-এর শিকল ধরে হাঁটা।

উচ্চতার সীমা — একটি ছোট প্রমাণ

ধরুন Lটি leaf আর উচ্চতা h (root-কে স্তর ১ ধরে, leaf স্তর h). প্রতিটি node-এর সর্বোচ্চ mটি child, তাই স্তর i-তে বড়জোর mⁱ⁻¹টি node; leaf-গুলো স্তর h-এ, তাই L ≤ m^h−1. উল্টো দিকে, root-এর অন্তত ২টি আর বাকি internal node-এর অন্তত ⌈m/2⌉টি child, তাই L ≥ 2·⌈m/2⌉^h−2. দুই দিক থেকে log নিলে:

দুই সীমাই log L-এর সমানুপাতিক, ভিত্তি কয়েকশো। m = ৪০০ আর L = ৪০,০০০ বসান: নিম্নসীমা 1 + 1.77 = 2.77, ঊর্ধ্বসীমা 2 + log₂₀₀ 20,000 = 2 + 1.87 = 3.87. উচ্চতা পূর্ণসংখ্যা, তাই ঠিক ৩। অর্থাৎ গাছটি যত খারাপভাবেই ভরা থাকুক, ভরাটের নিয়ম মানলে উচ্চতা log-এর বাইরে যেতে পারে না। এই নিশ্চয়তাই B+ tree-কে নির্ভরযোগ্য করে।

খোঁজ আর range scan, ধাপে ধাপে

নিচের গাছে প্রতিটি node একটি page. প্রথমে WHERE id = 45, তারপর WHERE id BETWEEN 42 AND 55:

এবার SQLite-এ একটি তারিখের range আর ORDER BY — দুটিই একই index-এর leaf শিকল ব্যবহার করে:

CREATE INDEX idx_orders_date ON orders(order_date);
EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE order_date BETWEEN '2025-03-01' AND '2025-03-07';
SELECT COUNT(*) AS n, SUM(amount) AS revenue
FROM orders WHERE order_date BETWEEN '2025-03-01' AND '2025-03-07';
EXPLAIN QUERY PLAN
SELECT * FROM orders ORDER BY order_date LIMIT 5;
EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE substr(order_date, 1, 7) = '2025-03';

৫ · B+ tree-এ insert আর delete — split, merge আর bulk loading

Insert-এর নিয়ম সরল: খোঁজের মতো নেমে ঠিক leaf-এ যান, সাজানো জায়গায় key বসান। leaf-এ জায়গা থাকলে কাজ শেষ। না থাকলে split: leaf-এর key-গুলো দুই ভাগ, ডান ভাগের প্রথম key-এর একটি কপি parent-এ ওঠে (leaf-এ key-টি থেকেও যায়)। parent-ও উপচে পড়লে সেটিও ভাগ হয়, কিন্তু internal node ভাগে মাঝের key-টি সরে ওপরে যায়। root ভাগ হলে নতুন root — গাছ এভাবেই, শুধু ওপরের দিকে, এক স্তর বাড়ে। তাই সব leaf চিরকাল একই গভীরতায় থাকে।

Delete — merge আর redistribute

Delete উল্টো পথে চলে: leaf থেকে entry মুছুন। leaf অর্ধেকের নিচে নামলে দুটি উপায়। পাশের leaf-এ বাড়তি key থাকলে একটি ধার নিন — redistribution — আর parent-এর ভাগ-করা key হালনাগাদ করুন। পাশের leaf-ও টায়টায় অর্ধেক হলে দুটিকে জুড়ে দিন — merge — আর parent থেকে একটি key সরান। parent অর্ধেকের নিচে নামলে একই কাজ ওপরে, আর root-এ একটিমাত্র child থাকলে root সরে যায় — গাছ এক স্তর নামে।

বাস্তব সিস্টেম অবশ্য এত তৎপর নয়। মুছে ফেলা জায়গা সাধারণত পরের insert-এর জন্য রেখে দেওয়া হয়, কারণ যে টেবিল থেকে মোছা হয় তাতে আবার লেখাও আসে। PostgreSQL-এর B-tree মূলত পুরো খালি page-ই সরায়; InnoDB একটি page-এর ভরাট একটি সীমার (ডিফল্টে ৫০%) নিচে নামলে পাশের page-এর সাথে জোড়ার চেষ্টা করে। অনেক মোছার পর index ফাঁপা হয়ে গেলে REINDEX বা পুনর্নির্মাণ করা হয়।

Bulk loading — একবারে পুরো গাছ

একটি বিদ্যমান ১ কোটি সারির টেবিলে CREATE INDEX চালালে DBMS ১ কোটিবার insert করে না। Bulk loading-এ আগে সব (key, rid) জোড়া সাজানো হয় (external sort, পর্ব ৪২), তারপর বাঁ থেকে ডানে leaf ভরা হয়, আর প্রতিটি leaf-এর প্রথম key দিয়ে নিচ থেকে ওপরে internal স্তর বানানো হয়। ফল: প্রায় sequential লেখা, কোনো split নেই, আর leaf-গুলো ঘন। leaf পুরো ভরা না রেখে কিছু জায়গা ফাঁকা রাখা হয়, যাতে পরের insert-এ সাথে সাথে split না লাগে — PostgreSQL-এর B-tree-এ এই fillfactor ডিফল্টে ৯০%.

৬ · কেন ডিস্কে B+ tree-ই রাজা

প্রায় পঞ্চাশ বছর ধরে প্রায় সব relational DBMS-এর ডিফল্ট index B+ tree. কারণগুলো একসাথে দেখুন:

গভীরে আরও দুটি ব্যাপার: প্রতিটি page-এ key সাজানো থাকায় page-এর ভেতরে binary search চলে, আর ওপরের স্তরগুলো ছোট বলে সবসময় মেমরিতে থাকে। DSA কোর্সের B-tree পর্বে একই গাছের অ্যালগরিদমিক দিক — order, split-এর প্রমাণ আর কোড — বিস্তারিত পাবেন।

৭ · Hash index — static, overflow আর extendible hashing

B+ tree-এ সমতার খোঁজও h টি page. Hash index সরাসরি লাফ দেয়: hash function h(key) থেকে bucket-এর নম্বর বের করে, সেই bucket-এর page পড়ে। আদর্শ অবস্থায় ১–২টি page. মূল ধারণা DSA-এর hash table পর্বের মতোই, শুধু এখানে প্রতিটি bucket একটি ডিস্ক page.

Static hashing: শুরুতে নির্দিষ্ট Mটি bucket, bucket = h(k) mod M. ডেটা বাড়লে bucket-এর page ভরে, তার সাথে বাড়তি page জোড়া লাগে — overflow chain. শিকল লম্বা হলে খোঁজ আর ১ page নয়, ৫–১০ page. সমাধান পুরো index নতুন M দিয়ে আবার hash করা — চালু ডেটাবেসে দীর্ঘ, ভারী কাজ।

Extendible hashing: একটি ছোট directory রাখুন, যার entry-সংখ্যা 2^d; d হলো global depth — hash মানের শেষ কয়টি bit দেখা হবে। প্রতিটি bucket-এর একটি local depth — তার key-গুলো শেষ কয়টি bit-এ মেলে। bucket ভরলে শুধু সেটিই ভাগ হয়। local depth আগেই global depth-এর সমান হলে আগে directory দ্বিগুণ হয় — directory ছোট, তাই সস্তা। নিচে সহজ করার জন্য h(k) = k-এর binary রূপ, আর প্রতিটি bucket-এ সর্বোচ্চ ২টি key:

Linear hashing directory ছাড়াই একই লক্ষ্যে পৌঁছায়: একটি “পরের-ভাগ” pointer ধরে bucket-গুলো পালাক্রমে একটি একটি করে ভাগ হয় — যে bucket উপচে পড়ল সেটি নয়, pointer যেটি দেখায় সেটি। তাই উপচে পড়া bucket-এ সাময়িক overflow page থাকে, কিন্তু index ধীরে ধীরে, সমানভাবে বাড়ে।

বাস্তবে hash index কম দেখা যায়। PostgreSQL-এ USING hash আছে, তবে version 10-এর আগে এর লেখা WAL-এ যেত না, তাই crash-এর পর নির্ভরযোগ্য ছিল না আর ডকুমেন্টেশন নিরুৎসাহিত করত। MySQL InnoDB-তে সাধারণ index (FULLTEXT আর SPATIAL ছাড়া) B+ tree; InnoDB নিজে ঘন ঘন পড়া page-এর জন্য মেমরিতে একটি adaptive hash index বানায়, আর MEMORY engine-এ আসল hash index আছে। Hash-এর আসল জয় মেমরিতে, সাময়িক কাজে — পর্ব ৪২-এর hash join.

৮ · Bitmap index আর অন্যান্য index

status কলামে হাতে-গোনা কয়েকটি মান — pending, shipped, delivered, cancelled. এমন কম আলাদা মানের (low-cardinality) কলামে B+ tree দুর্বল: “status = delivered” ৯০% সারি মেলায়, index দিয়ে লাভ নেই। Bitmap index অন্যভাবে ভাবে: প্রতিটি আলাদা মানের জন্য একটি bit-এর সারি, যার i-তম bit 1 মানে i-তম সারিতে সেই মান।

db-shop-এর orders (১০টি অর্ডার, order_id 1001–1010, status) আর customers (customer_id, name, city …) দিয়ে দুটি bitmap বানিয়ে AND করে দেখা যাক — “delivered অর্ডার, ঢাকার গ্রাহক”:

WITH b AS (
  SELECT o.order_id,
         (o.status = 'delivered')       AS delivered,
         COALESCE(c.city = 'Dhaka', 0) AS dhaka
  FROM orders o JOIN customers c ON c.customer_id = o.customer_id
)
SELECT group_concat(delivered, '' ORDER BY order_id)          AS delivered_bits,
       group_concat(dhaka, '' ORDER BY order_id)              AS dhaka_bits,
       group_concat(delivered & dhaka, '' ORDER BY order_id) AS both_bits,
       SUM(delivered & dhaka)                                 AS matches
FROM b;

১ কোটি সারিতে একটি bitmap = ১ কোটি bit ≈ ১.২৫ MB, চারটি মানে ৫ MB — একই কলামের B+ tree-এর চেয়ে অনেক ছোট, আর run-length ধরনের compression-এ আরও ছোট। পাঁচটি শর্তের কোয়েরি মানে পাঁচটি bitmap-এর AND — CPU-র সবচেয়ে সস্তা কাজ। তাই data warehouse-এ (পর্ব ৫৫) bitmap index খুব জনপ্রিয়; Oracle-এ CREATE BITMAP INDEX আছে। কিন্তু OLTP-তে বিপদ: একটি সারির status বদলানো মানে দুটি bitmap বদলানো, আর একটি bitmap অংশ বহু সারি ঢাকে বলে lock-এ অনেক লেখা আটকে যায়। PostgreSQL-এ স্থায়ী bitmap index নেই, কিন্তু কোয়েরির সময় একাধিক B+ tree থেকে সাময়িক bitmap বানিয়ে AND/OR করে — plan-এ BitmapAnd আর Bitmap Heap Scan.

আরও কিছু index, এক নজরে

CREATE INDEX idx_orders_hash ON orders USING hash (customer_id);
CREATE INDEX idx_docs_gin    ON documents USING gin (body_tsv);
CREATE INDEX idx_logs_brin   ON access_logs USING brin (logged_at);
CREATE INDEX idx_shops_gist  ON shops USING gist (location);  -- PostGIS

৯ · SQL-এ index — CREATE, UNIQUE, partial আর দাম

সিনট্যাক্স প্রায় সব DBMS-এ এক: CREATE [UNIQUE] INDEX নাম ON টেবিল(কলাম, …). মোছার ধরনে পার্থক্য আছে:

DROP INDEX idx_orders_customer;                 -- SQLite, PostgreSQL
DROP INDEX idx_orders_customer ON orders;       -- MySQL (টেবিলের নাম লাগে)
CREATE INDEX CONCURRENTLY idx_orders_date
    ON orders (order_date);                     -- PostgreSQL: লেখা না আটকে বানানো

UNIQUE index — গতি নয়, নিয়ম

Unique index একই key দুবার ঢুকতে দেয় না। index সাজানো বলে “এই মান আগে আছে কি?” প্রশ্নের উত্তর log-খরচে মেলে — তাই DBMS UNIQUE constraint এভাবেই প্রয়োগ করে। এখানে একটি নতুন members টেবিল (member_id, name, email):

CREATE TABLE members (
  member_id INTEGER PRIMARY KEY,
  name      TEXT NOT NULL,
  email     TEXT NOT NULL
);
CREATE UNIQUE INDEX ux_members_email ON members(email);
INSERT INTO members VALUES (1, 'Rahim', 'rahim@example.com');
INSERT INTO members VALUES (2, 'Karima', 'karima@example.com');
SELECT * FROM members;
INSERT INTO members VALUES (3, 'Rahim Ali', 'rahim@example.com');

Automatic index — যা আপনি না লিখলেও আছে

PRIMARY KEY আর UNIQUE ঘোষণা করলে DBMS নিজে index বানায়। SQLite সব index-এর তালিকা রাখে sqlite_master টেবিলে, আর PRAGMA index_list একটি টেবিলের index দেখায়। db-shop-এ আমরা একটিও CREATE INDEX লিখিনি:

SELECT type, name, tbl_name, sql
FROM sqlite_master WHERE type = 'index';
SELECT * FROM pragma_index_list('order_items');
PRAGMA index_list('customers');
SELECT * FROM pragma_index_info('sqlite_autoindex_order_items_1');

Partial index — শুধু দরকারি সারির

আমাদের ১০,০০০ অর্ডারের মাত্র ২০০টি pending, অথচ কুরিয়ার-ডেস্কের অ্যাপ সারাদিন শুধু pending অর্ডারই খোঁজে। পুরো টেবিলের index না বানিয়ে একটি WHERE দিয়ে শুধু সেই সারিগুলোর index — partial index:

CREATE INDEX idx_pending ON orders(customer_id) WHERE status = 'pending';
EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE status = 'pending' AND customer_id = 301;
EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE status = 'delivered' AND customer_id = 301;
SELECT order_id, order_date, amount FROM orders
WHERE status = 'pending' AND customer_id = 301;
SELECT name, sql FROM sqlite_master WHERE type = 'index';

Index-এর দাম — write amplification

প্রতিটি index একটি কপি, আর DBMS সেটি প্রতিটি লেখার একই transaction-এ মিলিয়ে রাখে। ধরুন orders-এ পাঁচটি index. তাহলে একটি INSERT মানে টেবিলে একটি লেখা, পাঁচটি গাছে পাঁচবার নেমে পাঁচটি leaf-এ লেখা (মাঝে মাঝে split), আর এর প্রতিটির WAL record. একটি যৌক্তিক লেখা ডিস্কে বহু লেখা হয় — write amplification. DELETE-এও প্রতিটি index থেকে মুছতে হয়; আর indexed কলামের UPDATE মানে সেই index-এ একটি delete আর একটি insert. সাথে জায়গা: পাঁচটি index মিলে টেবিলের সমান বা বড় হওয়া অস্বাভাবিক নয়, আর buffer pool-এ জায়গা নিয়ে প্রতিযোগিতা করে।

তাই নিয়ম: যে কোয়েরি সত্যিই চলে আর ধীর, তার জন্য index; অব্যবহৃত index মুছুন। PostgreSQL-এর pg_stat_user_indexes দেখায় কোন index কতবার ব্যবহার হয়েছে। কোন কলামে, কোন ক্রমে composite index, আর covering index — পর্ব ৪১-এর বিষয়।

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

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

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

• আগে আর পরে EXPLAIN চালিয়ে দেখেছি plan সত্যিই SCAN থেকে SEARCH-এ বদলেছে
• নমুনা ডেটায় index-এর আগে আর পরে কোয়েরির ফল (সারির সংখ্যা আর মান) মিলিয়েছি
• বিদ্যমান index-এর তালিকা দেখেছি — একই কলামে ডুপ্লিকেট নেই
• কলামের মানের বণ্টন গুনেছি; কম আলাদা মানে partial index বিবেচনা করেছি
• লেখার হার জেনে write amplification-এর দাম মেনে নিয়েছি
• UNIQUE index-এর আগে বিদ্যমান ডুপ্লিকেট খুঁজেছি (GROUP BY … HAVING COUNT(*) > 1)