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

〇〇

测试SQL脚本

create table t as select  mod(level,4)c1,mod(level,5)c2,mod(level,67)c3,
mod(case when mod(level,13)>0 then level end ,113)c4, level v from dual connect by level<=1E6

create table tcube as select c1,c2,c3,c4,sum(v)sv,count(v)cv,grouping_id(c1,c2,c3,c4)gid from t group by cube(c1,c2,c3,c4);

create table tcube as select/*+parallel(t,8) */ c1,c2,c3,c4,sum(v)sv,count(v)cv,grouping_id(c1,c2,c3,c4)gid from t group by cube(c1,c2,c3,c4);

create table t as select  mod(level,9)c1,mod(level,19)c2,mod(level,109)c3,
mod(case when mod(level,13)>0 then level end ,113)c4, level v from dual connect by level<=1E6

create table tcube as select c1,c2,c3,c4,sum(v)sv,count(v)cv,grouping_id(c1,c2,c3,c4)gid from t group by cube(c1,c2,c3,c4);

create table tcube as select/*+parallel(t,8) */ c1,c2,c3,c4,sum(v)sv,count(v)cv,grouping_id(c1,c2,c3,c4)gid from t group by cube(c1,c2,c3,c4);

create table t as select  mod(level,9)c1,mod(level,97)c2,mod(level,119)c3,
mod(case when mod(level,13)>0 then level end ,113)c4, level v from dual connect by level<=1E6

create table tcube as select c1,c2,c3,c4,sum(v)sv,count(v)cv,grouping_id(c1,c2,c3,c4)gid from t group by cube(c1,c2,c3,c4);

create table tcube as select/*+parallel(t,8) */ c1,c2,c3,c4,sum(v)sv,count(v)cv,grouping_id(c1,c2,c3,c4)gid from t group by cube(c1,c2,c3,c4);

〇〇

用vc6企业版的map和sgi stl map编译了，清除map的速度有提高
Set PATH=D:\app\pc\vc6\bin;%PATH%
Set INCLUDE=d:\app\stl;D:\app\VC6EN\VC98\include;%INCLUDE%
Set LIB=D:\app\VC6EN\VC98\lib;%LIB%
因为没有重载->
iter->second
改为
(*iter).second


D:\app>map8d
4,5,67,114,152760
申请源表内存0ms
填充源表数据46ms,recn=1000000,每毫秒21739行
申请一层内存32ms
新建一层节点202ms,recn=152760,每毫秒读4950行,每毫秒写756节点
申请后面内存0ms,152760
新建后面节点110ms,recn=234600,每毫秒读1388行key,每毫秒写744节点
0,first=3D65646F,renc=0
1,first=1000007F,renc=158036
2,first=20007F00,renc=160726
3,first=30007F7F,renc=225122
4,first=407F0000,renc=212892
5,first=507F007F,renc=225124
6,first=607F7F00,renc=226324
7,first=707F7F7F,renc=226316
8,first=8F000000,renc=220463
9,first=9F00007F,renc=225123
10,first=AF007F00,renc=225745
11,first=BF007F7F,renc=226315
12,first=CF7F0000,renc=226325
13,first=DF7F007F,renc=234418
14,first=EF7F7F00,renc=234485
15,first=FF7F7F7F,renc=234599
汇总后面节点15ms,recn=234600,每毫秒读10184行，每毫秒写5456行
释放所有动态内存0ms,234600
0,0
1,152760
2,152760
3,1340
4,152760
5,1340
6,30552
7,20
8,152760
9,1340
10,2280
11,20
12,30552
13,268
14,456
15,20
释放所有map内存16ms,234600
总时间421ms,234600
9,109,19,114,2124846
申请源表内存15ms
填充源表数据47ms,recn=1000000,每毫秒21276行
申请一层内存16ms
新建一层节点593ms,recn=941716,每毫秒读1686行,每毫秒写1588节点
申请后面内存15ms,941716
新建后面节点1123ms,recn=1346870,每毫秒读838行key,每毫秒写360节点
0,first=3D65646F,renc=0
1,first=1000007F,renc=941719
2,first=20007F00,renc=941718
3,first=30007F7F,renc=1327777
4,first=407F0000,renc=941717
5,first=507F007F,renc=1327779
6,first=607F7F00,renc=1343544
7,first=707F7F7F,renc=1343427
8,first=8F000000,renc=941716
9,first=9F00007F,renc=1327778
10,first=AF007F00,renc=1331000
11,first=BF007F7F,renc=1343426
12,first=CF7F0000,renc=1343545
13,first=DF7F007F,renc=1346736
14,first=EF7F7F00,renc=1346755
15,first=FF7F7F7F,renc=1346869
汇总后面节点47ms,recn=1346870,每毫秒读20036行，每毫秒写8620行
释放所有动态内存15ms,1346870
0,0
1,941716
2,941716
3,18639
4,941716
5,18639
6,19494
7,981
8,941716
9,18639
10,111834
11,981
12,19494
13,171
14,1026
15,981
释放所有map内存141ms,1346870
总时间2028ms,1346870
9,97,119,114,11843118
申请源表内存0ms
填充源表数据47ms,recn=1000000,每毫秒21276行
申请一层内存15ms
新建一层节点671ms,recn=1000000,每毫秒读1490行,每毫秒写1490节点
申请后面内存31ms,1000000
新建后面节点3822ms,recn=2299600,每毫秒读261行key,每毫秒写340节点
0,first=3D65646F,renc=0
1,first=1000007F,renc=1000003
2,first=20007F00,renc=1000002
3,first=30007F7F,renc=2260123
4,first=407F0000,renc=1000001
5,first=507F007F,renc=2260125
6,first=607F7F00,renc=2284774
7,first=707F7F7F,renc=2284669
8,first=8F000000,renc=1000000
9,first=9F00007F,renc=2260124
10,first=AF007F00,renc=2273610
11,first=BF007F7F,renc=2284668
12,first=CF7F0000,renc=2284775
13,first=DF7F007F,renc=2299366
14,first=EF7F7F00,renc=2299485
15,first=FF7F7F7F,renc=2299599
汇总后面节点140ms,recn=2299600,每毫秒读7142行，每毫秒写9282行
释放所有动态内存16ms,2299600
0,0
1,1000000
2,1000000
3,103887
4,1000000
5,103887
6,122094
7,873
8,1000000
9,103887
10,99522
11,873
12,122094
13,1071
14,1026
15,873
释放所有map内存218ms,2299600
总时间4976ms,2299600


iter->second
改为
(*iter).second
在AIX的速度没有变化

[ 本帖最后由 〇〇 于 2010-3-3 15:11 编辑 ]

〇〇

vc6en cl

[ 本帖最后由 〇〇 于 2010-3-3 15:19 编辑 ]

yulihua49

原帖由 〇〇 于 2010-3-3 15:18 发表
vc6en cl

学习红黑树，好像比平衡二叉树旋转次数少，但平衡度略差。平衡二叉树要求一个节点到它的叶路径长度之差不超过1，红黑树到最短的叶子和最长的叶子的路径长度不超过2倍。
减少了旋转次数从而提高了性能（不超过3次旋转就能搞定，平衡树就不知道要进行多少次旋转了）。是这样理解的吧？在我们的题目里并不进行值查找，高度的平衡性并无意义，因此红黑树是更好的选择。

你的程序性能较好的另一个原因是把key编码进行一次比较即可。但对数据类型进行了限制（如果key由各种各样的数据类型构成，怎么办呢？）。我那个比较器是自由的，它由两个字符串比较和一次整型比较构成，开销比较大。

其实我那个程序比你的直观而易理解。3个变量构成key分8组，所有key都不具备null，null是归并标志。
000，与任何一个变量无关，当然是总和。
001，只与3号变量有关，group by 3
011, group by (2,3)..以此类推，加入树时没有相同节点就加入，遇到相同节点就归并。各种工作函数嵌入遍历函数进行遍历。
其实平衡树与红黑树的处理步骤没什么不同。

你是把数据库的数据卸载到文件再处理，整套操作能比cube快吗？

[ 本帖最后由 yulihua49 于 2010-3-3 15:52 编辑 ]

〇〇

原帖由 yulihua49 于 2010-3-3 15:40 发表

学习红黑树，好像比平衡二叉树旋转次数少，但平衡度略差。平衡二叉树要求一个节点到它的叶路径长度之差不超过1，红黑树到最短的叶子和最长的叶子的路径长度不超过2倍。
减少了旋转次数从而提高了性能。是这样理解的吧？
你的程序性能较好的另一个原因是把key编码进行一次比较即可。但对数据类型进行了限制（如果key由各种各样的数据类型构成，怎么办呢？）。我那个比较器是自由的，它由两个字符串比较和一次整型比较构成，开销比较大。

其实我那个程序比你的直观而易理解。3个变量构成key分8组，所有key都不具备null，null是归并标志。
000，与任何一个变量无关，当然是总和。
001，只与3号变量有关，group by 3
011, group by (2,3)..以此类推，加入树时没有相同节点就加入，遇到相同节点就归并。各种工作函数嵌入遍历函数进行遍历。
其实平衡树与红黑树的处理步骤没什么不同。

你是把数据库的数据卸载到文件再处理，整套操作能比cube快吗？

排除数据类型()和计算精度(),速度对比在2楼已经一目了然.
文件操作时间已经考虑推算为数据库时间，但不能考虑连接时间。

yulihua49

原帖由 〇〇 于 2010-2-25 18:50 发表
用oci读写数据库，direct path、绑定变量真麻烦

所以DAU有好处，我是绝不直接用OCI的。

〇〇

因为你已经把它包装了,底层还是要用

〇〇

利用dcba的ociuldr读入数据比预计的慢很多
D:\app>cl  -ID:\app\pc\vc6\include /EHsc /O2 /TP map9.cpp /link oci.lib

create table t(c1 number(1,0),c2 number(1,0),c3 number(2,0),c4 number(3,0),v number(7,0));

insert into t select  mod(level,4)c1,mod(level,5)c2,mod(level,67)c3,
mod(case when mod(level,13)>0 then level end ,113)c4, level v from dual connect by level<=1E6;

D:\app\instantclient10_1>\app\timer \app\map9 user=LT/LT@x/orcl query="select c1,c2,c3,c4,v from t" file=NUL
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31

       0 rows exported at 2010-03-04 13:23:41
recn=0
  500000 rows exported at 2010-03-04 13:23:44
recn=500000
1000000 rows exported at 2010-03-04 13:23:47
         output file  closed at 1000000 rows.

sum=1
sum(c1+c2+c3+v)=500036999500
sum(c4)=51690810
从数据库把表读入内存6833ms
4,5,67,114,152760
申请map内存0ms
申请一层内存31ms
新建一层节点281ms,recn=151420,每毫秒读3558行,每毫秒写538节点
申请后面内存0ms,151420
新建后面节点140ms,recn=232560,每毫秒读1081行key,每毫秒写579节点
0,first=0,renc=0
1,first=1000007F,renc=157709
2,first=20007F00,renc=152456
3,first=30007F7F,renc=223159
4,first=407F0000,renc=158545
5,first=507F007F,renc=223161
6,first=607F7F00,renc=224356
7,first=707F7F7F,renc=224348
8,first=8F000000,renc=160539
9,first=9F00007F,renc=223160
10,first=AF007F00,renc=223782
11,first=BF007F7F,renc=224347
12,first=CF7F0000,renc=224357
13,first=DF7F007F,renc=232379
14,first=EF7F7F00,renc=232446
15,first=FF7F7F7F,renc=232559
汇总后面节点16ms,recn=232560,每毫秒读9463行，每毫秒写5071行
释放所有动态内存0ms,232560
释放所有map内存172ms,232560
总时间640ms,232560

Kernel Time  =     0.717 =    9%
User Time    =     3.244 =   43%
Process Time =     3.962 =   52%
Global Time  =     7.515 =  100%

D:\app\instantclient10_1>

create table t(c1 number(1,0),c2 number(2,0),c3 number(3,0),c4 number(3,0),v number(7,0));

insert into t select  mod(level,9)c1,mod(level,19)c2,mod(level,109)c3,
mod(case when mod(level,13)>0 then level end ,113)c4, level v from dual connect by level<=1E6;

D:\app\instantclient10_1>\app\timer \app\map9 user=LT/LT@x/orcl query="select c1,c2,c3,c4,v from t" file=NUL
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31

       0 rows exported at 2010-03-04 13:30:37
recn=0
  500000 rows exported at 2010-03-04 13:30:40
recn=500000
1000000 rows exported at 2010-03-04 13:30:43
         output file  closed at 1000000 rows.

sum=1
sum(c1+c2+c3+v)=500067498723
sum(c4)=51690810
从数据库把表读入内存7254ms
4,5,67,114,152760
申请map内存0ms
申请一层内存15ms
新建一层节点796ms,recn=933547,每毫秒读1256行,每毫秒写1172节点
申请后面内存15ms,933547
新建后面节点1654ms,recn=1335340,每毫秒读564行key,每毫秒写242节点
0,first=0,renc=0
1,first=1000007F,renc=933550
2,first=20007F00,renc=933549
3,first=30007F7F,renc=1316385
4,first=407F0000,renc=933548
5,first=507F007F,renc=1316387
6,first=607F7F00,renc=1321783
7,first=707F7F7F,renc=1321756
8,first=8F000000,renc=933547
9,first=9F00007F,renc=1316386
10,first=AF007F00,renc=1319608
11,first=BF007F7F,renc=1321755
12,first=CF7F0000,renc=1321784
13,first=DF7F007F,renc=1335117
14,first=EF7F7F00,renc=1335226
15,first=FF7F7F7F,renc=1335339
汇总后面节点46ms,recn=1335340,每毫秒读20294行，每毫秒写8734行
释放所有动态内存0ms,1335340
释放所有map内存5398ms,1335340
总时间7956ms,1335340

Kernel Time  =     0.842 =    5%
User Time    =    10.233 =   67%
Process Time =    11.076 =   72%
Global Time  =    15.243 =  100%

D:\app\instantclient10_1>

create table t(c1 number(1,0),c2 number(2,0),c3 number(3,0),c4 number(3,0),v number(7,0));

insert into t select  mod(level,9)c1,mod(level,97)c2,mod(level,119)c3,
mod(case when mod(level,13)>0 then level end ,113)c4, level v from dual connect by level<=1E6;

commit;

D:\app\instantclient10_1>\app\timer \app\map9 user=LT/LT@x/orcl query="select c1,c2,c3,c4,v from t" file=NUL
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31

       0 rows exported at 2010-03-04 13:33:07
recn=0
  500000 rows exported at 2010-03-04 13:33:10
recn=500000
1000000 rows exported at 2010-03-04 13:33:13
         output file  closed at 1000000 rows.

sum=1
sum(c1+c2+c3+v)=500111497488
sum(c4)=51690810
从数据库把表读入内存7269ms
4,5,67,114,152760
申请map内存0ms
申请一层内存16ms
新建一层节点764ms,recn=994110,每毫秒读1308行,每毫秒写1301节点
申请后面内存16ms,994110
新建后面节点3167ms,recn=2277949,每毫秒读313行key,每毫秒写405节点
0,first=0,renc=0
1,first=1000007F,renc=994113
2,first=20007F00,renc=994112
3,first=30007F7F,renc=2238698
4,first=407F0000,renc=994111
5,first=507F007F,renc=2238700
6,first=607F7F00,renc=2263252
7,first=707F7F7F,renc=2263147
8,first=8F000000,renc=994110
9,first=9F00007F,renc=2238699
10,first=AF007F00,renc=2252185
11,first=BF007F7F,renc=2263146
12,first=CF7F0000,renc=2263253
13,first=DF7F007F,renc=2277716
14,first=EF7F7F00,renc=2277835
15,first=FF7F7F7F,renc=2277948
汇总后面节点141ms,recn=2277949,每毫秒读7050行，每毫秒写9105行
释放所有动态内存15ms,2277949
释放所有map内存62431ms,2277949
总时间66565ms,2277949

Kernel Time  =     1.029 =    1%
User Time    =    68.921 =   93%
Process Time =    69.950 =   94%
Global Time  =    73.882 =  100%

D:\app\instantclient10_1>

〇〇

与数据是否实际存在数据库无关，oci函数读这么多数据就需要时间
D:\lt\dl>map9 LT/LT query="select c1,c2,c3,c4,v from(select  mod(level,4)c1,mod(level,5)c2,mod(level,67)c3,mod(case when mod(level,13)
>0 then level end ,113)c4, level v from dual connect by level<=1E6)" file=NUL

       0 rows exported at 2010-03-04 18:57:19
recn=0
  500000 rows exported at 2010-03-04 18:57:23
recn=500000
1000000 rows exported at 2010-03-04 18:57:26
         output file  closed at 1000000 rows.

sum=1
sum(c1+c2+c3+v)=500036999500
sum(c4)=51690810
从数据库把表读入内存7359ms
4,5,67,114,152760
申请map内存0ms
申请一层内存0ms
新建一层节点203ms,recn=151420,每毫秒读4926行,每毫秒写745节点
申请后面内存0ms,151420
新建后面节点109ms,recn=232560,每毫秒读1389行key,每毫秒写744节点
0,first=29,renc=0
1,first=1000007F,renc=156677
2,first=20007F00,renc=152456
3,first=30007F7F,renc=223159
4,first=407F0000,renc=161858
5,first=507F007F,renc=223161
6,first=607F7F00,renc=224356
7,first=707F7F7F,renc=224348
8,first=8F000000,renc=163578
9,first=9F00007F,renc=223160
10,first=AF007F00,renc=223782
11,first=BF007F7F,renc=224347
12,first=CF7F0000,renc=224357
13,first=DF7F007F,renc=232379
14,first=EF7F7F00,renc=232446
15,first=FF7F7F7F,renc=232559

〇〇

处理NULL的代码
              if (*(cols[c]->indp+r) >= 0)
              {
                if (fixlen)
/*                    fprintf(fp,cols[c]->fmtstr, cols[c]->colbuf+(r* cols[c]->dsize))*/;
                else
                {
                   //fwrite(cols[c]->colbuf+(r* cols[c]->dsize),*(cols[c]->col_retlen+r),1,fp);
                  
                   //printf("%d,%d,%d,%d\n",r,c,*(cols[c]->col_retlen+r),*(cols[c]->col_retcode+r));
                   //if (r>=30)exit(0);
                   switch(c)
                   {
                           case 0:c1[rn]=(char)atoi((const char *)(cols[c]->colbuf+(r* cols[c]->dsize)));break;
                           case 1:c2[rn]=(char)atoi((const char *)(cols[c]->colbuf+(r* cols[c]->dsize)));break;
                           case 2:c3[rn]=(char)atoi((const char *)(cols[c]->colbuf+(r* cols[c]->dsize)));break;
                           case 3:c4[rn]=(char)atoi((const char *)(cols[c]->colbuf+(r* cols[c]->dsize)));
                           /*if(*(cols[c]->col_retlen+r)==0)c4[rn]=(char)127;*/break;
                           case 4:v[rn]=atoi(((const char *)(cols[c]->colbuf+(r* cols[c]->dsize))));break;
                          
                    }
                    //exit(0);
                }
              }
                    else
                    {c4[rn]=(char)127;
  /**   indp    - place to store the length of the returned value. If returned
   **             value is:
   **             negative, the field fetched was NULL
   **             zero    , the field fetched was same length or shorter than
   **               the buffer provided
   **             positive, the field fetched was truncated*/