#title Index Seek 
[[TableOfContents]]

==== Index Seek란? ==== 
Index Seek는 Non-Clustered Index를 인덱스 트리를 타고 콕콕 찝어서 원하는 데이터에 접근했다고 설명 할 수 있다. Non-Clustered Index는 Dense Index이고, Secondary Index다. (자세한 사항은 [Index]를 참고하기 바란다) 다음과 같은 Query를 수행한다고 가정하자. 

{{{
SELECT * FROM TableA
WHERE ColA IN ('B105', 'C101')

--ColA에 Non-Clustered Index가 생성되어 있다.
--Clustered Index는 생성되지 않았다. 
--이 Query는 실제 실행에서 Index Seek를 한다고 가정한다.
}}}

Non-Clustered Index가 다음과 같이 생겼다고 가정한다. Data Page는 Heap이다. 참고로, 어떤 DBMS이건 데이터의 입/출력은 Byte단위로 일어나지 않는다. DBMS마다 최소 입/출력 단위가 정해져 있다. Oracle이나 Sybase제품은 이러한 최소 입/출력 단위를 조절할 수 있으나 MS-SQL Server는 최소 입/출력 단위가 8KB로 정해져 있다. (즉, 1Byte를 읽기 위해서 8KByte를 읽어야 한다.) 그림의 Index Page, Data Page는 모두 8KB이다.

attachment:index_seek01.jpg

SQL Server는  'B105'를 찾기 위해 다음과 같이 동작한다. (이 동작을 Index Seek라 부른다.)

 1. Root Page를 읽어서 다음에 접근할 Index Page를 찾는다. 'B102'로 시작되는 2번째 Index Page에는 'B102' ~ 'B105'까지 있음을 Root Page에서 알 수 있다.
 1. Index Depth 2이므로 중간 노드가 곧 리프노드이다. Leaf Index Page에서 행로케이터가 가리키는 데이터 페이지의 해당 Row를 읽는다.

SQL Server는  'C101'를 찾기 위해 다음과 같이 동작한다. 

 1. Root Page를 읽어서 다음 Index Page를 찾는다. ('C101'는 'B106'보다 크고 'C104'보다 작으므로 3번째 Index Page에 있음)
 1. Index Depth 2이므로 중간 노드가 곧 리프노드이다. Leaf Index Page에서 행로케이터가 가리키는 데이터 페이지의 해당 Row를 읽는다.

==== 총 몇 Page를 읽었는가? ====
총 몇 Page를 읽었는가? 다음과 같은 2가지 경우가 있다.

 * Non-Unique Index인 경우
 * Unique Index인 경우

'B105'를 찾기 위해 3Page(Index Page = 2, Data Page = 1)를 읽었고, 'C101'를 찾기 위해 또 3Page를 읽었다. 그러므로 총 6Page를 읽었다. 이것은 Unique Index일 경우에 그렇다. 만약 Non-Unique Index라면 'B105' 다음 값까지 읽어야만 'B105'가 마지막이라는 것을 알 수 있으므로 1Page(Index Page 3)까지 읽어야만 한다. 그러므로 만약 Unique하다면 반드시 Unique를 명시하여 인덱스를 생성해 주는 것이 성능상 이득이 있다. 

그러나 실제 총 Data Page는 4Page이므로 인덱스를 이용한 접근(6 or 7 Page)이 I/O가 더 많다. 즉, 입/출력 비용이 더 높다. 또한 Index Seek보다는 Data Page를 처음부터 끝까지 읽어들이면서 필요한 부분만을 추출하는 것[* 이를 Full Scan이라고 한다.]이 훨씬 단순하다. 그러므로 CPU비용도 Index Seek 보다는 Full Scan이 더 적을 것이다. 이러한 이유에서 많은 책에서 적은 Row수를 가지는 테이블에는 인덱스를 생성하지 말라고 하는 것이다. 앞의 Query문에서는 Index Seek를 할 것으로 가정을 했었지만, 실제로 DBMS는 Full Scan으로 최적화 할 것이다. MS-SQL Server의 비용산정공식은 밝혀지지 않았지만 어쨌든 기본적인 비용계산방법은 위와 같다. 그러므로 Index Seek를 할 지 Full Scan을 할 지는 Index를 이용할 때의 I/O와 Full Scan 할 때의 I/O를 비교하여 더 적은 I/O로 접근하는 방법을 택하면 그것이 옵티마이저의 선택과 대부분은 일치할 것이다. 

==== Random Access란? ====
Random Access란, Disk에서 데이터를 접근하는데 물리적인 임의의(정해지지 않은) 위치에 접근한다는 뜻이다. 데이터의 물리적인 위치는 계속적으로 변하기 때문에 말그대로 'Random'한 접근이다. 윈도우즈 OS에서 조각모음이라도 하면 데이터의 물리적인 위치가 변경되지만, 논리적으로는 변함이 없는 것과 같다. 필자가 알기로는 Random Access는 Oracle쪽에서 나온(파일시스템의 용어를 그냥 가져다 쓴 것 같다) 말이다. 누가 갖다 붙였는지 참.. 조낸 어렵게 만들었다. 필자는 Random Access라는 용어를 이해하는데 정말 오랜 시간이 걸렸다. 혼자 책 부여잡고 낑낑대다가 겨우 이해했지만 여러분은 그러지 말기를 바란다. Random Access를 SQL Server 2000에서는 Bookmark Lookup 라고 부르고, SQL Server 2005 이후 버전은 Key Lookup 또는 RID Lookup 이라고 부른다. (용어가 중요한 것은 아니다. 단지 의사소통을 위해 이음동의어라고 알고 있으면 좋다.)  

Random Access는 위의 'B105', 'C101'를 찾는 과정 중 2번째 과정인 ' ''Leaf Index Page에서 행로케이터가 가리키는 데이터 페이지의 해당 Row를 읽는다.'' ' 부분을 Random Access라고 부른다. Random이라는 것은 Data Page와 Data Page내의 행의 위치가 Random이므로 붙여진 이름이다. (책에서 본것은 아니고 필자의 생각이다.) 많은 책에서 Random Access를 줄이라고 하는데 그 이유가 Random에 있기도 하다. 위의 예제에서 모든 Data Page가 Disk상에만 존재하고 Memory상에는 존재하지 않는다고 가정해 보자. SQL Server는 'B105'가 존재하는 Data Page를 Disk에서 읽어서 Memory로 퍼올려야[* Query의 처리 비용이 가장 많이 드는 부분] 한다. 'C101'도 다른 Data Page에 존재하고, Memory에 존재하지 않으므로 Disk에서 Meomory로 Data를 읽어 들여야 한다. 이런 짓을 하는 이유는 CPU는 Memory에만 접근가능다[* 이것이 폰 노이만의 프로그램 내장방식이다.]는 제약이 있는 컴퓨터 구조상의 문제 때문이다. 만약 'B105'와 'C101'이 같은 Data Page에 존재했다면 Disk에서 Memory로 데이터를 퍼올리는 일을 하지 않고 Memory에서 직접 Access하면 되므로 처리 비용이 줄어들 것이다. 그래서 데이터의 정렬 상태 또는 오밀조밀 모여 있는 상태가 성능에 영향을 끼친다고 하는 것이다. 하지만 다음과 같은 쿼리에서는 Random Access가 일어나지 않을 것이다. 

{{{ 
SELECT ColA FROM TableA
WHERE ColA IN ('B105', 'C101')
}}}

Random Access가 일어나지 않는 이유는 Index Page만 읽어도 원하는 결과를 얻을 수 있기 때문이다. 만약 TableA가 ColA, ColB, ColC를 가질 경우 다음과 같은 Query는 Random Access가 일어날 것이다. 

{{{
--ColA에 Non-Clustered Index가 생성되어 있고, Index Seek를 가정한다. 

SELECT ColA, ColB --ColB가 Index만을 읽어서는 모른다. 데이터 페이지를 읽어야만 비로소 ColB를 가져올 수 있다.
FROM TableA 
WHERE ColA IN ('B105', 'C101') 

SELECT ColA, ColB, ColC --ColC로 위와 마찬가지다.
FROM TableA
WHERE ColA IN ('B105', 'C101')

SELECT ColA FROM TableA
WHERE ColA IN ('B105', 'C101')
AND ColB = '2005' --SELECT절에는 명시도지 않았지만 해당 Row가 조건에 맞는지 평가하려면 데이터 페이지를 읽어야 한다. 

SELECT ColA FROM TableA
WHERE ColA IN ('B105', 'C101')
ORDER BY ColC --정렬을 위해서는 ColC가 필요하기 때문에 역시 데이터 페이지를 읽어야 한다. 
}}}

==== Random Access의 부하 ====
실제 데이터에 접근하기 위해서 데이터베이스의 여러 블록이나 페이지등이라 불리워지는 최소입출력 단위로 접근을 해야 한다는 뜻이다. 중요한 것은 1바이트를 읽더라도 DBMS는 최소 입/출력 단위만큼 읽어 들인다는 것이다. MSSQL Server의 경우는 최소 입/출력 단위가 8KB로 정해져 있기 때문에 8KB를 읽어 들인다. 그러므로 Heap이나 Clustered Index가 어떤 컬럼을 기준으로 또는 어떻게 실제 물리적인 형태로 쌓여있는가가 Bookmark Lookup[* Bookmark lookup이므로 SQL Server 2000의 실행 계획이라는 것을 알 수 있다.]에 대한 실질적인 비용을 결정하는 것이다. 

attachment:random_access01.jpg

Bookmark Lookup 비용이 쿼리의 비용을 다 차지하는 것으로 나타났다. 그만큼 많은 페이지에 접근해야만 원하는 데이터를 가져올 수 있음을 알 수 있다. 이것이 바로 실제로 우리가 생각하는 이상과 현실을 차이이다. 


==== Non-Clustered Index와 Clustered Index가 함께 존재한다면? ====
위의 그림은 Heap에서의 Random Access 방법에 대해 이야기 했다. 하지만 Clustered Index와 Non-Clustered Index가 함께 존재한다면 Access 방법이 틀려진다. 만약 많은 삽입/갱신/삭제가 일어났고, ColB(값이 2005, 2006)에 Clustered Index가 생성되어 있다고 가정하면 다음과 같은 정도의 그림이 될 것이다. 

attachment:index_seek02.jpg?width=80%

현재 Clustered Index가 없고, Non-Clustered Index가 존재하는 상황이다. 이런 경우에는 Clustered Index를 생성하면 Non-Clustered Index가 다시 만들어 진다. 왜냐하면 Clustered Index를 구성하기 위해서 Split이나 재배열이 필요하게되면 행로케이터들이 쓸모가 없게 되버리기 때문이다. 만약 인덱스를 다시 생성하지 않는다면 Non-Clustered Index의 Leaf Node에 있는 행로케이터에 가봐야 원래 가리키고 있는 행이 있으리라는 보장이 없다. (정말 재수 있으면 있을 수도 있다) 그러므로 이런 상황에서는 Non-Clustered Index는 다시 만들어 진다. 

Clustered Index를 생성할 때에 Unique를 명시하지 않는 경우[* 당연히 Unique하지 않은 경우는 Clustered Index 생성 자체가 안 된다.]는 유일하게 만들기 위해 4Byte를 추가하여 유일하게 만든다. 왜냐하면 Clustered Index는 페이지를 가리키고 있기 때문(해당 페이지의 첫 행을 가리키고 있다고 보면 된다)에 위의 그림과 같이 Non-Unique한 Clustered Index를 생성했을 경우 Unique하지 않을 경우 엉뚱한 페이지를 가르킬 수도 있기 때문이다. 

==== 확인해 보자 ====
다음의 소스를 보자. 

{{{ 
use pubs
go

exec sp_helpindex titles
/*
index_name        index_description                                 index_keys 
----------------- ------------------------------------------------- ----------
titleind          nonclustered located on PRIMARY                   title      
UPKCL_titleidind  clustered, unique, primary key located on PRIMARY title_id
*/

dbcc show_statistics (titles, titleind)
/*
All density         Average Length       Columns              
------------------- -------------------- ---------------------
5.5555556E-2        33.0                 title
5.5555556E-2        39.0                 title, title_id --> title_id에는 클러스터드 인덱스가 생성되어 있다.
*/
}}}

논클러스터드 인덱스의 All Density에서 논클러스터드 인덱스를 잡을 당시의 title말고도 클러스터드 인덱스인 title_id가 있는 것을 볼 수 있다. 즉, 논클러스터드 인덱스 외에 다른 데이터를 접근할 필요가 있으면 클러스터드 인덱스나 클러스터드 인덱스가 없으면 힙(Heap)에 접근을 해야 하는 데, 여기에서는 title_id에 클러스터드 인덱스가 생성되어 있으므로 dbcc show_statistics의 결과에 나온 것이다. 이런 상황이라면 title뿐만아니라 title_id가 SQL문에 있어도 Bookmark lookup은 볼 수 없다. 왜냐하면 위의 결과에서 보는 바와 같이 논클러스터드 인덱스의 리프노드에 클러스터드 인덱스의 키 값(title에 대응되는 title_id 실제 데이터)이 있기 때문이다. 이것이 실행계획에 보이는 Bookmark lookup이다.

여기서 알 수 있는 또 한가지 사실은 Clutered Index와 Non-Clutered Index를 생성하는 순서가 성능에 영향을 끼친다는 것이다. 만약 Non-Clustered Index를 생성하고 Clustered Index를 생성할 경우 Non-Clustered Index의 Leaf Node는 Clustered Index의 Key Value로 갱신되어야 한다. 그러므로 Clustered Index와 Non-Clustered Index를 혼합하여 생성하는 경우가 있다면 Clustered Index부터 생성하는 것이 유리하다. 
==== unique vs non-unique ====
{{{
use tempdb;

set statistics io on
create table index_test
(
	seq bigint
);

insert index_test
select top 10000 row_number() over(order by(select 1)) seq
from master..spt_values a
	cross join master..spt_values b;

create index idx1 on index_test(seq);	
create unique index idx2 on index_test(seq);

--non unique index
select * from index_test with (index=idx1)
where seq <= 255 --논리적 읽기 수 2, 조건이 seq <= 256 이면 논리적 읽기수 3

--unique index
select * from index_test with (index=idx2)
where seq <= 367 --논리적 읽기 수 2, 조건이 seq <= 368 이면 논리적 읽기수 3
}}}

==== 인덱스에 대한 오해들 ====
많은 사람들이 다음과 같은 오해를 하고 있다. 

 1. 클러스터드 인덱스는 정렬을 유발하므로 생성하지 말아야 한다. 
 2. 풀스캔은 느리고, 인덱스에 의한 접근은 빠르다.
 3. 액세스 범위의 10%이하인 경우 인덱스를 사용하는 것이 빠르다.
 4. 인덱스를 생성한 테이블은 삽입, 삭제, 갱신이 인덱스가 없는 테이블보다 더 느리다. 

오해일까? 오해일 수도 있다. 단지 “상황”을 고려하지 않았기 때문이다. 모든 문장에 “상황에 따라서” 라는 문자열을 붙이면 맞냐 틀리냐를 구분할 수는 없다. 인덱스는 효율적인 데이터 접근을 위해 꼭 필요한 물리적인 요소이다. 그러나 우리가 생각하는 이상과 현실은 따로 존재한다. 각각의 상황에 맞게 인덱스를 구성하는 것이 매우 중요하다. 

==== 인덱스 설계 ====
attachment:IndexSeek/SQL_356.jpg
그림 출처:http://www.dbguide.net/db.db?cmd=view&boardUid=148221&boardConfigUid=9&categoryUid=216&boardIdx=140&boardStep=1
==== 더 깊은 곳으로... ====
더 이상 알고 싶다면 Inside SQL Server 시리즈 책을 보거나 SQL매거진을 구독하기 바란다. 더 이상의 깊은 곳은 필자도 모른다. 다만 이 정도만 알아도 DB쟁이로 먹고 사는데는 지장없다는 보장은 할 수 있다. 

==== 참고자료 ====
 * http://www.simple-talk.com/sql/database-administration/brads-sure-guide-to-indexes/
 * [http://www.simple-talk.com/sql/t-sql-programming/binary-trees-in-sql/?utm_source=simpletalk&utm_medium=email-main&utm_content=Binary-20100629&utm_campaign=SQL Binary Trees in SQL]
 * [Balanced Tree 그림모음]

인덱스 통계정보 갱신일
{{{
/*
테이블별 인덱스에 대한 통계가 마지막으로 업데이트된 날짜 찾기 
이종희 (필라넷) 2003.10. 작성
정원혁 (MS) 2004.8. 수정
*/ 
  
SELECT  USER_NAME( OBJECTPROPERTY( i.id, 'OwnerID' ) ) AS Owner
   ,OBJECT_NAME( i.id ) AS [Table]
   , i.name AS [Index]
   ,CASE INDEXPROPERTY( i.id , i.name , 'IsClustered')  WHEN 1 THEN 'Y'  ELSE ''   END AS IsClustered
   ,CASE INDEXPROPERTY( i.id , i.name , 'IsUnique'    )  WHEN 1 THEN 'Y'  ELSE ''   END AS IsUnique
   ,STATS_DATE( i.id , i.indid ) AS LastUpdatedDate
   ,dPages * 8. /1024 AS MB
FROM sysindexes AS i
WHERE OBJECTPROPERTY( i.id, 'IsMSShipped' ) = 0 
 AND 1 NOT IN ( INDEXPROPERTY( i.id , i.name , 'IsStatistics'   ) 
  , INDEXPROPERTY( i.id , i.name , 'IsAutoStatistics' ) 
  , INDEXPROPERTY( i.id , i.name , 'IsHypothetical'   )  )
 AND i.indid BETWEEN 1 And 250
-- AND dPages > 100 --작은 크기 테이블 무시
 AND (STATS_DATE( i.id , i.indid ) < getdate() - 15 
  OR STATS_DATE( i.id , i.indid ) IS NULL) --15일 이전까지도 업데이트 안된 것
ORDER BY Owner, [Table], [Index] 
  
--출처: dbguide.net 
}}}

----
좋은 글 잘 보고 갑니다. 감사합니다. -- db쟁이꿈나무 2023-01-05 12:59:41