2007/09/10

Задача о поиске свободного слота (дискуссия программистов, работающих с MySQL и Oracle)

Решение задачи возможно с использованием двух подходов:
1) «универсальный» или «независимый от платформы» (а, скорее, продиктованый возможностями, например, MySQL);
2) с использованием возможностей конкретной СУБД (в данном случае, естесственно, речь пойдет об Oracle).

Исходные данные:

SQL> select * from v$version;

BANNER
----------------------------------------------------------------
Oracle Database 10g Enterprise Edition Release 10.2.0.1.0 - Prod
PL/SQL Release 10.2.0.1.0 - Production
CORE 10.2.0.1.0 Production
TNS for 32-bit Windows: Version 10.2.0.1.0 - Production
NLSRTL Version 10.2.0.1.0 - Production

SQL> sho parameter db_block_size

NAME TYPE VALUE
------------------------------------ ----------- ------------------------------
db_block_size integer 8192

SQL> drop table slots;

Table dropped.

SQL> create table slots (
2 slot_id number,
3 slot_pad char(2000),
4 primary key (slot_id)) organization index;

Table created.

SQL> insert into slots (slot_id,slot_pad)
2 select rownum as slot_id, rpad(rownum,2000,'0') from all_objects where rownum<101;

100 rows created.

SQL> delete from slots where slot_id=&a;
Enter value for a: 51
old 1: delete from slots where slot_id=&a
new 1: delete from slots where slot_id=51

1 row deleted.

SQL> delete from slots where slot_id=&a;
Enter value for a: 52
old 1: delete from slots where slot_id=&a
new 1: delete from slots where slot_id=52

1 row deleted.

SQL> delete from slots where slot_id=&a;
Enter value for a: 78
old 1: delete from slots where slot_id=&a
new 1: delete from slots where slot_id=78

1 row deleted.

SQL> exec dbms_stats.gather_table_stats(ownname=>user,tabname=>'slots',cascade=>true)

PL/SQL procedure successfully completed.

SQL> select INDEX_NAME,BLEVEL,LEAF_BLOCKS from user_indexes where TABLE_NAME='SLOTS';

INDEX_NAME BLEVEL LEAF_BLOCKS
------------------------------ ---------- -----------
SYS_IOT_TOP_73146 1 34

Трассировка иллюстрирует различия.

Подход 1:

select min(s2)+1
from (
select a1.slot_id s1, a2.slot_id s2 from slots a1, slots a2
where a1.slot_id(+)=a2.slot_id+1)
where s1 is null

call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.00 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 0.00 0.00 0 138 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 0.00 0.00 0 138 0 1

Rows Row Source Operation
------- ---------------------------------------------------
1 SORT AGGREGATE (cr=138 pr=0 pw=0 time=2937 us)
4 FILTER (cr=138 pr=0 pw=0 time=2883 us)
97 NESTED LOOPS OUTER (cr=138 pr=0 pw=0 time=2714 us)
97 INDEX FAST FULL SCAN SYS_IOT_TOP_1396080 (cr=39 pr=0 pw=0 time=639 us)(object id 1396081)
93 INDEX UNIQUE SCAN SYS_IOT_TOP_1396080 (cr=99 pr=0 pw=0 time=1322 us)(object id 1396081)
********************************************************************************


Подход 2:

select min(slot_id)+1
from (
select slot_id,
(lead(slot_id) over (order by slot_id))-slot_id delta_slot_id
from slots)
where delta_slot_id>1

call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.00 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 0.00 0.00 0 39 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 0.00 0.00 0 39 0 1

Rows Row Source Operation
------- ---------------------------------------------------
1 SORT AGGREGATE (cr=39 pr=0 pw=0 time=1118 us)
3 VIEW (cr=39 pr=0 pw=0 time=1090 us)
97 WINDOW SORT (cr=39 pr=0 pw=0 time=974 us)
97 INDEX FAST FULL SCAN SYS_IOT_TOP_1396080 (cr=39 pr=0 pw=0 time=381 us)(object id 1396081)

********************************************************************************


Можно пойти дальше и, применив некоторые ухищрения, получить следующие результаты:

declare
cursor a1 is select /*+ NO_INDEX_FFS(ss)*/ ss.slot_id from slots ss order by 1;
curr number;
prev number := null;
type t_num is table of number;
nums t_num;
begin
open a1;
loop
fetch a1 bulk collect into nums limit 3;
/*processing*/
if nums.count>0 then
for i in nums.first..nums.last loop
curr:=nums(i);
exit when curr-nvl(prev,curr)>1;
prev:=curr;
end loop;
end if;
exit when curr-nvl(prev,curr)>1;
exit when a1%notfound;
end loop;
if prev!=curr then
dbms_output.put_line('Empty slot is: '||(prev+1));
else
dbms_output.put_line('Empty slot not found.');
end if;
close a1;
end;

call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.00 0 0 0 0
Execute 1 0.00 0.00 0 0 0 1
Fetch 0 0.00 0.00 0 0 0 0
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 2 0.00 0.00 0 0 0 1

********************************************************************************

SELECT /*+ NO_INDEX_FFS(ss)*/ SS.SLOT_ID
FROM
SLOTS SS ORDER BY 1

call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.01 0.00 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 17 0.00 0.00 0 19 0 51
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 19 0.01 0.00 0 19 0 51

Rows Row Source Operation
------- ---------------------------------------------------
51 INDEX FULL SCAN SYS_IOT_TOP_73164 (cr=19 pr=0 pw=0 time=283 us)(object id 73165)

********************************************************************************

В итоге, имеем еще меньшее использование ресурсов. В этом случае 19 LIO получено для первого свободного слота с номером 51, для такой реализации LIO будет зависеть от данных и, в большинстве случаев, все же будет меньше, чем то, что получено в подходе 2.

No comments: