Index ভেতরে কীভাবে কাজ করে

Database Design অধ্যায়ে দেখেছো একটা index দিয়ে query ৮০০ ms থেকে ০.১ ms এ নেমে আসে। কিন্তু কেন? Index ভেতরে আসলে কী? কখন সাহায্য করে আর কখন উল্টো ক্ষতি করে? এই অধ্যায়ে index এর ভেতরটা দেখবো, কারণ system design এ "এখানে index দেবো" বলার পরের প্রশ্ন সবসময় আসে "কোন index, কেন, আর এর দাম কী?"

#Index ছাড়া: পুরো বই পড়া

১ কোটি order এর table। "customer 42 এর order" খুঁজতে database কে প্রতিটা row পড়তে হবে। Data disk এ page (সাধারণত ৮ KB এর টুকরো) হিসেবে থাকে, তাই আসলে লাখ লাখ page পড়া। একে বলে sequential scan বা full table scan।

#B-Tree: সাজানো গাছ

PostgreSQL, MySQL সহ প্রায় সব relational database এর default index হলো B-Tree (balanced tree)। এটা হলো data এর একটা সাজানো copy, গাছের মতো স্তরে স্তরে:

মূল বৈশিষ্ট্য:

• সাজানো: তাই =, <, >, BETWEEN, ORDER BY, prefix LIKE 'abc%' সবই দ্রুত
• চওড়া আর অগভীর: প্রতিটা node এ শত শত key। ১ কোটি row এর জন্যও গাছ মাত্র ৩-৪ স্তর গভীর। মানে ১ কোটির মধ্যে খুঁজতে ৩-৪টা page পড়া, লাখ লাখ না।
• Leaf এ row এর ঠিকানা: index থেকে ঠিকানা পেয়ে আসল row পড়া হয়
• Balanced: সব leaf একই গভীরতায়, তাই যেকোনো key খুঁজতে প্রায় একই সময়

এটাই O(log n): data ১০ গুণ বাড়লে খোঁজার ধাপ মাত্র একটা বাড়ে।

#Index এর ধরন

#Composite index এর ক্রম

CREATE INDEX ON orders (customer_id, status, created_at) হলো "আগে customer, তারপর status, তারপর সময়" অনুযায়ী সাজানো ফোনবুক।

নিয়ম:

1. = এর column আগে, range বা sort এর column পরে
2. যে column দিয়ে বেশি বাছাই হয় (বেশি আলাদা মান), সেটা সাধারণত আগে
3. বাম থেকে ডানে (leftmost prefix) ব্যবহার হয়

#Covering index: table এ যেতেই হয় না

CREATE INDEX idx_orders_cust_cover ON orders (customer_id, created_at DESC) INCLUDE (total, status);

SELECT created_at, total, status FROM orders WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;

যা দরকার সব index এই আছে, তাই আসল table এ যাওয়ার দরকারই নেই (index-only scan)। খুব বেশি চলা query এর জন্য দারুণ।

#Partial index: শুধু দরকারি অংশ

-- ৯৯% order delivered, কিন্তু query হয় শুধু চলমান order এ
CREATE INDEX idx_active_orders ON orders (restaurant_id, created_at) WHERE status IN ('pending', 'preparing');

ছোট index, দ্রুত, কম জায়গা।

#Index কখন কাজ করে না

-- ✗ column এর উপর function: index এ lower() করা মান নেই
SELECT * FROM users WHERE lower(email) = 'a@b.com';
-- সমাধান: expression index
CREATE INDEX ON users (lower(email));

-- ✗ শুরুতে wildcard: সাজানো ক্রম কাজে লাগে না
SELECT * FROM products WHERE name LIKE '%burger%';
-- সমাধান: pg_trgm এর GIN index বা full-text search

-- ✗ type মেলেনি: phone TEXT, কিন্তু সংখ্যা দিয়ে তুলনা
SELECT * FROM users WHERE phone = 1711111111;

-- ✗ খুব কম বাছাই: অর্ধেক row যদি মেলে, পুরো table পড়াই দ্রুত
SELECT * FROM users WHERE is_active = true;

শেষেরটা গুরুত্বপূর্ণ: index দিয়ে প্রতিটা মেলা row এর জন্য আলাদা করে table এ যেতে হয় (random read)। মেলা row যদি অনেক হয়, database এর query planner নিজেই হিসাব করে পুরো table পড়া সস্তা, আর index উপেক্ষা করে। Planner এর এই হিসাব table এর statistics থেকে আসে, তাই বড় data বদলের পর ANALYZE চালানো দরকার হতে পারে।

#Index এর দাম

তাই write-heavy table (log, event, rider এর location) এ কম index, read-heavy table (product, menu) এ বেশি index চলে।

#অব্যবহৃত index খোঁজা

SELECT relname AS table, indexrelname AS index, idx_scan AS times_used,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes
ORDER BY idx_scan ASC, pg_relation_size(indexrelid) DESC;

times_used = 0 আর আকার বড় হলে সেই index শুধু লেখা ধীর করছে।

#System design এ index নিয়ে কথা বলা

Interview বা design doc এ "index দেবো" বলা যথেষ্ট না। বলো:

"সবচেয়ে বেশি চলা query হলো 'customer এর সর্বশেষ ২০টা order'। তাই (customer_id, created_at DESC) এর composite index দেবো, যাতে sort ছাড়াই সরাসরি ২০টা পাওয়া যায়। Order table এ write মাঝারি (peak ২০/সেকেন্ড), তাই আরও ২-৩টা index এর দাম সহনীয়। Restaurant এর dashboard এর জন্য চলমান order এর partial index দেবো, কারণ সেগুলো মোটের ১% এর কম।"

#অনুশীলন

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