B*Tree 인덱스

• B*Tree 인덱스는 데이터베이스에서 가장 일반적으로 사용되는 인덱스 구조며， 가령 숫자 컬럼에 인덱스를 가지고 있다면 개념적인 구조는 그림 11-1 처럼될것이다.

• 트리의 최하위 레벨 블록은 리프 노드(leaf node) 또는 리프 블록 (leaf block)이라고 불리는데，모든 인덱스 키와 인덱싱되는 로우를 가리키는 rowid를 포함하고 있다.
• 내부 블록인 리프 노드 위의 블록은 브랜치 블록(branch block)이라고 알려져 있다.

• 브랜치 블록은 인덱스 구조를 이동하는 데 사용된다. 인덱스에 42라는 값을 찾고자 한다면 트리의 최상위에서 출빌F해서 왼쪽으로 이통한다. 블록을 조사해서 우리
  가 필요한 블록을 찾아서 42부터 50 범위의 블록으로 이동한다.
• 인덱스 리프 노드는 실제로 양 방향 linked list이다. 리프노드에서 시작점을 찾은다음에는값의 정렬된 순서로 읽어나가기만하면 된다.

 where x between 20 and 30

• 오라클은 20 이상의 값중 가장작은 키 값을포함하는 첫 번째 리프블록을 찾은후에 30보다큰값을 발견할 때까지 수평 방향으로 리프 노드의 리스트를 읽어나가기만 하면 된다.
• B*Tree 인덱스에서는 유일하지 않은 엔트리는 존재하지 않는다. 유니크하지 않은 인덱스 (non-unique index) 에도 오라클은 인덱스 키 값에 추가적으로 rowid를 기타 컬럼으로 추가하게 되기 때문에 유일하게 된다.
  • ex) 예를 들어 CREATE INDEX 1 ON T( X. Y)라는 인덱스는 개념적으로 CREATE UNIQUE INDEX 1 ON T{X, Y, ROWID)라고 볼 수 있다
• B*Tree 특성 중 하나는 모든 리프 블록이 트리 안에서 모두 통일한 레벨에 존재한다는 것이다. 어떠한 조건이라도 루트 블록부터 리프 블록까지는 동일한 숫자의 블록을 방문한다 인덱스는 높이가 균형적이라고 말할 수 있다. 대부분B*Tree 인덱스는 수백만 개 로우를 갖고 있더라도 높이가 2 또는 3 이 된다.

• BLEVEL의 값은 통계정보가 수집된 이후에 USER_INDEXES 와 같은 일반 딕셔너리 테이블에서 조회할 수 있다.
• 숫자 컬럼이 기본 키로 설정된 10,000,000개 로우를 가진 테이블이 있다고 하자

select index_name , blevel , num_rows
  from user_indexes
 where table_name = 'BIG_DATA'

INDEX_NAME                         BLEVEL   NUM_ROWS
------------------------------ ---------- ----------
BIG_DATA_IDX                            2    1000000

• BLEVEL 2는 HEIGHT 3을 의미한다. 리프 블록을 찾는 데 두 번의 1/0 결과적으로는 세 번의 1/0를 수행한다는 것을 의미한다. 그래서 주어진 인덱스 키 값을 찾는 데 세 번의I/0를 예상할 수 있다

select x from big_data where x = 42;

----------------------------------------------------------------------------------
| Id  | Operation         | Name         | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |              |     1 |    13 |     2   (0)| 00:00:01 |
|*  1 |  INDEX UNIQUE SCAN| BIG_DATA_IDX |     1 |    13 |     2   (0)| 00:00:01 |

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          3  consistent gets
          0  physical reads
          0  redo size
        532  bytes sent via SQL*Net to client
        519  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

SQL> select x from big_data where x = 12345;


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
          3  consistent gets
          1  physical reads
          0  redo size
        534  bytes sent via SQL*Net to client
        519  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

SQL> select x from big_data where x = 1234567;

Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
          3  consistent gets
          5  physical reads
          0  redo size
        342  bytes sent via SQL*Net to client
        508  bytes received via SQL*Net from client
          1  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          0  rows processed

인덱스 키 압축

• B*Tree 인덱스를 압축할 수 있다는 것이다 ZIP 파일 압축과 같은 방식이 아니라 복합컬럼 (다수 컬럼) 인덱스 (결합 인덱스) 의 중복을 제거하는 것이다 (반복되는 값에 대한 공간 오버헤드를 줄이는 것이다).
• 압축 키 인덱스의 기본 개념은 모든 엔트리는 접두사 (prefix)와 접미사 (suffix) 두 부분으로나누어진다는 것이다. 접두사는 복합 컬럼의 앞부분으로 중복되는 값이 많이 존재하는 부분이고， 접미사는 인덱스 키 컬럼의 뒷부분으로 같은 접두사 안에서 고유한 값을 가진다.

다음으로 인덱스 키를 압축하여 재생성해보기

create table t
as select * from all_objects
where rownum <= 50000;

create index t_idx on t(owner , object_type , object_name);

analyze index t_idx validate structure ;

create table idx_stats
as
select 'noncompressed' what , a.*
from index_stats a;

create table idx_stats
as
select 'noncompressed' what , a.*
from index_stats a;

drop index t_idx;

create index t_idx on
t(owner,object_type,object_name)
compress &1;
analyze index t_idx validate structure;
select 'compress &1' ,  height , lf_blks , br_blks , btree_space , opt_cmpr_count , opt_cmpr_pctsave  from index_stats a;

--select what , height , lf_blks , br_blks , btree_space , opt_cmpr_count , opt_cmpr_pctsave
--from idx_stats;

WHAT              HEIGHT    LF_BLKS    BR_BLKS BTREE_SPACE OPT_CMPR_COUNT OPT_CMPR_PCTSAVE
------------- ---------- ---------- ---------- ----------- -------------- ----------------
noncompressed          3        362          3     2920096              2               28
compress 1             3        324          3     2614800              2               19
compress 2             3        259          3     2095060              2                0
compress 3             3        404          3     3254480              2               35

결론

• 1 개 컬럼을 압축할 경우는 압축하지 않은 인덱스의 89% 정도 크기 (B1REE_SP ACE) 인 것을 볼 수 있다.
• 압축 2를 사용했을 경우는 더 많은 공간이 절약되었다. 비압축 인덱스 크기의 72% 정도 크기로 감소하였고 인덱스 높이가 3에서 2로 줄어들어 각각의
  블록에 저장할 수 있었다.
• 압축3 의 경우는 오히려 안좋아졌다. 이유는 접두사의 중복은 제거하여 반복되는 공간은 절약할 수 있었지만， 리프 블록에 압축 스키마 정보 4바이트 크기의 오버헤드를 추가했기 때문이다.
• 압축은 비용을 수반한다. I/0 시간이 줄어드는 반면 CPU시간이 증가하는 반대급부가 발생한다.
• 압축된 인덱스를사용하게 되면 이전보다 더 많은 인덱스 엔트리가 버퍼 캐시에 존재하게 되고 버퍼 캐시의 히트율(hit ratio) 이 증가함으로써 물리적 I/0는 감소하
  게 된다. 그러나 인덱스를 다루기 위해서 CPU를 조금 더 사용한다.

리버스키 인덱스

• B*Tree 인덱스의 다른 특정은 키를 역으로 뒤집을 수 있다.(컬럼값의 역순)
• 리버스 키 인덱스는 특별한 상황과 특별한 목적을 위해 설계되었다. 오라클 RAC 환경에서 시퀀스 값 또는 타임스탬프 (timestamp) 값으로 생성되는 컬럼의 인덱스와 같이 오른쪽 (right-hand-side) 으로 증가히는 인덱스에 대한 리프 블록의 경합을 줄이기 위해 고안되었다.
• 일반적인 인덱스가 적용되는 모든 경우에 사용할 수 없다
• where x > 5 같은 조건 인덱스 사용안됨(인덱스의 데이터가 X 값으로 정렬되어 저장되어 있지 않고 REVERSE(X) 에 의해 저장되어 있기 때문)
• 결합 인덱스 (X. Y) 인 경우 ( where x = 5 ) 같은 조건은 리버스 키 인덱스를 사용할 수 있다

drop table t ;
create table t  tablespace assm
as
select 0 id, a.\*
from all_objects a
where 1=0;

alter table t
add constraint t_pk
primary key(id)
using index ( create index  t_pk on t (id) reverse tablespace assm);

create sequence s cache 1000;

create or replace procedure do_sql
as
begin
for x in ( select rownum r, all_objects.* from all_objects )
loop
  insert into t (ID
                ,OWNER
                ,OBJECT_NAME
                ,SUBOBJECT_NAME
                ,OBJECT_ID
                ,DATA_OBJECT_ID
                ,OBJECT_TYPE
                ,CREATED
                ,LAST_DDL_TIME
                ,TIMESTAMP
                ,STATUS
                ,TEMPORARY
                ,GENERATED
                ,SECONDARY
                ,NAMESPACE
                ,EDITION_NAME)
                values
                ( s.nextval
                ,x.OWNER
                ,x.OBJECT_NAME
                ,x.SUBOBJECT_NAME
                ,x.OBJECT_ID
                ,x.DATA_OBJECT_ID
                ,x.OBJECT_TYPE
                ,x.CREATED
                ,x.LAST_DDL_TIME
                ,x.TIMESTAMP
                ,x.STATUS
                ,x.TEMPORARY
                ,x.GENERATED
                ,x.SECONDARY
                ,x.NAMESPACE
                ,x.EDITION_NAME
                );
      if ( mod(x.r , 100) = 0 )
      then
        commit;
      end if;
end loop;
commit;
end ;
/

pl-sql , pro*C을 동시 수행했을때 비교

내림차순 인덱스

• 내림치순 인덱스는 B*Tree 인덱스의 확장 기능으로서 오라클 8i 버전에서 소개되었다.
• 오름차순(작은값에서 큰 값으로) 대신에 내림차순(큰 값에서 작은 값으로)으로 정렬되어 저장하는 인덱스를 의미한다.
• 오라클 8i 버전 이상에서의 DESC 키워드는 인덱스의 생성 및 사용방식에 변화를 가져왔다

예제

-- 인덱스 역순으로 읽은예 - SORT 작업이 없음
drop table t ;
create table t
as
select *
from all_objects;

create index t_idx on t( owner ,object_type , object_name);
begin
dbms_stats.gather_table_stats
( user, 'T' , method_opt=> 'for all indexed columns' );
end;
select owner , object_type
from t
where owner between 'T' and 'Z'
and object_type is not null
order by owner DESC, object_type DESC;


Plan hash value: 2685572958

-------------------------------------------------------------------------------------
| Id  | Operation                   | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |       |   357 |  5712 |     5   (0)| 00:00:01 |
|*  1 |  INDEX RANGE SCAN DESCENDING| T_IDX |   357 |  5712 |     5   (0)| 00:00:01 |
-------------------------------------------------------------------------------------

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

   1 - access("OWNER">='T' AND "OWNER"<='Z')
       filter("OBJECT_TYPE" IS NOT NULL)

-- 인덱스 복합 수행 - SORT 작업이 생김
select owner , object_type
from t
where owner between 'T' and 'Z'
and object_type is not null
order by owner DESC, object_type ASC;

Plan hash value: 2813023843

---------------------------------------------------------------------------
| Id  | Operation         | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |       |   357 |  5712 |     6  (17)| 00:00:01 |
|   1 |  SORT ORDER BY    |       |   357 |  5712 |     6  (17)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN| T_IDX |   357 |  5712 |     5   (0)| 00:00:01 |
---------------------------------------------------------------------------

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

   2 - access("OWNER">='T' AND "OWNER"<='Z')
       filter("OBJECT_TYPE" IS NOT NULL)

--owner 인덱스 내림차순 , object_type 오름차순 수행 - SORT 작업이 없음
drop index t_idx;

create index t_idx on
t(owner desc , object_type asc) ;

select owner , object_type
from t
where owner between 'T' and 'Z'
and object_type is not null
order by owner DESC, object_type ASC;

Plan hash value: 2946670127

--------------------------------------------------------------------------
| Id  | Operation        | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT |       |   357 |  5712 |     2   (0)| 00:00:01 |
|*  1 |  INDEX RANGE SCAN| T_IDX |   357 |  5712 |     2   (0)| 00:00:01 |
--------------------------------------------------------------------------

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

   1 - access(SYS_OP_DESCEND("OWNER")>=HEXTORAW('A5FF')  AND
              SYS_OP_DESCEND("OWNER")<=HEXTORAW('ABFF') )
       filter(SYS_OP_UNDESCEND(SYS_OP_DESCEND("OWNER"))>='T' AND
              SYS_OP_UNDESCEND(SYS_OP_DESCEND("OWNER"))<='Z' AND "OBJECT_TYPE" IS NOT
              NULL)

언제 B*Tree 인덱스를 사용해야 하는가?

• 전체 테이블 로우 수에 비해 선택하려는 로우 수가 적은 경우는 B*Tree 인덱스만을 사용한다.
• 테이블의 많은 로우를 처리하지만， 인덱스만으로 처리할수 있다면 B*Tree 인덱스를 사용한다.
• 위의 상황에 인덱스를 사용하는 두 가지 방법

테이블의 로우에 접근하는 방법으로서

• 테이블의 로우를 액세스하기 위해 인덱스를 읽을 수 있을것이다. 여기서는 전체 테이블의 로우 수에 비해 매우 적은 로우를 접근하려고 할 때다.

select owner, status
  from t
where owner = USER;


Plan hash value: 470836197

-------------------------------------------------------------------------------------
| Id  | Operation                   | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |       |  3709 | 48217 |    23   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| T     |  3709 | 48217 |    23   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | T_IDX |   247 |       |    15   (0)| 00:00:01 |
-------------------------------------------------------------------------------------

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

   2 - access(SYS_OP_DESCEND("OWNER")=SYS_OP_DESCEND(USER@!))
       filter(SYS_OP_UNDESCEND(SYS_OP_DESCEND("OWNER"))=USER@!)

• TABLE ACCESS BY INDEX ROWID를 수행해야만하는 경우에는 태이블 전체 블록 중 소량만을 읽도록 해야만 한다. 즉 전체 로우 중에 소량의 로우를읽어서 최대한 빨리 첫 번째 로우를 추출할 필요가 있는지 확인해 야 한다. 만약 테이블 로우의 대부분을 추출해야 하는 경우라면(추출 대상 로우가 20% 이상이라면)，B*Tree를 경유하는 것이 태이블 전체를 스캔하는 것보다 더 오래 걸릴 것이다.

쿼리에 응답하는 수단으로서

• 인덱스가 쿼리에 응답하기 위한 충분한 내용이 있는 경우라서 테이블에 접근할 필요가 없는 경우다. 이 경우는 인덱스가 테이블의 또 다른 축소판이 될것이다.

select count(*)
  from t
where owner = USER;

Plan hash value: 293504097

---------------------------------------------------------------------------
| Id  | Operation         | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |       |     1 |     6 |    15   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE   |       |     1 |     6 |            |          |
|*  2 |   INDEX RANGE SCAN| T_IDX |  3709 | 22254 |    15   (0)| 00:00:01 |
---------------------------------------------------------------------------

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

   2 - access(SYS_OP_DESCEND("OWNER")=SYS_OP_DESCEND(USER@!))
       filter(SYS_OP_UNDESCEND(SYS_OP_DESCEND("OWNER"))=USER@!)

• 인덱스만으로 결과를 처리하는 방식에 관한 이야기다. 하나의 인덱스 블록을 읽어서 많은 로우를 처리하고 다음 인덱스 블록을 읽어 나가는 방식으로 진행하고 테이블에는 접근하지 않았다.

물리구조

• 데이터를 물리적 디스크에 구조화하는 방식은 데이터 처리 에 영향을 주고 인덱스 액세스 비용에 영향을 주게 된다.
• 데이터를 테이블에 삽입할 때 시퀀스에 의해 생성되는 기본 키를 가진 테이블은 순차적으로 증가하는 시퀀스 숫자 값을 순서로 다음 로우와 서로 인접해 있게 된다 ( 일반적으로 기본키 값이 서로 가까운 로우들은 물리적으로도 인접한 위치에 있게 된다)

select * from T where primary_key between :x and :y

• 추출하고자하는 로우가 일반적으로 동일블록에 저장될 수 있다 이 경우에는 많은 양의 로우들에 접근하더라도 인덱스 범위 스캔이 효율적이다. 왜냐하면 데이터 들이 인접해 있으므로 반복적으로 읽게될 블록들이 대부분 캐시되어 있을 것 이기 때문이다.

로우가 인접해 있지 않은 경우에 동일 인덱스를 사용하게 되면，속도에 심각한 문제가 발생된다.

drop table colocated ;
create table colocated ( x int, y varchar2(80) );

begin
for i in 1 .. 100000
loop
insert into colocated(x ,y)
values (i, rpad(dbms_random.random,75,'*' ));
end loop;
end;

alter table colocated
add constraint colocated_Pk
primary key(x);

begin
dbms_stats.gather_table_stats( user, 'COLOCATED' ) ;
end;

• 블록의 크기가 8킬로바이트고 한 블록당 100개의 의 로우가 저장되는 앞의 예와 같은 테이블인 경우， 이테이블에는 X=l,2,3 이 같은 블록에 존재할 가능성이 매우 크다. 이제 의도적으로 이 테이블의 로우를 분산시켜 보자 COLOCATED 테이블에 랜덤 숫자로 구성된 컬럼 Y를 이용하여 데이터를 분산시켜서 더 이상 기본키값의 순서로 정렬 되 지 않도록 할 것이다.

create table disorganized
as
select x,y
from colocated
order by y;

alter table disorganized
add constraint disorganized_Pk
primary key (x);

begin
dbms_stats.gather_table_stats( user, 'disorganized' ) ;
end;

• TKPROF 결과

select *
from
 colocated where x between 20000 and 40000


call     count       cpu    elapsed       disk      query    current        rows
------- ------  -------- ---------- ---------- ---------- ----------  ----------
Parse        5      0.00       0.00          0          0          0           0
Execute      5      0.00       0.00          0          0          0           0
Fetch       55      0.04       0.03          0        465          0       25250
------- ------  -------- ---------- ---------- ---------- ----------  ----------
total       65      0.04       0.03          0        465          0       25250

Misses in library cache during parse: 1
Optimizer mode: ALL_ROWS
Parsing user id: 84

Rows     Row Source Operation
-------  ---------------------------------------------------
   5050  TABLE ACCESS BY INDEX ROWID COLOCATED (cr=93 pr=0 pw=0 time=2524 us cost=283 size=1620162 card=20002)
   5050   INDEX RANGE SCAN COLOCATED_PK (cr=22 pr=0 pw=0 time=757 us cost=43 size=0 card=20002)(object id 74640)

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

select /*+ index( disorganized disorganized_pk ) */* from disorganized
where x between 20000 and 40000

call     count       cpu    elapsed       disk      query    current        rows
------- ------  -------- ---------- ---------- ---------- ----------  ----------
Parse        5      0.00       0.00          0          0          0           0
Execute      5      0.00       0.00          0          0          0           0
Fetch       55      0.06       0.05          0      25355          0       25250
------- ------  -------- ---------- ---------- ---------- ----------  ----------
total       65      0.06       0.06          0      25355          0       25250

Misses in library cache during parse: 1
Optimizer mode: ALL_ROWS
Parsing user id: 84

Rows     Row Source Operation
-------  ---------------------------------------------------
   5050  TABLE ACCESS BY INDEX ROWID DISORGANIZED (cr=5071 pr=0 pw=0 time=8078 us cost=20041 size=1620162 card=20002)
   5050   INDEX RANGE SCAN DISORGANIZED_PK (cr=22 pr=0 pw=0 time=631 us cost=43 size=0 card=20002)(object id 74642)

• 물리 데이터의 구조의 차이가 다른 결과를 가져왔다.

테이블 전체 블록 수

select
a.index_name,
b.num_rows,
b.blocks,
a.clustering_factor
from user_indexes a, user_tables b
where index_name in ( 'COLOCATED_PK', 'DISORGANIZED_PK')
and a.table_name = b.table_name

INDEX_NAME                       NUM_ROWS     BLOCKS CLUSTERING_FACTOR
------------------------------ ---------- ---------- -----------------
COLOCATED_PK                       100000       1252              1190
DISORGANIZED_PK                    100000       1219             99921

• DISORGANIZED 테이 블에 대한 수행 결과는 앞에서 살펴본 것처럼 간단하게 계산할 수 있다.20,000 + 논리 1/ 0를 수행할 것을 예상했다
• 반면에 물리적으로 COLOCATED된 데이터 는 더 적은 논리 I/0를 수행하였다.
• 실제 운영 시스템에서 데이터를 덤프해서 개발 서버에 로드하는 경우에 "이 서버에서 다르게 동작할까， 동일하게 동작할까?"라는 질문에 대한 좋은 답변 중 하나가 될 것이다. 실제로 동일하게 동작하지 않는다.