Session重叠问题学习(六)--极致优化

接前文
Session重叠问题学习(二)，这是问题和需求的描述，执行时间90秒
http://blog.itpub.net/29254281/viewspace-2150229/

Session重叠问题学习(三)--优化，一次优化后,执行时间25秒
http://blog.itpub.net/29254281/viewspace-2150259/

Session重叠问题学习(四)--再优化，二次优化后,执行时间10秒
http://blog.itpub.net/29254281/viewspace-2150297/

Session重叠问题学习(五)--最优化，三次优化后,执行时间1.6秒
http://blog.itpub.net/29254281/viewspace-2150339/

周五晚上终于把这个算法初步实现了.
连续加班忙碌了一个星期,终于有点曙光了.
从这个问题的缘起,到目前应该已经优化了快100倍了
但是周末的时候,想想还是不对.
小花狸Session合并算法（对，以后这个算法就叫这个名称了）实现的合并速度应该是非常快的.代价仅仅是扫描一遍记录.
这1.6秒到底用在哪里了？

后来经过反复调试.发现还有两块可以优化改进的地方.
改进后的过程如下:

1. drop procedure p;  
2. DELIMITER $$    
3.     
4. CREATE DEFINER=`root`@`localhost` PROCEDURE `p`()    
5. BEGIN      
6.     declare done int default 0;          
7.     declare v_roomid bigint;      
8.     declare v_time timestamp(6);      
9.     declare v_cur_type smallint;    
10.     
11.     declare v_before_roomid bigint default -1;    
12.     declare v_before_type smallint default -1;    
13.     declare v_before_time timestamp(6) ;    
14.     
15.     declare v_num bigint default 0;    
16.     
17.     
18.     declare cur_test CURSOR for select roomid,type,timepoint from tmp_time_point order by roomid,timepoint,type ;    
19.     DECLARE  CONTINUE HANDLER FOR NOT FOUND  SET done = 1;          
20.     
21.           
22.     drop table if exists t1;      
23.     drop table if exists t2;    
24.     drop table if exists tmp_time_point;      
25.     drop table if exists tmp_result;    
26.     drop table if exists tmp_min_range;    
27.     drop table if exists tmp_s;  
28.     CREATE temporary TABLE `t1` (      
29.       `roomid` int(11) NOT NULL DEFAULT '0',      
30.       `userid` bigint(20) NOT NULL DEFAULT '0',      
31.       `s` timestamp(6),      
32.       `e` timestamp(6),  
33.        primary key(roomid,userid,s,e)  
34.     ) ENGINE=memory;      
35.     
36.    CREATE temporary TABLE `t2` (      
37.       `roomid` int(11) NOT NULL DEFAULT '0',      
38.       `s` timestamp(6),      
39.       `e` timestamp(6)  
40.     ) ENGINE=memory;      
41.     
42.     CREATE temporary TABLE `tmp_min_range` (      
43.       `roomid` int(11) NOT NULL DEFAULT '0',      
44.       `s` timestamp(6),      
45.       `e` timestamp(6),      
46.       primary key(roomid,s,e),  
47.       key(roomid,e)  
48.     ) ENGINE=memory;      
49.     
50.     create temporary table tmp_time_point(      
51.             roomid bigint,      
52.             timepoint timestamp(6),      
53.             type smallint,    
54.             key(roomid,timepoint)      
55.     ) engine=memory;      
56.         
57.     create temporary table tmp_result(      
58.             roomid bigint,      
59.             timepoint timestamp(6),    
60.             c int    
61.     ) engine=memory;      
62.       
63.     create temporary table tmp_s(  
64.         roomid bigint,  
65.         userid bigint,  
66.         s timestamp,  
67.         e timestamp,  
68.         i int  
69.     ) engine=memory;  
70.       
71. SET @A=0;      
72. SET @B=0;      
73.   
74. insert into tmp_s  
75.     SELECT x.roomid,x.userid,s,e,datediff(e,s)+1 i   
76.     FROM     
77.     (    
78.         (    
79.             SELECT @B:=@B+1 AS id,roomid,userid,s      
80.             FROM (      
81.                 SELECT DISTINCT roomid, userid, roomstart AS s          
82.                 FROM u_room_log a          
83.                 WHERE NOT EXISTS (SELECT *          
84.                     FROM u_room_log b          
85.                     WHERE a.roomid = b.roomid          
86.                         AND a.userid = b.userid          
87.                         AND a.roomstart > b.roomstart          
88.                         AND a.roomstart <= b.roomend)    
89.             ) AS p    
90.         ) AS x,      
91.         (    
92.             SELECT @A:=@A+1 AS id,roomid,userid,e      
93.             FROM     
94.             (      
95.                 SELECT DISTINCT roomid, userid, roomend AS e          
96.                 FROM u_room_log a          
97.                 WHERE NOT EXISTS (SELECT *          
98.                     FROM u_room_log b          
99.                     WHERE a.roomid = b.roomid          
100.                         AND a.userid = b.userid          
101.                         AND a.roomend >= b.roomstart          
102.                         AND a.roomend < b.roomend)      
103.             ) AS o    
104.         ) AS y      
105.     )     
106.     WHERE x.id = y.id AND x.roomid = y.roomid AND x.userid = y.userid   ;     
107.   
108. select max(i) into @c from tmp_s;  
109.       
110. insert ignore into t1(roomid,userid,s,e)    
111. select         
112. roomid,  userid,        
113. if(date(s)!=date(e) and id>1,date(s+interval id-1 date(s+interval id-1 date(e) ,e,date_format(s+interval id-1 '%Y-%m-%d 23:59:59')) e        
114. from tmp_s t1 STRAIGHT_JOIN      
115. nums on(nums.id<=t1.i)  
116. where nums.id<=@c  
117.      
118. ;        
119.     
120. insert into t2 (roomid,s,e)    
121. select roomid,    
122. s+interval startnum/1000000 second s,    
123. e-interval endnum/1000000 second e    
124.  from (    
125.     select     
126.     roomid,    
127.     s,e,    
128.     startnum,    
129.     when @eflag=eflag then @rn:=@rn+1 when @eflag:=eflag then @rn else @rn end endnum    
130.     from (    
131.         select * from (    
132.             select when @sflag=sflag then @rn:=@rn+1 when @sflag:=sflag then @rn else @rn end startnum,roomid,s,e,sflag,eflag from    
133.             (    
134.                 select * from     
135.                 (    
136.                     select t1.*,concat('[',roomid,'],',s) sflag,concat('[',roomid,'],',e) eflag from t1 order by roomid ,sflag    
137.                 )a,(select @sflag:='',@rn:=0,@eflag:='') vars    
138.             ) b      
139.         ) bb order by roomid,eflag    
140.     ) c    
141. ) d ;    
142.      
143.     insert into tmp_time_point(roomid,timepoint,type) select roomid,s,1 from t2;    
144.     insert into tmp_time_point(roomid,timepoint,type) select roomid,e,0 from t2;    
145.        
146.     insert ignore into tmp_min_range(roomid,s,e)    
147.                 select   roomid,starttime  starttime, endtime  endtime from (      
148.                     select       
149.                     if(@roomid=roomid,@d,'')  as starttime,@d:=str_to_date(timepoint,'%Y-%m-%d %H:%i:%s.%f'),@roomid:=roomid,p.roomid,str_to_date(timepoint,'%Y-%m-%d %H:%i:%s.%f') endtime      
150.                     from tmp_time_point p,(select @d:='',@roomid:=-1) vars      
151.                     order by roomid,timepoint      
152.                 ) v4 where starttime!='' and date(starttime)=date(endtime);    
153.     
154.     open cur_test;          
155.     repeat          
156.         fetch cur_test into v_roomid,v_cur_type,v_time;          
157.         if done !=1 then        
158.             -- 第一行或者每个房间的第一行    
159.             if v_before_roomid=-1 or v_roomid!=v_before_roomid  then    
160.                 set v_before_roomid:=v_roomid;    
161.                 set v_before_type:=1;    
162.                 set v_before_time:='0000-00-00 00:00:00';    
163.                 set v_num:=0;    
164.             end if;    
165.                 
166.                 
167.             if v_before_type=1  then    
168.              
169.                 set v_num:=v_num+1;    
170.           
171.                 insert into tmp_result(roomid,timepoint,c) values(v_roomid,v_time,v_num);    
172.             end if;    
173.                 
174.             if v_before_type=0 then    
175.                    
176.                 set v_num:=v_num-1;    
177.     
178.                 insert into tmp_result(roomid,timepoint,c) values(v_roomid,v_time,v_num);    
179.             end if;    
180.     
181.             set v_before_roomid:=v_roomid;    
182.             set v_before_type:=v_cur_type;    
183.             set v_before_time:=v_time;    
184.         end if;        
185.     until done end repeat;          
186.     close cur_test;       
187.       
188.     select roomid,date(s) dt,round(second,date_format(s,'%Y-%m-%d %H:%i:%s'),date_format(e,'%Y-%m-%d %H:%i:%s')))/60) ts,max(c)-1 c from (         
189.         select a.roomid,a.s,a.e,r.c,r.timepoint from tmp_result r     
190.         inner join     
191.         tmp_min_range a on( r.timepoint=a.e and r.roomid=a.roomid)    
192.         where     c>2    
193.     ) a group by roomid,date(s);      
194.     
195. END    

第一处改进
    原来同一房间同一用户重叠时间合并,然后再拆分跨天数据，用的是一条SQL
    现在改进如下

1. create temporary table tmp_s(  
2.         roomid bigint,  
3.         userid bigint,  
4.         s timestamp,  
5.         e timestamp,  
6.         i int  
7.     ) engine=memory;  
8.       
9. SET @A=0;      
10. SET @B=0;      
11.   
12. insert into tmp_s  
13.     SELECT x.roomid,x.userid,s,e,datediff(e,s)+1 i   
14.     FROM     
15.     (    
16.         (    
17.             SELECT @B:=@B+1 AS id,roomid,userid,s      
18.             FROM (      
19.                 SELECT DISTINCT roomid, userid, roomstart AS s          
20.                 FROM u_room_log a          
21.                 WHERE NOT EXISTS (SELECT *          
22.                     FROM u_room_log b          
23.                     WHERE a.roomid = b.roomid          
24.                         AND a.userid = b.userid          
25.                         AND a.roomstart > b.roomstart          
26.                         AND a.roomstart <= b.roomend)    
27.             ) AS p    
28.         ) AS x,      
29.         (    
30.             SELECT @A:=@A+1 AS id,roomid,userid,e      
31.             FROM     
32.             (      
33.                 SELECT DISTINCT roomid, userid, roomend AS e          
34.                 FROM u_room_log a          
35.                 WHERE NOT EXISTS (SELECT *          
36.                     FROM u_room_log b          
37.                     WHERE a.roomid = b.roomid          
38.                         AND a.userid = b.userid          
39.                         AND a.roomend >= b.roomstart          
40.                         AND a.roomend < b.roomend)      
41.             ) AS o    
42.         ) AS y      
43.     )     
44.     WHERE x.id = y.id AND x.roomid = y.roomid AND x.userid = y.userid   ;     
45.   
46. select max(i) into @c from tmp_s;  
47.       
48. insert ignore into t1(roomid,userid,s,e)    
49. select         
50. roomid,  userid,        
51. if(date(s)!=date(e) and id>1,date(s+interval id-1 date(s+interval id-1 date(e) ,e,date_format(s+interval id-1 '%Y-%m-%d 23:59:59')) e        
52. from tmp_s t1 STRAIGHT_JOIN      
53. nums on(nums.id<=t1.i)  
54. where nums.id<=@c  
55.      
56. ;        

先把同一房间同一用户的重叠部分合并,然后暂存临时表
记录最大的间隔时间,然后再拆分数据

拆分数据的时候 使用STRAIGHT_JOIN 强制连接顺序.
这样避免因为数字辅助表过大,而导致性能陡然变差.


第二处改进
    原来使用distinct的查询, 都改为在临时表上增加主键.
    然后使用insert ignore into 代替 insert into 
    这样大概优化了300毫秒

经过反复优化之后，执行时间大致稳定在1250毫秒 至 1300 毫秒

各个部分耗时分析如下
填充tmp_s，合并同一房间同一用户的重叠部分，耗时655毫秒
填充t1，拆分跨天的用户数据，耗时62毫秒
填充t2，用户时间段首尾相交或者首尾全部重合的数据拆分，耗时140毫秒
填充tmp_min_range,计算最小间隔范围，耗时156毫秒
小花狸Session合并算法，耗时219毫秒
结果统计展示，耗时47毫秒