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

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

مساله

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

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

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

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

همانطور که از نمودار فوق همچنین نمودار اولیه پیداست. تعداد بیشترین کاربر همزمان متصل به سیستم (بالاترین ترافیک) 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) باید مجموعه گرا بوده به این معنا که از حلقه، کرسر و چیزهایی شبیه به اینها صرف نظر کنید.

[IMG]file:///C:/Users/m/AppData/Local/Temp/moz-screenshot-3.png[/IMG][IMG]file:///C:/Users/m/AppData/Local/Temp/moz-screenshot-2.png[/IMG]

[IMG]file:///C:/Users/m/AppData/Local/Temp/moz-screenshot-1.png[/IMG][IMG]file:///C:/Users/m/AppData/Local/Temp/moz-screenshot.png[/IMG]

[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. به این مقاله هم میتونید رجوع کنید مخصوصا آخرین راه حل

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

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

  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

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