Composite indexes, covering indexes — Hinglish notes

4.4.14 · Coding › Databases

Composite index KYA hota hai?

Key idea yeh hai ki sort order hierarchical hota hai, bilkul dictionary mein words ki ordering ki tarah: (A, 1) < (A, 2) < (A, 9) < (B, 1) < (B, 5).

YEH EXIST KYU KARTE HAIN? (first principles)

Ek B-tree index tumhe binary-search-jaisi lookups karne deta hai: $N$ rows scan karne ( $O (N)$ ) ki jagah, tum ek balanced tree mein $O (lo g N)$ mein descend karte ho.

Lekin do problems abhi bhi rehti hain:

Multi-condition filters. Ek query WHERE a=? AND b=? do alag indexes par sirf ek ko efficiently use kar sakti hai, phir baaki ko filter karna padta hai. Ek composite (a,b) index dono ko ek saath narrow kar deta hai.
Extra fetch. Index matching row pointers find karne ke baad bhi, DB ko table par jaana padta hai doosre columns padhne ke liye jo tumne maange the. Har row ke liye woh ek random I/O hai. Covering index woh step hata deta hai.

Composite index ordering kaise kaam karta hai — leftmost-prefix rule

Kyun? Kyunki index lexicographically sorted hai. Sirf $c_{2}$ jaanna (bina $c_{1}$ ke) ek (last, first) phone book mein sirf first names jaanne jaisa hai — matching entries har jagah scattered hain, toh koi fast seek possible nahi hai.

Worked example Index

(a, b, c) — kaun si queries seek kar sakti hain?

Query predicate	Index use karta hai?	Yeh step kyun?
`a = 5`	✅ (a)	leftmost prefix present hai
`a = 5 AND b = 3`	✅ (a,b)	b tak full prefix
`a = 5 AND b = 3 AND c = 1`	✅ (a,b,c)	full prefix
`b = 3`	❌ (seek)	`a` missing → koi leftmost prefix nahi
`a = 5 AND c = 1`	⚠️ partial	`a` par seek karta hai, phir `c` filter karta hai (b par gap)
`a = 5 AND b > 3 AND c = 1`	⚠️	b par range seeking rok deti hai; `c` sirf filter karta hai

Covering index kaise kaam karta hai

Worked example Query ko "index-only" banana

SELECT user_id, total
FROM orders
WHERE status = 'paid';

Index (status) → rows find karta hai, phir table se user_id, total fetch karta hai. Extra I/O.
Index (status, user_id, total) → ✅ covering: status filtering ke liye, user_id, total index leaf mein present hain. Jawab seedha index se aata hai. Yeh kyun kaam karta hai: query jitne bhi columns touch karti hai sab index mein hain.

Search key bloat karne se bachne ke liye Postgres syntax: CREATE INDEX ON orders (status) INCLUDE (user_id, total); — status searchable key hai, baaki sirf leaves mein stored payload hain.

Figure — Composite indexes, covering indexes

Worked example: ek query ke liye ek index design karna

Worked example Real query

SELECT order_id, amount
FROM orders
WHERE customer_id = 42 AND status = 'open'
ORDER BY created_at DESC
LIMIT 10;

Step 1 — equality columns pehle: customer_id, status equalities hain → inhe pehle rakho. Kyun? Ye dono ek exact slice tak narrow karte hain. Step 2 — sort column aage: ORDER BY ke liye created_at → aage, taaki rows pre-sorted niklen aur LIMIT 10 bas top grab kare. Kyun? Koi alag sort step ki zaroorat nahi. Step 3 — output cover karo: order_id, amount ko INCLUDE payload ke roop mein add karo. Kyun? Phir koi table fetch nahi.

Final: CREATE INDEX ON orders (customer_id, status, created_at DESC) INCLUDE (order_id, amount);

Common mistakes

Flashcards

Composite index kya hota hai?

Multiple columns par ek index jo lexicographically sorted store hota hai — pehle col1 se, phir equal col1 ke andar col2 se, etc.

Leftmost-prefix rule batao.

(c1,…,cn) par ek index tabhi usable hai jab query ek leftmost prefix (c1, ya c1+c2, …) constrain kare; prefix columns par equality, phir agle par ek range.

Index (a,b) WHERE b = 5 ko efficiently kyun serve nahi kar sakta?

Entries pehle a se sorted hain, toh ek given b value poore mein scattered hai — seek karne ke liye koi contiguous range nahi.

Covering index kya hota hai?

Ek index jisme query ke saare columns hain (filter + SELECT), taaki koi table fetch na ho aur index-only answer mile.

Equality vs range columns — ordering rule kya hai?

Equality-predicate columns pehle rakho, range/ORDER BY column aakhir mein, taaki tum seek karke order mein range-scan kar sako.

Postgres INCLUDE (cols) kya karta hai?

Columns ko leaf pages mein non-key payload ke roop mein add karta hai taaki index covering bane, bina searchable key bloat kiye.

Covering/wide indexes ka main downside kya hai?

Zyada storage aur slower writes (har modification index update karna padta hai); cache mein fit nahi ho sakta.

Table fetch eliminate karna itna impactful kyun hai?

Har fetch scattered table pages par potential random I/O hai; index-only scan hazaron random reads avoid karta hai.

Recall Feynman: ek 12-saal ke bachche ko samjhao

Ek giant phone book imagine karo. Agar woh last name phir first name se sort hai, tum "Smith, Anna" super fast dhundh sakte ho. Lekin agar tum sirf "Anna" jaante ho (koi last name nahi), tumhe POORI book padhni padegi — isliye ek multi-column index ko tum chahta hai ki tum pehla column jaano. Ab imagine karo phone book har insaan ka phone number unke naam ke saath print bhi karti hai — phir tumhe unke ghar drive kar ke poochne ki zaroorat nahi. Woh printed-number trick ek covering index hai: jo kuch bhi chahiye woh sab wahin hai.

Connections

B-tree indexes — woh structure jo ordered seeks possible banata hai
Clustered vs non-clustered indexes — "extra fetch" kyun exist karta hai
Query planner / EXPLAIN — index-only scan verify kaise karein
Index selectivity & cardinality — kaun sa column lead kare yeh choose karna
Write amplification — indexes add karne ki cost side
Database normalization — affect karta hai ki tum kis column par filter karte ho