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

newkid

原帖由 tree_new_bee 于 2010-12-5 15:54 发表
newkid推荐的帖子， 过来试试。
弄了一下八皇后， 好像不是太难。



with t as (select  rownum-1 c from dual connect by rownum

8表连接没有问题，还有一个OO指出来的点睛之处是这些行（或列）满足连续的1-8，加上这个条件效率高很多。

newkid

原帖由 lastwinner 于 2010-12-5 23:17 发表
connect by的代价是低level的必须要列出，这点很讨厌，估计oracle 12g里能有改进

什么意思？不是可以用WHERE LEVEL 和 CONNECT_BY_ISLEAF过滤？
递归WITH是广度优先的，我也希望有关选项能够只保留最近一层。

tree_new_bee

原帖由 newkid 于 2010-12-6 00:26 发表

什么意思？不是可以用WHERE LEVEL 和 CONNECT_BY_ISLEAF过滤？
递归WITH是广度优先的，我也希望有关选项能够只保留最近一层。

原帖由 lastwinner 于 2010-12-5 23:17 发表
connect by的代价是低level的必须要列出，这点很讨厌，估计oracle 12g里能有改进

说connect by不好，不是说它本身的效率不好。
而是说由于没有对单列直接进行条件比较， 不能把条件带入inline view里去， 也就不能尽快对结果集的大小进行缩减。

tree_new_bee

原帖由 newkid 于 2010-12-6 00:24 发表


8表连接没有问题，还有一个OO指出来的点睛之处是这些行（或列）满足连续的1-8，加上这个条件效率高很多。

我的语句应该比你说的更彻底， 我不是加条件， 而是直接指定8个皇后的行号分别是1-8的。

select t1.c c1, t2.c c2, t3.c c3, t4.c c4, t5.c c5, t6.c c6, t7.c c7, t8.c c8
,0 r1, 1 r2, 2 r3, 3 r4, 4 r5, 5 r6, 6 r7, 7 r8 --行不同
from t t1, t t2, t t3, t t4, t t5, t t6, t t7, t t8

newkid

原帖由 tree_new_bee 于 2010-12-6 01:46 发表


我的语句应该比你说的更彻底， 我不是加条件， 而是直接指定8个皇后的行号分别是1-8的。

select t1.c c1, t2.c c2, t3.c c3, t4.c c4, t5.c c5, t6.c c6, t7.c c7, t8.c c8
,0 r1, 1 r2, 2 r3, 3 r4, 4 r5, 5 r6, 6 r7, 7 r8 --行不同
from t t1, t t2, t t3, t t4, t t5, t t6, t t7, t t8

还是你狠，我没有仔细看你的答案。
CONNECT BY的很多问题在11GR2的递归WITH都已经解决了，每层递归都可以很灵活地剪枝。

newkid

原帖由 tree_new_bee 于 2010-12-6 01:46 发表


我的语句应该比你说的更彻底， 我不是加条件， 而是直接指定8个皇后的行号分别是1-8的。

select t1.c c1, t2.c c2, t3.c c3, t4.c c4, t5.c c5, t6.c c6, t7.c c7, t8.c c8
,0 r1, 1 r2, 2 r3, 3 r4, 4 r5, 5 r6, 6 r7, 7 r8 --行不同
from t t1, t t2, t t3, t t4, t t5, t t6, t t7, t t8

我又看了以前在75楼的写法，其实和你一样，指定的是列数。
WITH c AS (
  SELECT id,x,y,x+y m,x-y n FROM (
    SELECT ROWNUM id, MOD(ROWNUM-1,8)+1 x,CEIL(ROWNUM/8) y FROM DUAL CONNECT BY ROWNUM<=64
    )
  )
SELECT '('||c1.x||','||c1.y||')'
     ||'('||c2.x||','||c2.y||')'
     ||'('||c3.x||','||c3.y||')'
     ||'('||c4.x||','||c4.y||')'
     ||'('||c5.x||','||c5.y||')'
     ||'('||c6.x||','||c6.y||')'
     ||'('||c7.x||','||c7.y||')'
     ||'('||c8.x||','||c8.y||')'
FROM c c1,c c2,c c3,c c4,c c5,c c6,c c7,c c8
WHERE (c1.y,c2.y,c3.y,c4.y,c5.y,c6.y,c7.y,c8.y) IN ((1,2,3,4,5,6,7,8))
      AND NOT (c1.x IN (c2.x,c3.x,c4.x,c5.x,c6.x,c7.x,c8.x)
            OR c1.m IN (c2.m,c3.m,c4.m,c5.m,c6.m,c7.m,c8.m)
            OR c1.n IN (c2.n,c3.n,c4.n,c5.n,c6.n,c7.n,c8.n)
            OR c2.x IN (c3.x,c4.x,c5.x,c6.x,c7.x,c8.x)
            OR c2.m IN (c3.m,c4.m,c5.m,c6.m,c7.m,c8.m)
            OR c2.n IN (c3.n,c4.n,c5.n,c6.n,c7.n,c8.n)
            OR c3.x IN (c4.x,c5.x,c6.x,c7.x,c8.x)
            OR c3.m IN (c4.m,c5.m,c6.m,c7.m,c8.m)
            OR c3.n IN (c4.n,c5.n,c6.n,c7.n,c8.n)
            OR c4.x IN (c5.x,c6.x,c7.x,c8.x)
            OR c4.m IN (c5.m,c6.m,c7.m,c8.m)
            OR c4.n IN (c5.n,c6.n,c7.n,c8.n)
            OR c5.x IN (c6.x,c7.x,c8.x)
            OR c5.m IN (c6.m,c7.m,c8.m)
            OR c5.n IN (c6.n,c7.n,c8.n)
            OR c6.x IN (c7.x,c8.x)
            OR c6.m IN (c7.m,c8.m)
            OR c6.n IN (c7.n,c8.n)
            OR c7.x IN (c8.x)
            OR c7.m IN (c8.m)
            OR c7.n IN (c8.n)
           )
;

tree_new_bee

原帖由 newkid 于 2010-12-6 04:39 发表


我又看了以前在75楼的写法，其实和你一样，指定的是列数。

WHERE (c1.y,c2.y,c3.y,c4.y,c5.y,c6.y,c7.y,c8.y) IN ((1,2,3,4,5,6,7,8))

还是有区别的， 我是直接指定具体数字，没有对表的访问，  
你还是要查询一下，只是能够尽早对结果集进行剪裁而已。 并且前面生成的已经是个大的结果集， 构造这个大结果集还是比较费时的。

这里的区别如同：
select 1 from dual
和
select c from 多行表 where c=1
的区别。

newkid

什么大结果集? 总共才8X8=64行，用WHERE过滤出其中的8行，然后再做8表连接进行其他过滤。
你的TT集合里面也是8^8行。
我比较了执行计划和stats，两个写法非常相似。

tree_new_bee

原帖由 newkid 于 2010-12-6 23:12 发表
什么大结果集? 总共才8X8=64行，用WHERE过滤出其中的8行，然后再做8表连接进行其他过滤。
你的TT集合里面也是8^8行。
我比较了执行计划和stats，两个写法非常相似。

在未加入后面三个过滤条件下的情况下的比较：

scott@O9I.US.ORACLE.COM> with t as (select  rownum-1 c from dual connect by rown
um<=8)
  2  ,tt as ( select t1.c c1, t2.c c2, t3.c c3, t4.c c4, t5.c c5, t6.c c6, t7.c
c7, t8.c c8
  3  ,0 r1, 1 r2, 2 r3, 3 r4, 4 r5, 5 r6, 6 r7, 7 r8 --行不同
  4  from t t1, t t2, t t3, t t4, t t5, t t6, t t7, t t8 )
  5  select count(*) from tt
  6  /

  COUNT(*)
----------
  16777216

已用时间:  00: 00: 13.01
scott@O9I.US.ORACLE.COM> WITH c AS (
  2    SELECT id,x,y,x+y m,x-y n FROM (
  3      SELECT ROWNUM id, MOD(ROWNUM-1,8)+1 x,CEIL(ROWNUM/8) y FROM DUAL CONNEC
T BY ROWNUM<=64
  4      )
  5    )
  6  ,tt as (SELECT '('||c1.x||','||c1.y||')'
  7       ||'('||c2.x||','||c2.y||')'
  8       ||'('||c3.x||','||c3.y||')'
  9       ||'('||c4.x||','||c4.y||')'
10       ||'('||c5.x||','||c5.y||')'
11       ||'('||c6.x||','||c6.y||')'
12       ||'('||c7.x||','||c7.y||')'
13       ||'('||c8.x||','||c8.y||')'
14  FROM c c1,c c2,c c3,c c4,c c5,c c6,c c7,c c8
15  WHERE (c1.y,c2.y,c3.y,c4.y,c5.y,c6.y,c7.y,c8.y) IN ((1,2,3,4,5,6,7,8))
16  )
17  select count(*) from tt
18  /

  COUNT(*)
----------
  16777216

已用时间:  00: 00: 37.02
scott@O9I.US.ORACLE.COM>

newkid

差距这么大？在我这里是1.71和2.06秒。如果我把自己的写法的过滤提前并固定化，则提高为1.8秒，比你多了8次过滤。

WITH c AS (
   SELECT id,x,y,x+y m,x-y n FROM (
     SELECT ROWNUM id, MOD(ROWNUM-1,8)+1 x,CEIL(ROWNUM/8) y FROM DUAL CONNECT BY ROWNUM<=64
     )
   )
,c1 as (select /*+ materialize */ * from c where y=1)
,c2 as (select /*+ materialize */ * from c where y=2)
,c3 as (select /*+ materialize */ * from c where y=3)
,c4 as (select /*+ materialize */ * from c where y=4)
,c5 as (select /*+ materialize */ * from c where y=5)
,c6 as (select /*+ materialize */ * from c where y=6)
,c7 as (select /*+ materialize */ * from c where y=7)
,c8 as (select /*+ materialize */ * from c where y=8)
,tt as (SELECT c1.y,c2.y,c3.y,c4.y,c5.y,c6.y,c7.y,c8.y
FROM  c1, c2, c3, c4,c5, c6, c7, c8
)
select count(*) from tt
/