ফান্ডামেন্টালস অব ডাটাবেজ ইনডেক্সিং
ডাটাবেজের যেকোনো টেবিলে দ্রুত কুয়েরি অপারেশনের একটা স্ট্র্যাটেজি হলো ইনডেক্সিং। আর Index হলো একটা স্পেশাল ডাটা স্ট্রাকচার যেটা দিয়ে এটা ইমপ্লিমেন্ট করা হয়ে থাকে।
কনসেপচুয়ালি ডাটাবেজের ইনডেক্স আর যেকোনো বইয়ের শেষদিকে থাকা ইনডেক্সের মধ্যে কোনো পার্থক্য নেই। একটা বইয়ের শেষদিকে সেই বইয়ে ব্যবহৃত গুরুত্বপূর্ণ টার্মগুলো যেভাবে পেইজ ধরে ইনডেক্স করা থাকে, যাতে পাঠক সহজেই বইয়ের যে পেইজে টার্মটা ব্যবহৃত হয়েছে সেখানে সরাসরি জাম্প করতে পারে, তেমনি ডাটাবেজের ডাটার মহাসমুদ্রে ছড়িয়ে-ছিটিয়ে থাকা কোনো টেবিলের সারি গুলো নির্দিষ্ট কিছু কলাম ধরে যদি আগে থেকেই ইনডেক্স করে রাখা যায় তাহলে যেকোনো রীড কুয়েরি অপারেশন অত্যন্ত দ্রুত হবে। টেবিলের কোন কলামগুলোর উপর ইনডেক্সিং করা উচিত সেটা বেশ কিছু প্যারামিটারের উপর নির্ভর করে। তবে ইনডেক্সিং নিয়ে কথা বলার আগে ডাটাবেজ স্টোরেজে এই ডাটাগুলো আসলে কীভাবে জমা থাকে সেটা বোঝা দরকার, নয়তো ইনডেক্সিং কেন দরকার হয় সেটা ভালোমতো বোঝা যাবে না।
আমরা ডাটাবেজের ফ্রন্টেন্ডে যখন ডাটা ভিউ করি, তখন দেখা যায় ডাটাগুলো খুব সুন্দরভাবে টেবিল আকারে শো হচ্ছে। টেবিলের প্রত্যেক সারিতে একটা ইনডিভিজুয়াল এন্টিটি/ রেকর্ড এবং কলামগুলোতে এই এন্টিটির ফিল্ড/প্রপার্টি গুলোর ভ্যালু জমা থাকছে। কিন্তু সত্যি বলতে ডাটাবেজের ডিস্ক মেমোরিতে টেবিলের মতো কোনো স্ট্রাকচার থাকে না। আমরা যদি একটা Row বেইজড ডাটাবেজের কথা চিন্তা করি তাহলে দেখা যায়, যেকোনো টেবিলের Row গুলো আসলে কোনো একটা পেইজের মধ্যে একটার পর একটা জমা থাকে। পেইজ হলো একটা ফিক্সড সাইজের মেমোরি, এবং ডাটাবেজ প্ল্যাটফর্মের উপর ভিত্তি করে এই সাইজের তারতম্য থাকতে পারে। সুতরাং কোনো পেইজে একটা টেবিলের কয়টা করে Row জমা থাকবে সেটা পুরোপুরি নির্ভর করছে পেইজের সাইজ এবং Row বা Row তে জমা থাকা কলামগুলোর ডাটা সাইজের উপর। আবার সবগুলো পেইজ জমা থাকে একটা Heap এর মধ্যে। এই Heap আর Data Structure এর Heap আসলে এক না। একে আমরা ফ্রী Pool of Memory হিসেবে চিন্তা করতে পারি। তাহলে দেখা যাচ্ছে Heap ই হলো আসল জায়গা যেখানো সব ডাটা জমা থাকে। হাই লেভেল থেকে বোঝার জন্য নীচের ছবিটা দেখা যেতে পারে।
এবার আসি একটা বিখ্যাত ইন্টারভিউ প্রশ্নে। নীচের কুয়েরিটি খেয়াল করা যাক,
SELECT * from Employeeবলতে হবে উপরের কুয়েরিটি কেন স্লো এবং কেন এপ্লিকেশনে এই ধরনের কুয়েরি সাধারণত করা উচিত না।
আমি যখন প্রথম এই প্রশ্ন দেখি, তখন চিন্তা করেছিলাম এই কুয়েরি স্লো হওয়ার কারণ হয়তো এই, এখানে কোনো ফিল্টার ইউজ করা হচ্ছে না। আরেকটা কারণ হতে পারে যে এখানে কোনো প্রকার প্রজেকশনও নেই। মানে কন্ডিশনের উপর ভিত্তি করে স্পেসিফিক কিছু কলামের ডাটা তুলে না এনে আমরা সব ডাটা একসাথে তুলে আনছি।
আমরা দেখেছি ডাটাবেজের মেমোরিতে ডাটাগুলো পেইজ আকারে Heap এর মধ্যে জমা থাকে। কাজেই দেখা যাচ্ছে, উপরের কুয়েরির উপর ভিত্তি করে ডাটা রিট্রিভ করতে গেলে একেবারে পেইজ ধরে স্ক্যান করা লাগছে। আমরা যেহেতু কোনো ফিল্টার এপ্লাই করতে পারছি না সুতরাং কোনো সারিকে SKIP করে যাওয়ারও কোনো সুযোগ নেই।
এখন কথা হলো, উপরের রীজনিংটা কি যথাযথ ?
উত্তর হলো, না। সেটা আরেকটু গভীরভাবে দেখলেই বোঝা যাবে, তবে এই রীজনিংটা সঠিক উত্তর এর দিকে যাওয়ার জন্য প্রথম স্টেপ বলা চলে। মানে রীজনিং এর শুরুটা ঠিক আছে।
এবার আমাদের রীজনিং ওয়াইজ কুয়েরিটাকে আরেকটু অপ্টিমাইজ করা যাক। এর জন্য আমরা ফিল্টার এবং প্রজেকশন এড করি।
SELECT FirstName, LastName, Email, Category
from Employee
WHERE Category = Maangerএই কুয়েরিটা আমাদের দৃশ্যপটে কোনো ইমপ্রুভমেন্ট এনেছে কি?
আমরা দেখেছি, একটা Row বেইজড ডাটাবেজের ডাটাগুলো মূলতঃ পেইজ আকারে হিপের মধ্যে জমা থাকে। প্রত্যেকটা পেইজে আবার থাকে একটা ফিক্সড নাম্বার অব Row। এখন আমরা যে ফিল্টারটা যোগ করেছি সেটার সাপেক্ষে ডাটা রিট্রিভ করার জন্য ডাটাবেজকে তাহলে হিপের মধ্যে থাকা প্রত্যেকটা পেইজ স্ক্যান করে দেখা লাগবে যে আমাদের কাংখিত সারিটা কি আসলে এই পেইজের মধ্যে পড়ছে কিনা। এখানে লক্ষ্যণীয়,
আমরা আসলে ডাটাবেজে Row বেইজড কোনো সার্চ করতে পারি না।
এটা অত্যন্ত গুরুত্বপূর্ণ ব্যাপার। কারণ ডিস্ক মেমোরি র্যামের মতো বাইট এড্রেসবল না যে আমরা সরাসরি মেমোরির এড্রেসে গিয়ে একটা পার্টিকুলার সারিকে তুলে আনতে পারবো। আপনি Array এর কথা চিন্তা করেন। Array থাকে র্যামের মধ্যে, এবং আপনি কোনোভাবে Array এর মেমোরি এড্রেস বা ফার্স্ট এলিমেন্টের এড্রেস জানতে পারলে ওই Array এর যেকোনো এলিমেন্টের এড্রেস আপনি বের করতে পারবেন। কিন্তু আমরা ডাটাবেজের সারিগুলো স্টোর করছি একটা ফ্রী মেমোরি পুলে। আমরা আগে থেকেই জানিনা ঠিক কোন পেইজের মধ্যে একটা পার্টিকুলার সারি স্টোর থাকবে। সুতরাং পেইজের এড্রেস পাওয়ার জন্য আমাদেরকে হিপের মধ্যে থাকা প্রত্যেকটা পেইজ স্ক্যান করে দেখা লাগবে আমরা যে সারির ডাটা খুঁজছি সেটা আসলে এই পেইজের মধ্যেই আছে কিনা।
একই কারণে আমরা প্রজেকশন ইউজ করেও কুয়েরি লেভেলে তেমন ইম্প্রুভমেন্ট আনতে পারি না। কারণ আমাদেরকে আল্টিমেটলি পেইজ ধরে প্রত্যেকটা Row এর ডাটাই স্ক্যান করে দেখা লাগছে। মজার ব্যাপার হলো আমরা যে পেইজের মধ্যে Match পাচ্ছি, সেই পেইজে শুধু মাত্র ওই Row এর সব ডাটাই থাকছে তা না, বরং অন্য আরেকটা Row যেটা ফিল্টারের সাথে পুরোপুরি ম্যাচ করছে না তার ডাটাও থাকছে এবং লজিকালি আমরা সেটাকেও read করছি। কাজেই দেখা যাচ্ছে, আমরা যে প্রজেকশনটা যোগ করেছি কুয়েরি লেভেলে সেটার কোনো বেনিফিট নেই এবং এরমতো করে ডাটা সিরিয়ালাইজেশনটা হচ্ছে ঠিক ডিস্ক থেকে ডাটা তুলে আনার পর। তবে মনে রাখতে হবে ডাটা সিরিয়ালাইজেশন এবং ডিসিরিয়ালাইজেশনের একটা cost থাকে। আবার এই ডাটা over the network যখন ডাটাবেজ সার্ভার থেকে ব্যাকেন্ড সার্ভারে আসে, সেটারও একটা cost থাকে। কাজেই এপ্লিকেশন লেভেলে চিন্তা করলে অবশ্যই কুয়েরিতে প্রজেকশন ব্যবহার করা উচিত।
আমরা মূল প্রশ্নে ফিরে যায়। তাহলে দেখা যাচ্ছে, ফিল্টার এবং প্রজেকশন ব্যবহার করেও আমরা ডাটাবেজের স্ক্যানিং লেভেলে কোনো প্রকার ইমপ্রুভমেন্ট আনতে পারছি না। ঠিক এখানেই আসলে ইনডেক্সিং এর প্রয়োজন পড়ে। যেকোনো বড়ো সাইজের টেবিলে ইনডেক্সিং করা দরকার, নাহলে যেকোনো প্রকার কুয়েরি করতে গেলেই ডাটাবেজের স্ক্যানিং Cost অনেক বেশি পড়ে। এমনকী ফ্রন্টেণ্ড থেকে API রিকোয়েস্ট করে যদি ডাটা তুলে আনা লাগে, অনেক সময় দেখবেন টেবিলে ইনডেক্স করা না থাকলে একটা বিশাল পেজিনেশন গ্যাপ দিয়ে API কল করলে ডাটা তুলে আনতে আনতেই ব্যাকেণ্ড 504 Error কোড দিয়ে রেস্পন্স ধরিয়ে দিবে।
যাইহোক, এবার দেখা দরকার ইন্ডেক্সিংটা আসলে কীভাবে করে।
ইন্ডেক্সিং কীভাবে করে ?
ইনডেক্সিং করার জন্য ডাটাবেজ একটা ডাটা স্ট্রাকচার ব্যবহার করে যার নাম Index (B-tree is used mostly)। সহজভাবে বলতে গেলে এটা আসলে একটা কন্টেইনার যেটা নিজেই Heap এর বাইরে আলাদা করে পেইজিং মেনটেইন করে থাকে। একটা বইয়ের ইনডেক্সে আসলে কী করা হয়, বইয়ে ব্যবহৃত বিভিন্ন গুরুত্বপূর্ণ কীওয়ার্ড/টার্মগুলোর পাশে বইয়ের যে পেইজে সেটা উল্লেখিত হয়েছে সেই পেইজ নাম্বারটা জুড়ে দেয়া হয়, এবং পুরো ইন্ডেক্সটাই Alphabetical অর্ডারে সাজানো থাকে যাতে পাঠক সহজেই কীওয়ার্ডটা সার্চ করতে পারে। এখানে লক্ষ্যণীয় যে, পাঠককে এক্ষেত্রে দুইবার সার্চ করা লাগে। একবার ইন্ডেক্স পেইজে টার্মটার পেইজ নাম্বার বের করতে, আরেকবার ঠিক সেই মেইন পেইজে। ডাটাবেজের ইনডেক্সিংও একই টেকনিকে চলে। এখানে Index ডাটা স্ট্রাকচারে মূলতঃ একটা সারির পেইজ এড্রেস এবং যে কলাম দিয়ে ইন্ডেক্স করা হয়েছে তার Value থাকে (যেমন Employee Category, যদি এটা দিয়ে ইনডেক্স করা থাকে)।
ডাটাবেজ প্রথমে এই ইন্ডেক্সের পেইজ স্ক্যান করে দেখে যে, চলমান কুয়েরির জন্য Matched Rows আসলে হিপের মধ্যে ঠিক কোন পেইজের মধ্যে থাকতে পারে। এরপর ম্যাচ হওয়া পেইজের এড্রেসে হিট করে উদ্দিষ্ট সারিগুলো ফিল্টার ওয়াইজ তুলে আনে। এভাবে ইন্ডেক্সিং এর ফলে কুয়েরি অনেক দ্রুত হয়, কারণ এখন আর আমাদেরকে হিপের মহাসমুদ্র সাঁতরে পেইজ নাম্বার বের করা লাগছে না। আমরা খুব সহজেই ইন্ডেক্স পেইজ স্ক্যান করে পেইজ এড্রেস পেয়ে যেতে পারি এবং হিপের মধ্যে ডিরেক্ট এই পেইজের এড্রেসেই হিট করতে পারি। অবশ্যই এই ইনডেক্স পেইজের স্ক্যানিংয়েরও একটা cost থাকে, কিন্তু সেটা হিপ মেমোরির পেইজ স্ক্যান থেকে অনেক অনেক দ্রূত। এক্ষেত্রে সর্টিংয়েও বাড়তি সুবিধা পেতে পারি যদি যে কলাম ধরে ইন্ডেক্স করছি সেটা দিয়েই ডাটা সর্ট করা হয়। কারণ আমরা যদি ইনসার্শনের সময়েই অর্ডার মেইনটেইন করে ইনসার্ট করতে পারি, তাহলে ডাটা কুয়েরির পর নতুন করে আর সর্ট করা লাগে না। কারণ তুলে আনা ডাটাগুলো অলরেডি সর্টেড।
কাজেই আমাদের আগের কুয়েরিটা বিশ্লেষণ করলে দেখা যায়, আমরা যদি Employee টেবিলের Category Column এর উপর ইন্ডেক্স করে রাখি, তাহলে Category দিয়ে ফিল্টার করা কুয়েরি রান করার জন্য ডাটাবেজ ইঞ্জিন প্রথমে ইন্ডেক্স ডাটা স্ট্রাকচার রীড করে দেখবে এই প্রকার ক্যাটাগরির সারিগুলো হিপের মধ্যে কোন কোন পেইজের মধ্যে থাকে। এরপর হিপের মধ্যে পেইজ বাই পেইজ স্ক্যান না করে ডিরেক্ট ইন্ডেক্স থেকে পাওয়া পেইজগুলোর এড্রেসেই হিট করে ডাটাবেজ ইঞ্জিন কুয়েরি করবে।
যেমন আমরা কুয়েরি করেছি Manager Category দিয়ে ফিল্টার করে। কাজেই ডাটাবেজ ইঞ্জিন প্রথমে ইন্ডেক্স থেকে দেখে নিবে এই ক্যাটাগরির Employee রা হিপের ভেতর কোন পেইজের মধ্যে থাকে। ধরে নিচ্ছি পেইজ ১, ২ এবং ৩ তে থাকে। তাহলে ডাটাবেজ ইঞ্জিন আমাদের কুয়েরি অনুযায়ী এই তিনটা পেইজের সব সারি তুলে এনে রিটার্ন করে দিতে পারবে। আমরা যদি আরো কন্ডিশন এড করতাম তাহলে, হিপের মধ্যে থাকা এই ৩ টা পেইজের মধ্যে ফার্দার ফিল্টার করে ইঞ্জিন ডাটা তুলে আনতো। এখানে বলে রাখা ভালো, আমরা চাইলে একাধিক কলামের উপর ইন্ডেক্সিং করতে পারি, কিংবা কয়েকটা কলাম মিলিয়েও একটা কম্পোজিট ইন্ডেক্স বানাতে পারি। এটা পুরোপুরি নির্ভর করছে ইউজ কেইসের উপর।
ইন্ডেক্সিং এর খরচ
ইনডেক্সিং কুয়েরি লেভেলে আমাদেরকে যে অপ্টিমাইজেশনটা দেয় এটা ফ্রীতে না। ইনডেক্সিং এর সুবিধা পেতে হলে ডাটাবেজকে ডাটা Insertion সময় একটা খরচ বহন করতে হয়। কারণ, মেইন পেইজে ডাটা রাখা, সেই ডাটার পেইজ রেফারেন্স আবার ইনডেক্স পেইজের মধ্যে রাখা এগুলো অবশ্যই Data Insertion Cost বাড়িয়ে দেয়। এছাড়া আলাদা করে ইনডেক্স পেইজ সার্চ করার cost তো আছেই। আবার কোন কলামের উপর ইনডেক্স করছি সেটারও উপরও অনেক কিছু ডিপেন্ড করে। তাই না বুঝে যেমন তেমন কলামের উপর ইনডেক্স করা উচিত না, এক্ষেত্রে ক্রিটিকাল মোমেন্টে লাভের চেয়ে ক্ষতিই বরং বেশি হয়।
কোন কলামগুলোর উপর ইনডেক্সিং করা উচিত
কোন কলামের উপর ইনডেক্সিং করা উচিত এটা কিছু ফ্যাক্টরের ওপর নির্ভর করে।
১। কার্ডিনালিটি অব কলাম
একটা কলামের Cardinality বা ডিস্টিংক্ট ভ্যালুর সংখ্যা কেমন সেটার ওপর ইন্ডেক্সিং এর দক্ষতা নির্ভর করছে। সাধারণত একেবারেই লো কার্ডিনালিটি কিংবা খুব হাই কার্ডিনালিটির কলামগুলোর ওপর ইনডেক্সিং করা উচিত না। কারণ একটা কলামের ডিস্টিংক্ট ভ্যালুর সংখ্যা কম হলে দেখা যাবে, ইন্ডেক্স লেভেলে ডাটাবেজ ইঞ্জিন খুব বেশি পেইজকে এলিমিনেট করতে পারছে না। যেমন ধরেন একটা কলাম হলো Sex, আমাদের টেবিলে Sex এর যদি শুধু দুইরকম ভ্যালু থাকে Male এবং Female, তাহলে ইনডেক্স লেভেলে খালি এই দুইপ্রকার পার্টিশনই পাবেন। মানে, আপনি হয় Male আছে পেইজ গুলো স্ক্যান করবেন নাহয় Female আছে এমন পেইজ গুলোকে স্ক্যান করবেন। এখন আপনার যদি ৩০ টা পেইজ থাকে ডাটাবেজের, এবং শুধুমাত্র পাঁচটা পেইজে যদি থাকে শুধু Male এর ডাটা, তাহলে চিন্তা করেন Femaleআছে এমন Row কুয়েরির জন্য ডাটাবেজকে ২৫টা পেইজকেই স্ক্যান করতে হচ্ছে।
একই কারণে দরকার না পড়লে হাই কার্ডিনালিটির কলামগুলোর জন্যও ইনডেক্সিং করা ভালো সিদ্ধান্ত না। কারণ এক্ষেত্রেও দেখা যাবে ডাটাবেজকে বিভিন্ন পেইজ ধরে ডাটা রিট্রিভ করে আনা লাগে। কারণ একেকটা Row এর জন্য দেখা যাবে একেক রকম পেইজ ইনডেক্স করা আছে। উদাহরণ স্বরূপ বলা যায়, GUID ডাটার ওপর কখনো ইনডেক্সিং করা উচিত না। কারণ GUID মানেই ডিস্টিংক্ট ভ্যালু। আপনার টেবিলে যদি এক লক্ষ Rows থাকে, তাহলে এক লক্ষ GUID। এবং এই লক্ষ GUID এর জন্য আলাদা করে ইন্ডেক্স ডাটা স্ট্রাকচার মেইনটেইন করা এটা মশা মারতে কামান দাগানোর মতোই ব্যাপার।
তাহলে বোঝা যাচ্ছে আমাদেরকে ইনডেক্সিং করতে হবে এমন কলামের ওপর যেগুলোর ডিস্টিংক্ট ভ্যালু খব বেশিও না, আবার কমও না এবং টেবিলের সব ডাটার একটা ইভেন ডিস্ট্রিবিউশন থাকবে এইসব ডিস্টিংক্ট ভ্যালুগুলোকে কেন্দ্র করে। সেক্ষেত্রে ডাটাবেজ ইঞ্জিন মেইন পেইজে যাওয়ার আগেই বুঝে যাবে, কুয়েরির রেইঞ্জের ডাটাগুলোর জন্য কোন কোন পেইজগুলো আসলে স্ক্যান করার দরকারই নাই।
২। ফ্রীকোয়েন্টলি ফিল্টার্ড কলাম
যেসব কলামগুলো ধরে ফ্রীকোয়েন্টলি কুয়েরি করা হয়, সেগুলোর ওপর ফিল্টার করলে ভালো রেজাল্ট পাওয়া যাবে।
৩। সর্টেবল কলাম
যে কলামের ওপর বেইজ করে ডাটা সর্ট করা হয়ে থাকে সেই কলামের ওপর ইনডেক্স করা থাকলে ভালো রেজাল্ট পাওয়া যায়। যেমন একটা টেবিলের মোস্ট রিসেন্টলি এডেড ডাটাগুলো যদি আগে শো করানো লাগে, তাহলে ক্রিয়েশন ডেইটের ওপর ইনডেক্স করলে ভালো রেজাল্ট পাওয়া যাবে।
৪। যেসব ফিল্ডের ওপর বেইজ করে JOIN অপারেশন করা হয় সেগুলোর ওপর ইনডেক্সিং করা যায়।
৫। Text searchable ফীল্ডগুলোর ওপর ( searched through wild card match or Regex) ইনডেক্সিং থাকা একটা ভালো আইডিয়া। যেমন Email, FirstName, LastName।
সত্যি বলতে এখানে হার্ড কোডেড কোনো রুলস বানানোর চেয়েও TradeOff টা বোঝা বেশি জরুরী। এটা শুধু এক্ষেত্রে নয়, বরং সিস্টেম ডিজাইন বা আর্কিটেকচারের যেকোনো ক্ষেত্রেই সত্য। এখানে কোনো কিছুই চূড়ান্তভাবে ভালো বা খারাপ নয়, বরং কোন সীনারিওতে আমরা কোন জিনিসটা ইমপ্লিমেন্ট করছি এটাই মূল বিষয়।
এই লেখায় ইন্ডেক্সিং এর একেবার বেসিক আলাপটুকু করলাম। ভবিষ্যতে আরো বিস্তারিত লেখার ইচ্ছা আছে।
[দুনিয়ার কোনো জিনিসই ফ্রী না, কিন্তু আপনি যে এই লেখাটা পড়লেন এটা একেবারেই ফ্রী। মিডিয়াম এর জন্য আমাকে এক পয়সাও দিবে না। কিন্তু আপনি চাইলে আমাকে একটা কফি খাওয়াতে পারেন 😉। আমাকে কফি খাওয়াতে চাইলে বিকাশ করুন ০১৮৩১৩০৯৩০২ নাম্বারে যতো ইচ্ছা ]
References:
[Udemy Course] Fundamentals of Database Engineering by Hussain nasser
[Book] Database System Concepts — Abraham Silberschatz Henry F. Korth S. Sudarshan
Wikipedia
