Query processing — sort আর join অ্যালগরিদম

১ · একটি কোয়েরির যাত্রা — parse থেকে execute

আপনি লেখেন কী চান; কীভাবে আনতে হবে, সেটি DBMS ঠিক করে। SQL তাই declarative ভাষা। কিন্তু শেষ পর্যন্ত কাউকে না কাউকে ডিস্ক থেকে page পড়তে হয়, সারি মেলাতে হয়, সাজাতে হয়। এই পুরো কাজের নাম query processing.

1. 📝ParseSQL → parse treeব্যাকরণ, নাম যাচাই
3. 🔣Translateσ, π, ⋈relational algebra
5. 🧮Optimizephysical planসস্তা পথ বাছাই
7. ⚙️Executeopen / nextসারি তৈরি

প্রথম ধাপে parser SQL-কে একটি parse tree-তে ভাঙে, আর system catalog দেখে যাচাই করে যে টেবিল আর কলামগুলো সত্যিই আছে। দ্বিতীয় ধাপে গাছটি পর্ব ৩২-এর relational algebra-র একটি expression tree হয় — যেমন π_{name, order_id}(σ_city='Dhaka'(customers ⋈ orders)). এটি একটি logical plan: কী করতে হবে, কীভাবে নয়। তৃতীয় ধাপে optimizer সমতুল্য বহু গাছ আর প্রতিটি operator-এর জন্য বহু অ্যালগরিদম থেকে সবচেয়ে সস্তাটি বাছে — একটি physical plan. বাছাইয়ের বিদ্যা পর্ব ৪৩-এর বিষয়। এই পর্বের বিষয় চতুর্থ ধাপ: বাছা হয়ে গেলে প্রতিটি অ্যালগরিদম আসলে কীভাবে চলে, আর তার খরচ কত। কারণ optimizer-এর হিসাব এই খরচগুলো দিয়েই তৈরি।

লাইভ SQL চলে দোকানের ডেটাবেসে (db-shop): customers (customer_id, name, city, phone, joined_on — ৮ জন), categories (৪টি শ্রেণি), products (১০টি পণ্য), orders (order_id, customer_id, order_date, status — ১০টি অর্ডার) আর order_items (order_id, product_id, quantity, unit_price — ১৬টি লাইন)। প্রতিবার চালালে ডেটাবেস নতুন করে তৈরি হয়। নিচের প্রথম স্টেটমেন্ট কোয়েরিটি চালায় না, শুধু plan দেখায় — পর্ব ৩-এ দেখা EXPLAIN QUERY PLAN:

EXPLAIN QUERY PLAN
SELECT c.name, o.order_id
FROM customers c JOIN orders o ON o.customer_id = c.customer_id
WHERE c.city = 'Dhaka';

SELECT c.name, o.order_id
FROM customers c JOIN orders o ON o.customer_id = c.customer_id
WHERE c.city = 'Dhaka';

২ · Physical operator আর iterator মডেল

Physical plan হলো physical operator-এর একটি গাছ: Seq Scan, Index Scan, Nested Loop Join, Hash Join, Sort, Aggregate. প্রায় সব প্রচলিত DBMS এগুলোকে একটি সাধারণ নিয়মে জোড়ে, যার নাম iterator মডেল (Volcano মডেল)। প্রতিটি operator তিনটি কাজ জানে:

চমৎকার দিকটি হলো, কোনো operator জানে না তার child কে — scan, join না sort. সবাই একই তিনটি কাজ বোঝে, তাই যেকোনো গাছ জোড়া যায়। উপরের SQLite plan-টি iterator হিসেবে চালিয়ে দেখুন। ওপরের operator next() ডাকলে কীভাবে একটি একটি সারি “টেনে” তোলা হয়:

Pipelining বনাম materialization

উপরের ধারা, যেখানে একটি operator-এর output সরাসরি পরেরটির input — মাঝে কোথাও জমা নয় — তাকে বলে pipelining. বিকল্প হলো materialization: একটি operator-এর পুরো ফল একটি অস্থায়ী টেবিলে লিখে, তারপর পরেরটি সেখান থেকে পড়ে। Pipelining-এ মেমোরি কম লাগে, অস্থায়ী টেবিল লেখার I/O বাঁচে, আর প্রথম সারি আসে তাড়াতাড়ি — LIMIT 10 থাকলে দশটি সারির পরই কাজ থামে।

কিন্তু কিছু operator স্বভাবতই blocking: সব input না দেখে প্রথম output দিতেই পারে না। ORDER BY-র sort — শেষ সারিটিই হয়তো সবচেয়ে ছোট। Hash join-এর build অংশ — পুরো ছোট টেবিলের hash table না বানিয়ে probe শুরু করা যায় না। GROUP BY-র hash aggregate — শেষ সারিটি যেকোনো দলের যোগফল বদলাতে পারে। উপরের কোয়েরিতে ORDER BY c.name যোগ করলে ফলের প্রথম সারি আসবে পাঁচটি সারি জমা আর সাজানোর পরে। Plan-এর গাছে এই বিন্দুগুলোই pipeline-কে টুকরো করে।

৩ · খরচের একক — page I/O

পর্ব ৩৯-এ দেখেছেন, ডিস্ক থেকে ডেটা আসে page ধরে — সাধারণত ৪ থেকে ১৬ KB-র একেকটি খণ্ড। মেমোরিতে কাজ করা ডিস্ক পড়ার চেয়ে বহুগুণ দ্রুত, তাই ডেটাবেসের পাঠ্যবইয়ে অ্যালগরিদমের খরচ মাপা হয় page I/O-এর সংখ্যায়: কতবার একটি page ডিস্ক থেকে পড়া বা ডিস্কে লেখা হলো। এই পর্ব জুড়ে একই চিহ্ন:

দুটি প্রচলিত নিয়ম মনে রাখুন। এক, শেষ ফল লেখার খরচ ধরা হয় না — যেকোনো join অ্যালগরিদমে ফলের আকার একই, তাই তুলনায় সেটি বাদ। দুই, এই মডেল CPU-র কাজ, random আর sequential পড়ার পার্থক্য আর cache উপেক্ষা করে। মডেলটি তাই মোটা দাগের, কিন্তু অ্যালগরিদমের মধ্যে হাজার গুণের পার্থক্য ঠিকই ধরে। আসল optimizer-এর সূত্র এর চেয়ে সূক্ষ্ম — পর্ব ৪৩-এ।

পরীক্ষার জন্য এবার একটি বড় পরীক্ষাগার বানাই। ১০ হাজার সারি হাতে লেখা অসম্ভব, তাই পর্ব ২৫-এর recursive CTE দিয়ে সংখ্যা তৈরি করে সেখান থেকে সারি বানানো হবে। এই এডিটরে customers_big (cid, city, name — ২,০০০ জন, চার শহরে সমান ভাগ) আর returns_big (rid, cid, reason — ৩০০টি পণ্য-ফেরত) আগে থেকেই তৈরি; কোডে আপনি বানাচ্ছেন orders_big (oid, cid, amount — ১০,০০০টি অর্ডার):

CREATE TABLE orders_big (oid INTEGER PRIMARY KEY,
                         cid INTEGER, amount INTEGER);
WITH RECURSIVE n(i) AS (
  SELECT 1 UNION ALL SELECT i + 1 FROM n WHERE i < 10000)
INSERT INTO orders_big
SELECT i, (i * 7) % 2000 + 1, (i * 37) % 5000 + 100 FROM n;

SELECT COUNT(*) AS orders, COUNT(DISTINCT cid) AS customers,
       MIN(amount) AS lo, MAX(amount) AS hi FROM orders_big;
SELECT * FROM orders_big LIMIT 3;

৪ · Selection — scan, binary search না index?

সবচেয়ে সরল operator হলো selection σ: শর্ত মেলে এমন সারি বের করা। পর্ব ৪০-এর ভাষায় তিনটি পথ:

এখানে h হলো B+ tree-এর উচ্চতা (বড় টেবিলেও সাধারণত ৩–৪), আর sel হলো selectivity — মোট সারির কত ভাগ শর্ত মেলে। শেষ সারিটিই সবচেয়ে বড় ফাঁদ। ধরুন orders-এর ২ লাখ সারি ২,০০০ page-এ, আর শর্তে ৫% — ১০ হাজার সারি — মেলে। Secondary index-এ খারাপ ক্ষেত্রে ১০,০০০ + h page I/O, অথচ পুরো scan মাত্র ২,০০০! তাই optimizer কম selectivity-তে index নেয়, বেশিতে scan. PostgreSQL-এর bitmap heap scan মাঝের পথ: আগে index থেকে সব ঠিকানা জোগাড় করে page-এর ক্রমে সাজায়, তারপর প্রতিটি page একবারই পড়ে।

পরীক্ষাগারে তিনটি অবস্থা দেখুন — primary key, index ছাড়া কলাম, আর index বানানোর পরে:

EXPLAIN QUERY PLAN SELECT * FROM orders_big WHERE oid = 77;
EXPLAIN QUERY PLAN SELECT * FROM orders_big WHERE amount = 500;

CREATE INDEX ob_amt ON orders_big(amount);
EXPLAIN QUERY PLAN SELECT * FROM orders_big WHERE amount = 500;
EXPLAIN QUERY PLAN
SELECT oid FROM orders_big WHERE amount BETWEEN 500 AND 600;
SELECT COUNT(*) FROM orders_big WHERE amount BETWEEN 500 AND 600;

৫ · External merge sort — মেমোরির চেয়ে বড় ফাইল সাজানো

ORDER BY, DISTINCT, GROUP BY, sort-merge join, index বানানো — সবখানে sort লাগে। ডেটা মেমোরিতে ধরলে quicksort-ই যথেষ্ট। কিন্তু ২০ GB টেবিল আর ২ GB মেমোরি হলে? তখন লাগে external merge sort, যার মূল ভাবনা DSA কোর্সের merge sort-এর merge ধাপ।

// N page-এর ফাইল, মেমোরিতে B buffer page
Pass 0:  প্রতিবার B page পড়ো, মেমোরিতে সাজাও, একটি sorted run লেখো
         → ⌈N/B⌉টি run, প্রতিটি B page (শেষটি ছোট হতে পারে)
Pass i:  B−1টি input buffer, 1টি output buffer
         প্রতিবার B−1টি run একসাথে merge করে একটি বড় run লেখো
যতক্ষণ না একটিই run থাকে

pass-এর সংখ্যা = 1 + ⌈log_(B−1) ⌈N/B⌉⌉
প্রতি pass-এ প্রতিটি page একবার পড়া + একবার লেখা = 2N
মোট খরচ = 2N × (1 + ⌈log_(B−1) ⌈N/B⌉⌉)

পাস-সংখ্যার যুক্তি। Pass 0-এর পর run-এর সংখ্যা r₀ = ⌈N/B⌉. প্রতিটি merge pass B−1টি run-কে একটিতে মেলায়, তাই k-তম pass-এর পর r_k = ⌈r_k−1/(B−1)⌉ ≤ ⌈r₀/(B−1)^k⌉. একটি run থাকে প্রথম সেই k-তে, যেখানে (B−1)^k ≥ r₀, অর্থাৎ k = ⌈log_B−1 r₀⌉. সাথে pass 0 যোগ করলে সূত্রটি আসে। কেন B−1, B নয়? একটি buffer সবসময় output-এর জন্য লাগে — output buffer ভরলে ডিস্কে লেখা হয়, তবেই merge এগোয়।

এবার N = 20, B = 4 দিয়ে পুরো কাজটি ধাপে ধাপে দেখুন:

শেষ বাক্যটির হিসাব: B = 1,000 page (৮ KB page-এ মাত্র ৮ MB) হলে এক merge pass-এ ৯৯৯টি run মেলে, আর pass 0-এর run প্রতিটি ১,০০০ page — তাই দুই pass-এ সাজানো যায় প্রায় B × (B−1) ≈ ১০ লাখ page, অর্থাৎ প্রায় ৮ GB. সাধারণভাবে N ≤ B(B−1) হলে দুই pass যথেষ্ট, মোটামুটি B ≥ √N.

SQLite-এ দেখুন ORDER BY কখন sort চায়, আর index কীভাবে sort-কে পুরো সরিয়ে দেয়:

EXPLAIN QUERY PLAN
SELECT oid, amount FROM orders_big ORDER BY amount DESC LIMIT 5;

CREATE INDEX ob_amt ON orders_big(amount);
EXPLAIN QUERY PLAN
SELECT oid, amount FROM orders_big ORDER BY amount DESC LIMIT 5;
SELECT oid, amount FROM orders_big ORDER BY amount DESC LIMIT 5;

৬ · Join ১ — nested loop পরিবার

Join সবচেয়ে দামি আর সবচেয়ে বৈচিত্র্যময় operator. পর্ব ১৯-এর JOIN-এর অর্থ এক, কিন্তু চালানোর পথ অনেক। শুরু সবচেয়ে সরলটি দিয়ে — দুটি লুপ।

// tuple nested loop:    খরচ = M + (p_R · M) · N
for each tuple r in R:
    for each tuple s in S:            // প্রতিটি r-এর জন্য পুরো S
        if r.k = s.k: output (r, s)

// page nested loop:     খরচ = M + M · N
for each page P_R of R:
    for each page P_S of S:
        প্রতিটি (r ∈ P_R, s ∈ P_S) জোড়া মেলাও

// block nested loop:    খরচ = M + ⌈M / (B−2)⌉ · N
for each block of (B−2) pages of R:   // 1টি S-এর input, 1টি output
    for each page P_S of S:
        block-এর প্রতিটি r আর P_S-এর প্রতিটি s মেলাও

Tuple nested loop-এ R-এর প্রতিটি tuple-এর জন্য S-এর N page পুরো একবার পড়া হয় — p_R·M বার। Page সংস্করণে প্রতিটি R page-এর জন্য একবার, তাই M বার। Block nested loop আরও এক ধাপ এগোয়: মেমোরির B page-এর মধ্যে একটি S-এর input আর একটি output-এর জন্য রেখে বাকি B−2 page-এ R-এর একটি “block” ভরে, আর S-এর একবার পড়ায় পুরো block-এর সাথে মেলায়। তাই S পড়া হয় ⌈M/(B−2)⌉ বার। তিনটি সূত্রেই প্রথম M হলো R নিজে একবার পড়া। ছোট উদাহরণে ধাপগুলো দেখুন:

একটি সূক্ষ্ম কথা: কোনটি outer হবে? সূত্রে M দুবার আসে, N একবার — তাই ছোট টেবিলকে outer রাখা সস্তা। বড় উদাহরণে (M = 500, N = 2,000, B = 52) customers outer হলে 500 + ⌈500/50⌉ × 2,000 = 20,500; orders outer হলে 2,000 + ⌈2,000/50⌉ × 500 = 22,000.

Index nested loop

S-এর join কলামে index থাকলে ভেতরের লুপে পুরো S পড়ার দরকারই নেই — প্রতিটি r-এর জন্য index-এ সরাসরি মিল খোঁজা যায়। এটিই index nested loop (INL), আর অংশ ১-এর SQLite plan ঠিক এটিই করেছিল।

শেষ পদটি আবার clustered না secondary তার ওপর নির্ভর করে। বড় উদাহরণে orders.cid-তে একটি secondary B+ tree ধরুন, প্রতি খোঁজে ৩ page আর প্রত্যেক গ্রাহকের ৫টি অর্ডার পাঁচটি আলাদা page-এ: 500 + 40,000 × (3 + 5) = 3,20,500 — block nested loop-এর চেয়ে ১৫ গুণ খারাপ! কিন্তু শুধু Sylhet-এর ২০০ জন গ্রাহক চাইলে, আর customers-এর city-তে index থাকলে outer-এর দিকেও scan লাগে না: মোটামুটি 200 × 8 = ১,৬০০ I/O, আর প্রথম ফল আসে প্রায় সাথে সাথে। ছোট outer + ভেতরে index = INL-এর রাজত্ব। OLTP অ্যাপের অধিকাংশ join ঠিক এমন: “এই গ্রাহকের অর্ডারগুলো দেখাও।”

৭ · Join ২ — sort-merge আর hash join

Sort-merge join

দুটি টেবিলই join কলামে সাজানো থাকলে দুটি আঙুল একসাথে নিচে নামানো যায় — ঠিক দুটি সাজানো রেজিস্টার পাশাপাশি রেখে রোল নম্বর মেলানোর মতো। Sort-merge join-এর দুই ধাপ: দরকার হলে দুটিকে অংশ ৫-এর মতো sort করা, তারপর merge. Merge-এ ছোট দিকের আঙুল এগোয়; সমান হলে দুই দিকের সমান-মানের পুরো দল জোড়া লাগে। ডুপ্লিকেটই এখানে আসল চ্যালেঞ্জ:

বড় উদাহরণে B = 52: customers-এর ⌈500/52⌉ = ১০টি run, orders-এর ⌈2,000/52⌉ = ৩৯টি — দুটিই এক merge pass-এ মেলে, তাই প্রতিটির ২ pass. খরচ 2,000 + 8,000 + 2,500 = 12,500. একটি পরিচিত উন্নতি: দুই টেবিলের মোট run-সংখ্যা (১০ + ৩৯ = ৪৯) B−1-এর বেশি না হলে শেষ merge pass আর join-এর merge একসাথে করা যায় — ফাইল লিখে আবার পড়ার দরকার নেই। তখন খরচ হয় 3(M+N) = 7,500; এর শর্ত মোটামুটি B > √L, যেখানে L বড় টেবিলটির page.

Hash join

Hash join-এর ভাবনা লাইব্রেরির তাকের মতো: ছোট টেবিলের প্রতিটি সারি তার key-এর hash অনুযায়ী একটি bucket-এ রাখা (build), তারপর বড় টেবিলের প্রতিটি সারির জন্য শুধু তার bucket-টি দেখা (probe). Hash table-এর মূল কথা DSA কোর্সের hash table পর্বে। দোকানের ডেটায় customers-এর ওপর build, orders দিয়ে probe; hash হলো customer_id mod 4:

ছোট টেবিলটিও মেমোরির চেয়ে বড় হলে Grace hash join: ভাগ (partition) ধাপে R আর S দুটিকেই একই hash ফাংশন h₁ দিয়ে B−1টি ভাগে ভাঙা হয় (একটি input buffer, B−1টি output buffer), আর ভাগগুলো ডিস্কে লেখা হয় — খরচ 2(M+N), সব পড়া আর সব লেখা। একই key সবসময় একই নম্বরের ভাগে যায়, তাই R-এর ভাগ i-এর সারি শুধু S-এর ভাগ i-এর সারির সাথেই মিলতে পারে। Build-probe ধাপে প্রতিটি i-এর জন্য R_i মেমোরিতে এনে আরেকটি hash ফাংশন h₂ দিয়ে hash table, তারপর S_i পড়ে probe — খরচ M + N.

শর্তটির যুক্তি: probe-এর সময় একটি input আর একটি output buffer লাগে, তাই hash table-এর জন্য থাকে B−2 page. ভাগগুলো সমান হলে M/(B−1) ≤ B−2 দরকার, অর্থাৎ মোটামুটি M ≤ B², বা B ≥ √M (hash table-এর বাড়তি জায়গার জন্য একটি গুণক f যোগ হয়: B > √(f·M)). খেয়াল করুন, শর্তটি শুধু ছোট টেবিলের ওপর — বড়টি যত বড়ই হোক। বড় উদাহরণে √500 ≈ 22.4 < 52, তাই খরচ 3 × 2,500 = 7,500. কোনো একটি key খুব বেশি ঘন ঘন এলে (ধরুন একটি পাইকারি ক্রেতার লাখো অর্ডার) তার ভাগ মেমোরিতে ধরে না — তখন সেই ভাগটিকে আবার আলাদা hash দিয়ে ভাগ করতে হয় (recursive partitioning).

৮ · কোনটি কখন জেতে — আর SQLite, PostgreSQL কী করে

বড় উদাহরণের (customers M = 500, p_R = 80; orders N = 2,000; B = 52) সব হিসাব একসাথে:

সিদ্ধান্তের চারটি নিয়ম মনে রাখুন। ছোট outer আর ভেতরে index → index nested loop. দুটি বড় টেবিলের equi-join → hash join. ইনপুট আগে থেকে সাজানো (যেমন index-এর ক্রমে আসছে), বা ফল সাজানো চাই (ORDER BY একই কলামে) → sort-merge, কারণ sort-এর খরচ হয় নেই, নয়তো দুই কাজে ভাগ হয়। আর শর্ত সমতা নয় (<, BETWEEN, LIKE) → nested loop পরিবার, কারণ hash আর merge দুটিই equi-join-এর জন্য — সমান key-ই একই bucket-এ বা পাশাপাশি আসে। (Band join-এর মতো কিছু range শর্তে sort-ভিত্তিক বিশেষ কৌশলও আছে।)

SQLite-এ লাইভ: index ছাড়া আর index-সহ join

SQLite-এ hash join বা merge join নেই — প্রতিটি join-ই nested loop. তার বদলে, ভেতরের টেবিলের join কলামে index না থাকলে SQLite কোয়েরি চলার সময়ই একটি অস্থায়ী automatic index বানিয়ে নেয়, আর সাম্প্রতিক সংস্করণে (৩.৩৮, ২০২২ থেকে) একটি Bloom filter-ও — যাতে মিলবে না এমন সারির জন্য index খোঁজাই না লাগে। কার্যত এটি hash join-এর build-এর মতো কাজ: একবার ভেতরের টেবিল পড়ে খোঁজার গঠন বানানো। দেখুন:

-- join কলাম cid-এ কোনো দিকেই index নেই
EXPLAIN QUERY PLAN
SELECT o.oid, r.reason
FROM orders_big o JOIN returns_big r ON r.cid = o.cid;

CREATE INDEX ob_cid ON orders_big(cid);
EXPLAIN QUERY PLAN
SELECT o.oid, r.reason
FROM orders_big o JOIN returns_big r ON r.cid = o.cid;
SELECT COUNT(*) FROM orders_big o JOIN returns_big r ON r.cid = o.cid;

Automatic index বন্ধ করলে SQLite-কে খাঁটি nested loop চালাতে হয় — পাঠ্যবইয়ের সবচেয়ে সরল অ্যালগরিদম:

PRAGMA automatic_index = OFF;
EXPLAIN QUERY PLAN
SELECT o.oid, r.reason
FROM orders_big o JOIN returns_big r ON r.cid = o.cid;
SELECT COUNT(*) FROM orders_big o JOIN returns_big r ON r.cid = o.cid;

এবার এমন join, যেখানে সমতা নেই। দোকান অর্ডারের টাকা অনুযায়ী ছাড় দেয়: ১,০০০-এর নিচে ০%, ১,০০০–২,৯৯৯-এ ৫%, তার বেশিতে ১০%. প্রতিটি অর্ডারকে তার “স্ল্যাব”-এর সাথে মেলানো একটি non-equi join:

CREATE TABLE slabs (lo INTEGER, hi INTEGER, pct INTEGER);
INSERT INTO slabs VALUES (0, 999, 0), (1000, 2999, 5), (3000, 99999, 10);

EXPLAIN QUERY PLAN
SELECT o.oid, s.pct FROM orders_big o
JOIN slabs s ON o.amount BETWEEN s.lo AND s.hi;

SELECT s.pct, COUNT(*) AS orders FROM orders_big o
JOIN slabs s ON o.amount BETWEEN s.lo AND s.hi
GROUP BY s.pct;

একটি সিমুলেশন — I/O আর তুলনা গুনে দেখা

সূত্রগুলো কি সত্যিই মেলে? নিচের Python প্রোগ্রাম এলোমেলো key দিয়ে ছোট R (৮০টি tuple, প্রতি page-এ ৪টি, তাই M = 20) আর S (১৬০টি, N = 40) বানায়, B = 7 ধরে তিনটি অ্যালগরিদম আসলে চালায়, page I/O আর কাজ (তুলনা বা probe) গোনে, আর ফলের সারি মিলিয়ে দেখে। শেষ লাইনে বড় উদাহরণের সূত্রগুলো:

import math, random, collections
random.seed(42)
P = 4                                    # tuples per page
def paged(keys): return [keys[i:i + P] for i in range(0, len(keys), P)]
R = paged([random.randrange(100) for _ in range(80)])    # M = 20 pages
S = paged([random.randrange(100) for _ in range(160)])   # N = 40 pages
M, N, B = len(R), len(S), 7
flat = lambda rel: [t for p in rel for t in p]
def bnl():                               # block nested loop, R outer
    io = cmp = out = 0
    for i in range(0, M, B - 2):
        block = flat(R[i:i + B - 2]); io += len(R[i:i + B - 2])
        for sp in S:                     # one full read of S per block
            io += 1; cmp += len(sp) * len(block)
            out += sum(r == s for s in sp for r in block)
    return io, cmp, out
def sort_cost(n, b):                     # 2n I/O per pass; count passes exactly
    runs, passes = math.ceil(n / b), 1
    while runs > 1: runs, passes = math.ceil(runs / (b - 1)), passes + 1
    return 2 * n * passes
def sort_merge():
    r, s = sorted(flat(R)), sorted(flat(S))
    i = j = cmp = out = 0
    while i < len(r) and j < len(s):
        cmp += 1
        if r[i] < s[j]: i += 1
        elif r[i] > s[j]: j += 1
        else:                            # equal key: pair the two groups
            a, b = r[i:].count(r[i]), s[j:].count(r[i])
            out += a * b; i += a; j += b
    return sort_cost(M, B) + sort_cost(N, B) + M + N, cmp, out
def grace():                             # partition with h(k) = k mod (B-1)
    part = lambda rel: [[t for t in flat(rel) if t % (B - 1) == h] for h in range(B - 1)]
    pr, ps = part(R), part(S)
    written = sum(math.ceil(len(x) / P) for x in pr + ps)
    tables = [collections.Counter(br) for br in pr]     # build: one table per R partition
    out = sum(tables[h][t] for h, bs in enumerate(ps) for t in bs)   # probe with S
    return M + N + 2 * written, len(flat(S)), out
print(f"M={M} N={N} B={B}   page NLJ formula M+M*N = {M + M * N}")
for name, f in (("block NLJ", bnl), ("sort-merge", sort_merge), ("grace hash", grace)):
    print("{:10}  page_io={:4}  work={:6}  rows={}".format(name, *f()))
M, N, B, pR = 500, 2000, 52, 80          # the big example, formulas only
print("big: tupleNLJ", M + pR * M * N, " pageNLJ", M + M * N, " BNL", M + math.ceil(M / (B - 2)) * N,
      " SMJ", sort_cost(M, B) + sort_cost(N, B) + M + N, " grace", 3 * (M + N))

PostgreSQL-এর plan পড়া

PostgreSQL-এ তিনটি join-ই আছে, আর plan-এ নাম ধরেই দেখায়: Nested Loop, Hash Join, Merge Join. নিচের plan-টি ব্যাখ্যার জন্য, এই পাতায় চালানো যায় না; cost আর সময়ের সংখ্যা বাদ দিয়ে কাঠামোটুকু রাখা হয়েছে। গাছটি পড়ুন ভেতর থেকে বাইরে, নিচ থেকে ওপরে:

EXPLAIN ANALYZE
SELECT c.city, SUM(o.amount)
FROM customers c JOIN orders o ON o.customer_id = c.customer_id
GROUP BY c.city;

HashAggregate                          -- ৪. শহর ধরে hash-এ যোগফল
  Group Key: c.city
  ->  Hash Join                        -- ৩. probe: প্রতিটি অর্ডার
        Hash Cond: (o.customer_id = c.customer_id)
        ->  Seq Scan on orders o       -- ২. বড় দিক, pipeline-এ আসে
        ->  Hash                       -- ১. build: আগে পুরো customers
              Buckets: 65536  Batches: 1  Memory Usage: ...kB
              ->  Seq Scan on customers c

-- একই কোয়েরি, অন্য পরিস্থিতিতে যে নোড দেখতে পারেন:
--   Merge Join  Merge Cond: (c.customer_id = o.customer_id)
--     -> Index Scan using customers_pkey on customers c
--     -> Sort  Sort Key: o.customer_id
--              Sort Method: external merge  Disk: ...kB
--   Nested Loop
--     -> Seq Scan on customers c  Filter: (city = 'Sylhet')
--     -> Index Scan using orders_customer_id_idx on orders o
--          Index Cond: (customer_id = c.customer_id)

তিনটি জিনিস খুঁজে দেখার অভ্যাস করুন। Hash নোডের Batches: 1 মানে পুরো build দিক মেমোরিতে ধরেছে; ১-এর বেশি হলে PostgreSQL Grace-ধাঁচে (আসলে hybrid hash) ভাগ করে ডিস্কে লিখেছে। Sort Method: quicksort Memory মানে মেমোরিতেই সাজানো, external merge Disk মানে অংশ ৫-এর external sort, আর top-N heapsort মানে LIMIT-এর জন্য শুধু সেরা কয়েকটি রাখা। দুটির মেমোরিই work_mem সেটিং ঠিক করে — এটিই এই পর্বের B. পরীক্ষার জন্য SET enable_hashjoin = off; দিয়ে একটি অ্যালগরিদম নিষেধ করে দেখতে পারেন optimizer পরের পছন্দ কী নেয় — শুধু পরীক্ষায়, চালু সিস্টেমে নয়। MySQL দীর্ঘদিন শুধু nested loop-ভিত্তিক ছিল; 8.0.18 সংস্করণে hash join যোগ হয়, আর 8.0.20 থেকে block nested loop-এর জায়গা নেয়।

৯ · Projection, aggregation আর set operation

Join ছাড়াও তিনটি operator-এ একই দুই কৌশল ফিরে আসে — sort না hash:

• Duplicate বাদ দেওয়া (DISTINCT, relational algebra-র π): sort-ভিত্তিক পথে অপ্রয়োজনীয় কলাম ফেলে sort, তারপর পাশাপাশি সমান সারিগুলোর একটি রাখা — sort-এর pass 0-তেই কলাম ফেলা আর শেষ merge-এ duplicate বাদ দেওয়া যায়। Hash-ভিত্তিক পথে ভাগ করে প্রতিটি ভাগের hash table-এ “আগে দেখেছি কি?” প্রশ্ন। SQL-এর সাধারণ SELECT duplicate রাখে (bag semantics), তাই duplicate elimination-এর দাম দিতে হয় শুধু DISTINCT চাইলে।
• Aggregation (GROUP BY): sort করলে একই দলের সারি পাশাপাশি আসে, একটি scan-এ চলতি SUM/COUNT. Hash aggregate-এ প্রতিটি দলের জন্য একটি entry আর চলতি যোগফল — মেমোরি লাগে দলের সংখ্যা অনুযায়ী, সারির সংখ্যা নয়; ২ লাখ অর্ডার আর ৪টি শহর হলে hash table-এ ৪টি entry. GROUP BY ছাড়া SUM-এ শুধু একটি scan.
• Set operation: UNION, INTERSECT আর EXCEPT duplicate বাদ দেয় (পর্ব ২২), তাই দুই input মিলিয়ে sort বা hash লাগে। UNION ALL-এ কিছুই লাগে না — প্রথম input শেষ হলে দ্বিতীয়টি, খাঁটি pipeline.

EXPLAIN QUERY PLAN
SELECT cid, SUM(amount) FROM orders_big GROUP BY cid;
EXPLAIN QUERY PLAN SELECT DISTINCT cid FROM returns_big;

CREATE INDEX ob_cid_amt ON orders_big(cid, amount);
EXPLAIN QUERY PLAN
SELECT cid, SUM(amount) FROM orders_big GROUP BY cid;
SELECT cid, COUNT(*) AS n, SUM(amount) AS total
FROM orders_big GROUP BY cid LIMIT 3;

EXPLAIN QUERY PLAN
SELECT cid FROM returns_big UNION SELECT cid FROM customers_big WHERE city = 'Dhaka';
EXPLAIN QUERY PLAN
SELECT cid FROM returns_big UNION ALL SELECT cid FROM customers_big WHERE city = 'Dhaka';
SELECT COUNT(*) AS dhaka_with_returns FROM (
  SELECT cid FROM returns_big
  INTERSECT
  SELECT cid FROM customers_big WHERE city = 'Dhaka');

১০ · AI-এর যুগে query processing

“কোয়েরিটা ধীর কেন?” — AI চট করে উত্তর দেয়, কিন্তু আপনার plan, ডেটার মাপ আর index সে না দেখে অনুমান করে। প্রচলিত ভুল:

AI-এর দেওয়া “দ্রুত করার” পরামর্শ মানার আগে — চেকলিস্ট

• আগে আর পরে আসল plan দেখেছি (SQLite-এ EXPLAIN QUERY PLAN, PostgreSQL-এ EXPLAIN ANALYZE)
• নতুন কোয়েরির ফল পুরোনোর সাথে মিলিয়েছি — COUNT, আর দুই দিকের EXCEPT খালি
• NULL key, duplicate key আর খালি টেবিল দিয়ে test করেছি
• প্রস্তাবিত index-টি কোন operator বদলায় (scan → search, sort বাদ) তা plan-এ দেখেছি
• খরচের সূত্র বা সংখ্যা থাকলে একটি ছোট উদাহরণে হাতে গুনে মিলিয়েছি
• AI যে সিনট্যাক্স বা সেটিং বলেছে, তা আমার ডেটাবেসের সংস্করণে সত্যিই আছে