سومین چالش SQL (بیشترین کاربر همزمان متصل)

[محمد سلیم آبادی]

مساله

هدف ما بدست آوردن بیشترین تعداد کاربر همزمان متصل به سیستم (در یک لحظه) است. با در نظر گرفتن محدودیت و شرایط خاص مورد اشاره در انتهای مساله که باید پاسخ داشته باشد.
به تصویر زیر دقت کنید:



http://www.30sharp.com/Contents/313/ch01.png


این تصور بازه های زمانی که کاربر به سیستم متصل بوده را به نمایش گذاشته است. این ورود و خروج مرتبط به 24 ساعت یک روز هست. البته برای ساده سازی مساله در اینجا از اعداد 1تا24 به جای تاریخ و زمان استفاده شده است.

اولین اتصال به سیستم در زمان 1 صورت گرفت و تا زمان 15 ادامه داشته است. در این بین 7 اتصال دیگر به سیستم رخ داده است.
در زمان 1 تعداد کاربران همزمان متصل به سیستم 1 نفر است. در زمان 2 دو نفر، در زمان 5 چهار نفر، در زمان 21 نیز هیچ کاربر متصلی وجود ندارد.

تعداد کاربران متصل به سایت در زمان های مختلف در نمودار زیر دیده میشود:

http://www.30sharp.com/Contents/313/ch02.png

همانطور که از نمودار فوق همچنین نمودار اولیه پیداست. تعداد بیشترین کاربر همزمان متصل به سیستم (بالاترین ترافیک) 4 است. کار شما پیدا کردن این عدد است.
جدولی که وظیفه ذخیره داده ها را به عهده گرفته همراه با داده های نمونه برای بدست آوردن خروجی در زیر وجود دارد:


CREATE TABLE Logining
(nbr INTEGER IDENTITY NOT NULL PRIMARY KEY,
log_in INT NOT NULL,
log_out INT NOT NULL,
CHECK (log_in < log_out),
CHECK (log_in BETWEEN 1 AND 24 AND log_out BETWEEN 1 AND 24));

INSERT Logining(log_in, log_out) VALUES
(1, 15), (2, 6), (3, 6), (4, 5), (7, 9), (8, 12), (10, 12), (12, 13), (17, 20);

راه حل پیشنهادی برای حل مساله نباید نیازمند به جدول کمکی اعداد باشد. و برای هر تعداد کاربر همزمان متصل مناسب باشد (منطور از جدول می تواند ویو، CTE، TVF یا derived table باشد). روش (query) باید مجموعه گرا بوده به این معنا که از حلقه، کرسر و چیزهایی شبیه به اینها صرف نظر کنید.




file:///C:/Users/m/AppData/Local/Temp/moz-screenshot-3.pngfile:///C:/Users/m/AppData/Local/Temp/moz-screenshot-2.png
file:///C:/Users/m/AppData/Local/Temp/moz-screenshot-1.pngfile:///C:/Users/m/AppData/Local/Temp/moz-screenshot.png

[behrouzlo]

/* behrouzlo 126 chars */
Select Max(cnt)
From ( Select ( Select Count(*)
From Logining L2
Where L2.Log_in <= L1.Log_in
And L2.log_out >= L1.Log_in
) cnt
From Logining L1
) List

[محمد سلیم آبادی]

تشکر از پاسختون. روش بسیار خوبی هست (عالیه!). از لحاظ منطقی هم بنظر میرسه که مساله رو بطور کامل حل میکند. (هنوز کامل بررسیش نکردم)
لطفا در کنار راه حلتون توضیحی هم راجبش بدین. که چطور مساله رو حل میکنه و منطقش چیه. و اگر نکات فنی راجب عملکردش دارین برامون بگین، مثلا تحلیل plan.
و همچنین اگر index مناسبی برای کوئریتان پیشنهاد دارین می تونید پست کنید.

راه حلتون رو از لحاظ اینکه چند بار جدول رو scan میکنه بررسی کردم. که نتیجش این شد (10 بار خواندن کل جدول از روی دیسک - 20 بارم خواندن جدول از روی حافظه اصلی)

set statistics io on
/* behrouzlo 126 chars */
Select Max(cnt)
From ( Select ( Select Count(*)
From Logining L2
Where L2.Log_in <= L1.Log_in
And L2.log_out >= L1.Log_in
) cnt
From Logining L1
) List
set statistics io off

/*
Table 'Logining'. Scan count 10, logical reads 20
*/


همچنین اگر از APPLY بجای scalar correlated subquery که در ماده ی select وجود داره استفاده کنید کدتون کوتاهتر و خواناتر هم خواهد شد:

--APPLY version 119 chars
select max(c)
from logining l1
cross apply
(select count(*)
from logining l2
where L2.Log_in <= L1.Log_in
And L2.log_out >= L1.Log_in) d(c)

همانطور که قطعا میدونید نیاز به دادن نام مستعار به جدول داخلی نداریم. بیشتر اینکار رو برای افزایش خوانایی و تسریع در عیب یابی (و حفظ استیل کد) انجام میدیم. پس با حذف این کاراکتر های غیر ضروری داریم:

--Apply version: 109 chars
select max(c)
from logining l1
cross apply
(select count(*) c
from logining
where Log_in <= L1.Log_in
And log_out >= L1.Log_in) d

بازم ممنونم از اینکه در بحث شرکت کردید.

[محمد سلیم آبادی]

اجازه بدین 2 مساله ی کوچیک مرتبط رو مطرح کنم. اولی رو 3.2 و دومی رو 3.3 نام گذاری میکنم.
مساله 3.2 (زوج کاربران همزمان متصل همراه با تعداد برخورد)
ما در کنار ورود و خروج ها کد کاربر هم درج می کنیم. هدف پیدا کردن زوج کاربرها همراه با تعداد برخورد (به معنای همزمان آنلاین بودنش هست) می باشد.
خروجی ما با داده های زیر:

declare @sample table
(u_nbr int not null,
i int not null,
j int not null,
check (i<=j));

insert @sample values
(1,1,5),
(2,2,2),
(2,3,3),
(2,6,10),
(1,7,7),
(1,8,8),
(3,11,16),
(1,12,12),
(2,13,15),
(1,14,18),
(4,17,17);

به این شکل است:

u_nbr u_nbr cnt
----------- ----------- -----------
1 2 5
1 3 2
2 3 1
1 4 1

مساله 3.3 (بازه ای که بیشترین ترافیک رو داشته)
هدف پیدا کردن شروع و پایان زمانی است که بیشترین کاربر به سیستم متصل بوده اند.
جدول و داده ها دقیقا همون چیزی هست که در پست اولی ارسال شده.
فقط نتیجه ی مورد نظرمون این هست:

starting ending cnt
-------------------- -------------------- -----------
4 5 4
12 12 4

شما باید از جدول اعداد برای حل این مساله استفاده کنید.

[Reza_Yarahmadi]

مساله 3.2 (زوج کاربران همزمان متصل همراه با تعداد برخورد)
Select
S1.u_nbr,
S2.u_nbr,
cnt = COUNT(*)
From
@Sample S1, @Sample S2
Where
S1.u_nbr < S2.u_nbr
AND(
(S1.i >= S2.i AND S1.i <= S2.j)
OR
(S2.i >= S1.i AND S2.i <= S1.j))
Group By S1.u_nbr, S2.u_nbr
Order By S1.u_nbr, S2.u_nbr

[محمد سلیم آبادی]

راهنمایی برای حل مساله 3.3
شما باید از قبل یک جدولی تولید کرده باشید که دارای یک ستون با مقادیر 1 تا 24 باشد (حد اقل) سپس توسط اون تعداد کاربر آنلاین در هر ساعت رو توسط کوئری شبیه به زیر تولید میکنید:

select n, count(*) cnt
from Nbrs N join logining l
on n between l.log_in and l.log_out
--and n between 1 and 24
group by n
/*
n cnt
-------------------- -----------
1 1
2 2
3 3
4 4
5 4
6 3
7 2
8 3
9 3
10 3
11 3
12 4
13 2
14 1
15 1
17 1
18 1
19 1
20 1

(19 row(s) affected)
*/

سپس نیاز هست که سطرهایی که بیشترین Count رو دارن انتخاب بشن یعنی اینها:

;with c as (select n, count(*) cnt
from Nbrs N join logining l
on n between l.log_in and l.log_out
--and n between 1 and 24
group by n)

select *
from c
where cnt = (select MAX(cnt) from c)
/*
n cnt
-------------------- -----------
4 4
5 4
12 4

(3 row(s) affected)
*/
حالا تنها مساله ای که باقی می مونه اینه که سطرهایی که مقدار ستون n آنها بطور sequence هست مثل 4و5 در یک گروه در نظر گرفته بشن. سپس با کمک توابع min و max بازه بدست میاد.
این مشکل آخر معروف هست به Region یا Islands. به این مقاله (http://www.30sharp.com/article/13/241/11/%d8%ac%d8%b2%db%8c%d8%b1%d9%87-%d9%87%d8%a7-islands.aspx) هم میتونید رجوع کنید مخصوصا آخرین راه حل

[محمد سلیم آبادی]

متاسفانه بازم با اینکه جواب رو بطور غیر مستقیم دادم. کسی حاضر نشد که اونو ارسال کنه.


with c as(
select n, count(*) cnt
from Nbrs N join logining l
on n between l.log_in and l.log_out
--and n between 1 and 24
group by n)
select min(n) starting, max(n) ending, cnt
from
(
select n,cnt, n-row_number()over(order by n) fct
from c
where cnt = (select max(cnt) from c)
)d
group by fct, cnt

[behrouzlo]

کل لذت حل مساله مربوط به شیوه حل مساله می باشد. وقتی که راه حل به نوع ارائه می شود و یا اشاره به آن می شود لذت حل آن از سر آدم می پره

[behrouzlo]

اینم یک روش دیگه

;With List As (
Select L1.log_in,L.C As Cnt From dbo.Logining L1
Cross Apply (Select Count(*) As C From Logining L2 Where L2.log_in <= L1.log_in And L2.log_out >= L1.log_in) As l
)

Select List.log_in,l.log_out,List.Cnt From List
Cross Apply (Select Min(Logining.log_out) log_out From Logining Where Logining.log_out >= List.log_in) L
Where Cnt = (Select Max(Cnt) From List)

[محمد سلیم آبادی]

اینم یک روش دیگه

;With List As (
Select L1.log_in,L.C As Cnt From dbo.Logining L1
Cross Apply (Select Count(*) As C From Logining L2 Where L2.log_in <= L1.log_in And L2.log_out >= L1.log_in) As l
)

Select List.log_in,l.log_out,List.Cnt From List
Cross Apply (Select Min(Logining.log_out) log_out From Logining Where Logining.log_out >= List.log_in) L
Where Cnt = (Select Max(Cnt) From List)


من کوئریتون رو به شکل زیر در آوردم. دیگه نیازی به CTE نداره. خوانایش افزایش پیدا کرده.
البته زمان کافی ندارم که بیشتر روش کار کنم باید سریع آماده بشم برم بیرون.

Select top 1 with ties L1.log_in, d.log_out, L.C As Cnt
From dbo.Logining L1
Cross Apply (Select Count(*) As C From Logining Where log_in <= L1.log_in And log_out >= L1.log_in) As l
Cross Apply (Select Min(log_out) log_out From Logining Where log_out >= l1.log_in) d
order by cnt desc;

[behrouzlo]

آقا محمد ما منتظر چالش بعدی هستیم

[محمد سلیم آبادی]

الان که فرصت کردم دوباره کوئریتون رو بررسی کنم به این نتیجه رسیدم که شما نیاز به 2 سابکوئری ندارین. یکی کافیه!
اگه این محودیت نبود:
/*Multiple columns are specified in an aggregated expression containing an outer reference.*/

کوئری به این شکل در میومد:

Select top 1 with ties
L1.log_in,
m as log_out,
c As Cnt
From dbo.Logining L1
Cross Apply (Select Count(*) As C ,
min(case when log_out >= l1.log_in then log_out end) as m
From Logining
Where log_in <= L1.log_in And log_out >= L1.log_in
)l
order by cnt desc;

ولی عملا این جواب داد:

/*simpler version*/
Select top 1 with ties
L1.log_in,
m as log_out,
c As Cnt
From dbo.Logining L1
Cross Apply (Select Count(*) As C ,
min(m) as m
From (select case when log_out >= l1.log_in then log_out end m
from Logining
Where log_in <= L1.log_in And log_out >= L1.log_in) As d
)l
order by cnt desc;

با مقایسه این کوئری با کوئری که دوتا cross apply داره نتیجه ی زیر بدست اومد که نشان دهنده بهبود یافتن راه حل از نظر عملکردی هست:

--Two Subquery Version
Table 'Logining'. Scan count 13, logical reads 26
--Simpler Version
Table 'Logining'. Scan count 10, logical reads 20

قابل ذکر هست که این دو با شرایط مساوی (بدون ایندکس) با هم مقایسه شدن