索引結合スキャン

• MySQL

(8.0.26)
https://dev.mysql.com/doc/refman/8.0/ja/index-merge-optimization.html#index-merge-intersection

drop table tab1;
create table tab1(
    col1 bigint 
   ,col2 bigint
   ,col3 bigint
   ,col4 varchar(1000)
   ,col5 varchar(1000)
   ,col6 varchar(1000)
   ,col7 varchar(1000)
   ,col8 varchar(1000)
   ,col9 varchar(1000)
   ,col10 varchar(1000)
   ,col11 varchar(1000)
   ,col12 varchar(1000)
   ,col13 varchar(1000)
   ,col14 varchar(1000)
   ,col15 varchar(1000)
   );

drop procedure proc1;

delimiter //
create procedure proc1(in x int)
begin
  declare i int;
  set i = 0;
  start transaction;
  while i < x do
    set i = i + 1;
    insert into tab1 values(
     i
    ,mod(i,20)
    ,mod(i,20)
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    ,concat( md5(rand() ),md5( rand() ),md5( rand() ) )
    );
  end while;
  commit;
end
//
delimiter ;

call proc1(1000000);

select count(*) from tab1;
select * from tab1 order by rand() limit 20;
alter table tab1 add constraint tab1pk primary key (col1);
create index ind12 on tab1(col2);
create index ind13 on tab1(col3);

analyze table tab1;

explain analyze
select /* NO_INDEX_MERGE(t1 ind12,ind13) */ max(t1.col1)
from tab1 t1
where t1.col2 = 1
and  t1.col3 = 1
;
show warnings;

→Index range scan on t1 using intersect(ind12,ind13)
0.03 sec

explain analyze
select /* NO_INDEX_MERGE(t1 ind12,ind13) */ max(t1.col2)
from tab1 t1
where t1.col2 = 1
and  t1.col3 = 1
;
show warnings;

→Index range scan on t1 using intersect(ind12,ind13)
0.03 sec

explain analyze
select /*+ NO_INDEX_MERGE(t1 ind12,ind13) */ max(t1.col15)
from tab1 t1
where t1.col2 = 1
and  t1.col3 = 1
;
show warnings;

→Index range scan on t1 using intersect(ind12,ind13)
4.77 sec

インデックスマージ交差アクセスアルゴリズム
インデックスマージ結合アクセスアルゴリズム

※範囲条件の場合は主キーのみ適用可能

• Oracle

(19c)

https://docs.oracle.com/cd/F19136_01/tgsql/optimizer-access-paths.html#GUID-21258F63-7506-4019-9FB4-323E9D2DE087

drop table tab1 purge;
create table tab1(
    col1 int 
   ,col2 int
   ,col3 int
   ,col4 varchar2(1000)
   ,col5 varchar2(1000)
   ,col6 varchar2(1000)
   ,col7 varchar2(1000)
   ,col8 varchar2(1000)
   ,col9 varchar2(1000)
   ,col10 varchar2(1000)
   ,col11 varchar2(1000)
   ,col12 varchar2(1000)
   ,col13 varchar2(1000)
   ,col14 varchar2(1000)
   ,col15 varchar2(1000)
  );

declare
begin
for i in 1..1000000 loop
  insert into tab1 values(
    i
   ,i
   ,i
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   ,standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')||standard_hash(dbms_random.value(), 'MD5')
   );
  end loop;
end;
/

commit;

select count(*) from tab1;
select * from tab1 order by dbms_random.value()  fetch first 20 rows only;
alter table tab1 add constraint tab1pk primary key (col1);
create index ind12 on tab1(col2);
create index ind13 on tab1(col3);

set time on
set timing on

exec dbms_stats.gather_table_stats(user,'TAB1');

explain plan for
select /* INDEX_JOIN(t1) */ max(t1.col1)
from tab1 t1
where t1.col2 <= 50000
and  t1.col3 <= 50000
;

select * from table(dbms_xplan.display(format=>'ALL') );

→BITMAP CONVERSION FROM ROWIDS+BITMAP AND+BITMAP CONVERSION TO ROWIDS
経過: 00:00:00.06

explain plan for
select /* INDEX_COMBINE(t1) */ max(t1.col2)
from tab1 t1
where t1.col2 <= 50000
and  t1.col3 <= 50000
;

select * from table(dbms_xplan.display(format=>'ALL') );

→INDEX JOIN
経過: 00:00:00.04

索引結合スキャンは、問合せによってリクエストされたすべての列をまとめて返す、
複数の索引のハッシュ結合です。
すべてのデータは索引から取得されるため、データベースは表にアクセスする必要がありません。

explain plan for
select  max(t1.col15)
from tab1 t1
where t1.col2 <= 50000
and  t1.col3 <= 50000
;

select * from table(dbms_xplan.display(format=>'ALL') );

→BITMAP CONVERSION FROM ROWIDS+BITMAP AND+BITMAP CONVERSION TO ROWIDS
経過: 00:00:00.07

INDEX_COMBINEヒント ⇒ BITMAP ANDを使用する
INDEX_JOINヒント ⇒ 索引結合を使用する

• PostgreSQL

(14)
https://www.postgresql.jp/document/13/html/indexes-bitmap-scans.html

drop table tab1;
create table tab1(
    col1 bigint 
   ,col2 bigint 
   ,col3 bigint 
   ,col4 varchar(1000)
   ,col5 varchar(1000)
   ,col6 varchar(1000)
   ,col7 varchar(1000)
   ,col8 varchar(1000)
   ,col9 varchar(1000)
   ,col10 varchar(1000)
   ,col11 varchar(1000)
   ,col12 varchar(1000)
   ,col13 varchar(1000)
   ,col14 varchar(1000)
   ,col15 varchar(1000)
   );
   

start transaction;
insert into tab1 select
   g
  ,g
  ,g
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
  ,md5(random()::text)||md5(random()::text)||md5(random()::text)
from generate_series(1,1000000) g;

commit;

select count(*) from tab1;
select * from tab1 order by random() limit 20;
alter table tab1 add constraint tab1pk primary key (col1);
create index ind12 on tab1(col2);
create index ind13 on tab1(col3);

\timing 1
\pset pager 0
set pg_hint_plan.debug_print = on;

analyze tab1;

explain analyze
select max(t1.col1)
from tab1 t1
where t1.col2 <= 50000
and  t1.col3 <= 50000
;

→Index Scan using ind13 on tab1 t1
時間: 13.673 ミリ秒

explain analyze
select max(t1.col2)
from tab1 t1
where t1.col2 <= 50000
and  t1.col3 <= 50000
;

→Index Scan Backward using ind12 on tab1 t1
時間: 0.370 ミリ秒

explain analyze
select  max(t1.col15)
from tab1 t1
where t1.col2 <= 50000
and  t1.col3 <= 50000
;

→Index Scan using ind13 on tab1 t1
時間: 22.824 ミリ秒

BitmapScanヒントでBitmapAndとなるが、いずれも処理時間は悪化

• SQL Server

(2019)

drop table tab1;
create table tab1(
    col1 bigint not null
   ,col2 bigint 
   ,col3 bigint 
   ,col4 varchar(1000)
   ,col5 varchar(1000)
   ,col6 varchar(1000)
   ,col7 varchar(1000)
   ,col8 varchar(1000)
   ,col9 varchar(1000)
   ,col10 varchar(1000)
   ,col11 varchar(1000)
   ,col12 varchar(1000)
   ,col13 varchar(1000)
   ,col14 varchar(1000)
   ,col15 varchar(1000)
   );

set nocount on
declare @i int;
set @i = 1;
begin transaction;
while @i <= 100000
begin
  insert into tab1 values(
     @i
    ,@i
    ,@i
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    ,master.dbo.fn_varbintohexstr(HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) )+HASHBYTES('MD5',cast(rand() as varchar) ) )
    );

 set @i = @i + 1;
end
commit;

select count(*) from tab1;
select top 20 * from tab1 order by newid();
alter table tab1 add constraint tab1pk primary key (col1);
create index ind12 on tab1(col2);
create index ind13 on tab1(col3);

set statistics time on

update statistics tab1;

select max(t1.col1)
from tab1 t1
where t1.col2 <= 50000
and  t1.col3 <= 50000
;

→Clustered Index Scan
経過時間 = 32 ミリ秒

select max(t1.col2)
from tab1 t1
where t1.col2 <= 50000
and  t1.col3 <= 50000
;

→Index Seek(ind12)+key lookup
経過時間 = 0 ミリ秒

select  max(t1.col15)
from tab1 t1
where t1.col2 <= 50000
and  t1.col3 <= 50000
;

→Clustered Index Scan
経過時間 = 36 ミリ秒

SQL Serverには索引結合スキャンに類するものはない模様