Query optimization — cost, statistics আর plan

১ · Optimizer-এর কাজ — একই উত্তরের অনেক পথ

পর্ব ৪২-এ আপনি দেখেছেন একটি কোয়েরি চালানোর যন্ত্রপাতি: full scan আর index scan, nested loop, sort-merge আর hash join, বাইরের sort. কিন্তু একটি কোয়েরিতে কোন যন্ত্রটি কোথায় লাগবে, কোন টেবিল আগে পড়া হবে — সেই সিদ্ধান্ত নেয় DBMS-এর query optimizer. SQL একটি declarative ভাষা: আপনি বলেন কী চান, কীভাবে আনতে হবে বলেন না। সেই “কীভাবে” লেখা থাকে একটি query plan-এ।

যেকোনো optimizer-কে তিনটি প্রশ্নের উত্তর দিতে হয়:

একটি সূক্ষ্ম কথা মনে রাখুন: optimizer “সবচেয়ে ভালো plan” খোঁজে না, খোঁজে সবচেয়ে কম আনুমানিক খরচের plan. দুটি এক নয়। আর পুরো খোঁজটি হতে হবে কোয়েরি চালানোর চেয়ে অনেক কম সময়ে — এক মিলিসেকেন্ডের কোয়েরির জন্য এক সেকেন্ড ধরে plan খোঁজা অর্থহীন। তাই বাস্তব optimizer পুরো plan space দেখে না; নিয়ম দিয়ে ছাঁটে, আর বাকিটা চতুরভাবে খোঁজে।

এই পর্বের লাইভ SQL চলে দুটি তৈরি-করা টেবিলে, যা প্রতিটি এডিটর একটি recursive CTE দিয়ে (পর্ব ২৫) নতুন করে বানায় — নমুনা ডেটার বাক্সে পুরো স্ক্রিপ্ট দেখতে পাবেন। cust-এ ২,০০০ গ্রাহক: id, city (৭টি শহর — Dhaka অর্ধেক, Chattogram ২০%, Gazipur ১০%, বাকি চারটি ৫% করে), division (বিভাগ; শহরের সাথে বাঁধা — Gazipur ঢাকা বিভাগে) আর phone (প্রতি দশজনে একজনের NULL). ord-এ ২০,০০০ অর্ডার: id, cust_id, status (delivered ৮৫%, pending ১০%, cancelled ৪%, returned ১%) আর amount (৭০% অর্ডার ১,০০০ টাকার নিচে, অল্প কিছু ৫০ হাজার পর্যন্ত)। প্রথম ২০ জন গ্রাহক বিশেষ: প্রত্যেকের প্রায় ২৬০টি অর্ডার। ডেটাটি ইচ্ছে করে অসমান — বাস্তব ডেটার মতোই।

২ · Heuristic rewrite — নিয়ম দিয়ে গাছ বদলানো

Optimizer-এর প্রথম ধাপ cost হিসাব নয়, কিছু নিয়ম। এই heuristic rewrite-গুলো প্রায় সব ক্ষেত্রেই লাভজনক, তাই খরচ না মেপেই করা হয়। Parser SQL থেকে একটি প্রাথমিক query tree বানায়: নিচে টেবিলগুলোর cartesian product, ওপরে WHERE-এর সব শর্ত একসাথে, তারও ওপরে SELECT-এর কলাম। তারপর পর্ব ৩২–৩৩-এর equivalence rule দিয়ে গাছটি ধাপে ধাপে বদলায়। প্রশ্নটি: Sylhet-এর যে গ্রাহকদের কোনো অর্ডার ফেরত এসেছে, তাঁদের ফোন নম্বর।

SELECT c.phone
FROM cust c, ord o
WHERE c.id = o.cust_id AND c.city = 'Sylhet' AND o.status = 'returned';

এই নিয়মগুলোর পেছনের যুক্তি সরল: প্রতিটি অপারেটরের খরচ তার ইনপুটের আকারের সাথে বাড়ে, আর selection কখনো সারি বাড়ায় না। তাই selection যত আগে, পরের সব অপারেটরের ইনপুট তত ছোট বা সমান। তবে “প্রায় সবসময়” — ব্যতিক্রমও আছে। শর্তটি নিজেই দামি হলে (ধরুন প্রতিটি সারিতে একটি ধীর user-defined function, পর্ব ২৮), আগে join করে সারি কমিয়ে তারপর শর্ত চালানো সস্তা হতে পারে। তাই আধুনিক optimizer এমন শর্তকেও cost দিয়ে বিচার করে।

আরও তিনটি বড় rewrite

• View merging: পর্ব ২৪-এ দেখেছেন, view-এর নামের জায়গায় তার SELECT বসে (view expansion), আর সম্ভব হলে বাইরের কোয়েরির সাথে এক হয়ে যায় — তখন ওপরের সব নিয়ম view-এর ভেতরেও খাটে।
• View-এ predicate pushdown: view-টি GROUP BY-ওয়ালা হলে পুরোপুরি মেশানো যায় না, কিন্তু GROUP BY-এর কলামের ওপর বাইরের শর্তটি ভেতরে ঠেলে দেওয়া যায় — সব দলের যোগফল না করে শুধু দরকারি দলটির।
• Subquery unnesting (decorrelation): পর্ব ২১-এর correlated subquery বাইরের প্রতিটি সারিতে একবার চলে। optimizer তাকে join বা semi-join-এ বদলাতে পারলে পুরো খোঁজটি একবারে হয়।

আসল SQLite-এ দেখুন। EXPLAIN QUERY PLAN কোয়েরি না চালিয়ে plan দেখায়: ফলের detail কলামে প্রতিটি লাইন একটি loop, ওপরের লাইন বাইরের loop. (notused কলামটি উপেক্ষা করুন।) এই এডিটরে ord.cust_id-তে একটি index আগে থেকেই আছে:

CREATE VIEW cust_total AS
  SELECT cust_id, COUNT(*) AS n, SUM(amount) AS total
  FROM ord GROUP BY cust_id;
EXPLAIN QUERY PLAN SELECT * FROM cust_total WHERE cust_id = 7;
SELECT * FROM cust_total WHERE cust_id = 7;

CREATE VIEW sylhet_orders AS
  SELECT o.id, o.cust_id, o.amount
  FROM ord o JOIN cust c ON c.id = o.cust_id
  WHERE c.city = 'Sylhet';
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM sylhet_orders WHERE cust_id = 18;
SELECT COUNT(*) FROM sylhet_orders WHERE cust_id = 18;

এবার decorrelation. প্রশ্ন: কতগুলো অর্ডারের টাকা সেই গ্রাহকের নিজের গড় অর্ডারের চেয়ে বেশি? correlated রূপে প্রতিটি অর্ডারের জন্য সেই গ্রাহকের গড় আবার হিসাব হয়; হাতে করা unnesting-এ সব গড় একবারে, তারপর join:

EXPLAIN QUERY PLAN
SELECT COUNT(*) FROM ord o
WHERE o.amount > (SELECT AVG(o2.amount) FROM ord o2 WHERE o2.cust_id = o.cust_id);
SELECT COUNT(*) FROM ord o
WHERE o.amount > (SELECT AVG(o2.amount) FROM ord o2 WHERE o2.cust_id = o.cust_id);

EXPLAIN QUERY PLAN
WITH a AS (SELECT cust_id, AVG(amount) AS avg_amt FROM ord GROUP BY cust_id)
SELECT COUNT(*) FROM ord o JOIN a ON a.cust_id = o.cust_id WHERE o.amount > a.avg_amt;
WITH a AS (SELECT cust_id, AVG(amount) AS avg_amt FROM ord GROUP BY cust_id)
SELECT COUNT(*) FROM ord o JOIN a ON a.cust_id = o.cust_id WHERE o.amount > a.avg_amt;

৩ · Plan space — join order-এর বিস্ফোরণ

নিয়মের পর বড় সিদ্ধান্ত: join order. Inner join commutative আর associative (পর্ব ৩৩), তাই চারটি টেবিল A, B, C, D যেকোনো ক্রমে আর যেকোনো বন্ধনীতে join করলে ফল একই — কিন্তু মধ্যবর্তী ফলের আকার আকাশ-পাতাল আলাদা হতে পারে। গাছের আকার দুই রকম:

কতগুলো ক্রম? Left-deep গাছ ঠিক করে দেয় টেবিলগুলোর একটি সারি — কোনটি প্রথম, কোনটি দ্বিতীয় … — তাই n টেবিলে n! টি left-deep গাছ: প্রথম জায়গায় n টি পছন্দ, দ্বিতীয়তে n − 1, এভাবে। Bushy গাছ গুনতে দুটি জিনিস লাগে: n টি পাতাওয়ালা পূর্ণ binary গাছের আকার কতভাবে হয় (Catalan সংখ্যা C_n−1), আর প্রতিটি আকারে পাতায় টেবিল বসানোর n! উপায়। গুণফল n! · C_n−1 = (2n − 2)! / (n − 1)!.

প্রতিটি গাছে প্রতিটি join-এর তিন-চারটি অ্যালগরিদম আর প্রতিটি টেবিলের কয়েকটি access path যোগ করলে সংখ্যাটি আরও বহুগুণ। দশ টেবিলের একটি রিপোর্ট-কোয়েরি বাস্তবে বিরল নয়। তাই দুটি কৌশল প্রায় সর্বজনীন: cross product এড়ানো — যে দুটি টেবিলের মধ্যে join শর্ত নেই, তাদের আগে জোড়া না লাগানো — আর একই উপসমস্যা বারবার না সমাধান করা, যা নিয়ে পরের অংশ।

৪ · System R-এর dynamic programming — Selinger-এর পদ্ধতি

মূল পর্যবেক্ষণটি principle of optimality: ধরুন {A, B, C, D}-এর সেরা left-deep plan শেষে D join করে। তাহলে তার ভেতরের {A, B, C}-এর অংশটিও {A, B, C}-এর সেরা plan হতেই হবে — নইলে সেই অংশ সস্তাটি দিয়ে বদলালে পুরো plan আরও সস্তা হতো। তাই প্রতিটি টেবিল-উপসেটের সেরা plan একবার হিসাব করে জমিয়ে রাখা যায়, আর বড় উপসেট গড়া যায় ছোটগুলো থেকে। এটিই dynamic programming — DSA কোর্সের DP-র ভিত্তি পর্বের সেই একই চিন্তা।

for each table R:
    best[{R}] = সবচেয়ে সস্তা access path (scan বা index)
for size = 2 .. n:
    for each subset S with |S| = size:
        for each table R in S:            # R হবে শেষে join হওয়া টেবিল
            if S − {R} আর R-এর মধ্যে join শর্ত নেই: continue
            p = join(best[S − {R}], R, সবচেয়ে সস্তা join অ্যালগরিদম)
            if cost(p) < cost(best[S]): best[S] = p
return best[{all tables}]

খরচ: উপসেট আছে 2ⁿ − 1টি, প্রতিটিতে সর্বোচ্চ n টি “শেষ টেবিল” চেষ্টা — তাই O(n · 2ⁿ) টি plan তুলনা, n! নয়। n = 10-এ n! প্রায় ৩৬ লাখ, অথচ n · 2ⁿ মাত্র ১০,২৪০. Bushy plan-ও ধরলে প্রতিটি উপসেটকে দুই ভাগে ভাঙার সব উপায় দেখতে হয়, মোট কাজ O(3ⁿ)। এবার চারটি টেবিলে হাতে চালান। ধরা যাক একটি বড় দোকান (সংখ্যাগুলো হিসাবের জন্য ধরে নেওয়া): customers-এর মধ্যে Sylhet-এর ১০০ জন (C′), orders ২০,০০০ (O), order_items ৬০,০০০ (I), আর products-এর মধ্যে Books শ্রেণির ১০টি (P′)। join শর্তগুলো একটি শিকল: C′–O–I–P′. সরল cost model: সব মধ্যবর্তী join-ফলের আকারের যোগফল (যত কম সারি পথে তৈরি হয়, তত সস্তা)। join-এর আকার অংশ ৬-এর সূত্রে।

শেষ ধাপের কথাটির নাম interesting order, আর এটি Selinger-এর প্রবন্ধের সবচেয়ে সূক্ষ্ম অবদান। কোনো plan-এর ফল যদি এমন কলামে সাজানো থাকে, যা পরে কাজে লাগবে (ORDER BY, GROUP BY, বা পরের merge join-এর কলাম), তাহলে সেটি একটু দামি হলেও বাদ দেওয়া যায় না — কারণ সস্তা plan-টির পরে আলাদা sort লাগতে পারে। তাই DP প্রতিটি উপসেটে একটি নয়, প্রতিটি interesting order-এর জন্য একটি সেরা plan রাখে। principle of optimality তখন খাটে “একই উপসেট আর একই ক্রমের” plan-গুলোর মধ্যে।

৫ · Cardinality estimation — statistics আর histogram

DP-র প্রতিটি সংখ্যা — ১,০০০, ৩,০০০, ৩০০ — আসলে অনুমান। কোয়েরি না চালিয়ে DBMS এগুলো পায় আগে থেকে জমানো statistics থেকে, যা ANALYZE কমান্ড (বা স্বয়ংক্রিয় একটি কাজ) টেবিল পড়ে, প্রায়ই একটি নমুনা থেকে, বানায় আর system catalog-এ রাখে। প্রচলিত statistics:

• সারির সংখ্যা |R| আর page-এর সংখ্যা — scan-এর খরচের জন্য।
• Distinct মানের সংখ্যা V(R, a) — n_distinct; equality আর join-এর অনুমানের ভিত্তি।
• NULL-এর ভাগ — a = 5 বা a IS NULL-এর অনুমানে লাগে।
• Most common values (MCV) — সবচেয়ে প্রচলিত কয়েকটি মান আর তাদের ভাগ।
• Histogram — বাকি মানগুলো কোন পরিসরে কতটা ঘন।

নিজের হাতে PostgreSQL-এর pg_stats-এর মতো পরিসংখ্যান বানান:

-- আকার, distinct মান, NULL-এর ভাগ
SELECT COUNT(*) AS n_rows, COUNT(DISTINCT city) AS v_city,
       COUNT(DISTINCT division) AS v_division,
       ROUND(AVG(phone IS NULL), 2) AS null_frac_phone
FROM cust;
-- status-এর MCV তালিকা: মান আর ভাগ
SELECT status, COUNT(*) AS cnt, ROUND(COUNT(*) / 20000.0, 3) AS freq
FROM ord GROUP BY status ORDER BY cnt DESC;
-- cust_id: কয়টি আলাদা মান, গড়ে আর সর্বোচ্চ কয়টি সারি
SELECT COUNT(DISTINCT cust_id) AS v_cust,
       ROUND(COUNT(*) * 1.0 / COUNT(DISTINCT cust_id), 1) AS avg_rows,
       (SELECT MAX(c) FROM (SELECT COUNT(*) AS c FROM ord GROUP BY cust_id)) AS max_rows
FROM ord;

Equi-width বনাম equi-depth histogram

amount-এর মতো সংখ্যার কলামে হাজারো আলাদা মান, সবার জন্য MCV রাখা যায় না। তখন histogram: মানের পরিসরকে কয়েকটি bucket-এ ভাগ করে প্রতিটির সারি গোনা। দুই রকম ভাগ:

-- equi-depth: ১০টি bucket, প্রতিটিতে সমান সারি (NTILE, পর্ব ২৬)
SELECT b AS bucket, COUNT(*) AS rows_in, MIN(amount) AS lo, MAX(amount) AS hi
FROM (SELECT amount, NTILE(10) OVER (ORDER BY amount) AS b FROM ord)
GROUP BY b ORDER BY b;
-- equi-width: ১০টি সমান চওড়া bucket (100 থেকে 49994)
SELECT (amount - 100) * 10 / 49895 AS bucket, COUNT(*) AS rows_in
FROM ord GROUP BY bucket ORDER BY bucket;
-- আসল উত্তর
SELECT COUNT(*) AS actual FROM ord WHERE amount < 1000;

বাস্তব সিস্টেমে এগুলো DBMS নিজে বানায়। PostgreSQL-এ default_statistics_target সাধারণত ১০০ — সর্বোচ্চ ১০০টি MCV আর ১০০ bucket-এর histogram, আর ANALYZE একটি নমুনা পড়ে (target-এর ৩০০ গুণ সারি)। MySQL 8.0 থেকে histogram আছে, তবে হাতে বানাতে হয়। তুলনার জন্য (এখানে চালানো যায় না):

-- PostgreSQL
ANALYZE ord;
SELECT attname, null_frac, n_distinct, most_common_vals,
       most_common_freqs, histogram_bounds
FROM pg_stats WHERE tablename = 'ord';
ALTER TABLE ord ALTER COLUMN amount SET STATISTICS 500;  -- বেশি bucket

-- MySQL 8.0+
ANALYZE TABLE ord UPDATE HISTOGRAM ON amount WITH 64 BUCKETS;

৬ · Selectivity-র সূত্র — হাতে হিসাব

একটি শর্তের selectivity হলো সে মোট সারির কত ভগ্নাংশ রাখে; অনুমিত সারি = |R| × sel. System R-এর সময় থেকে প্রচলিত সূত্রগুলো:

Join-এর সূত্রটি কোথা থেকে? ধরুন V(R,a) ≤ V(S,a), আর ধরে নেওয়া হলো R-এর প্রতিটি a-মান S-এও আছে (মান-সেটের containment). R-এর একটি সারি নিন; তার a-মানটি S-এর V(S,a)টি মানের একটি, আর uniformity ধরলে S-এর প্রতিটি মানের |S| / V(S,a)টি সারি। তাই R-এর প্রতিটি সারি গড়ে |S| / V(S,a)টি সারির সাথে মেলে, মোট |R| · |S| / V(S,a). V(S,a) দুইয়ের বড়টি, তাই হর-এ max. বিশেষ ক্ষেত্র: a যদি S-এর primary key আর R-এর foreign key হয়, তাহলে V(S,a) = |S|, আর সূত্র দেয় ঠিক |R| — প্রতিটি অর্ডার ঠিক একজন গ্রাহকের সাথে মেলে। System R-এর মূল প্রবন্ধে statistics না থাকলে কিছু নির্দিষ্ট মানও ধরা হতো: equality-তে ১/১০, তুলনায় ১/৩, BETWEEN-এ ১/৪.

এবার সূত্র বনাম আসল সারি, আমাদের ডেটায়। ভাগগুলো আগের এডিটরের statistics থেকে: Dhaka ০.৫, ঢাকা বিভাগ ০.৬, Gazipur ০.১, চট্টগ্রাম বিভাগ ০.২, phone NULL ০.১, returned ০.০১:

SELECT 2000 / 7 AS est_by_1_over_V,
       SUM(city = 'Sylhet') AS sylhet, SUM(city = 'Dhaka') AS dhaka FROM cust;
SELECT 2000 * 0.5 * 0.6 AS est_and, COUNT(*) AS actual
FROM cust WHERE city = 'Dhaka' AND division = 'Dhaka';
SELECT 2000 * 0.1 * 0.2 AS est_and, COUNT(*) AS actual
FROM cust WHERE city = 'Gazipur' AND division = 'Chattogram';
SELECT ROUND(2000 * (0.5 + 0.1 - 0.5 * 0.1)) AS est_or, COUNT(*) AS actual
FROM cust WHERE city = 'Dhaka' OR phone IS NULL;
SELECT ROUND(100 * 20000.0 / 1505) AS est_join, COUNT(*) AS actual
FROM cust c JOIN ord o ON o.cust_id = c.id WHERE c.city = 'Sylhet';
SELECT ROUND(100 * 20000.0 / 1505 * 0.01) AS est_3, COUNT(*) AS actual
FROM cust c JOIN ord o ON o.cust_id = c.id
WHERE c.city = 'Sylhet' AND o.status = 'returned';

৭ · অনুমান কোথায় ভুল হয় — আর ভুল কীভাবে গুণ হয়

প্রতিটি সূত্রের পেছনে একটি “ধরে নেওয়া” আছে, আর বাস্তব ডেটা প্রায়ই সেটি ভাঙে। পাঁচটি পরিচিত উৎস:

ভুল কেন গুণ হয়? join-এর অনুমান = বাঁ দিকের অনুমান × ডান দিকের অনুমান × join selectivity. ধরুন প্রতিটি শর্তের অনুমান সঠিকের f গুণ (f = ৩ মানে তিন গুণ বেশি বা কম)। দুটি শর্তের পর ভুল f², আর k টি এমন ধাপের পর f^k পর্যন্ত — f = ৩ আর k = ৫ হলে ২৪৩ গুণ। সব ভুল একদিকে যায় না, তবু ১৯৯১ সালে Ioannidis আর Christodoulakis দেখান, খারাপ ক্ষেত্রে join-এর সংখ্যার সাথে ভুল সূচকীয় হারে বাড়ে। ২০১৫ সালে Leis ও সহকর্মীদের “How Good Are Query Optimizers, Really?” প্রবন্ধ IMDb-র আসল ডেটায় কয়েকটি বড় DBMS পরীক্ষা করে দেখায়, বহু-join কোয়েরিতে সবাই প্রায়ই অনেক কম অনুমান করে, আর plan-এর গুণমানে cost model-এর চেয়ে cardinality-র ভুলের প্রভাব অনেক বেশি।

প্রতিকারের একটি পথ বাড়তি statistics. PostgreSQL 10 থেকে extended statistics দিয়ে কয়েকটি কলামের সম্পর্ক জানানো যায় (নিচের mcv ধরনটি এসেছে PostgreSQL 12-এ); SQL Server আর Oracle-এ বহু-কলামের statistics-এর নিজস্ব ব্যবস্থা আছে:

CREATE STATISTICS cust_city_div (dependencies, ndistinct, mcv)
  ON city, division FROM cust;
ANALYZE cust;   -- এখন city = 'Dhaka' AND division = 'Dhaka'-এ প্রায় ১,০০০

৮ · হাতে-কলমে — index, ANALYZE আর plan-এর বদল

SQLite-এর optimizer-ও cost-based. তার statistics থাকে sqlite_stat1 টেবিলে, যা ANALYZE বানায়। প্রথমে দেখুন সেখানে কী থাকে:

CREATE INDEX ord_status ON ord(status);
CREATE INDEX ord_cust   ON ord(cust_id);
CREATE INDEX cust_city  ON cust(city);
ANALYZE;
SELECT * FROM sqlite_stat1;

এবার একটি join-এর plan কীভাবে বদলায়, index যোগ করতে করতে। প্রশ্নটি অংশ ২-এর: Sylhet-এর গ্রাহকদের returned অর্ডার। (এখানে ANALYZE নেই।)

-- ক. কোনো index নেই
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM cust c JOIN ord o ON o.cust_id = c.id
WHERE c.city = 'Sylhet' AND o.status = 'returned';
-- খ. city আর join-কলামে index
CREATE INDEX cust_city ON cust(city);
CREATE INDEX ord_cust  ON ord(cust_id);
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM cust c JOIN ord o ON o.cust_id = c.id
WHERE c.city = 'Sylhet' AND o.status = 'returned';
-- গ. status-এও index
CREATE INDEX ord_status ON ord(status);
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM cust c JOIN ord o ON o.cust_id = c.id
WHERE c.city = 'Sylhet' AND o.status = 'returned';

এবার তিনটি index-ই আছে। ANALYZE চালালে কী হয়, আর কোন পথে আসলে কত সারি ছুঁতে হয়:

EXPLAIN QUERY PLAN SELECT COUNT(*) FROM cust c JOIN ord o ON o.cust_id = c.id
WHERE c.city = 'Sylhet' AND o.status = 'returned';
ANALYZE;
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM cust c JOIN ord o ON o.cust_id = c.id
WHERE c.city = 'Sylhet' AND o.status = 'returned';
-- দুই পথে কত সারি পড়তে হয়?
SELECT (SELECT COUNT(*) FROM ord o JOIN cust c ON c.id = o.cust_id
        WHERE c.city = 'Sylhet') AS via_city,
       (SELECT COUNT(*) FROM ord WHERE status = 'returned') AS via_status;
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM ord WHERE status = 'delivered' AND amount > 40000;

Statistics তাজা রাখা আর plan-এর কারণ পড়া

• PostgreSQL: autovacuum নিজে থেকে ANALYZE চালায়, যখন শেষবারের পর যথেষ্ট সারি বদলায় (মোটামুটি টেবিলের ১০% আর একটি ছোট নির্দিষ্ট সংখ্যা)। বড় bulk load বা নতুন টেবিলের পর নিজে ANALYZE চালান — নইলে পরের কয়েকটি কোয়েরি পুরোনো ছবিতে plan পায়।
• MySQL/InnoDB: persistent statistics নিজে হালনাগাদ হয়; বড় পরিবর্তনের পর ANALYZE TABLE.
• SQLite: statistics কখনো নিজে হয় না। SQLite-এর নির্দেশিকা অনুযায়ী ডেটাবেস বন্ধের আগে বা মাঝে মাঝে PRAGMA optimize চালানো ভালো, যা দরকার মনে হলে ANALYZE করে।

plan কেন বাছা হলো, তা পড়ার মূল কৌশল: প্রতিটি ধাপে আনুমানিক সারি বনাম আসল সারি মেলানো। PostgreSQL-এর EXPLAIN ANALYZE কোয়েরি সত্যিই চালায়, আর প্রতিটি গিঁটে দুটিই দেখায়। নিচে আকৃতিটি (সংখ্যাগুলো ব্যাখ্যার জন্য, কোনো আসল রানের নয়):

Nested Loop  (cost=… rows=13 …) (actual time=… rows=42 loops=1)
  -> Index Scan using cust_city on cust c  (… rows=100 …) (actual … rows=100 loops=1)
  -> Index Scan using ord_cust on ord o  (… rows=1 …) (actual … rows=0 loops=100)
        Filter: (status = 'returned')

প্রথম rows= অনুমান, actual … rows= আসল (প্রতি loop-এ গড়)। খোঁজার নিয়ম: নিচ থেকে ওপরে যান, আর প্রথম যে গিঁটে অনুমান আর আসলের মধ্যে ১০ গুণ বা তার বেশি ফারাক, সেখানেই সাধারণত ভুল plan-এর শিকড়। ওপরের গিঁটগুলো সেই ভুলের ওপর দাঁড়িয়ে।

৯ · অনেক join, plan cache আর hint

অনেক টেবিল: randomized আর greedy খোঁজ

O(n · 2ⁿ)-ও অসীম নয়: ২০টি টেবিলে ২ কোটির বেশি plan. তাই প্রতিটি DBMS একটি সীমার পর পুরো DP ছেড়ে দেয়। PostgreSQL-এ FROM-এর আইটেম geqo_threshold-এর (সাধারণত ১২) সমান বা বেশি হলে GEQO চালু হয় — genetic algorithm-এর মতো: কয়েকটি এলোমেলো join order-এর একটি “জনসংখ্যা”, ভালোগুলো মিলিয়ে নতুন ক্রম, কয়েক প্রজন্ম পর সেরাটি। ফল ভালো, কিন্তু নিশ্চিতভাবে সেরা নয়। join_collapse_limit (সাধারণত ৮) ঠিক করে, লেখা JOIN-ক্রম কতটা নতুন করে সাজানো হবে। MySQL-এর optimizer greedy খোঁজ ব্যবহার করে, যার গভীরতা optimizer_search_depth দিয়ে বদলানো যায়।

Plan cache আর parameter-এর ফাঁদ

প্রতিবার plan বানানো দামি, তাই অ্যাপ prepared statement (পর্ব ৪৯) ব্যবহার করলে DBMS একটি plan জমা রাখে (plan cache). সমস্যা: WHERE status = ?-এর জন্য একটি plan, অথচ 'returned'-এ index চমৎকার আর 'delivered'-এ সর্বনাশ। SQL Server প্রথম ডাকের মান দেখে plan বানায় আর জমা রাখে — parameter sniffing; প্রথম ডাকটি বিরল মানের হলে পরের সব সাধারণ মানের ডাক ধীর। প্রতিকার আছে: SQL Server-এ OPTION (RECOMPILE) বা OPTIMIZE FOR, আর SQL Server 2022-এ parameter-sensitive plan optimization, যা একই কোয়েরির কয়েকটি plan রাখতে পারে। PostgreSQL প্রথম পাঁচবার প্রতিটি মানের জন্য আলাদা custom plan বানায়, তারপর একটি generic plan-এ যায় যদি সেটি গড়ে খুব খারাপ না হয়; plan_cache_mode দিয়ে এটি বদলানো যায়।

Adaptive execution

অনুমান যখন অনিশ্চিত, সিদ্ধান্তটি কিছুটা চালানোর সময় পর্যন্ত পিছিয়ে দেওয়া যায় — adaptive execution. Oracle 12c-র adaptive plan প্রথম কিছু সারি দেখে nested loop আর hash join-এর মধ্যে বেছে নেয়; SQL Server 2017-এর adaptive join একই রকম। Spark SQL-এর adaptive query execution প্রতিটি পর্যায়ের আসল আকার দেখে বাকি plan বদলায়।

Hint আর plan forcing — শেষ উপায়

Hint মানে optimizer-কে বলে দেওয়া — এই index ব্যবহার করা, এই ক্রমে join করা। প্রতিটি DBMS-এর নিজস্ব রূপ (তুলনার জন্য, এখানে চালানো যায় না):

-- MySQL 8.0
SELECT /*+ JOIN_ORDER(o, c) INDEX(o ord_status) */ COUNT(*)
FROM cust c JOIN ord o ON o.cust_id = c.id WHERE … ;
-- Oracle
SELECT /*+ LEADING(o c) USE_NL(c) INDEX(o ord_status) */ COUNT(*) FROM … ;
-- SQL Server
SELECT COUNT(*) FROM ord o WITH (INDEX(ord_status)) JOIN cust c ON …
OPTION (FORCE ORDER);
-- PostgreSQL: মূল সংস্করণে hint নেই; pg_hint_plan extension দিয়ে
/*+ Leading(o c) IndexScan(o ord_status) */ SELECT COUNT(*) FROM … ;

SQLite-এ hint-এর কাজ করে তিনটি জিনিস: likelihood(X, p) — শর্ত X কত ভাগ সারিতে সত্য, তা বলে দেওয়া; likely(X) মানে p = 0.9375, unlikely(X) মানে p = 0.0625; আর CROSS JOIN লিখলে বাঁ দিকের টেবিল বাইরের loop-এ থাকতে বাধ্য। অংশ ৮-এর ভুল plan-টি দিয়ে পরীক্ষা করুন — এই এডিটরে তিনটি index আর ANALYZE আগে থেকেই করা:

-- ক. কোনো hint নেই
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM cust c JOIN ord o ON o.cust_id = c.id
WHERE c.city = 'Sylhet' AND o.status = 'returned';
-- খ. unlikely(): শর্তটি 6.25% সারিতে সত্য
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM cust c JOIN ord o ON o.cust_id = c.id
WHERE c.city = 'Sylhet' AND unlikely(o.status = 'returned');
-- গ. likelihood(): আসল ভাগ 1%
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM cust c JOIN ord o ON o.cust_id = c.id
WHERE c.city = 'Sylhet' AND likelihood(o.status = 'returned', 0.01);
-- ঘ. CROSS JOIN: ord বাইরে থাকতে বাধ্য
EXPLAIN QUERY PLAN SELECT COUNT(*) FROM ord o CROSS JOIN cust c
WHERE o.cust_id = c.id AND c.city = 'Sylhet' AND o.status = 'returned';

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

“এই কোয়েরি দ্রুত করো” — AI সহজেই নতুন index, hint বা নতুন করে লেখা কোয়েরি দেয়। কিন্তু আপনার ডেটার বণ্টন, statistics আর আসল plan সে দেখেনি। সাধারণ ভুল:

AI-এর দেওয়া optimization চালু করার আগে — চেকলিস্ট

• আগে আর পরে EXPLAIN দেখেছি; plan সত্যিই বদলেছে, আর আনুমানিক বনাম আসল সারি মিলিয়েছি
• নতুন করে লেখা কোয়েরির ফল পুরোনোটির সাথে দুই দিকেই EXCEPT দিয়ে মিলিয়েছি — NULL আর duplicate-সহ
• সময় মেপেছি আসল মাপের ডেটায়, শুধু ছোট নমুনায় নয়; বিরল আর প্রচলিত দুই রকম parameter-এ
• statistics তাজা (ANALYZE) কি না দেখেছি, hint দেওয়ার আগে
• নতুন index-এর লেখার খরচ আর জায়গা হিসাব করেছি (পর্ব ৪১)
• hint থাকলে তার কারণ আর তারিখ মন্তব্যে লিখেছি