Category Archives: SQL

8 queens chess problem: solution in Oracle SQL

Posted on by Posted in curious, oracle, SQL 1,876 Page views 1 Comment

This is just another solution of this problem for a chessboard, but you can choose any size of the checkerboard:

with 
 t as (select level i, cast(level as varchar2(1)) c from dual connect by level<=&d)
,x(l,s,n) as (
       select 1 l, c s, chr(97)||c||' ' from t
       union all
       select l+1, x.s||t.c, n||chr(97+l)||i||' '
       from x
            join t
                 on instr(s,c)=0
                    and not exists(select 0 from dual 
                                   where L+1 - t.i = level - substr(s,level,1)
                                      or L+1 + t.i = level + substr(s,level,1)
                                   connect by level<=length(s))
       where L<&d
 )
select n
from x
where l=&d

8x8:

[sourcecode language=”sql”]
SQL> @tests/f
Size[8]: 8

N
——————————————————————————–
a1 b5 c8 d6 e3 f7 g2 h4
a1 b6 c8 d3 e7 f4 g2 h5
a1 b7 c4 d6 e8 f2 g5 h3
a1 b7 c5 d8 e2 f4 g6 h3
a2 b4 c6 d8 e3 f1 g7 h5
a2 b5 c7 d1 e3 f8 g6 h4
a2 b5 c7 d4 e1 f8 g6 h3
a2 b6 c1 d7 e4 f8 g3 h5
a2 b6 c8 d3 e1 f4 g7 h5
a2 b7 c3 d6 e8 f5 g1 h4
a2 b7 c5 d8 e1 f4 g6 h3
a2 b8 c6 d1 e3 f5 g7 h4
a3 b1 c7 d5 e8 f2 g4 h6
a3 b5 c2 d8 e1 f7 g4 h6
a3 b5 c2 d8 e6 f4 g7 h1
a3 b5 c7 d1 e4 f2 g8 h6
a3 b5 c8 d4 e1 f7 g2 h6
a3 b6 c2 d5 e8 f1 g7 h4
a3 b6 c2 d7 e1 f4 g8 h5
a3 b6 c2 d7 e5 f1 g8 h4
a3 b6 c4 d1 e8 f5 g7 h2
a3 b6 c4 d2 e8 f5 g7 h1
a3 b6 c8 d1 e4 f7 g5 h2
a3 b6 c8 d1 e5 f7 g2 h4
a3 b6 c8 d2 e4 f1 g7 h5
a3 b7 c2 d8 e5 f1 g4 h6
a3 b7 c2 d8 e6 f4 g1 h5
a3 b8 c4 d7 e1 f6 g2 h5
a4 b1 c5 d8 e2 f7 g3 h6
a4 b1 c5 d8 e6 f3 g7 h2
a4 b2 c5 d8 e6 f1 g3 h7
a4 b2 c7 d3 e6 f8 g1 h5
a4 b2 c7 d3 e6 f8 g5 h1
a4 b2 c7 d5 e1 f8 g6 h3
a4 b2 c8 d5 e7 f1 g3 h6
a4 b2 c8 d6 e1 f3 g5 h7
a4 b6 c1 d5 e2 f8 g3 h7
a4 b6 c8 d2 e7 f1 g3 h5
a4 b6 c8 d3 e1 f7 g5 h2
a4 b7 c1 d8 e5 f2 g6 h3
a4 b7 c3 d8 e2 f5 g1 h6
a4 b7 c5 d2 e6 f1 g3 h8
a4 b7 c5 d3 e1 f6 g8 h2
a4 b8 c1 d3 e6 f2 g7 h5
a4 b8 c1 d5 e7 f2 g6 h3
a4 b8 c5 d3 e1 f7 g2 h6
a5 b1 c4 d6 e8 f2 g7 h3
a5 b1 c8 d4 e2 f7 g3 h6
a5 b1 c8 d6 e3 f7 g2 h4
a5 b2 c4 d6 e8 f3 g1 h7
a5 b2 c4 d7 e3 f8 g6 h1
a5 b2 c6 d1 e7 f4 g8 h3
a5 b2 c8 d1 e4 f7 g3 h6
a5 b3 c1 d6 e8 f2 g4 h7
a5 b3 c1 d7 e2 f8 g6 h4
a5 b3 c8 d4 e7 f1 g6 h2
a5 b7 c1 d3 e8 f6 g4 h2
a5 b7 c1 d4 e2 f8 g6 h3
a5 b7 c2 d4 e8 f1 g3 h6
a5 b7 c2 d6 e3 f1 g4 h8
a5 b7 c2 d6 e3 f1 g8 h4
a5 b7 c4 d1 e3 f8 g6 h2
a5 b8 c4 d1 e3 f6 g2 h7
a5 b8 c4 d1 e7 f2 g6 h3
a6 b1 c5 d2 e8 f3 g7 h4
a6 b2 c7 d1 e3 f5 g8 h4
a6 b2 c7 d1 e4 f8 g5 h3
a6 b3 c1 d7 e5 f8 g2 h4
a6 b3 c1 d8 e4 f2 g7 h5
a6 b3 c1 d8 e5 f2 g4 h7
a6 b3 c5 d7 e1 f4 g2 h8
a6 b3 c5 d8 e1 f4 g2 h7
a6 b3 c7 d2 e4 f8 g1 h5
a6 b3 c7 d2 e8 f5 g1 h4
a6 b3 c7 d4 e1 f8 g2 h5
a6 b4 c1 d5 e8 f2 g7 h3
a6 b4 c2 d8 e5 f7 g1 h3
a6 b4 c7 d1 e3 f5 g2 h8
a6 b4 c7 d1 e8 f2 g5 h3
a6 b8 c2 d4 e1 f7 g5 h3
a7 b1 c3 d8 e6 f4 g2 h5
a7 b2 c4 d1 e8 f5 g3 h6
a7 b2 c6 d3 e1 f4 g8 h5
a7 b3 c1 d6 e8 f5 g2 h4
a7 b3 c8 d2 e5 f1 g6 h4
a7 b4 c2 d5 e8 f1 g3 h6
a7 b4 c2 d8 e6 f1 g3 h5
a7 b5 c3 d1 e6 f8 g2 h4
a8 b2 c4 d1 e7 f5 g3 h6
a8 b2 c5 d3 e1 f7 g4 h6
a8 b3 c1 d6 e2 f5 g7 h4
a8 b4 c1 d3 e6 f2 g7 h5

92 rows selected.
[/sourcecode]

[collapse]

Solution for N between 10 and 100

[sourcecode language=”sql”]
with
t as (select level i, to_char(level,’fm00′) c from dual connect by level<=&d)
,x(l,s,n) as (
select 1 l, c s, chr(97)||c||’ ‘ from t
union all
select l+1, x.s||t.c, n||chr(97+l)||to_char(i,’fm00′)||’ ‘
from x
join t
on instr(s,c)=0
and not exists(select 0 from dual
where L+1 – t.i = level – substr(s,length(c)*level-1,length(c))
or L+1 + t.i = level + substr(s,length(c)*level-1,length(c))
connect by level<=length(s))
where L<&d
)
select n
from x
where l=&d
[/sourcecode]

[collapse]

It works quite fast:
8*8 ~ 0.1s
9*9 ~ 0.6s
10*10 ~4s

script for sqlplus

[sourcecode language=”sql”]
set arrays 1000;
col n for a80;
accept d prompt "Size[8]: " default 8;
with
t as (select/*+inline*/ level i, cast(level as varchar2(2)) c from dual connect by level<=&d)
,x(l,s,n) as (
select 1 l, c s, chr(97)||c||’ ‘ from t
union all
select l+1, x.s||t.c, n||chr(97+l)||i||’ ‘
from x
join t
on instr(s,c)=0
and not exists(select 0 from dual
where L+1 – t.i = level – substr(s,level,1)
or L+1 + t.i = level + substr(s,level,1)
connect by level<=length(s))
where L<&d
)
select n
from x
where l=&d
/
col n clear;
[/sourcecode]

[collapse]

Update: Fixed the typo, thanks to Brian Fitzgerald (@ExaGridDba)

WINDOW NOSORT STOPKEY + RANK()

Posted on by Posted in CBO, oracle, query optimizing, SQL 2,140 Page views Leave a comment

Recently I found that WINDOW NOSORT STOPKEY with RANK()OVER() works very inefficiently: http://www.freelists.org/post/oracle-l/RANKWINDOW-NOSORT-STOPKEY-stopkey-doesnt-work
The root cause of this behaviour is that Oracle optimizes WINDOW NOSORT STOPKEY with RANK the same way as with DENSE_RANK:

rnk1

[sourcecode language=”sql” highlight=””]
create table test(n not null) as
with gen as (select level n from dual connect by level<=100)
select g2.n as n
from gen g1, gen g2
where g1.n<=10
/
create index ix_test on test(n)
/
exec dbms_stats.gather_table_stats(”,’TEST’);
select/*+ gather_plan_statistics */ n
from (select rank()over(order by n) rnk
,n
from test)
where rnk<=3
/
select * from table(dbms_xplan.display_cursor(”,”,’allstats last’));
drop table test purge;
[/sourcecode]

[collapse]
Output

[sourcecode language=”sql” highlight=”29,30,31″]
N
———-
1
1
1
1
1
1
1
1
1
1

10 rows selected.

PLAN_TABLE_OUTPUT
———————————————————————————————————————–
SQL_ID 8tbq95dpw0gw7, child number 0
————————————-
select/*+ gather_plan_statistics */ n from (select rank()over(order by
n) rnk ,n from test) where rnk<=3

Plan hash value: 1892911073

———————————————————————————————————————–
| Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | OMem | 1Mem | Used-Mem |
———————————————————————————————————————–
| 0 | SELECT STATEMENT | | 1 | | 10 |00:00:00.01 | 3 | | | |
|* 1 | VIEW | | 1 | 1000 | 10 |00:00:00.01 | 3 | | | |
|* 2 | WINDOW NOSORT STOPKEY| | 1 | 1000 | 30 |00:00:00.01 | 3 | 73728 | 73728 | |
| 3 | INDEX FULL SCAN | IX_TEST | 1 | 1000 | 31 |00:00:00.01 | 3 | | | |
———————————————————————————————————————–

Predicate Information (identified by operation id):
—————————————————

1 – filter("RNK"<=3)
2 – filter(RANK() OVER ( ORDER BY "N")<=3)
[/sourcecode]

[collapse]

As you can see, A-Rows in plan step 2 = 30 – ie, that is the number of rows where 

DENSE_RANK<=3

but not 

RANK<=3

The more effective way will be to stop after first 10 rows, because 11th row already has RANK more than 3!
But we can create own STOPKEY version with PL/SQL:

PLSQL STOPKEY version

[sourcecode language="sql"]
create or replace type rowids_table is table of varchar2(18);
/
create or replace function get_rowids_by_rank(
n int
,max_rank int
)
return rowids_table pipelined
as
begin
for r in (
select/*+ index_rs_asc(t (n)) */ rowidtochar(rowid) chr_rowid, rank()over(order by n) rnk
from test t
where t.n > get_rowids_by_rank.n
order by n
)
loop
if r.rnk <= max_rank then
pipe row (r.chr_rowid);
else
exit;
end if;
end loop;
return;
end;
/
select/*+ leading(r t) use_nl(t) */
t.*
from table(get_rowids_by_rank(1, 3)) r
,test t
where t.rowid = chartorowid(r.column_value)
/
[/sourcecode]

[collapse]
In that case the fetch from a table will stop when rnk will be larger than max_rank

Little quiz: Ordering/Grouping – Guess the output

Posted on by Posted in curious, oracle, SQL 1,795 Page views Leave a comment

How many times have you guessed the right answer? 🙂

1

[sourcecode language=”SQL”]
select * from dual order by -1;
select * from dual order by 0;
[/sourcecode]

[collapse]
2

[sourcecode language=”SQL”]
select * from dual order by -(0.1+0/1) desc;
select 1 n,0 n,2 n,0 n,1 n from dual group by grouping sets(1,2,3,2,1,0) order by -(0.1+0/1) desc;
[/sourcecode]

[collapse]
3

[sourcecode language=”SQL”]
select 1 n,0 n,2 n,0 n,1 n from dual group by grouping sets(1,2,3,2,1,0) order by 0;
select 1 n,0 n,2 n,0 n,1 n from dual group by grouping sets(1,2,3,2,1,0) order by 0+0;
select 1 n,0 n,2 n,0 n,1 n from dual group by grouping sets(1,2,3,2,1,0) order by 3+7 desc;
select 1 n,0 n,2 n,0 n,1 n from dual group by grouping sets(1,2,3,2,1,0) order by -(3.1+0f) desc;
[/sourcecode]

[collapse]
4

[sourcecode language=”SQL”]
select column_value x,10-column_value y from table(ku$_objnumset(5,4,3,1,2,3,4)) order by 1.9;
select column_value x,10-column_value y from table(ku$_objnumset(5,4,3,1,2,3,4)) order by 2.5;
select column_value x,10-column_value y from table(ku$_objnumset(5,4,3,1,2,3,4)) order by 2.7 desc;
select column_value x,10-column_value y from table(ku$_objnumset(5,4,3,1,2,3,4)) order by -2.7 desc;
[/sourcecode]

[collapse]