Database Indexing

နားလည်ထားရမယ့် အချက်

Index မရှိရင် condition နဲ့ ကိုက်ညီတဲ့ row တွေကို ရှာဖို့ table scan အပြည့်လုပ်ရပါတယ် — database က row တိုင်းကို တစ်ခုချင်း ဖတ်ပြီး စစ်ရတာကြောင့် table ကြီးလာလေ၊ O(n) time ကြာလေဖြစ်ပါတယ်။ Query ကို ဘယ်လောက်ပဲ selective ဖြစ်ဖြစ် ဒီပြဿနာက ရှိနေမှာပါ။ Index ဆိုတာ column value တွေကနေ row location ကို sorted mapping ထားတဲ့ separate ဖြစ်တဲ့ auxiliary data structure (အများဆုံးက B-tree) တစ်ခုပါ — ဒါက lookup ကို tree ထဲမှာ binary search O(log n) နဲ့ လုပ်နိုင်စေပြီး ကိုက်ညီတဲ့ row ကို တန်းသွားနိုင်စေပါတယ်၊ စာအုပ်တစ်အုပ်ရဲ့ index ကနေ page ကို တန်းသွားနိုင်တာလို ပါပဲ၊ အစအဆုံး ဖတ်စရာ မလိုပါဘူး။ ဒီ speed ကတော့ အခမဲ့ မရပါဘူး — INSERT၊ UPDATE၊ DELETE တိုင်းက table ပေါ်က index အားလုံးကိုပါ update လုပ်ရမှာဖြစ်ပြီး index တစ်ခုစီက disk space ပိုစားပါတယ်။ Index ဆယ်ခုပါတဲ့ table တစ်ခုက index နှစ်ခုပဲပါတဲ့ table ထက် write ပိုနှေးပါတယ်။ Column မှားရွေးပြီး index လုပ်တာ (boolean flag လို cardinality နည်းတဲ့ column က search ကို သိပ်မကျဉ်းပေးနိုင်ပါဘူး) ဒါမှမဟုတ် 'ဖြစ်လာမလားလို့' index အများကြီးထည့်တာက read မှာ ချွေတာနိုင်တာထက် write overhead နဲ့ storage ကို ပိုကုန်တတ်ပါတယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ဟာ page load တိုင်းမှာနီးပါး 'slug = X ဖြစ်တဲ့ lesson အားလုံးရှာမယ်' လို query ကို run ပါတယ် — ဒါကြောင့် lessons table မှာ slug column ပေါ်မှာ index ထားလိုက်တာဟာ row ထောင်ချီရှိတဲ့ full scan တစ်ခုကို instant lookup လိုမျိုး ပြောင်းပေးလိုက်ပါတယ်။ ဒါပေမဲ့ အစပိုင်းမှာ engineer တစ်ယောက်က 'is_published' (value နှစ်ခုပဲရှိတဲ့ boolean) ပေါ်မှာလည်း index ထည့်ခဲ့ဖူးပါတယ် — ဒါက search ကို သိပ်မကျဉ်းပေးနိုင်ဘဲ content update တိုင်းကို read speed ကို မထိရောက်စွာ နှေးစေတဲ့ cardinality နည်းတဲ့ data ကို index လုပ်တဲ့ classic case ပါပဲ။ WHERE/JOIN clause တွေမှာ column ဘယ်ဟာတွေ တကယ်သုံးလဲဆိုတာ ခန့်မှန်းမယ့်အစား စစ်ဆေးဖို့က index set ကို အသုံးဝင်စေတဲ့ အချက်ပါ။

Index မရှိရင် condition ရှာဖို့ row တိုင်းကို scan လုပ်ရတဲ့ O(n) full table scan ဖြစ်ပါတယ်။
B-tree index က sorted structure ဖြစ်ပြီး O(log n) lookup ပြုနိုင်စေပါတယ်၊ book index ကဲ့သို့ပါပဲ။
Index တိုင်းက write ကို နှေးစေပြီး disk space စားစေပါတယ်၊ column မှားရွေးရင် ဒီစရိတ်က အကျိုးထက် ပိုပါတယ်။

အတူတူ စမ်းရေးကြည့်မယ်

text

WITHOUT INDEX (full table scan)          WITH INDEX (B-tree on `slug`)
+-------------------------+               +---------------------+
| row 1: slug="go-intro"  | check         | B-tree (sorted)     |
| row 2: slug="rust-fn"   | check         |      [go-intro]     |
| row 3: slug="cdn-edge"  | check <- MATCH|     /            \   |
| row 4: slug="sharding"  | check         | [cdn-edge]  [rust-fn]|
| ... (10,000 more rows)  | check x 10000 +---------------------+
+-------------------------+               lookup("cdn-edge")
O(n) — cost grows with table size          -> binary search, O(log n)
                                            -> jump straight to match

Trade-off: every INSERT/UPDATE/DELETE must also update the B-tree.
More indexes = slower writes + more disk space, even if reads are fast.

You should see

Index တစ်ခုက read ကို O(n) မှ O(log n) အောင် မြှင့်ပေးပေမယ့် write operation တိုင်းကို index structure ကိုပါ update ရအောင် ဖြစ်စေတယ်ဆိုတာ ပြသပါတယ်။

၅ မိနစ် စမ်းကြည့်

Tutorial Platform ရဲ့ 'quiz_attempts' table မှာ column တွေက user_id၊ lesson_id၊ score၊ attempted_at ပါတယ်။ 'user တစ်ယောက်ရဲ့ attempt history ကို attempted_at အလိုက် ပြသမယ်' ဆိုတဲ့ query type အတွက် ဘယ် column(s) ပေါ်မှာ index ချမလဲ ဆုံးဖြတ်ကြည့်ပါ။

သတိလေးတစ်ချက်

Low-cardinality column (boolean/status flag) ကို index လုပ်လိုက်ရင် row များစွာက value တူနေတဲ့အတွက် search space သိပ်မကျဉ်းဘဲ index ကို scan နီးပါးလုပ်ရသလို ဖြစ်သွားတတ်ပါတယ်။

'ဖြစ်လာမလားလို့' column တိုင်းကို index ထည့်တာက write performance ကို significant ကျစေပြီး rarely-queried index တွေက storage ကို အလကားစားနေတတ်ပါတယ်။

Wikipedia — Database index — System Design