Database Indexes - Database এর দ্রুত Data খুঁজে পাওয়ার রহস্য

০০ যে প্রশ্নগুলোর উত্তর খুঁজবো

আগের সেশনগুলোতে আমরা database কে copy করেছি (০৩), তার সামনে cache বসিয়েছি (০৪), আর কয়েকটা machine এ ভাগ করেছি (০৫)। কিন্তু একটা machine এর ভেতরে database কীভাবে একটা row খুঁজে পায়, সেটা এখনো দেখিনি। এই সেশনে আমরা database এর ভেতরে ঢুকবো। প্রশ্নগুলোর উত্তর জানা হয়ে গেলে আপনি বুঝবেন, একটা query কীভাবে full scan থেকে binary search এ নেমে আসে।

০১ Database এর কাছে একটা row চাইলে, database কীভাবে সেই row টা খুঁজে পায়?

সকাল দশটা। রয় একটা চায়ের দোকানে বসে আপনার application এ login করছে। সে email আর password দিলো, তারপর button চাপলো। Screen এ spinner ঘুরছে। তিন সেকেন্ড পার হলো, তারপর login হলো। একটা সামান্য login এ এত সময় লাগলো কেন?

Login এর সময় application প্রথমে email দিয়ে user কে খোঁজে। ধরুন আপনার users table এ ১ কোটি row আছে। Application তখন এই query টা পাঠায়:

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

Table টা একটা বিশাল খাতার মতো। Row গুলো insertion order এ store হয়, মানে যে আগে এসেছে সে আগে (user 1, user 2, user 3…)। Email অনুযায়ী সাজানো থাকে না। তাই roy@example.com খুঁজতে database একে একে প্রতিটা row চেক করে:

Row 1: alice@example.com: মেলেনি।
Row 2: bob@example.com: মেলেনি।
...
Row 7,234,891: roy@example.com: মিলেছে।

অর্থাৎ match না পাওয়া পর্যন্ত database একটার পর একটা row পড়তেই থাকে। এটাকে বলে full table scan। Table এ m টা row থাকলে এর complexity O(m)। এর মানে খুব সোজা: row যতগুণ বাড়ে, কাজও ঠিক ততগুণ বাড়ে।

একটা lookup এর জন্যই database কে ১ কোটি পর্যন্ত row পড়তে হতে পারে। প্রতি সেকেন্ডে এমন হাজারটা query এলে system overloaded হয়ে যায়।

০২ বড় table এ একটা row খুঁজে বের করা তো slow। lookup fast করবো কীভাবে?

একটা কাগজের phone book এর কথা ভাবুন। এতে লাখ লাখ নাম থাকে। একটা নাম খুঁজতে আপনি নিশ্চয়ই page 1 থেকে পড়া শুরু করবেন না। আপনি বইটা মাঝখানে খুলবেন। একটা নাম দেখবেন। তারপর ঠিক করবেন, আপনার নামটা এর আগে নাকি পরে। প্রতি ধাপে বাকি page এর অর্ধেক বাদ পড়ে যায়। এই পদ্ধতির নাম binary search।

Binary search কাজ করে একটাই কারণে: phone book টা sorted। নামগুলো random order এ থাকলে একটা নাম দেখে বোঝার উপায় থাকতো না, আপনার নামটা আগে নাকি পরে। তাই binary search শুধু sorted data তেই কাজ করে।

Binary search এ speed এর পার্থক্যটা বিশাল

১ কোটি row এর মধ্য থেকে একটা নাম খুঁজতে:

• Full scan (unsorted): সর্বোচ্চ ১,০০,০০,০০০ টা read লাগে।
• Binary search (sorted): মাত্র ২৩-২৪টা read লাগে। কারণ ১ কোটিকে বারবার অর্ধেক করলে প্রায় ২৪ বারে একটা মাত্র row বাকি থাকে (২^২৪ ≈ ১.৬ কোটি)।

এই speed কে লেখা হয় O(log m)। এর মানে: data দ্বিগুণ হলে binary search এ মাত্র একটা ধাপ বাড়ে। অথচ full scan এর কাজ দ্বিগুণ হয়ে যায়। Data বাড়তে থাকলে এই পার্থক্যটাই ঠিক করে দেয়, কোন system টিকে থাকবে আর কোনটা ভেঙে পড়বে।

একটা সমস্যা আছে

একটা table কে physically একবারে শুধু একভাবেই sort করা যায়। Email দিয়ে sort করলে email order টা থাকে। কিন্তু তারপর username দিয়ে sort করলে email order টা নষ্ট হয়ে যায়, শুধু শেষ sort টাই টিকে থাকে। অথচ আমরা প্রায়ই অনেক column এ search করি (email, username, phone)। একটা table কে সব column অনুযায়ী একসাথে sorted রাখা যায় না।

০৩ Index আসলে কী? (কোন data structure ব্যবহার হয়?)

সমাধান হলো পুরো table কে sort না করা। তার বদলে আমরা একটা ছোট, আলাদা, sorted structure বানাই। এতে শুধু search এর column টা থাকে, আর থাকে আসল row এর দিকে একটা pointer (row টা কোথায় আছে তার ঠিকানা)।

TABLE (insertion order, unsorted):
Row 1: id:1, email: roy@example.com
Row 2: id:2, email: alice@example.com
Row 3: id:3, email: bob@example.com

INDEX on email (sorted, আলাদা structure):
alice@example.com  →  Row 2
bob@example.com    →  Row 3
roy@example.com    →  Row 1

এবার WHERE email = 'roy@example.com' খুঁজতে database তিনটা কাজ করে:

1. Sorted index এ binary search করে। প্রায় ২৪ ধাপে roy@example.com পেয়ে যায়।
2. Entry টা দেখায় যে row টা আছে Row 1 এ।
3. Database সরাসরি table এর Row 1 এ চলে যায়।

Table কে physically sort না করেই আপনি binary search এর speed পেয়ে গেলেন। আর index যেহেতু আলাদা structure, তাই অনেকগুলো index বানানো যায়। প্রতিটা search এর প্রয়োজনে একটা করে:

INDEX on email    →  row এর দিকে pointer
INDEX on username →  row এর দিকে pointer
INDEX on phone    →  row এর দিকে pointer

এটা আসলে একটা B-tree

আসল database গুলো index কে একটা লম্বা sorted list হিসেবে রাখে না। কারণ বিশাল একটা list এর মাঝখানে কিছু insert করতে গেলে পরের সবকিছু সরাতে হতো। তাই database index রাখে একটা B-tree (বা B+ tree) হিসেবে। এটা একটা sorted tree। উপর থেকে নিচের দিকে নামলে প্রতি ধাপে খোঁজার range টা ছোট হয়ে আসে।

B-tree এর তিনটা গুরুত্বপূর্ণ বৈশিষ্ট্য:

• Sorted data: তাই binary search এর মতো করে lookup করা যায়।
• Insert আর delete সহজ: নতুন entry এলে সবকিছু সরাতে হয় না।
• Lookup O(log m): ১ কোটি row তেও মাত্র ২৩-২৪ ধাপ লাগে।

কেউ “database index ব্যবহার করে” বললে প্রায় সবসময় সে একটা B-tree index এর কথাই বোঝায়। মনে রাখার ছবিটা সহজ: একটা sorted tree, যেটা ধরে নিচে নামলে দ্রুত জিনিস খুঁজে পাওয়া যায়।

০৪ INSERT, UPDATE, DELETE করলে table আর index এ কী হয়?

এবার দেখবো প্রতিটা operation এ ভেতরে আসলে কী ঘটে। আমাদের setup হলো একটা users table, যার email column এ একটা index আছে।

TABLE (insertion order):                INDEX on email (sorted):
Row 1: id:1, email: roy@example.com     alice@example.com  →  Row 2
Row 2: id:2, email: alice@example.com   bob@example.com    →  Row 3
Row 3: id:3, email: bob@example.com     roy@example.com    →  Row 1

READ (SELECT): সুবিধাটা এখানে

Query: SELECT * FROM users WHERE email = 'roy@example.com'

Index ছাড়া (full scan): worst case এ সব m টা row scan করতে হয়। Cost O(m), তাই slow।

Index সহ (B-tree binary search): database index এ roy@example.com খোঁজে (প্রায় ২৪ ধাপ)। তারপর pointer ধরে সরাসরি Row 1 এ চলে যায়। Cost O(log m), তাই fast। Index এর পুরো সুবিধা এটাই।

Index শুধু নিজের column এর read এ সাহায্য করে। যে column এ index নেই, সেখানে read করলে database আবার full scan এ ফিরে যায়।

নতুন row INSERT

id:4, email: carol@example.com insert করুন।

Step 1: table এ row লেখা (শেষে, insertion order):
Row 4: carol@example.com     ← নতুন row

Step 2: index এ সঠিক SORTED position এ insert:
alice@example.com  →  Row 2
bob@example.com    →  Row 3
carol@example.com  →  Row 4     ← sorted জায়গায় বসলো, শেষে না
roy@example.com    →  Row 1

Cost: ১টা table write, আর প্রতিটা index এ ১টা B-tree insert (সঠিক জায়গা খুঁজতে প্রায় log m ধাপ)।

Indexed column UPDATE

Row 3 এর email bob@example.com থেকে বদলে zoe@example.com করুন। Index এ এই value এর sorted position টা বদলে যায়। তাই এটা আসলে দুইটা কাজ: পুরোনো entry delete, তারপর নতুন entry insert।

Step 1: table এ value বদলান (Row 3: zoe@example.com)

Step 2: index থেকে পুরোনো entry delete (bob@example.com চলে গেলো)
Step 3: নতুন sorted position এ insert:
alice@example.com  →  Row 2
carol@example.com  →  Row 4
roy@example.com    →  Row 1
zoe@example.com    →  Row 3     ← নতুন sorted position

তাই indexed column update করা মানে একটা delete আর একটা insert। এটাই সবচেয়ে expensive operation।

Non-indexed column UPDATE

Row 1 এর last_login_time বদলান। last_login_time এ কোনো index নেই, তাই email index এ কোনো পরিবর্তন হয় না। Cost শুধু একটা table write।

Row DELETE

Row 2 (alice@example.com) delete করুন। Database table থেকে row টা সরায়, আর index থেকে তার entry টাও সরায়। Cost: ১টা table delete, আর প্রতিটা index এ ১টা B-tree delete।

সব operation একসাথে

০৫ Index যদি read fast করে, তাহলে প্রতিটা column index করি না কেন?

কারণ index free না। n টা index থাকলে একটা row insert এর cost মোটামুটি এরকম:

১ (table write) + n × log(m)

এখানে n হলো index এর সংখ্যা, আর m হলো table এর row সংখ্যা। প্রতিটা write এর পর database কে প্রতিটা সংশ্লিষ্ট index sorted রাখতে হয়।

কোন column index করবেন, তার কয়েকটা guideline:

• প্রায়ই search হয় এমন column: index করুন।
• খুব কম search হয়, কিন্তু প্রায়ই write হয় এমন column: index করবেন না।
• Write-heavy table: যত কম index, তত ভালো।
• Read-heavy table: বেশি index রাখলে লাভ হয়।
• প্রায়ই বদলায় এমন column: index করলে সবচেয়ে বেশি ক্ষতি হয়, কারণ প্রতিটা change মানে B-tree তে একটা delete আর একটা insert।

উদাহরণ: Logs Table

একটা logs table এ সেকেন্ডে ৫০,০০০ insert হয়। কিন্তু search হয় সপ্তাহে মাত্র একবার।

• Index কম রাখুন: table টা write-heavy আর read খুব কম। প্রতিটা index সেকেন্ডে ৫০,০০০ write এর cost বাড়ায়, অথচ সুবিধা দেয় সপ্তাহে মাত্র একবার।
• শুধু logtime index করুন: সাপ্তাহিক debugging এ query প্রায় সবসময় সময় ধরে filter করে (“২টা থেকে ৩টার মধ্যের log”)। তাই index শুধু এই column এ রাখুন।
• দ্বিতীয় index যোগ করবেন না: created_by এর মতো আরেকটা column দিয়ে সত্যিই query না করা পর্যন্ত তার index বানাবেন না।
• Bonus: log একবারই লেখা হয়, পরে আর বদলায় না। তাই indexed column এর expensive update cost এখানে একেবারেই লাগে না।

০৬ একাধিক column এ filter করার জন্য কীভাবে index করবো?

দুই বা তার বেশি column একসাথে নিয়ে বানানো index কে বলে composite index (compound বা multi-column index):

INDEX on (last_name, first_name)

এই index প্রথমে প্রথম column দিয়ে sort করে। প্রথম column এর value সমান হলে দ্বিতীয় column দিয়ে sort করে, তারপর তৃতীয় দিয়ে। ঠিক একটা phone book এর মতো, যেটা আগে last_name, তারপর first_name দিয়ে সাজানো:

Rahman, Abdul
Rahman, Fatima
Rahman, Karim      ← আগে last name দিয়ে group...
Rahman, Zara          ...তারপর প্রতিটা last name এর ভেতরে first name দিয়ে sort
Roy, Amit

Left-prefix rule (যেখানে সবাই আটকায়)

ধরুন একটা (A, B, C) composite index আছে। এটা শুধু সেই query গুলোতে সাহায্য করে, যেগুলো বাম দিক থেকে টানা column এ filter করে: শুধু A, বা A+B, বা A+B+C। এটাকে বলে left prefix। যে query প্রথম column টা বাদ দেয়, সেখানে এই index কাজে আসে না।

(last_name, first_name) index দিয়ে উদাহরণ:

• WHERE last_name = 'Rahman': সাহায্য করে (left prefix; সব Rahman একসাথে থাকে)।
• WHERE last_name = 'Rahman' AND first_name = 'Karim': সাহায্য করে (পুরো prefix)।
• WHERE first_name = 'Karim': সাহায্য করে না (প্রথম column নেই; Karim নামের সবাই আলাদা আলাদা last name এর মধ্যে ছড়িয়ে আছে)।

দুই ধরনের সমস্যা: পার্থক্যটা গুরুত্বপূর্ণ

• মাঝের column বাদ গেলে: index আংশিক সাহায্য করে। বাদ পড়া column এর আগের অংশটুকু কাজ করে। Index ততদূর পর্যন্ত খোঁজা ছোট করে, তারপর database বাকিটা scan করে।
• প্রথম column বাদ গেলে: index কোনো সাহায্য করে না। Index এ ঢোকার শুরুর জায়গাটাই (entry point) থাকে না।

(country, city, age) index দিয়ে উদাহরণ:

• WHERE country='BD' AND age=25 (মাঝের city নেই): আংশিক সাহায্য। Index সরাসরি BD এর row গুলোতে যায়। কিন্তু city না থাকায় ধারাটা ভেঙে যায়, তাই সেই row গুলোর মধ্যে age=25 খুঁজতে scan করতে হয়।
• WHERE city='Dhaka' (প্রথম country নেই): কোনো সাহায্য নেই, কারণ entry point নেই।
• WHERE city='Dhaka' AND age=25 (প্রথম country নেই): কোনো সাহায্য নেই। দুইটা column ই index এ আছে, কিন্তু প্রথম column না থাকায় index অকেজো।

Composite index এ column এর order

Column গুলো সাজান আপনার query কীভাবে খোঁজে সেই অনুযায়ী। যে column দিয়ে সবসময় filter করেন, সেটা আগে রাখুন। যেটা দিয়ে মাঝে মাঝে বাড়তি filter করেন, সেটা পরে রাখুন।

উদাহরণ: ধরুন আপনার দুইটা query আছে। একটা হলো “customer X এর সব order”, আরেকটা “একটা date range এ customer X এর order”। তাহলে index হবে (customer_id, order_date)। দুইটা query তেই customer_id আছে, তাই এটাই left prefix। কিন্তু “একটা date এ সব customer এর order” query তে এই index কাজে আসবে না। ওই query শুধু date এ filter করে, আর date left prefix না।

Covering index (এই term টা জানা দরকার)

Query তে যত column লাগে, সবগুলো index এ থাকলে database কে আর table এ যেতে হয় না। পুরো উত্তর index থেকেই দেওয়া যায়। যেমন (last_name, first_name) index আছে। এবার SELECT first_name FROM users WHERE last_name='Rahman' query টা চালালেন। এই query তে লাগে শুধু last_name আর first_name, আর দুইটাই index এ আছে। তাই database table এ না গিয়েই উত্তর দিয়ে দেয়। এটাকে বলে covering index (index টা query এর সব column “cover” করে)। Table এ যাওয়ার ধাপটা বাদ যায় বলে এটা আরো দ্রুত।

০৭ কখন index কাজে আসে না, বরং উল্টো ক্ষতি করে?

Index কাজে আসে না যখন:

• Non-indexed column এ filter: database কে full scan করতে হয়।
• Composite index এর প্রথম column বাদ: index এ ঢোকার entry point থাকে না।
• Table খুব ছোট: full scan এমনিতেই fast, তাই index এর overhead এর কোনো লাভ নেই।
• Column এ distinct value খুব কম: একটা column এ কতগুলো আলাদা value আছে, সেটাকে বলে cardinality। যেমন gender column এ মাত্র কয়েকটা value থাকে, তাই এর cardinality কম। এমন column এর index দিয়ে খুঁজলে বিশাল একটা অংশের row ফেরত আসে, তাই খুব একটা সময় বাঁচে না। Email এর মতো প্রায় সব row এ আলাদা value থাকা column (high cardinality) হলো index এর জন্য ভালো candidate।

Index ক্ষতি করে যখন:

• Write-heavy table এ খুব কম পড়া index: এটা শুধু write এর cost আর storage বাড়ায়।
• প্রায়ই বদলায় এমন column এ index: প্রতিটা change এ B-tree তে একটা delete আর একটা insert হয়।
• Over-indexing (“প্রতিটা column index করুন”): বেশিরভাগ index কখনো ব্যবহারই হয় না। অথচ সবগুলোই প্রতিটা write slow করে আর storage নেয়।

০৮ Full picture: index আগের সব কিছুর সাথে কীভাবে যুক্ত?

আগের সেশনগুলোতে আমরা database কে copy করেছি (০৩), cache করেছি (০৪), আর ভাগ করেছি (০৫)। এসব কাজ হয়েছে database এর বাইরে, অনেক machine জুড়ে। Index থাকে একটা single database এর ভেতরে, আর সেখানে প্রতিটা query কে দ্রুত করে।

আগের সেশনের সাথে সম্পর্ক

• Performance: একটা database এর ভেতরে read দ্রুত করার সবচেয়ে বড় উপায় হলো index (O(m) থেকে O(log m))।
• Caching (সেশন ০৪): দুটোই read দ্রুত করে, আর বিনিময়ে write এর cost আর storage বাড়ায়। Cache থাকলে query database পর্যন্ত যায়ই না। আর query database এ যেতেই হলে index সেটাকে দ্রুত করে।
• Sharding (সেশন ০৫): shard key ঠিক করে data কোন machine এ আছে। আর index ঠিক করে ওই machine এর কোথায় আছে। দুটোরই design নির্ভর করে আপনার query কীভাবে data খোঁজে তার উপর।
• বারবার ফিরে আসা শিক্ষা: replication, caching, sharding এর মতো index ও free না। আপনার query যেভাবে data খোঁজে সেই অনুযায়ী optimize করুন, আর তার cost টা জেনে বুঝে মেনে নিন।

০৯ মগজে প্রেশার দিন

আগে নিজে ভাবুন। তারপর দেখুন: সবাই যেভাবে ভাবে, কেন সেটা অসম্পূর্ণ, আর আসল insight টা কোথায়।

১০ যে টার্মগুলো শিখলাম

১১ শর্ট সামারি

১২ মনে রাখুন

• Sorted data দ্রুত খোঁজা যায়: index একটা column কে sorted রাখে, যাতে scan এর বদলে binary search করা যায়।
• Index শুধু নিজের column এর read এ সাহায্য করে: অন্য column এর query কোনো সুবিধা পায় না।
• প্রতিটা index write এর cost বাড়ায়: বেশি index মানে slower insert/delete/update আর বেশি storage। অভ্যাসের বশে না, query কীভাবে খোঁজে সেটা দেখে index করুন।
• Composite index এ column এর order একটা design decision: যে column প্রায় সবসময় filter হয় সেটা আগে রাখুন। কোন query সুবিধা পাবে, সেটা ঠিক করে left-prefix rule।
• Composite index এর প্রথম column বাদ দেওয়া যায় না: সেটা বাদ গেলে index অকেজো, query তে বাকি indexed column থাকলেও।
• Indexed column update এ cost দ্বিগুণ (delete + insert): প্রায়ই বদলায় এমন column index করা এড়িয়ে চলুন।
• Caching আর sharding এর মতোই চিন্তা: index ও একই trade-off মেনে চলে, শুধু database এর ভেতরে। Read এর speed পেতে write এর cost দিতে হয়।