CTE আর recursive query

১ · CTE কী — কোয়েরিকে নাম দেওয়া ধাপে ভাঙা

মুদি দোকানের মাসিক হিসাব করতে বসে মালিক খাতার পাশে একটি কাগজে আগে লেখেন: “ধাপ ১ — বাতিল অর্ডার বাদ দিলাম। ধাপ ২ — প্রতিটি পণ্যের মোট বিক্রি। ধাপ ৩ — সেই বিক্রির গড়।” তারপর শেষ প্রশ্নের উত্তর দেন: কোন পণ্য গড়ের চেয়ে বেশি বিক্রি হয়েছে? প্রতিটি ধাপের একটি নাম আছে, আর পরের ধাপ আগের ধাপের নাম ধরে কথা বলে।

পর্ব ২১-এ (Subquery — nested, correlated আর EXISTS) একই ধরনের প্রশ্ন আপনি বন্ধনীর ভেতরে বন্ধনী দিয়ে লিখেছেন। ফল ঠিক আসে, কিন্তু পড়তে হয় ভেতর থেকে বাইরে, আর একই টুকরো দুবার লিখতে হয়। CTE (common table expression) ঠিক ওই কাগজের ধাপগুলোর মতো। WITH শব্দের পরে প্রতিটি ধাপকে একটি নাম দিয়ে লেখা হয়, আর শেষে মূল SELECT সেই নামগুলোকে টেবিলের মতো ব্যবহার করে।

WITH নাম1 AS (SELECT …),            -- ধাপ ১
     নাম2 AS (SELECT … FROM নাম1)    -- ধাপ ২: আগের ধাপ ব্যবহার করে
SELECT … FROM নাম2;                 -- মূল কোয়েরি

এই পর্বের লাইভ SQL চলে আগের পর্বগুলোর দুটি নমুনা ডেটাবেসে। db-shop একটি দোকান: customers (customer_id, name, city — ৮ জন), categories, products (product_id, name, category_id, price, stock — ১০টি পণ্য), orders (order_id, customer_id, order_date, status — সেপ্টেম্বর আর অক্টোবর ২০২৫-এর ১০টি অর্ডার, একটি cancelled) আর order_items (order_id, product_id, quantity, unit_price). db-uni একটি বিশ্ববিদ্যালয়; এই পর্বে মূলত লাগবে instructors (instructor_id, name, dept_id, salary, mentor_id) — mentor_id হলো নতুন শিক্ষককে দেখাশোনা করেন যে সিনিয়র শিক্ষক, তাঁর instructor_id. কিছু এডিটরে নিজস্ব ছোট টেবিল যোগ হয়, সেগুলোর বর্ণনা সেখানেই পাবেন। প্রতিবার চালালে ডেটাবেস নতুন করে তৈরি হয়।

তিন স্তরের subquery, আর তার CTE-রূপ

প্রশ্ন: বাতিল অর্ডার বাদ দিয়ে কোন পণ্যের মোট বিক্রি (revenue) সব বিক্রি-হওয়া পণ্যের গড় বিক্রির চেয়ে বেশি? পর্ব ২১-এর কৌশলে লিখলে দাঁড়ায় এমন:

SELECT name FROM products
WHERE product_id IN (
  SELECT product_id FROM (
    SELECT product_id, SUM(quantity * unit_price) AS revenue
    FROM order_items
    WHERE order_id IN (SELECT order_id FROM orders WHERE status <> 'cancelled')
    GROUP BY product_id) AS r
  WHERE r.revenue > (
    SELECT AVG(revenue) FROM (
      SELECT SUM(quantity * unit_price) AS revenue          -- একই টুকরো আবার
      FROM order_items
      WHERE order_id IN (SELECT order_id FROM orders WHERE status <> 'cancelled')
      GROUP BY product_id)));

এটি চলে, আর ফল দেয় Mobile Phone আর Smart Watch. কিন্তু “বাতিল বাদ দাও” আর “পণ্যভিত্তিক বিক্রি” দুবার করে লেখা। কাল কেউ “pending-ও বাদ দাও” বললে দুই জায়গাতেই বদলাতে হবে, আর একটিতে ভুলে গেলে গড় আর তুলনা দুই আলাদা ডেটা থেকে আসবে। CTE-রূপে একই প্রশ্ন তিনটি নাম দেওয়া ধাপ:

WITH valid_orders AS (
  SELECT order_id FROM orders WHERE status <> 'cancelled'
),
revenue AS (
  SELECT product_id, SUM(quantity * unit_price) AS revenue
  FROM order_items
  WHERE order_id IN (SELECT order_id FROM valid_orders)
  GROUP BY product_id
),
avg_rev AS (SELECT AVG(revenue) AS avg_revenue FROM revenue)
SELECT p.name, r.revenue, a.avg_revenue
FROM revenue r
JOIN products p ON p.product_id = r.product_id
CROSS JOIN avg_rev a
WHERE r.revenue > a.avg_revenue
ORDER BY r.revenue DESC;

২ · একাধিক CTE, একটির ওপর আরেকটি, আর একাধিকবার ব্যবহার

উপরের উদাহরণে তিনটি নিয়ম কাজ করেছে, আলাদা করে লিখে রাখুন:

• একটি WITH, অনেক CTE: CTE-গুলো কমা দিয়ে আলাদা হয়। প্রতিটির আগে আবার WITH লেখা ভুল।
• পরেরটি আগেরটিকে দেখে: revenue ব্যবহার করেছে valid_orders, avg_rev ব্যবহার করেছে revenue. উল্টোটা সাধারণ (non-recursive) CTE-তে চলে না — যে নাম এখনো লেখা হয়নি, তা ব্যবহার করা যায় না।
• নামের আয়ু এক statement: শেষ সেমিকোলনের পর valid_orders আর নেই। পরের কোয়েরিতে আবার লাগলে আবার লিখতে হবে, নয়তো view বানাতে হবে (পর্ব ২৪)।

CTE-র কলামের নাম দুইভাবে দেওয়া যায়: ভেতরের SELECT-এর alias দিয়ে (AS revenue), অথবা নামের পাশে বন্ধনীতে তালিকা দিয়ে — WITH t(product_id, revenue) AS (…). Recursive CTE-তে দ্বিতীয় রূপটিই প্রচলিত, অংশ ৪-এ দেখবেন। আর একটি CTE যদি কোনো আসল টেবিলের নামে হয়, যেমন WITH orders AS (…), তবে সেই statement-এ orders মানে CTE-টি, আসল টেবিল নয়। এটি বৈধ, কিন্তু বিভ্রান্তিকর — এড়িয়ে চলুন।

পর্ব ২১-এ একটি কোয়েরি ঠিক ফল দিলেও পড়তে কষ্টকর ছিল: “যে অর্ডার নিজের গ্রাহকের গড় অর্ডারের চেয়ে বড়”, যেখানে অর্ডারের মোটের derived table দুবার লিখতে হয়েছিল। CTE-তে সেটি একবার লেখা হয়, আর ব্যবহার হয় দুবার — একবার বাইরে, একবার correlated subquery-র ভেতরে:

WITH order_totals AS (
  SELECT o.order_id, o.customer_id, SUM(i.quantity * i.unit_price) AS total
  FROM orders o JOIN order_items i ON i.order_id = o.order_id
  GROUP BY o.order_id, o.customer_id
)
SELECT order_id, customer_id, total
FROM order_totals ot
WHERE total > (SELECT AVG(total) FROM order_totals
               WHERE customer_id = ot.customer_id)
ORDER BY order_id;

৩ · CTE বনাম view, derived table আর temp table — আর materialization

চারটি জিনিসই “একটি কোয়েরির ফলকে টেবিলের মতো ব্যবহার” করতে দেয়। পার্থক্য হলো তারা কতক্ষণ বাঁচে, কোথায় সংরক্ষিত থাকে, আর কে ব্যবহার করতে পারে:

Materialize, নাকি inline?

DBMS একটি CTE দুইভাবে চালাতে পারে। এক, materialization: CTE-র পুরো ফল আগে একটি অস্থায়ী জায়গায় বানিয়ে রাখা, তারপর মূল কোয়েরি সেখান থেকে পড়ে। দুই, inlining: CTE-কে derived table-এর মতো মূল কোয়েরির ভেতরে বসিয়ে দেওয়া, যাতে optimizer বাইরের WHERE ভেতরে ঠেলে দিতে পারে আর index ব্যবহার করতে পারে। CTE বারবার ব্যবহার হলে ও হিসাবটি ভারী হলে প্রথমটি ভালো; একবার ব্যবহার হলে আর বাইরে কড়া ছাঁকনি থাকলে দ্বিতীয়টি।

PostgreSQL-এ ১২ সংস্করণের (২০১৯) আগে প্রতিটি CTE সবসময় materialize হতো, তাই CTE ছিল একটি optimization fence: বাইরের শর্ত ভেতরে ঢুকত না। ১২ থেকে নিয়ম বদলেছে — যে non-recursive CTE-র কোনো পার্শ্বপ্রতিক্রিয়া নেই আর মাত্র একবার ব্যবহার হয়, সেটি স্বাভাবিকভাবে inline হয়। একাধিকবার ব্যবহার হলে materialize হয়। নিজে ঠিক করে দিতে চাইলে AS MATERIALIZED বা AS NOT MATERIALIZED লেখা যায়। SQLite-ও ৩.৩৫ সংস্করণ (২০২১) থেকে এই দুটি শব্দ বোঝে। নিচে একই প্রশ্ন দুই ইঙ্গিতে চালিয়ে SQLite-এর পরিকল্পনা দেখুন:

-- MATERIALIZED: আগে পুরো CTE একটি অস্থায়ী টেবিলে
EXPLAIN QUERY PLAN
WITH t AS MATERIALIZED (SELECT * FROM orders WHERE status = 'delivered')
SELECT order_id FROM t WHERE customer_id = 2;

-- NOT MATERIALIZED: CTE বাইরের কোয়েরির সাথে মিশে যায়
EXPLAIN QUERY PLAN
WITH t AS NOT MATERIALIZED (SELECT * FROM orders WHERE status = 'delivered')
SELECT order_id FROM t WHERE customer_id = 2;

-- ফল দুই ক্ষেত্রেই একই
WITH t AS MATERIALIZED (SELECT * FROM orders WHERE status = 'delivered')
SELECT order_id FROM t WHERE customer_id = 2;

-- বড় হিসাব একবারই হোক, যদিও তিনবার ব্যবহার হবে
WITH order_totals AS MATERIALIZED (
  SELECT order_id, SUM(quantity * unit_price) AS total
  FROM order_items GROUP BY order_id
)
SELECT … ;

-- উল্টো: একবার ব্যবহার, বাইরে index-যোগ্য শর্ত — inline হোক
WITH recent AS NOT MATERIALIZED (SELECT * FROM orders)
SELECT * FROM recent WHERE order_id = 1007;   -- primary key index ব্যবহার হবে

অন্যদের আচরণ আলাদা। SQL Server CTE-কে কখনো নিজে থেকে সংরক্ষণ করে না — প্রতিটি ব্যবহারে CTE-র সংজ্ঞাটি কোয়েরিতে বসিয়ে দেয়, তাই তিনবার ব্যবহার মানে তিনবার হিসাব হতে পারে; একবার হিসাব চাইলে temp table নিন। MySQL 8 সাধারণ derived table-এর মতোই CTE-কে মিশিয়ে দেয় বা materialize করে, আর একাধিকবার ব্যবহার হলে সাধারণত একবার materialize করে। তাই “CTE দ্রুত না ধীর” প্রশ্নের একটিই উত্তর নেই — উত্তরটি পাবেন নিজের DBMS-এর query plan-এ।

Data-modifying CTE — PostgreSQL-এর বিশেষ ক্ষমতা

PostgreSQL ৯.১ (২০১১) থেকে WITH-এর ভেতরে শুধু SELECT নয়, INSERT, UPDATE বা DELETE-ও বসানো যায়; তার বদলানো সারি পরের অংশে পড়তে চাইলে তাতে RETURNING লাগে। একে বলে data-modifying CTE. ধরুন মুদি পণ্যের (category 4) দাম ৫% বাড়বে, আর প্রতিটি পরিবর্তন একটি লগ টেবিলে লিখে রাখতে হবে — একটিই statement-এ:

CREATE TABLE price_log (product_id int, new_price numeric, changed_on date);

WITH changed AS (
  UPDATE products SET price = price * 1.05
  WHERE category_id = 4
  RETURNING product_id, price AS new_price      -- বদলানো সারিগুলো ফেরত দেয়
)
INSERT INTO price_log (product_id, new_price, changed_on)
SELECT product_id, new_price, CURRENT_DATE FROM changed;

এখানে তিনটি নিয়ম জানা জরুরি, PostgreSQL-এর ডকুমেন্টেশনেই লেখা। (১) WITH-এর সব অংশ আর মূল statement একই snapshot দেখে — একটি অংশের পরিবর্তন অন্য অংশ টেবিলে দেখে না, শুধু RETURNING-এর মাধ্যমে পায়। (২) Data-modifying অংশটি সবসময় একবার আর পুরোপুরি চলে, মূল কোয়েরি তার ফল পড়ুক বা না পড়ুক। (৩) একই statement-এ একই সারি দুবার বদলানোর চেষ্টা করলে কোন পরিবর্তন টিকবে তা নিশ্চিত নয় — এমন লেখা এড়িয়ে চলুন। পুরো কাজটি একটি statement বলে এটি নিজেই atomic: হয় দাম বদলাবে আর লগ হবে, নয়তো কিছুই না (পর্ব ৪৪)।

SQLite আর MySQL-এ CTE-র ভেতরটি অবশ্যই SELECT; সেখানে একই কাজ করতে একটি transaction-এর ভেতরে দুটি আলাদা statement লাগে, অথবা পর্ব ২৯-এর trigger. SQL Server-এ ভিন্ন একটি কৌশল প্রচলিত: সহজ CTE-র মাধ্যমে নিচের টেবিল বদলানো যায় — WITH d AS (SELECT …) DELETE FROM d WHERE … — যা duplicate মোছার কাজে বহুল ব্যবহৃত (পর্ব ২৭)।

৪ · Recursive CTE-র গঠন — anchor, recursive member আর UNION ALL

পর্ব ২০-এ (Self join, cross join, semi join আর anti join) দেখেছেন, mentor-এর mentor খুঁজতে দুটি self join লাগে, আর k স্তর ওপরে যেতে k-টি। গভীরতা আগে থেকে জানা না থাকলে self join দিয়ে কোয়েরি লেখাই যায় না। এবার সমাধান। একটি CTE যদি নিজের নাম নিজের ভেতরে ব্যবহার করে, তবে সেটি recursive CTE. তার দুটি অংশ, মাঝে UNION ALL:

WITH RECURSIVE nums(n) AS (
  SELECT 1                              -- anchor member: শুরুর সারি
  UNION ALL
  SELECT n + 1 FROM nums WHERE n < 10   -- recursive member: আগের সারি থেকে পরের
)
SELECT n FROM nums;

• Anchor member: নিজের নাম ব্যবহার করে না। একবারই চলে, আর প্রথম সারিগুলো দেয়।
• Recursive member: FROM-এ নিজের নাম (nums) ব্যবহার করে। কিন্তু প্রতিবার সে পুরো nums দেখে না — দেখে শুধু আগের ধাপে নতুন আসা সারিগুলো। পরের অংশে এটি ধাপে ধাপে দেখবেন।
• থামার শর্ত: WHERE n < 10. recursive member যখন একটিও নতুন সারি দেয় না, recursion থামে।
• RECURSIVE শব্দ: standard SQL, PostgreSQL আর MySQL-এ বাধ্যতামূলক। SQLite-এ ঐচ্ছিক, আর SQL Server ও Oracle-এ এই শব্দটি লেখাই যায় না — সেখানে শুধু WITH.

এই কাঠামো দিয়ে সংখ্যার ধারা, আর একটু বুদ্ধি খাটালে factorial আর Fibonacci-ও বানানো যায়। প্রতিটি সারি আগের সারির মান বহন করে, ঠিক লুপের ভেতরের চলকের মতো:

-- ১ থেকে ১০
WITH RECURSIVE nums(n) AS (
  SELECT 1
  UNION ALL
  SELECT n + 1 FROM nums WHERE n < 10
)
SELECT n FROM nums;

-- একই লুপে factorial আর Fibonacci: প্রতিটি সারি আগের মানগুলো বয়ে আনে
WITH RECURSIVE f(n, fact, fib, fib_next) AS (
  SELECT 1, 1, 1, 1
  UNION ALL
  SELECT n + 1, fact * (n + 1), fib_next, fib + fib_next FROM f WHERE n < 10
)
SELECT n, fact, fib FROM f;

PostgreSQL-এ সংখ্যা বা তারিখের ধারার জন্য তৈরি ফাংশন আছে — generate_series(1, 10). SQLite-এ generate_series একটি extension হিসেবে আসে, যা সব build-এ থাকে না; তাই সব জায়গায় চলবে এমন উপায় হলো recursive CTE.

তারিখের ধারা — অক্টোবরের কোন দিন অর্ডার আসেনি

পর্ব ১৮-এ দেখেছেন, GROUP BY শুধু ডেটায় যা আছে তা থেকে দল বানায়। যে দিন একটিও অর্ডার আসেনি, সেই দিনের সারিই তৈরি হয় না — দৈনিক বিক্রির চার্টে দিনটি নিঃশব্দে হারিয়ে যায়। সমাধান: আগে মাসের প্রতিটি দিনের একটি তালিকা বানান, তারপর তার সাথে orders-এর LEFT JOIN. বড় সিস্টেমে এর জন্য একটি স্থায়ী calendar table রাখা হয়; একবারের কাজে recursive CTE যথেষ্ট:

WITH RECURSIVE october(day) AS (
  SELECT '2025-10-01'
  UNION ALL
  SELECT date(day, '+1 day') FROM october WHERE day < '2025-10-31'
)
SELECT d.day,
       substr('SunMonTueWedThuFriSat', 1 + 3 * strftime('%w', d.day), 3) AS wd,
       COUNT(o.order_id) AS n_orders
FROM october d
LEFT JOIN orders o ON o.order_date = d.day
GROUP BY d.day
ORDER BY d.day;

SELECT d::date AS day, COUNT(o.order_id) AS n_orders
FROM generate_series(date '2025-10-01', date '2025-10-31', interval '1 day') AS d
LEFT JOIN orders o ON o.order_date = d::date
GROUP BY d ORDER BY d;

৫ · ভেতরে কী ঘটে — working table আর থামার নিয়ম

Recursive CTE-কে “নিজেকে ডাকা ফাংশন” ভাবলে ভুল হয়। আসলে এটি একটি লুপ, যা দুটি টেবিল রাখে: ফল (এ পর্যন্ত যত সারি এসেছে) আর working table (শুধু শেষ ধাপে নতুন আসা সারি)। নিয়মটি:

ফল    ← anchor চালাও
W     ← ফল                                  -- working table
যতক্ষণ W খালি নয়:
    নতুন ← recursive member চালাও, যেখানে নিজের নাম = W
    (UNION হলে: নতুন থেকে আগে-আসা সারি বাদ দাও)
    ফল   ← ফল ∪ নতুন
    W    ← নতুন
মূল SELECT চলে ফল-এর ওপর

এবার db-uni-র ছয়জন শিক্ষক নিয়ে লুপটি চালিয়ে দেখি। প্রশ্ন: প্রত্যেক শিক্ষক mentor-শৃঙ্খলের কোন স্তরে? যাঁর mentor নেই, তিনি স্তর ১. মনে রাখুন: Shahana-র mentor 1 (Anisur), Rumana-র 3 (Mahbub), Tasnim-এর 2 (Shahana).

কেন থামে — একটি ছোট প্রমাণ

ধরুন mentor-সম্পর্কে কোনো চক্র নেই (কেউ নিজের পূর্বসূরির mentor নন), আর শিক্ষক মোট n জন। ধাপ k-এর working table-এর প্রতিটি সারি একটি শৃঙ্খল-পথের শেষ মাথা, যে পথে ঠিক k + 1 জন আলাদা মানুষ — আলাদা, কারণ কোনো চক্র নেই। n জনের বেশি আলাদা মানুষ নেই, তাই k + 1 ≤ n, অর্থাৎ ধাপ n - 1-এর পরে working table অবশ্যই খালি। লুপ সর্বোচ্চ n বার ঘোরে। চক্র থাকলে এই যুক্তি ভাঙে — পথ অসীম লম্বা হতে পারে — আর তখনই অংশ ৭ আর ৮-এর পাহারা লাগে।

তত্ত্বের ভাষায়, ফলটি একটি fixpoint: এমন একটি টেবিল R, যার ওপর “anchor ∪ recursive(R)” চালালে আবার R-ই পাওয়া যায়। প্রতিটি ধাপে ফল শুধু বাড়ে, কমে না (monotone), আর এমন প্রক্রিয়া সবচেয়ে ছোট fixpoint-এ গিয়ে থামে। এই কারণেই standard SQL recursive member-এ aggregate, window function বা NOT EXISTS-এর মতো “অ-monotone” জিনিস সীমিত করে — SQLite-এ recursive অংশে aggregate দিলে সরাসরি ত্রুটি আসে: recursive aggregate queries not supported. আর recursive member-এ নিজের নাম একবারই থাকতে পারে (linear recursion); দুবার দিলে SQLite বলে multiple references to recursive table.

৬ · Hierarchy — mentor-শৃঙ্খল, category tree আর bill of materials

mentor_id-এর মতো “নিজের টেবিলের দিকে আঙুল” দিয়ে গাছ রাখাকে বলে adjacency list. অফিসের boss–কর্মী (org chart), জেলা–উপজেলা–ইউনিয়ন, ফেসবুক মন্তব্যের উত্তর — সবই এমন hierarchical data. Recursive CTE দিয়ে এগুলোর ওপর তিনটি প্রশ্ন সবচেয়ে বেশি আসে: কে কোন স্তরে, ওপর থেকে নিচ পর্যন্ত পথ কী, আর একটি শাখার নিচে কারা কারা।

Mentor-শৃঙ্খল, পথসহ

নিচের কোয়েরিতে দুটি CTE একটিই WITH RECURSIVE-এর নিচে: প্রথমটি (short) সাধারণ — নাম থেকে “Dr. ” বাদ দিয়ে প্রথম শব্দটি নেয়; দ্বিতীয়টি (chain) recursive, আর প্রথমটিকে ব্যবহার করে। WITH RECURSIVE লিখলে তার নিচের সব CTE-ই নিজেকে ডাকতে পারে, কিন্তু ডাকতে বাধ্য নয়:

WITH RECURSIVE
short AS (
  SELECT instructor_id, mentor_id,
         substr(replace(name, 'Dr. ', ''), 1,
                instr(replace(name, 'Dr. ', '') || ' ', ' ') - 1) AS nick
  FROM instructors
),
chain(id, level, path) AS (
  SELECT instructor_id, 1, nick FROM short WHERE mentor_id IS NULL
  UNION ALL
  SELECT s.instructor_id, c.level + 1, c.path || ' > ' || s.nick
  FROM short s JOIN chain c ON s.mentor_id = c.id
)
SELECT level, path FROM chain ORDER BY path;

Category tree — গাছের মতো সাজানো আর একটি শাখার সব সদস্য

অনলাইন দোকানে শ্রেণির ভেতরে উপশ্রেণি থাকে। এই এডিটরে একটি নতুন টেবিল cat_tree (id, name, parent_id) যোগ হয়: Electronics-এর নিচে Mobile আর Accessories, Accessories-এর নিচে Charger আর Headphone; Books-এর নিচে Academic আর Novel, Academic-এর নিচে Programming.

-- পুরো গাছ, স্তর অনুযায়ী ডানে সরানো
WITH RECURSIVE tree(id, name, depth, sort_key) AS (
  SELECT id, name, 0, name FROM cat_tree WHERE parent_id IS NULL
  UNION ALL
  SELECT c.id, c.name, t.depth + 1, t.sort_key || '/' || c.name
  FROM cat_tree c JOIN tree t ON c.parent_id = t.id
)
SELECT substr('............', 1, 3 * depth) || name AS category, depth
FROM tree ORDER BY sort_key;

-- Accessories (3)-এর নিচে সবাই, নিজেসহ
WITH RECURSIVE sub(id) AS (
  SELECT 3
  UNION ALL
  SELECT c.id FROM cat_tree c JOIN sub s ON c.parent_id = s.id
)
SELECT c.id, c.name FROM cat_tree c WHERE c.id IN (SELECT id FROM sub);

Bill of materials — একটি রিকশায় কয়টি spoke?

কারখানায় একটি পণ্য তৈরি হয় অংশ দিয়ে, অংশ তৈরি হয় আরও ছোট অংশ দিয়ে। এই তালিকাকে বলে bill of materials (BOM). এখানে গাছের প্রতিটি ডালে একটি সংখ্যাও আছে, আর গভীরে যেতে যেতে সংখ্যাগুলো গুণ হয়। এডিটরে দুটি টেবিল: parts (part) আর bom (parent, child, qty). ধরা যাক একটি রিকশায় ৩টি চাকা, ১টি সিট আর ১টি চেইন; প্রতিটি চাকায় ৩৬টি spoke, ১টি টায়ার আর ১টি rim; সিটে ৪টি spring (সংখ্যাগুলো উদাহরণের জন্য):

WITH RECURSIVE need(part, qty, level) AS (
  SELECT 'Rickshaw', 1, 0
  UNION ALL
  SELECT b.child, n.qty * b.qty, n.level + 1      -- গভীরে গেলে গুণ
  FROM bom b JOIN need n ON b.parent = n.part
)
SELECT part, SUM(qty) AS total_qty
FROM need
WHERE part NOT IN (SELECT parent FROM bom)        -- শুধু একেবারে নিচের অংশ
GROUP BY part ORDER BY part;

৭ · Graph — রাস্তা, চক্র আর সবচেয়ে কম ধাপের পথ

গাছে প্রত্যেকের একজনই অভিভাবক, তাই কোনো চক্র নেই। রাস্তার মানচিত্র তেমন নয়: ঢাকা থেকে কুমিল্লা যাওয়া যায়, কুমিল্লা থেকে ঢাকাও। এখানে কাজ করতে হয় graph নিয়ে। এডিটরের টেবিল roads (src, dst) একটি সরলীকৃত মানচিত্র — বাস্তবের সব শহর বা দূরত্ব নয়: Dhaka–Cumilla, Dhaka–Sylhet, Cumilla–Sylhet, Cumilla–Feni আর Feni–Chattogram. প্রতিটি রাস্তা দুই দিকে চলে, তাই টেবিলে ১০টি সারি। Dhaka–Cumilla–Sylhet একটি ত্রিভুজ — অর্থাৎ চক্র।

Recursive member যদি শুধু “এই শহর থেকে পাশের শহরে যাও” বলে, তবে Dhaka → Cumilla → Dhaka → Cumilla … কখনো শেষ হবে না। পাহারা হলো প্রতিটি সারিতে এ পর্যন্ত যাওয়া শহরগুলোর একটি পথ-স্ট্রিং রাখা, যেমন /Dhaka/Cumilla/, আর পরের শহরটি সেই স্ট্রিংয়ে থাকলে আর না যাওয়া। এটি cycle detection-এর সবচেয়ে প্রচলিত SQL কৌশল। শহরের নামের দুই পাশে “/” রাখার কারণ: শুধু নাম খুঁজলে একটি নাম আরেকটির অংশ হলে (ধরুন “Feni” আর “Fenix”) ভুল মিল হতো।

WITH RECURSIVE trip(city, hops, path) AS (
  SELECT 'Dhaka', 0, '/Dhaka/'
  UNION ALL
  SELECT r.dst, t.hops + 1, t.path || r.dst || '/'
  FROM trip t JOIN roads r ON r.src = t.city
  WHERE instr(t.path, '/' || r.dst || '/') = 0     -- আগে যাওয়া শহরে নয়
)
SELECT city, MIN(hops) AS min_hops, COUNT(*) AS n_paths
FROM trip GROUP BY city ORDER BY min_hops, city;

-- Dhaka থেকে Chattogram-এর সবচেয়ে কম ধাপের পথ: মূল SELECT বদলে দেখুন
-- SELECT path, hops FROM trip WHERE city = 'Chattogram' ORDER BY hops LIMIT 1;

৮ · অসীম recursion থেকে বাঁচা — UNION, depth আর LIMIT

Visited path ছাড়াও তিনটি পাহারা আছে, প্রতিটির নিজের সুবিধা আর সীমা। নিচের এডিটরে একই roads টেবিলে তিনটিই চালিয়ে দেখুন। সতর্কতা: এই এডিটরগুলোর থামার শর্ত মুছে চালালে কোয়েরি কখনো শেষ হবে না, আর ব্রাউজারের ট্যাবটি আটকে যেতে পারে — SQLite নিজে থেকে recursion থামায় না।

-- ১. UNION: হুবহু একই সারি আবার এলে বাদ — শুধু শহর রাখলে চক্র থামে
WITH RECURSIVE reach(city) AS (
  SELECT 'Dhaka'
  UNION
  SELECT r.dst FROM reach JOIN roads r ON r.src = reach.city
)
SELECT city FROM reach;

-- ২. depth কলাম: পাহারা নেই, শুধু ৬ ধাপে থামা — সারি কত দ্রুত বাড়ে?
WITH RECURSIVE walk(city, hops) AS (
  SELECT 'Dhaka', 0
  UNION ALL
  SELECT r.dst, w.hops + 1 FROM walk w JOIN roads r ON r.src = w.city
  WHERE w.hops < 6
)
SELECT hops, COUNT(*) AS n_rows FROM walk GROUP BY hops;

-- ৩. LIMIT: থামার শর্তই নেই, কিন্তু ৫টি সারির পর থামে (SQLite)
WITH RECURSIVE forever(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM forever LIMIT 5)
SELECT n FROM forever;

DBMS-ভেদে নিয়ম

WITH RECURSIVE trip(city, hops) AS (
  SELECT 'Dhaka', 0
  UNION ALL
  SELECT r.dst, t.hops + 1 FROM trip t JOIN roads r ON r.src = t.city
) CYCLE city SET is_cycle USING path      -- path কলাম PostgreSQL নিজে বানায়
SELECT city, hops, path FROM trip WHERE NOT is_cycle;

SET SESSION cte_max_recursion_depth = 5000;   -- ডিফল্ট 1000

WITH RECURSIVE chain (id, path) AS (
  SELECT instructor_id, CAST(name AS CHAR(500))  -- anchor-এর type-ই পুরো কলামের type
  FROM instructors WHERE mentor_id IS NULL
  UNION ALL
  SELECT i.instructor_id, CONCAT(c.path, ' > ', i.name)
  FROM instructors i JOIN chain c ON i.mentor_id = c.id
)
SELECT * FROM chain;
-- ডিফল্ট সীমায় (1000) পেরোলে: Recursive query aborted after 1001 iterations ...

WITH chain (id, lvl) AS (               -- RECURSIVE শব্দ নেই
  SELECT instructor_id, 1 FROM instructors WHERE mentor_id IS NULL
  UNION ALL
  SELECT i.instructor_id, c.lvl + 1
  FROM instructors i JOIN chain c ON i.mentor_id = c.id
)
SELECT * FROM chain
OPTION (MAXRECURSION 200);              -- ডিফল্ট 100, 0 = সীমাহীন

৯ · পারফরম্যান্স আর ইতিহাস

Recursive CTE-র খরচ বুঝতে লুপটির কথা ভাবুন। প্রতিটি ধাপে working table-এর সারিগুলো মূল টেবিলের সাথে join হয়। hierarchy-তে মোট কাজ মোটামুটি ধাপের সংখ্যা × প্রতি ধাপের join-এর খরচ। join-এর কলামে (mentor_id, parent_id, roads.src) index থাকলে প্রতিটি সারির সন্তান খুঁজতে পুরো টেবিল পড়তে হয় না — B+ tree-তে O(log n) খোঁজ, তারপর মিল-পাওয়া সারিগুলো (পর্ব ৪০)। index না থাকলে প্রতিটি ধাপ একটি পুরো scan, আর d স্তরের গাছে খরচ d × n. foreign key কলামে অনেক DBMS নিজে থেকে index বানায় না (PostgreSQL আর SQLite বানায় না), তাই hierarchy-র কলামে index নিজে দিন।

• পথ-স্ট্রিং বাড়ে: d গভীরতার প্রতিটি সারিতে path-এর দৈর্ঘ্য d-এর সমানুপাতিক, তাই n সারির ফলে মেমরি O(n × d).
• Graph-এ পথের বিস্ফোরণ: visited path চক্র ঠেকায়, কিন্তু প্রতিটি সারি শুধু নিজের পথ মনে রাখে। ঘন graph-এ চক্রহীন পথের সংখ্যা শহরের সংখ্যার সাথে exponential হারে বাড়তে পারে। শুধু “কোথায় পৌঁছানো যায়” চাইলে UNION আর শুধু city কলাম রাখুন।
• বারবার একই প্রশ্ন: প্রতিদিন হাজারবার “এই শ্রেণির সব উপশ্রেণি” লাগলে প্রতিবার recursion না চালিয়ে closure table (প্রতিটি পূর্বসূরি–উত্তরসূরি জোড়ার একটি সারি), materialized path (যেমন '1/3/4', PostgreSQL-এর ltree extension) বা nested set মডেল ভাবুন — পড়া দ্রুত, লেখা জটিল (পর্ব ৩৮-এর denormalization-এর মতো দর-কষাকষি)।

SELECT LEVEL, name,
       SYS_CONNECT_BY_PATH(name, ' > ') AS path   -- ' > Dr. Anisur Rahman > Shahana Parvin'
FROM instructors
START WITH mentor_id IS NULL                      -- anchor
CONNECT BY PRIOR instructor_id = mentor_id        -- recursive member-এর join
ORDER SIBLINGS BY name;

CONNECT BY-তে LEVEL হলো স্তর, PRIOR মানে “আগের স্তরের সারি”, আর চক্র থাকলে CONNECT BY NOCYCLE লিখে CONNECT_BY_ISCYCLE দিয়ে চক্রের সারি চেনা যায়। এটি সংক্ষিপ্ত, কিন্তু শুধু Oracle-এ চলে (এবং আংশিকভাবে কয়েকটি Oracle-সামঞ্জস্যপূর্ণ ডেটাবেসে)। নতুন কোড লিখলে standard WITH RECURSIVE বেছে নিন, যাতে অন্য DBMS-এ সরাতে সমস্যা না হয়।

১০ · AI-এর যুগে CTE আর recursive query

AI-কে “সব উপশ্রেণি দাও” বা “mentor-শৃঙ্খল দেখাও” বললে সে সাধারণত দ্রুত একটি recursive CTE লেখে, আর ছোট ডেটায় সেটি চলেও। কিন্তু recursive কোয়েরির ভুলগুলো বেশিরভাগ ছোট নমুনায় দেখা দেয় না — দেখা দেয় চক্র এলে, গভীরতা বাড়লে বা অন্য DBMS-এ সরালে:

AI-এর লেখা recursive কোয়েরি হাতে পেলে — যাচাইয়ের চেকলিস্ট

• anchor আলাদা চালিয়ে দেখেছি, শুরুর সারিগুলো ঠিক কি না
• দুই-তিন ধাপ হাতে trace করে working table মিলিয়েছি
• পরীক্ষার ডেটায় একটি চক্র রেখে দেখেছি কোয়েরি থামে
• UNION না UNION ALL — duplicate মোছা এখানে কাম্য কি না ভেবেছি
• ফলের সারি-সংখ্যা জানা উত্তরের সাথে মিলিয়েছি (যেমন উপশ্রেণির মোট সংখ্যা)
• লক্ষ্য DBMS-এ চালিয়েছি, আর join-কলামের index EXPLAIN-এ দেখেছি