出个SQL题：4皇后问题（新增马步问题在第7页）

tree_new_bee · 发表于 2010-12-7 10:52

原帖由 newkid 于 2010-12-7 09:53 发表
差距这么大？在我这里是1.71和2.06秒。如果我把自己的写法的过滤提前并固定化，则提高为1.8秒，比你多了8次过滤。

嗯。
我的语句是直接生成8^8个记录，
你原来的语句是生成64^8个记录，然后经过过滤只保留其中的1/(8^8), 剩余 (64^8)/(8^8) = 8^8个。

修改后的这个语句，则是为每个64过滤成1/8，相当于 (64/8)^8=8^8, 预先对每个64取8的开销几乎可以忽略不计了。

另外，发现一个有意思的现象：无论以上哪个语句，如果加入no_merge提示，性能都很好，在我这里都是2-3秒。

no_merge后，所有的执行计划里的nest loop改成了merge join cartesian, 至于这样的执行计划为什么这么快，没想明白。

newkid · 发表于 2010-12-7 22:48

原帖由 tree_new_bee 于 2010-12-7 10:52 发表

嗯。
我的语句是直接生成8^8个记录，
你原来的语句是生成64^8个记录，然后经过过滤只保留其中的1/(8^8), 剩余 (64^8)/(8^8) = 8^8个。

修改后的这个语句，则是为每个64过滤成1/8，相当于 (64/8)^8=8^8, 预先对每个64取8的开销几乎可以忽略不计了。

另外，发现一个有意思的现象：无论以上哪个语句，如果加入no_merge提示，性能都很好，在我这里都是2-3秒。

no_merge后，所有的执行计划里的nest loop改成了merge join cartesian, 至于这样的执行计划为什么这么快，没想明白。

原来如此，我还在同情你的硬件配置呢，原来是查询计划的问题。我在11G下不用加任何提示就是MERGE JOIN CARTESIAN, 所以执行速度相差无几。
我把过滤提前造成的变化也很费解，从计划上看，不提前则一边连接一边过滤，其实每次也是过滤后再连接，但是就慢了0.2秒。

tree_new_bee · 发表于 2010-12-7 23:17

原帖由 newkid 于 2010-12-7 22:48 发表

原来如此，我还在同情你的硬件配置呢，原来是查询计划的问题。我在11G下不用加任何提示就是MERGE JOIN CARTESIAN, 所以执行速度相差无几。
我把过滤提前造成的变化也很费解，从计划上看，不提前则一边连接一边过滤，其实每次也是过滤后再连接，但是就慢了0.2秒。

听你这么一说，郁闷了。下载11g去。
不说性能了，至少能玩玩model语法了。

newkid · 发表于 2010-12-7 23:20

原帖由 tree_new_bee 于 2010-12-7 23:17 发表

听你这么一说，郁闷了。下载11g去。
不说性能了，至少能玩玩model语法了。

MODEL在10G就有了，最值得玩的是递归的WITH子查询，买本我们的新书看吧，哈哈。

tree_new_bee · 发表于 2010-12-9 23:08

原帖由 newkid 于 2010-12-7 22:48 发表

原来如此，我还在同情你的硬件配置呢，原来是查询计划的问题。我在11G下不用加任何提示就是MERGE JOIN CARTESIAN, 所以执行速度相差无几。
我把过滤提前造成的变化也很费解，从计划上看，不提前则一边连接一边过滤，其实每次也是过滤后再连接，但是就慢了0.2秒。

装上了11g, 11g下执行速度确实非常快。

看来要仔细研究下不同环境的执行计划了。

[ 本帖最后由 tree_new_bee 于 2010-12-9 23:15 编辑 ]

newkid · 发表于 2010-12-10 00:11

回到顶楼的问题，我当时在第四页37楼的解答用的是十进制相加来变相实现BITOR的方法。因为十进制NUMBER在ORACLE中有位数限制，无法做49位的加法，所以不得不拆成两截来相加。
我的朋友Frank Zhou给出了用UTL_RAW.BIT_OR的方法。我当初不是没有想过，但是因为它的参数和返回值都是RAW的，转换很麻烦。其实不需要做二进制转换，直接用16进制，这样就可以按字符串来解析结果。

比如 BITOR(1000,0010), 不需要把操作数变成8和2, 再把返回值又逐位求出来。就用 RAWTOHEX(UTL_RAW.BIT_OR(HEXTORAW('1000'),HEXTORAW('0010')))，得到的仍然是0和1的字符串。内部做的是4096和16的BITOR操作但不影响我们的判断逻辑。
用ORACLE的隐性转换，连HEXTORAW和RAWTOHEX都可以省掉。要注意的是UTL_RAW.BIT_OR总是返回偶数位长度，奇数则左边会补一个零，所以我们要做49位运算时必须从第二位取结果。

WITH c AS (
SELECT ROWNUM id, MOD(ROWNUM-1,7)+1 x,CEIL(ROWNUM/7) y FROM DUAL CONNECT BY ROWNUM<=49
)
  ,cells AS (
SELECT c1.id,c1.x,c1.y
      ,REPLACE(SYS_CONNECT_BY_PATH(CASE WHEN c1.x=c2.x OR c1.y = c2.y
                                             OR c1.x-c2.x IN (c1.y-c2.y,c2.y-c1.y)
                                       THEN '1'
                                       ELSE '0'
                                    END,',')
               ,',') cover
   FROM c c1, c c2
WHERE level=49
START WITH c2.id=1
CONNECT BY c1.id = PRIOR c1.id AND c2.id = PRIOR c2.id+1
)
SELECT c1.x||c1.y||'-'||c2.x||c2.y||'-'||c3.x||c3.y||'-'||c4.x||c4.y AS result
  FROM cells c1,cells c2, cells c3, cells c4
WHERE c1.x BETWEEN 1 AND 4
   AND c1.y BETWEEN 1 AND 4
   AND c1.x <= c1.y
   AND c1.id < c2.id AND c2.id < c3.id AND c3.id < c4.id
   AND SUBSTR(c1.cover,c2.id,1)='0'
   AND SUBSTR(c1.cover,c3.id,1)='0'
   AND SUBSTR(c1.cover,c4.id,1)='0'
   AND SUBSTR(c2.cover,c3.id,1)='0'
   AND SUBSTR(c2.cover,c4.id,1)='0'
   AND SUBSTR(c3.cover,c4.id,1)='0'
   AND INSTR(SUBSTR(UTL_RAW.BIT_OR(UTL_RAW.BIT_OR(UTL_RAW.BIT_OR(c1.cover,c2.cover),c3.cover),c4.cover),2),'0')=0
;

[ 本帖最后由 newkid 于 2010-12-10 00:13 编辑 ]