اگر جزء اون دسته از افرادی
هستید که
به SQL عشق می ورزید، قطعا و بدون شک
تقسیم رابطه ای را به خاطر خواهید آورد.
تقسیم رابطه (Relational
Division) را به دو دسته ی کلی می توانیم تقسیم کنیم. تقسیم با
باقیمانده (Division with a Remainder) و تقسیم دقیق
(Exact Division). در مقاله ی قبلی به "تقسیم با باقیمانده"
بطور کاملی پرداختم و چهار روش اصلی این مساله را معرفی کردم. و هم
اکنون وقت آن
رسیده است که نوع دوم این تقسیم یعنی "تقسیم دقیق" را بیشتر بشناسیم و ببینیم آیا
راه حل های آن محدود به تعداد انگشتان دست است یا خیر.
آقای Joe Celko
در
این مقاله تنها به معرفی یک راه حل (برای تقسیم دقیق) بسنده کرده اند.
ولی آیا این بهینه ترین و سریع ترین راه حل است؟
چند روز پیش
بعد از مدت طولانی به سایت sqlteam.com
سر زدم و بطور اتفاقی به
لینکی در یک تاپیکی برخورد کردم که به یک پست در یک وبلاگ ارجاع داده شده بود.
بله MVP Peter Larsson سوئدی کمی گرد و خاک بپا کرده بود!
ظاهرا با آقای Joe Celko برای بدست آوردن موثر ترین و بهینه
ترین Query رقابت کرده بودند. ولی من هم بیکار ننشستم و در
طول چند روز بیش از 10 راه حل متنوع، کاربردی و سریع ارسال کردم.
در ادامه صورت مساله را کامل با مثال
شرح خواهم داد و به ارائه راه حل های مختلف و متنوع که توسط آقایان
Peter Larsson،
Joe Celko و
Mohammad
Salimabadi خلق و معرفی شده اند می پردازم. و در انتهای مقاله
عملکرد روشها را (با کمک ابزار ارزیابی SET STATISTICS IO ON)
با یکدیگر مقایسه می کنم.
شرح صورت مساله
ما دو جدول کلی در بحث تقسیم رابطه ای داریم. یک جدول
با نام مقسوم (Dividend) و دیگری با نام مقسوم علیه (Divisor).
ما مقسوم علیه را یک مجموعه (Set) در نظر
می گیریم. ولی اگر عناصر مقسوم علیه معین، محدود و مشخص باشند از روش های متنوع
دیگری نیز مساله قابل حل شدند است که بحث آن در اینجا نمی گنجد.
CREATE TABLE dbo.Dividend
(
group_id INTEGER NOT NULL,
item_name VARCHAR(10) NOT NULL,
PRIMARY KEY (
group_id,
item_name
)
);
INSERT INTO dbo.Dividend
(
group_id,
item_name
)
VALUES (1, 'one'),
(1, 'two'),
(1, 'three'),
(1, 'four'),
(2, 'one'),
(2, 'two'),
(2, 'three'),
(3, 'one'),
(3, 'two');
CREATE TABLE dbo.Divisor
(
item_name VARCHAR(10) NOT NULL PRIMARY KEY
);
INSERT INTO dbo.Divisor
(
item_name
)
VALUES ('one'),
('two'),
('three');
مساله از این قرار است که در جدول
Dividend هر group_id می تواند یک
مجموعه ای از item_name ها را انتخاب کند. بطور مثال گروهی
با شماره ی 1، item_name هایی با نام های one
و two و three و four
را انتخاب کرده است. و گروه 3 نیز دو item
با نام های one و two را انتخاب
کرده است. حالا در جدول Divisor نیز نام یکسری از
item ها وجود دارد. هدف ما انتخاب گروهایی از جدول Dividend
است که تمام دقیقا تمام آیتم های جدول Divisor را
انتخاب کرده اند. نه کمتر و نه بیشتر. در مثال فوق تنها گروه شماره ی 2 دقیقا تمام
item ها را در جدول Dividend در
برگرفته است. و گروه 1 یک Item اضافی دارد و گروه 3 نیز یک
Item کمتر از جدول Divisor دارد.
راه حل ها
ابتدا روش های آقای Joe Celko
را لیست می کنم:
-- Celko 1
SELECT D1.group_id
FROM Dividend AS D1
WHERE D1.item_name IN (SELECT item_name FROM Divisor)
GROUP BY D1.group_id
HAVING COUNT(DISTINCT D1.item_name) = (SELECT COUNT(*) FROM Divisor)
AND COUNT(DISTINCT D1.item_name) = (SELECT COUNT(*) FROM Dividend AS D2 WHERE D2.group_id = D1.group_id)
-- Celko 2
SELECT D1.group_id
FROM Dividend AS D1
WHERE D1.item_name IN (SELECT item_name FROM Divisor)
AND NOT EXISTS (
SELECT *
FROM Dividend AS D2
WHERE D2.group_id = D1.group_id
AND D2.item_name NOT IN (SELECT item_name FROM Divisor)
)
GROUP BY D1.group_id
HAVING COUNT(DISTINCT D1.item_name) = (SELECT COUNT(*) FROM Divisor)
-- Celko 3
SELECT D1.group_id
FROM (
SELECT group_id,
item_name,
COUNT(*) OVER (PARTITION BY group_id) AS cnt
FROM Dividend
) AS D1
WHERE D1.item_name IN (SELECT item_name FROM Divisor)
AND cnt = (SELECT COUNT(*) FROM Divisor)
GROUP BY D1.group_id
HAVING COUNT(D1.cnt) = (SELECT COUNT(*) FROM Divisor)
--Celko 4
;WITH Divisor2
AS (
SELECT group_id,
MIN(CASE WHEN item_name IN (SELECT item_name FROM Divisor) THEN 1 ELSE 0 END) OVER(PARTITION BY group_id) AS single,
SUM(CASE WHEN item_name IN (SELECT item_name FROM Divisor) THEN 1 ELSE 0 END) OVER(PARTITION BY group_id) AS full_basket
FROM Dividend
)
SELECT D.group_id
FROM Dividend AS D,
Divisor2
WHERE D.group_id = Divisor2.group_id
AND Divisor2.single = 1
AND Divisor2.full_basket = (SELECT COUNT(*) FROM Divisor)
GROUP BY D.group_id
--Celko 5
SELECT group_id
FROM Dividend D1
LEFT OUTER JOIN
Divisor D2
ON D1.item_name = D2.item_name
GROUP BY group_id
HAVING COUNT(D1.item_name) = (SELECT COUNT(*) FROM Divisor)
AND COUNT(D2.item_name) = (SELECT COUNT(*) FROM Divisor);
و اکنون روش های MVP Peter Larsson
-- Peso 1
SELECT group_id
FROM (
SELECT t.group_id,
SUM(CASE WHEN t.item_name = n.item_name THEN 1 ELSE 0 END) AS cnt,
COUNT(*) AS Items
FROM dbo.Dividend AS t
CROSS JOIN dbo.Divisor AS n
GROUP BY t.group_id,
t.item_name
) AS d
GROUP BY group_id
HAVING SUM(cnt) = MIN(Items)
AND MIN(cnt) >= 1 -- 1 means no remainder, 0 means remainder
-- Peso v2
SELECT t.group_id
FROM (
SELECT group_id,
COUNT(*) AS cnt
FROM dbo.Dividend
GROUP BY group_id
) AS kc
INNER JOIN (
SELECT COUNT(*) AS cnt
FROM dbo.Divisor
) AS nc ON nc.cnt = kc.cnt
INNER JOIN dbo.Dividend AS t ON t.group_id = kc.group_id
INNER JOIN dbo.Divisor AS n ON n.item_name = t.item_name
GROUP BY t.group_id
HAVING COUNT(*) = MIN(nc.cnt)
حالا نوبت روش های متنوع، پیشرفته و
کاربردی خودم رسیده است:
--msalim 1
;WITH D1(group_id, cnt, min_item, max_item) AS
(SELECT group_id, COUNT(*), MIN(item_name), MAX(item_name)
FROM Dividend
GROUP BY group_id),
D2(cnt, min_item, max_item) AS
(SELECT COUNT(*), MIN(item_name), MAX(item_name)
FROM Divisor)
SELECT group_id
FROM D1 JOIN D2
ON D1.cnt = D2.cnt
AND D1.min_item = D2.min_item
AND D1.max_item = D2.max_item
WHERE D1.cnt = (SELECT COUNT(*)
FROM Dividend D
JOIN Divisor D2
ON D.item_name = D2.item_name
WHERE D1.group_id = D.group_id) ;
--msalim 2
;WITH D AS
(SELECT *, COUNT(*) OVER(PARTITION BY group_id) AS cnt,
MIN(item_name) OVER(PARTITION BY group_id) AS min_item,
MAX(item_name) OVER(PARTITION BY group_id) AS max_item
FROM Dividend)
SELECT group_id
FROM D AS D1
JOIN (SELECT item_name, COUNT(*) OVER() AS cnt,
MIN(item_name) OVER() AS min_item,
MAX(item_name) OVER() AS max_item
FROM Divisor) D2
ON D1.cnt = D2.cnt
AND D1.min_item = D2.min_item
AND D1.max_item = D2.max_item
AND D1.item_name = D2.item_name
GROUP BY group_id
HAVING COUNT(*) = MAX(D1.cnt) ;
--msalim 3
SELECT *
FROM (SELECT DISTINCT group_id
FROM Dividend) D
WHERE NOT EXISTS
(SELECT *
FROM Divisor D1
FULL OUTER JOIN
(SELECT item_name
FROM Dividend
WHERE group_id = D.group_id) D2
ON D1.item_name = D2.item_name
WHERE D1.item_name IS NULL
OR D2.item_name IS NULL) ;
--msalim 4
SELECT *
FROM (SELECT DISTINCT group_id
FROM Dividend) D
WHERE NOT EXISTS
(
SELECT * FROM
(
SELECT item_name
FROM Divisor
UNION ALL
SELECT DISTINCT item_name
FROM Dividend
WHERE group_id = D.group_id
)d
GROUP BY d.item_name
HAVING COUNT(item_name) = 1
) ;
-- msalim 5
SELECT *
FROM (SELECT DISTINCT group_id
FROM Dividend) D
WHERE NOT EXISTS
(
SELECT item_name
FROM Divisor
EXCEPT
SELECT item_name
FROM Dividend
WHERE group_id = D.group_id
)
AND NOT EXISTS
(
SELECT item_name
FROM Dividend
WHERE group_id = D.group_id
EXCEPT
SELECT item_name
FROM Divisor
) ;
-- msalim 6
SELECT group_id
FROM (SELECT group_id, COUNT(*) AS cnt
FROM (SELECT group_id, item_name
FROM Dividend
UNION ALL
SELECT group_id, item_name
FROM (SELECT DISTINCT group_id
FROM Dividend) D
CROSS JOIN
Divisor) D
GROUP BY group_id, item_name
) D
GROUP BY group_id
HAVING MAX(CASE WHEN cnt = 1 THEN 1 ELSE 0 END) = 0 ;
-- msalim 7
SELECT D1.group_id
FROM Dividend AS D1
WHERE D1.item_name IN (SELECT item_name FROM Divisor)
GROUP BY D1.group_id
HAVING COUNT(DISTINCT D1.item_name) = (SELECT COUNT(*) FROM Divisor)
EXCEPT
SELECT group_id
FROM Dividend
WHERE item_name NOT IN
(SELECT item_name
FROM Divisor) ;
-- msalim 8
SELECT D1.group_id
FROM Dividend D1
LEFT OUTER JOIN
Divisor D2
ON D1.item_name = D2.item_name
GROUP BY D1.group_id
HAVING COUNT(D1.item_name) = (SELECT COUNT(*) FROM Divisor)
AND MAX(CASE WHEN D2.item_name IS NULL THEN 1 ELSE 0 END) = 0 ;
-- msalim 9
;WITH groups AS
(SELECT DISTINCT group_id
FROM Dividend),
[A*B] AS
(SELECT *
FROM groups
CROSS JOIN
Divisor)
SELECT group_id
FROM groups
EXCEPT
SELECT group_id
FROM ((SELECT * FROM Dividend
EXCEPT
SELECT * FROM [A*B])
UNION
(SELECT *
FROM [A*B]
EXCEPT
SELECT *
FROM Dividend)
) D ;
-- msalim 10
;WITH groups AS
(SELECT DISTINCT group_id
FROM Dividend)
SELECT group_id
FROM groups
EXCEPT
(
SELECT COALESCE(D1.group_id, D2.group_id)
FROM Dividend D1
FULL OUTER JOIN
(SELECT *
FROM groups
CROSS JOIN
Divisor
) D2
ON D1.group_id = D2.group_id
AND D1.item_name = D2.item_name
WHERE D1.group_id IS NULL
OR D2.group_id IS NULL) ;
-- msalim 11
SELECT d.group_id
FROM (SELECT group_id, COUNT(*), MIN(item_name), MAX(item_name)
FROM Dividend
GROUP BY group_id
)D(group_id, cnt,min_item, max_item)
INNER JOIN
(SELECT COUNT(*) , MIN(item_name), MAX(item_name)
FROM Divisor) dd(cnt,min_item, max_item)
ON d.cnt=dd.cnt
AND d.min_item=dd.min_item
and d.max_item=dd.max_item
EXCEPT
SELECT group_id
FROM Dividend
WHERE item_name NOT IN (SELECT item_name FROM Divisor) ;
این روش (#12) محدودیت هایی دارد. 1.
VARCHAR محدودیت دارد (حتی نوع MAX
آن) 2. با این تکنیک (CASE) سطرهای محدودی را می توانیم
الحاق کنیم.
-- msalim 12
SELECT DD.group_id
FROM (
SELECT group_id,
MAX(CASE WHEN ranking = 1 THEN item_name ELSE '' END) +
MAX(CASE WHEN ranking = 2 THEN ',' + item_name ELSE '' END) +
MAX(CASE WHEN ranking = 3 THEN ',' + item_name ELSE '' END) +
MAX(CASE WHEN ranking = 4 THEN ',' + item_name ELSE '' END) AS concatenating
FROM (
SELECT *, ROW_NUMBER() OVER(PARTITION BY group_id ORDER BY item_name) AS Ranking
FROM Dividend
) AS D
GROUP BY group_id
) AS DD
JOIN
(
SELECT ',' + item_name
FROM Divisor
ORDER BY item_name ASC
FOR XML PATH('')
) AS D(concatenating)
ON DD.concatenating = STUFF(D.concatenating, 1, 1, '') ;
مقایسه عملکرد روشها
یکی از مهمترین فاکتورهای ارزیابی
عملکرد یک Qeury تعداد دفعاتی است که داده ها را از جداول
Scan کرده و می خواند. هرچه تعداد دفعات خواندن داده ها
کمتر باشد سرعت اجرا شدن Query نیز بالاتر است. البته بی شک
برای ارزیابی صحیح و قطعی عملکرد یک query بایستی آزمایش را
روی حد اقل 10 هزار سطر انجام دهیم.
بخش های رنگی تعداد read
خیلی کم تری نسبت به بقیه روشها دارند.
=== Celko 1 ===
Table 'Dividend'. Scan count 3, logical reads 6
Table 'Divisor'. Scan count 2, logical reads 20
=== Celko 2 ===
Table 'Divisor'. Scan count 3, logical reads 32
Table 'Dividend'. Scan count 4, logical reads 8
=== Celko 3 ===
Table 'Divisor'. Scan count 3, logical reads 10
Table 'Worktable'. Scan count 3, logical reads 34
Table 'Dividend'. Scan count 1, logical reads 2
=== Celko 4 ===
Table 'Dividend'. Scan count 2, logical reads 9
Table 'Worktable'. Scan count 3, logical reads 34
Table 'Divisor'. Scan count 1, logical reads 38
=== Celko 5 ===
Table 'Divisor'. Scan count 3, logical reads 23
Table 'Dividend'. Scan count 1, logical reads 2
=== Peso 1 ===
Table 'Divisor'. Scan count 1, logical reads 19
Table 'Dividend'. Scan count 1, logical reads 2
=== Peso 2 ===
Table 'Divisor'. Scan count 1, logical reads 8
Table 'Dividend'. Scan count 2, logical reads 4
=== msalim 1 ===
Table 'Dividend'. Scan count 1, logical reads 8
Table 'Divisor'. Scan count 2, logical reads 4
=== msalim 2 ===
Table 'Worktable'. Scan count 14, logical reads 160
Table 'Divisor'. Scan count 1, logical reads 19
Table 'Dividend'. Scan count 1, logical reads 2
=== msalim 3 ===
Table 'Dividend'. Scan count 4, logical reads 8
Table 'Divisor'. Scan count 1, logical reads 7
=== msalim 4 ===
Table 'Dividend'. Scan count 4, logical reads 8
Table 'Divisor'. Scan count 1, logical reads 7
=== msalim 5 ===
Table 'Divisor'. Scan count 2, logical reads 15
Table 'Dividend'. Scan count 3, logical reads 22
=== msalim 6 ===
Table 'Divisor'. Scan count 1, logical reads 7
Table 'Dividend'. Scan count 2, logical reads 4
=== msalim 7 ===
Table 'Divisor'. Scan count 3, logical reads 28
Table 'Dividend'. Scan count 3, logical reads 6
=== msalim 8 ===
Table 'Divisor'. Scan count 2, logical reads 21
Table 'Dividend'. Scan count 1, logical reads 2
=== msalim 9 ===
Table 'Dividend'. Scan count 12, logical reads 35
Table 'Divisor'. Scan count 3, logical reads 14
=== msalim 10 ===
Table 'Worktable'. Scan count 1, logical reads 6
Table 'Divisor'. Scan count 1, logical reads 7
Table 'Dividend'. Scan count 3, logical reads 6
=== msalim 11 ===
Table 'Divisor'. Scan count 2, logical reads 8
Table 'Dividend'. Scan count 2, logical reads 4
=== msalim 12 ===
Table 'Dividend'. Scan count 1, logical reads 2
Table 'Divisor'. Scan count 1, logical reads 2
ولی اینجا پایان کار نیست. و بنظر می رسد که بهترین روش مخفی باشد
و روزی فرد علاقه مندی آن را معرفی کند.
موفق باشید!