Skip to main content

Database Indexing in Django application

 


Database Indexing




Database indexing is a technique used to optimize the performance of database queries by allowing the database management system (DBMS) to quickly locate and retrieve specific rows of data. Indexes are data structures that provide a faster way to look up records based on the values stored in one or more columns of a table. When you create an index on a table, the DBMS creates a separate data structure that maps the values in the indexed columns to the corresponding rows in the table. Default Type of Index is B-Tree Index ( The king of all indexes)


বইতে কোন টপিক খুজতে গেলে আমরা টেবিল অফ কনটেন্ট থেকে দেখি এই টপিক কত নম্বর পেজে আছে।যাতে করে আমাদের পুরো বই খুজতে না হয়। ডেটাবেজ ইনডেক্সিং ও তেমনই একটা ইফিসিয়েন্ট টেকনিক।ডেটাবেজে কোন ডেটাকে দ্রুত খুজে বের করার জন্য ইনডেক্সিং করা লাগে।যদি এমন হয় একটা কুয়েরি বার বার এক্সিকিউট করতে হচ্ছে এবং একটা কলাম থেকে ভ্যালু বার বার খুজতে হচ্ছে তখন আমরা সেই কলামে ইনডেক্সিং করতে পারি।এর মাধ্যমে কোন ডেটা দ্রুত রিট্রাইভ করা যায়।কিন্তু ইন্টার্নালি কাজটা কিভাবে হয়?যখন আমরা ইনডেক্স ক্রিয়েট করি তখন ইন্টার্নালি সেই কলামের সবগুলা ডেটা আলাদা একটা ফাইলে রাখা হয়।এবং সেই ডেটা গুলা B-Tree ডেটা স্ট্রাকচার অনুযায়ী সাজানো হয়।B-Tree হলো বাইনারি সার্চ ট্রি এর মতই তবে কিছুটা এডভান্স।এই ট্রি এর লিফ সবসময় সেম লেভেলে থাকে এবং ট্রি সবসময় সেল্ফ ব্যালেন্স মেইনটেইন করে।বাইনারি সার্চ ট্রি তে একটা নোডে একটাই Key থাকে।কিন্তু এখানে একাধিক Key থাকে।এবং Key গুলা এসেন্ডিং অর্ডারে সাজানো থাকে।যার ফলে দ্রুত কোন ডেটা এখান থেকে রিট্রাইভ করা সম্ভব হয়।তবে অপ্রয়োজনী ইনডেক্সিং করলে ইফিসিয়েন্সি কমে আসে কারণ ইনডেক্সিং এর জন্য এক্সট্রা মেমোরি দরকার হয়।এছাড়া যেসব অপারেশনে রিড বেশি হয় সেখানে ইনডেক্সিং ভালো কাজ করে।কিন্তু আপডেট বা ইনসার্ট অপারেশন ইনডেক্সিং এর জন্য স্লো কাজ করে।
আমি ৫০ হাজার রো এর একটা ডেটাবেজে ইনডেক্সিং করে টেস্ট করলাম।রেসপন্স আসছে ৫০ মিলি সেকেন্ডে।আর ইনডেক্সিং ছাড়া অলমোস্ট ২০০ মিলি সেকেন্ড প্লাস।তার মানে আমরা টাইম লিমিট ৪ গুন কমাতে পারছি


B-Tree Index

# How does a B-Tree index work?

B-tree index is the most common in use. It achieves its goal by creating a tree structure of blocks containing key values in ascending order. Each of these blocks references another two child blocks, where left side keys keep value lesser than the current keys and the right side ones are more than the current keys. This way seeking values inside an index comes up to simple comparison calculations. B-tree can also handle equality and range queries on data that can be sorted into an ordering.

1. suppose you have these values: 1 2 3 4 5 6 7 8 9 

2. Now B-Tree index will create a tree as blow. Index Root and Leaf blocks



3. Now Search for the value 5 
    1. Now it'll Scan the index root

            
        

    2. Find the leaf block

    

    

    3. Search the value of the leaf block

    





database indexing এ কেন B+ Tree data structure ব্যাবহার করা হয়?

ডাটাবেজের ডাটা সাধারণত হার্ডডিস্ক বা SSD-তে জমা থাকে, ডাটাবেসে indexing-এর জন্য B+ Tree ব্যবহার করা হয় কারণ এটি disk-based storage-এর জন্য অত্যন্ত optimized। Database-এর মূল bottleneck সাধারণত CPU নয়, বরং disk I/O। B+ Tree এমনভাবে ডিজাইন করা হয়েছে যাতে কম সংখ্যক disk access-এ data খুঁজে পাওয়া যায়।

B+ Tree-এর প্রতিটি node-এ অনেকগুলো key রাখা যায়।

উদাহরণ:

Binary Search Tree-তে একটি node-এ ১টি key থাকে।

B+ Tree-তে একটি node-এ 100–500 বা তারও বেশি key থাকতে পারে (page size-এর উপর নির্ভর করে)।

ফলে tree-এর height অনেক কম হয়।

ধরুন প্রতি node-এ 100টি child থাকতে পারে।

Level 0 1

|

Level 1 100

|

Level 2 10,000

|

Level 3 1,000,000

মাত্র ৩–৪ level-এ লাখ লাখ row index করা সম্ভব।

এর মানে:

  • কম disk read
  • দ্রুত search





Applying index into a django model. 




This is our model. Here we didn't apply any indexing in this model. If we want to get value using movie_key field filtering , It’s clear that PostgreSQL will decide to use sequential scan to retrieve the item, which simply means that it had to scan all table rows to finish its action. This practice has a clear impact on execution time value. Therefore, to improve the performance of the API, we should use an index on the movie_key field. Thanks to Django, we can make this change directly in our model by applying db_index=True in the desired field. After running the database migrations and sending the request once again, we can see the change in the executed query.

This time, the database engine used index scan on the index automatically created by PostgreSQL. This means that no sequence scanning was performed as the engine searched the index tree by providing a specific movie_key value. The execution time is significantly lower this time, coming down to less than 1ms.

Note: Database create default indexes in primary key

Surprisingly though, there is a way to optimize this query even more, allowing the database to skip the part of searching the table at all. This is achievable using a covering/inclusive index.

Covering / Inclusive Indexes 

They are useful when performing “value-for-value” lookups, which means retrieving one column value in the table based on another one. The index can be set up in the Meta class of our model. Additional field value is added in the include parameter of the UniqueConstraint index

for this query where Movie is the model : 

Movie.objects.filter(movie_key=movie_key).values_list('original_title',flat=True).get()

SELECT original_title FROM movie WHERE movie_key='Kjrkdj'




Cons:

1. Make index much bigger

2. Can sometimes replace composite indexes ( which are include lot of columns)


Labels:

Comments

Post a Comment

Popular posts from this blog

WSGI vs ASGI: What Every Django Developer Should Know !

  If you've been developing with Django, you've probably come across WSGI (Web Server Gateway Interface), the trusted friend of all traditional, synchronous web apps. But in this fast-moving, real-time world, you may have also heard about its dynamic, asynchronous cousin ASGI (Asynchronous Server Gateway Interface). WSGI (Web Server Gateway Interface): 1. The OG (original) Django interface, designed for synchronous HTTP requests. 2. Perfect for blogs, CMS, e-commerce, and standard web apps. 3. Uses servers like Gunicorn or uWSGI. 4. Limited to handling one request at a time. ASGI (Asynchronous Server Gateway Interface): 1. The modern, scalable interface designed for asynchronous web apps. 2. Ideal for handling WebSockets, HTTP/2, and real-time features like chat apps. 3. Built for high concurrency; uses Uvicorn, Daphne, or similar ASGI servers. 4. Allows you to leverage Python’s async and await for non-blocking code. When to Choose What: WSGI: Traditional apps where synchronou...
Post a Comment
Read more

Django pk vs id

 Django pk VS id If you don’t specify primary_key=True for any fields in your model, Django will automatically add an IntegerField to hold the primary key, so you don’t need to set primary_key=True on any of your fields unless you want to override the default primary-key behavior. The primary key field is read-only. If you change the value of the primary key on an existing object and then save it, a new object will be created alongside the old one Example: class UserProfile ( models . Model ): name = models . CharField ( max_length = 500 ) email = models . EmailField ( primary_key = True ) def __str__ ( self ): return self . name suppose we have this model. In this model we have make email field as primary key. now django default primary key id field will be gone. It'll remove from database. we can not query as   UserProfile.objects.get(id=1) after make email as primary key this query will throw an error.  Now we have to use pk  Us...
Post a Comment
Read more

How Django stores passwords

  Django Password Django provides a flexible password storage system and uses PBKDF2 by default. Django saves the password as below. <algorithm>$<iterations>$<salt>$<hash> example of a Hashed password stored in database: pbkdf2_sha256$390000$LCm33kvO7rbjbZhwJA90Sf$xfuGOzl/MJyUxqWNhsNdSThaQUvn1EjEfxZ48HA8HF4= Those are the components used for storing a User’s password,separated by the dollar-sign character and consist of:  1. The hashing algorithm 2. The number of algorithm iterations (work factor) 3. The random salt 4. The resulting password hash.  Most password hashes include a salt along with their password hash in order to protect against rainbow table attacks. Example of Making Hashed password: Here’s a simplified overview of how Django handles password storage: 1. Password Creation or Change : # When someone creates a new account or decides to change their password, Django takes their chosen password and performs a process called hashing. Has...
Post a Comment
Read more