🗂️ धडा 06 — Indexes: कार्ड कॅटलॉग

📍 तुम्ही इथे आहात: 18 पैकी धडा 06 · मागे: lesson-05-data-modelling · पुढे: lesson-07-concurrency

📦 या ब्रँचमध्ये काय आहे

धडे 01–05, आणि काही प्रश्नांना milliseconds का लागतात आणि काहींना मिनिटे का: indexes (कार्ड कॅटलॉग), B-trees, EXPLAIN QUERY PLAN, आणि प्रत्येक कॅटलॉग प्रत्येक write वर आकारतो ती किंमत.

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

हजेरीच्या नोंदवहीत 200,000 ओळी आहेत. "student 4242 किती दिवस हजर होती?" — दप्तरदार प्रत्येक ओळ वाचतो. प्रत्येक वेळी. हा SCAN: 5 ओळींवर ठीक, 200,000 वर चहाचा ब्रेक.

म्हणून दप्तरदार एक कार्ड कॅटलॉग 🗂️ बनवतो: student number नुसार लावलेल्या cards चा ड्रॉवर, प्रत्येक card सांगते की ती विद्यार्थिनी कोणत्या ओळींवर आहे. आता "student 4242" म्हणजे थेट एका card पर्यंत चालणे — एक SEARCH. तोच प्रश्न, 2.4 ms वरून मोजताही न येणाऱ्या वेळेवर.

कॅटलॉग फुकट नाही: प्रत्येक वेळी ओळ जोडली की तिचे card सुद्धा लावावे लागते. दहा कॅटलॉग असलेली नोंदवही प्रत्येक ओळीसाठी दहा cards लिहिते. आणि 5 ओळींच्या नोंदवहीसाठीचा कॅटलॉग त्या 5 ओळी वाचण्यापेक्षा हळू असतो. म्हणून: ज्या columns वर तुम्ही filter, join आणि sort करता त्यांनाच index करा, आणि काहीही बनवण्याआधी दप्तरदाराला मार्ग विचारा — EXPLAIN QUERY PLAN.

🗺️ आकृती

flowchart LR
    q["❓ SELECT COUNT(*) FROM attendance<br/>WHERE student_id = 4242"]
    scan["🚶 SCAN attendance<br/>read 200,000 lines → 2.4 ms"]
    idx["🗂️ CREATE INDEX idx_attendance_student<br/>ON attendance(student_id) — a B-tree"]
    search["🔍 SEARCH … USING INDEX<br/>straight to the card → 0.0 ms"]
    q -->|"1 before"| scan
    q -->|"2 after"| idx --> search
    cost["⚖️ every INSERT files a card · composite order matters · tiny tables: no catalogue"]
    idx -.->|"3"| cost

❓ काय

Index = एक किंवा अधिक columns वरची क्रमाने लावलेली रचना (बहुधा B-tree), rows कडे परत बोट दाखवणारी. Primary keys आणि UNIQUE constraints ना ती आपोआप मिळते.
EXPLAIN QUERY PLAN <query> (SQLite; Postgres मध्ये EXPLAIN / EXPLAIN ANALYZE) SCAN विरुद्ध SEARCH … USING INDEX दाखवतो — चालण्याआधीचा मार्ग.
काय index करायचे: WHERE, JOIN … ON, ORDER BY मधील columns; foreign keys ("अनेक" बाजूला index नसलेला join scan करतो).
Composite indexes (class_id, name) हे WHERE class_id = ? ORDER BY name साठी उपयोगी पडतात — पण फक्त WHERE name = ? साठी नाही: क्रम महत्त्वाचा, सर्वात डावा आधी.
किंमत: हळू writes, जास्त जागा, आणि table खूप लहान असेल किंवा filter बहुतेक rows शी जुळत असेल तर planner तरीही scan निवडू शकतो.
Covering index: query ला लागणारा प्रत्येक column index मध्येच असेल, तर नोंदवही उघडलीच जात नाही (USING COVERING INDEX).

🤔 का

कारण "वाढत जाईल तसे हळू होणारे" app आणि न होणारे app यांतील फरक जवळजवळ पूर्णपणे कोणत्या प्रश्नांना कार्ड कॅटलॉग आहे यावर अवलंबून असतो. आणि index नसलेले writes स्वस्त असतात पण index नसलेले reads चक्रवाढीने वाढतात: ज्या दिवशी table दहा लाख rows ओलांडते, त्या दिवशी हरवलेला index outage बनतो.

🔧 कसे (या repo मध्ये)

db/demo.py मधील index() 200,000 rows चा attendance table बनवते, index शिवाय प्रश्नाची वेळ मोजते, index बनवते, आणि पुन्हा वेळ मोजते — दोन्ही वेळा EXPLAIN QUERY PLAN छापत. schema.sql आधीच दोन foreign keys ना index करते.

🧪 करून पाहा

python3 db/demo.py index
python3 - <<'EOF'
import sqlite3, time; c = sqlite3.connect("db/school.db")
for q in ["SELECT * FROM grades WHERE subject = 'maths'", "SELECT * FROM students WHERE class_id = 1 ORDER BY name"]:
    print(c.execute("EXPLAIN QUERY PLAN " + q).fetchall()[0][3], "←", q)
c.execute("CREATE INDEX IF NOT EXISTS idx_grades_subject ON grades(subject)")
print(c.execute("EXPLAIN QUERY PLAN SELECT * FROM grades WHERE subject = 'maths'").fetchall()[0][3], "← after the index")
# the cost side: time 20,000 inserts into attendance with the index present
t=time.perf_counter(); c.executemany("INSERT INTO attendance (student_id, day, present) VALUES (?,?,?)", [(i, '2026-01-01', 1) for i in range(20000)]); c.commit(); print(f"20,000 inserts with an index: {(time.perf_counter()-t)*1000:.0f} ms")
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

index आधी millisecond वेळेसह SCAN attendance छापतो, मग ~0 ms सह SEARCH attendance USING COVERING INDEX. तुमची दुसरी query आधीच SEARCH … USING INDEX idx_students_class दाखवते (schema.sql मधील foreign key index); तुम्ही index बनवल्यानंतर grades.subject query SCAN वरून SEARCH वर जाते; वेळ मोजलेले inserts दाखवतात की write ची किंमत खरी आहे पण लहान.

🏁 तुम्ही आत्ताच काय सिद्ध केले

तुम्ही 200,000 ओळींचे पूर्ण वाचन एका card lookup मध्ये बदलले, planner चा मार्ग बदलताना पाहिला, आणि कॅटलॉग writes वर किती किंमत घेतो ते मोजले.

⚠️ नेहमीच्या चुका

"कदाचित लागेल म्हणून" प्रत्येक column ला index करणे — writes रेंगाळतात आणि planner त्यातले बहुतेक दुर्लक्षित करतो
foreign-key indexes विसरणे — "अनेक" बाजूवरचा प्रत्येक JOIN scan करतो
चुकीच्या क्रमातील composite index (WHERE class_id = ? साठी (name, class_id))
email वरच्या index वर WHERE LOWER(email) = ? — function column लपवते (expression index वापरा)
5 rows वर मोजून ship करणे — मोठ्या प्रमाणावर planner वेगळा वागतो

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: "index जोडा" हा 30 seconds च्या page ला 30 milliseconds मध्ये बदलणारा सर्वात सामान्य एका ओळीचा fix आहे — आणि write throughput गुपचूप अर्धा करणारा सर्वात सामान्य एका ओळीचा बदलही. प्रत्येक वेळी आधी आणि नंतर EXPLAIN.

⏭️ पुढे

भाग 2 सुरू होतो: रेकॉर्ड रूम खऱ्या जगात चालवणे. आधी, दोन clerks आणि एक नोंदवही — concurrency आणि isolation.

git checkout lesson-07-concurrency

🗂️ Lesson 06 — Indexes: the card catalogue

📍 You are here: Lesson 06 of 18 · Previous: lesson-05-data-modelling · Next: lesson-07-concurrency

📦 What's in this branch

Lessons 01–05, plus why some questions take milliseconds and some take minutes: indexes (the card catalogue), B-trees, EXPLAIN QUERY PLAN, and the cost every catalogue charges on every write.

🧒 Explain like I'm 5

The attendance register has 200,000 lines. "How many days was student 4242 present?" — the archivist reads every line. Every time. That is a SCAN: fine at 5 lines, a coffee break at 200,000.

So the archivist builds a card catalogue 🗂️: a drawer of cards sorted by student number, each card saying which lines that student is on. Now "student 4242" is a straight walk to one card — a SEARCH. Same question, from 2.4 ms to nothing you can measure.

The catalogue is not free: every time a line is added, its card must be filed too. A register with ten catalogues writes ten cards per line. And a catalogue for a 5-line register is slower than reading the 5 lines. So: index the columns you filter, join and sort on, and ask the archivist for the route first — EXPLAIN QUERY PLAN — before building anything.

🗺️ Diagram

flowchart LR
    q["❓ SELECT COUNT(*) FROM attendance<br/>WHERE student_id = 4242"]
    scan["🚶 SCAN attendance<br/>read 200,000 lines → 2.4 ms"]
    idx["🗂️ CREATE INDEX idx_attendance_student<br/>ON attendance(student_id) — a B-tree"]
    search["🔍 SEARCH … USING INDEX<br/>straight to the card → 0.0 ms"]
    q -->|"1 before"| scan
    q -->|"2 after"| idx --> search
    cost["⚖️ every INSERT files a card · composite order matters · tiny tables: no catalogue"]
    idx -.->|"3"| cost

❓ What

Index = a sorted structure (usually a B-tree) over one or more columns, pointing back to rows. Primary keys and UNIQUE constraints get one automatically.
EXPLAIN QUERY PLAN <query> (SQLite; EXPLAIN / EXPLAIN ANALYZE in Postgres) shows SCAN vs SEARCH … USING INDEX — the route before the walk.
What to index: columns in WHERE, JOIN … ON, ORDER BY; foreign keys (a join without an index on the many side scans).
Composite indexes (class_id, name) serve WHERE class_id = ? ORDER BY name — but not WHERE name = ? alone: order matters, leftmost first.
Costs: slower writes, more space, and the planner may still choose a scan when the table is tiny or the filter matches most rows.
Covering index: when the index holds every column the query needs, the register is never opened (USING COVERING INDEX).

🤔 Why

Because the difference between an app that "gets slow as it grows" and one that does not is almost entirely which questions have a card catalogue. And because unindexed writes are cheap but unindexed reads compound: the day the table crosses a million rows is the day a missing index becomes an outage.

🔧 How (in this repo)

index() in db/demo.py builds a 200,000-row attendance table, times the question without an index, creates one, and times it again — printing EXPLAIN QUERY PLAN both times. schema.sql already indexes the two foreign keys.

🧪 Try it

python3 db/demo.py index
python3 - <<'EOF'
import sqlite3, time; c = sqlite3.connect("db/school.db")
for q in ["SELECT * FROM grades WHERE subject = 'maths'", "SELECT * FROM students WHERE class_id = 1 ORDER BY name"]:
    print(c.execute("EXPLAIN QUERY PLAN " + q).fetchall()[0][3], "←", q)
c.execute("CREATE INDEX IF NOT EXISTS idx_grades_subject ON grades(subject)")
print(c.execute("EXPLAIN QUERY PLAN SELECT * FROM grades WHERE subject = 'maths'").fetchall()[0][3], "← after the index")
# the cost side: time 20,000 inserts into attendance with the index present
t=time.perf_counter(); c.executemany("INSERT INTO attendance (student_id, day, present) VALUES (?,?,?)", [(i, '2026-01-01', 1) for i in range(20000)]); c.commit(); print(f"20,000 inserts with an index: {(time.perf_counter()-t)*1000:.0f} ms")
EOF

✅ Verify — what you should see

index prints SCAN attendance with a millisecond time, then SEARCH attendance USING COVERING INDEX with ~0 ms. Your second query already shows SEARCH … USING INDEX idx_students_class (the foreign key index from schema.sql); the grades.subject query flips from SCAN to SEARCH after you create the index; the timed inserts show the write cost is real but small.

🏁 What you just proved

You turned a full read of 200,000 lines into a card lookup, saw the planner's route change, and measured what the catalogue costs on writes.

⚠️ Common mistakes

indexing every column "just in case" — writes crawl and the planner ignores most of them
forgetting foreign-key indexes — every JOIN on the many side scans
a composite index in the wrong order ((name, class_id) for WHERE class_id = ?)
WHERE LOWER(email) = ? on an index over email — the function hides the column (use an expression index)
measuring on 5 rows and shipping — the planner behaves differently at scale

🏭 Why this matters in production: "add an index" is the most common one-line fix that turns a 30-second page into 30 milliseconds — and the most common one-line change that quietly halves write throughput. EXPLAIN before and after, every time.

⏭️ Next

Part 2 begins: running the record room for real. First, two clerks and one register — concurrency and isolation.

git checkout lesson-07-concurrency

← Previousdata modelling Next →concurrency

This page is the lesson's README from the lesson-06-indexes branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.