数据库问题的改进讨论

key

之前的讨论在这里：
http://www.freeoz.org/forum/thread-856151-1-1.html

现在改变一下需求，看看大家有什么答案：

有一个数据库表，有字段 x , 和 y，如果 y 一共有4个值，
而x任意互不重复的整数值。
现在把数据库表按照x来递增排序，并把所有记录按40个值为一组，
对每一组数据依次统计y为0, 1, 2, 3的结果。。。。
用一条sql来解决，不能使用动态sql，尽量符合SQL标准（如SQL99, SQL92之流）

最好能列出五个列
x的起始值, y=0统计值, y=1统计值, y=2统计值, y=3统计值

coredump

再加个辅助字段，把这个问题专成原来的问题

key

原帖由 coredump 于 6-9-2009 14:52 发表

                               
登录/注册后可看大图

再加个辅助字段，把这个问题专成原来的问题

具体点？

key

原帖由 key 于 6-9-2009 15:23 发表

                               
登录/注册后可看大图

具体点？

我现在的做法是利用前面那个讨论中的sum()方案，再利用count(*)来建立一个新的x列表，最后按照原来那个方案来做。
但这样一来速度就很成问题了。

coredump

SELECT
   RANK() OVER (ORDER BY x ASC) AS ranking   //RANK()也可以换成ROW_NUMBER() ，看你的数据库支持哪个

然后ranking和y就相当于前面的那个问题了。
RANK(), ROW_NUMBER()都属于SQL Window function的一种,SQL92没这东西，SQL2003才引入标准(http://en.wikipedia.org/wiki/Select_(SQL))

如果是用ORACLE，可以用ROWNUM伪列代替

GPS

单纯从算法的角度看，觉得要实现目标，首先一个排序是必须的，能不能在排序的同时，也解决分组呢？不太确定，不过这不影响分析。假设排序的效率是O(f(n)), 前面已经看到分组可以实现到O(n)。f(n)的阶至少是>=n的。所以
总的效率是有O(f(n))决定的，即排序的效率决定了整个算法的效率。
LZ觉得速度慢，那么应该考虑提高排序速度，比如，对x采用合适的索引，可能效果会好点。
等高手指点一下怎样分析SQL的效率吧。

zycbob

sqlite不支持 RANK() 和 ROW_NUMBER() 吧

earthengine

原帖由 key 于 6-9-2009 15:25 发表

                               
登录/注册后可看大图

我现在的做法是利用前面那个讨论中的sum()方案，再利用count(*)来建立一个新的x列表，最后按照原来那个方案来做。
但这样一来速度就很成问题了。

理论上，用一条SQL语句是可以完成的，见下：
SELECT
  MIN((SELECT COUNT(*) FROM temptest1 a WHERE a.x<=b.x) ) AS x0,
  SUM( (CASE WHEN y=0 THEN 1 ELSE 0 END) ) AS y0,
  SUM( (CASE WHEN y=1 THEN 1 ELSE 0 END) ) AS y1,
  SUM( (CASE WHEN y=2 THEN 1 ELSE 0 END) ) AS y2,
  SUM( (CASE WHEN y=3 THEN 1 ELSE 0 END) ) AS y3
FROM temptest1 b
GROUP BY ( ((SELECT COUNT(*) FROM temptest1 a WHERE a.x<=b.x)-1)/40)
ORDER BY x0

不过如你所说，这样做有很大的效率问题。
为了提高效率，可以考虑采用临时表方案：
CREATE TABLE temp (x int,recno int)

INSERT INTO temp (x,recno)
SELECT x, (SELECT count(*) FROM temptest1 a WHERE a.x<=b.x)
FROM temptest1 a

SELECT min(b.x) AS x0,
   SUM (CASE WHEN y=0 THEN 1 ELSE 0 END) AS y0,
   SUM (CASE WHEN y=1 THEN 1 ELSE 0 END) AS y1,
   SUM (CASE WHEN y=2 THEN 1 ELSE 0 END) AS y2,
   SUM (CASE WHEN y=3 THEN 1 ELSE 0 END) AS y3
FROM temptest1 INNER JOIN temp b ON a.x=b.x
GROUP BY (b.recno-1)/40
ORDER BY x0

DROP TABLE temp