用过程语言实现group by cube的代码挑战赛

newkid

主要就是AGG的开销。

再来一版，层层叠加：

DECLARE
   TYPE t_num IS TABLE OF NUMBER INDEX BY VARCHAR2(42);
   lv_rownum t_num;
   TYPE t_row IS TABLE OF yourcube%ROWTYPE;
   lv_result t_row := t_row();
      
   cursor c is SELECT * FROM T;
   
   TYPE t_row2 IS TABLE OF c%ROWTYPE;
   lv_row t_row2;
   lv_cnt NUMBER;
   lv_cnt2 NUMBER;
   PROCEDURE agg (p_c1 IN NUMBER,p_c2 IN NUMBER,p_c3 IN NUMBER, p_c4 IN NUMBER, p_v IN NUMBER, p_c IN NUMBER, p_gid IN NUMBER)
   IS
      lv_idx NUMBER;
      lv_key VARCHAR2(42) := LPAD(NVL(TO_CHAR(p_c1),' '),10)||LPAD(NVL(TO_CHAR(p_c2),' '),10)||LPAD(NVL(TO_CHAR(p_c3),' '),10)||LPAD(NVL(TO_CHAR(p_c4),' '),10)||LPAD(p_gid,2);
   BEGIN
       BEGIN
          lv_idx := lv_rownum(lv_key);
          IF p_v IS NOT NULL THEN
             lv_result(lv_idx).sv := NVL(lv_result(lv_idx).sv,0) + p_v;
          END IF;

       EXCEPTION
          WHEN NO_DATA_FOUND THEN
               lv_idx := lv_rownum.COUNT+1;
               IF lv_idx>lv_result.COUNT THEN
                  lv_result.EXTEND(10000);
               END IF;
               lv_rownum(lv_key) := lv_idx;
               lv_result(lv_idx).c1 := p_c1;
               lv_result(lv_idx).c2 := p_c2;
               lv_result(lv_idx).c3 := p_c3;
               lv_result(lv_idx).c4 := p_c4;
               lv_result(lv_idx).sv := p_v;
               lv_result(lv_idx).gid := p_gid;
               lv_result(lv_idx).cv := 0;
       END;
       lv_result(lv_idx).cv := lv_result(lv_idx).cv + p_c;
      
   END agg;
BEGIN
    OPEN c;
    LOOP
        FETCH c BULK COLLECT INTO lv_row LIMIT 1000;
        FOR I IN 1..lv_row.COUNT LOOP
            agg(lv_row(I).c1,lv_row(I).c2,lv_row(I).c3,lv_row(I).c4,lv_row(I).v,CASE WHEN lv_row(I).v IS NULL THEN 0 ELSE 1 END,0);
        END LOOP;
        EXIT WHEN C%NOTFOUND;
    END LOOP;
    CLOSE C;
    lv_cnt := lv_rownum.COUNT;
   
    FOR I IN 1..lv_cnt LOOP
            agg(lv_result(I).c1,lv_result(I).c2,lv_result(I).c3,NULL           ,lv_result(I).sv,lv_result(I).cv,1);
            agg(lv_result(I).c1,lv_result(I).c2,NULL           ,lv_result(I).c4,lv_result(I).sv,lv_result(I).cv,2);
            agg(lv_result(I).c1,NULL           ,lv_result(I).c3,lv_result(I).c4,lv_result(I).sv,lv_result(I).cv,4);
            agg(NULL           ,lv_result(I).c2,lv_result(I).c3,lv_result(I).c4,lv_result(I).sv,lv_result(I).cv,8);
    END LOOP;
   
    lv_cnt := lv_cnt +1;
    lv_cnt2 := lv_rownum.COUNT;

    FOR I IN lv_cnt..lv_cnt2 LOOP
        IF lv_result(I).gid = 1 THEN
            agg(lv_result(I).c1,lv_result(I).c2,NULL           ,NULL           ,lv_result(I).sv,lv_result(I).cv,3);
            agg(lv_result(I).c1,NULL           ,lv_result(I).c3,NULL           ,lv_result(I).sv,lv_result(I).cv,5);
            agg(NULL           ,lv_result(I).c2,lv_result(I).c3,NULL           ,lv_result(I).sv,lv_result(I).cv,9);
        ELSIF lv_result(I).gid = 2 THEN
            agg(NULL           ,lv_result(I).c2,NULL           ,lv_result(I).c4,lv_result(I).sv,lv_result(I).cv,10);
        ELSIF lv_result(I).gid = 4 THEN
            agg(lv_result(I).c1,NULL           ,NULL           ,lv_result(I).c4,lv_result(I).sv,lv_result(I).cv,6);
            agg(NULL           ,NULL           ,lv_result(I).c3,lv_result(I).c4,lv_result(I).sv,lv_result(I).cv,12);
        END IF;
    END LOOP;

    lv_cnt := lv_cnt2 +1;
    lv_cnt2 := lv_rownum.COUNT;

    FOR I IN lv_cnt..lv_cnt2 LOOP
        IF lv_result(I).gid = 3 THEN
            agg(lv_result(I).c1,NULL           ,NULL           ,NULL           ,lv_result(I).sv,lv_result(I).cv,7);
            agg(NULL           ,lv_result(I).c2,NULL           ,NULL           ,lv_result(I).sv,lv_result(I).cv,11);
            agg(NULL           ,NULL           ,NULL           ,NULL           ,lv_result(I).sv,lv_result(I).cv,15);
        ELSIF lv_result(I).gid = 5 THEN
            agg(NULL           ,NULL           ,lv_result(I).c3,NULL           ,lv_result(I).sv,lv_result(I).cv,13);
        ELSIF lv_result(I).gid = 6 THEN
            agg(NULL           ,NULL           ,NULL           ,lv_result(I).c4,lv_result(I).sv,lv_result(I).cv,14);
        END IF;
    END LOOP;
   
    FORALL I IN 1..lv_rownum.COUNT
        INSERT INTO yourcube VALUES lv_result(i);
END;
/

PL/SQL procedure successfully completed.

Elapsed: 00:00:23.12




[ 本帖最后由 newkid 于 2010-2-24 06:35 编辑 ]

newkid

用GROUP BY CUBE生成TCUBE是9秒多。
我偷偷把我的游标改成cursor c is SELECT C1,C2,C3,C4,SUM(V) SV,COUNT(V) CV FROM T GROUP BY c1,c2,c3,c4;
结果13秒就完成了。

〇〇

我把11楼
lv_key VARCHAR2(42) := LPAD(NVL(TO_CHAR(p_c1),' '),10)||LPAD(NVL(TO_CHAR(p_c2),' '),10)||LPAD(NVL(TO_CHAR(p_c3),' '),10)||LPAD(NVL(TO_CHAR(p_c4),' '),10)||LPAD(p_gid,2);
改成
lv_key VARCHAR2(42) := LPAD(NVL(TO_CHAR(p_c1),' '),1)||LPAD(NVL(TO_CHAR(p_c2),' '),1)||LPAD(NVL(TO_CHAR(p_c3),' '),2)||LPAD(NVL(TO_CHAR(p_c4),' '),3)||LPAD(p_gid,2);
从
25.08 减少到 21.71

改成
lv_key VARCHAR2(9) := NVL(TO_CHAR(p_c1),' ')||NVL(TO_CHAR(p_c2),' ')||LPAD(NVL(TO_CHAR(p_c3),' '),2)||LPAD(NVL(TO_CHAR(p_c4),' '),3)||LPAD(p_gid,2);

减少到 19.70
改成（我的数据恰好都在0-126之间）
lv_key VARCHAR2(5) := chr(NVL(p_c1,127))||chr(NVL(p_c2,127))||chr(NVL(p_c3,127))||chr(NVL(p_c4,127))||chr(p_gid);减少到 14.72

又把agg里的WHEN NO_DATA_FOUND THEN异常处理改为if lv_rownum.exists(lv_key) then
没有变化
在aix 4.4G cpu 上
group by cube 7.75秒，11楼plsql反而26.06比pc服务器还慢,不理解

[ 本帖最后由 〇〇 于 2010-2-24 15:20 编辑 ]

〇〇

不知道这个
http://download.oracle.com/otn/java/olap/awm112010_standalone.zip
建立cube是什么算法？

yulihua49

原帖由 〇〇 于 2010-2-24 09:34 发表
不知道这个
http://download.oracle.com/otn/java/olap/awm112010_standalone.zip
建立cube是什么算法？

你把那个C程序试一下如何？结果对否？速度如何？

〇〇

你那个C程序需要改写才能适合这道题，我没看太懂，改不出来，请您改改

〇〇

我分别测试各层，第一层9秒，第1+2层13.52秒，后面的几乎不花时间

有趣的是，同样对第一层扫描
agg(lv_result(I).c1,lv_result(I).c2,lv_result(I).c3,NULL           ,lv_result(I).sv,lv_result(I).cv,1);
比
agg(NULL           ,lv_result(I).c2,lv_result(I).c3,lv_result(I).c4,lv_result(I).sv,lv_result(I).cv,8);
快多了
看来还跟列的取值范围有关。

[ 本帖最后由 〇〇 于 2010-2-24 15:31 编辑 ]

yulihua49

原帖由 〇〇 于 2010-2-24 15:22 发表
你那个C程序需要改写才能适合这道题，我没看太懂，改不出来，请您改改

我试了，是group by cube快。
用的我的那个tjrb，7552个记录：
SELECT unit,tabname,flg,count(*) count,sum(dat1) s,avg(dat1) ag FROM TICKET.tjrb GROUP BY CUBE (unit,tabname,flg)
18ms，
树group，70ms
没有null的，二者结果完全相同。共归并出552项

1. 
   
2. main(int argc,char **argv)
   
3. {
   
4. cube_stu cube;
   
5. TJRB_stu tjrb;
   
6. DAU tjrb_DAU,cube_DAU;
   
7. T_SQL_Connect SQL_Connect;
   
8. int ret,num=0;
   
9. char stmt[4096];
   
10. INT64 now;
    
11. T_PkgType tj_tpl[5];
    
12. struct t_node node;
    
13. T_Tree *root=0;
    
14. 
    
15.         if(argc>1) ret=envcfg(argv[1]);
    
16.         ret=db_open(&SQL_Connect);
    
17.         if(ret) {
    
18.                 printf("%s,dbopen error\n",argv[0]);
    
19.                 return 1;
    
20.         }
    
21.         patt_copy(tj_tpl,TJRB_tpl,"unit,tabname,flg,dat1");
    
22.         DAU_init(&tjrb_DAU,&SQL_Connect,0,&tjrb,tj_tpl);
    
23. //测试树group
    
24.         node.num=#
    
25.         now=now_usec();
    
26.         *stmt=0;
    
27.         ret=DAU_prepare(&tjrb_DAU,stmt);
    
28.         ShowLog(5,"%s:stmt=%s",__FUNCTION__,stmt);
    
29.         if(ret!=0) {
    
30.                 printf("%s,err=%d,%s\n",stmt,
    
31.                         SQL_Connect.Errno,
    
32.                         SQL_Connect.ErrMsg);
    
33.         } else {
    
34.                 while(!DAU_next(&tjrb_DAU)) {
    
35.                         node.count=1;
    
36.                         node.s=tjrb.dat1;
    
37.                         *node.unit=0;
    
38.                         *node.tabname=0;
    
39.                         node.flg=SHORTNULL;
    
40.                         root=BB_Tree_Add(root,&node,sizeof(node),cmp,add_dup); //000
    
41.                         node.flg=tjrb.flg;
    
42.                         root=BB_Tree_Add(root,&node,sizeof(node),cmp,add_dup); //001
    
43.                         strcpy(node.tabname,tjrb.tabname);
    
44.                         root=BB_Tree_Add(root,&node,sizeof(node),cmp,add_dup); //011
    
45.                         node.flg=SHORTNULL;
    
46.                         root=BB_Tree_Add(root,&node,sizeof(node),cmp,add_dup); //010
    
47.                         strcpy(node.unit,tjrb.unit);
    
48.                         root=BB_Tree_Add(root,&node,sizeof(node),cmp,add_dup); //110
    
49.                         node.flg=tjrb.flg;
    
50.                         root=BB_Tree_Add(root,&node,sizeof(node),cmp,add_dup); //111
    
51.                         *node.tabname=0;
    
52.                         root=BB_Tree_Add(root,&node,sizeof(node),cmp,add_dup); //101
    
53.                         node.flg=SHORTNULL;
    
54.                         root=BB_Tree_Add(root,&node,sizeof(node),cmp,add_dup); //100
    
55.                 }
    
56.                 if(root) {
    
57.                         BB_Tree_Scan(root,avg);
    
58.                         BB_Tree_Scan(root,print_node);
    
59.                         BB_Tree_Free(&root,0);
    
60.                 }
    
61.                 printf("num=%d,TIMEVAL=%lld\n",num,now_usec()-now);
    
62.         }
    
63.         DAU_free(&tjrb_DAU);
    
64. //测试CUBE
    
65.         num=0;
    
66.         DAU_init(&cube_DAU,&SQL_Connect,0,&cube,cube_tpl);
    
67.         now=now_usec();
    
68.         strcpy(stmt,"GROUP BY CUBE (unit,tabname,flg)");
    
69.         ret=DAU_prepare(&cube_DAU,stmt);
    
70.         ShowLog(5,"%s:stmt=%s",__FUNCTION__,stmt);
    
71.         if(ret!=0) {
    
72.                 printf("%s,err=%d,%s\n",stmt,
    
73.                         SQL_Connect.Errno,
    
74.                         SQL_Connect.ErrMsg);
    
75.         } else {
    
76.                 while(!DAU_next(&cube_DAU)) {
    
77.                         num++;
    
78.                         DAU_pack(&cube_DAU,stmt);
    
79.                         printf("%s\n",stmt);
    
80.                 }
    
81.         }
    
82.         printf("num=%d,TIMEVAL=%lld\n",num,now_usec()-now);
    
83. 
    
84.         DAU_free(&cube_DAU);
    
85.         ___SQL_CloseDatabase__(&SQL_Connect);
    
86.         return 0;
    
87. }
    
88. //附cube模板:
    
89. T_PkgType cube_tpl[]={
    
90.         {CH_CHAR,9,"unit",0,-1},
    
91.         {CH_CHAR,9,"tabname"},
    
92.         {CH_SHORT,sizeof(short),"flg"},
    
93.         {CH_INT,sizeof(int),"count(*) count"},
    
94.         {CH_INT64,sizeof(INT64),"sum(dat1) s"},
    
95.         {CH_DOUBLE,sizeof(double),"avg(dat1) ag","%.2lf"},
    
96.         {-1,0,"tjrb","tjdate|unit|tabname|flg|"}
    
97. };
    
98. 
    
99. extern T_PkgType cube_tpl[];
    
100. typedef struct {
     
101.         char unit[9];
     
102.         char tabname[9];
     
103.         short flg;
     
104.         int count;
     
105.         INT64 s;
     
106.         double ag;
     
107. } cube_stu;
     
108. 
     
109. 
     

复制代码

[ 本帖最后由 yulihua49 于 2010-2-24 17:15 编辑 ]

〇〇

1. /* compiled by cl of vc2003*/
   
2. #include <time.h>
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. #include <map>
   
6. #include <iostream>
   
7. using namespace std;
   
8. struct ltstr
   
9. {
   
10.   bool operator()(const char* s1, const char* s2) const
    
11.   {
    
12.     return strcmp(s1, s2) < 0;
    
13.   }
    
14. };
    
15. struct ltint
    
16. {
    
17.   bool operator()(const int s1, const int s2) const
    
18.   {
    
19.     return (s1<s2) ;
    
20.   }
    
21. };
    
22. int main()
    
23. {
    
24. char* c1=(char*)malloc(1E6L);
    
25. char* c2=(char*)malloc(1E6L);
    
26. char* c3=(char*)malloc(1E6L);
    
27. char* c4=(char*)malloc(1E6L);
    
28. int*  v1=(int* )malloc(4E6L);
    
29. __int64* v2;//store sum(v1);
    
30. long t=clock();
    
31. for (int i=0;i<1E6L;i++)
    
32. {
    
33.         int j=i+1;
    
34.         c1[i]=j%4;
    
35.         c2[i]=j%5;
    
36.         c3[i]=j%67;
    
37.         c4[i]=(j%13?j%113:127);
    
38.         v1[i]=j;
    
39. }
    
40. 
    
41. 
    
42. map<const int, int, ltint> key_recn;
    
43. int c=0;
    
44. for (int i=0;i<1E6L;i++)
    
45. {
    
46.         int key=(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i];
    
47.         //printf("key=%d\n",key);
    
48.         if((key_recn.find(key))== key_recn.end())
    
49.                 key_recn[key]=c++;
    
50. }
    
51. 
    
52. 
    
53. int *C=(int*)malloc(c*4);//store count(c1)
    
54. int *k=(int*)malloc(c*4);//store key
    
55. 
    
56. v2=(__int64*)malloc(c*8);
    
57. /*
    
58. memset(C,0,c*4); //need?
    
59. memset(v2,0,c*8);
    
60. */
    
61. 
    
62. for (int i=0;i<1E6L;i++)
    
63. {
    
64. int recn=key_recn[(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i]];
    
65. k[recn]=(c1[i]<<24)+(c2[i]<<16)+(c3[i]<<8)+c4[i];
    
66. C[recn]++;
    
67. v2[recn]=v2[recn]+v1[i];
    
68. 
    
69. }
    
70. int d=
    
71. printf("%dms,recn=%d,c1=%d,c2=%d,c3=%d,c4=%d,count=%d,sum=%ld",clock()-t,c,
    
72. (k[c-1]>>24),((k[c-1]>>16)&255),((k[c-1]>>8)&255),(k[c-1]&255),C[c-1],v2[c-1]);
    
73. 
    
74. free(c1);
    
75. free(c2);
    
76. free(c3);
    
77. free(c4);
    
78. free(v1);
    
79. free(v2);
    
80. free(C);
    
81. free(k);
    
82. return 0;
    
83. 
    
84. }

复制代码

输出
D:\>map
1250ms,recn=152760,c1=3,c2=1,c3=58,c4=104,count=5,sum=3028355

验证
SQL> select count(*) from tcube where gid=0;

  COUNT(*)
----------
    152760


         
         
SQL> select * from tcube where gid=0 and c1=3 and c2=1 and c3=58 and c4=104;

        C1         C2         C3         C4         SV         CV        GID
---------- ---------- ---------- ---------- ---------- ---------- ----------
         3          1         58        104    3028355          5          0

〇〇

照搬newkid的思路
19楼用cl /02 编译输出
D:\>cl /O2 map.cpp /EHsc
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86
Copyright (C) Microsoft Corporation 1984-2002. All rights reserved.

map.cpp
Microsoft (R) Incremental Linker Version 7.10.3077
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:map.exe
map.obj

D:\>map
421ms,recn=152760,c1=3,c2=1,c3=58,c4=104,count=5,sum=3028355      

生成第一层的时间，不包括从数据库读的时间