쿼리에 필요한 블록 전송 및 검색 작업 수를 찾는 방법

Question

선택 및 비교를 수행하는 쿼리가 있습니다. 지정된 수의 튜플, 디스크 블록 및 인덱스 유형 (예 : 키의 기본 B + 트리 인덱스)을 사용하여 쿼리를 완료하는 데 필요한 블록 전송 및 검색 작업 수를 계산하려면 어떻게해야합니까? 우리는 이드의 값을 알고

select cid 
from payment 
where eid = 1200 and amount > 30 

균일하게 1과 100 사이에 분포하고 있으며, 양의 값은 균일 15000 개 디스크 블록에 포함 1000000 튜플이 있습니다 (1) 및 (50) 사이에 분포되어 있다고 가정 해 봅시다.

즉, 주어진 경우는 없음

양에 이드, 보조 B + 트리 인덱스의 양, 보조 B + 트리 인덱스에서 이드 차 B + 트리 인덱스의 인덱스, 기본 B + 트리 인덱스.

eid는 직원의 기본 키이고 cid는 고객의 기본 키이며 cid는 eid가 지불 할 후보 키를 생성합니다. 금액은 지불의 속성입니다.

Answer 1

좋아요. B + 트리 또는 다른 구조로 인덱싱을 사용하여 데이터베이스 쿼리를 통해 전송되는 블록의 기본 사항을 배우려는 사람들을위한 실질적인 솔루션을 발견했습니다.

값을 검색 할 색인이 정의되어 있지 않으면 보조 디스크에있는 모든 데이터가 블록 및 블록으로 전송되어야합니다. 따라서 모든 블록이 전송되고 값이 순차적으로 검색됩니다. 데이터에 대한 블록이 디스크에서 어떤 주소로 시작되는지 알면 충분합니다. 그런 다음 강조 표시된대로 값이 순차적으로 검색됩니다. 따라서이 예에 따르면 쿼리 중에 15000 개의 블록이 전송됩니다. 1 시크이면 충분합니다. 이드에 차 차 B + 트리 인덱스가있는 경우

, 우리는 주어진 쿼리에서 두 가정을 만들 수 있습니다 이드 = 1200

첫째, B + 트리를 검색하고이 값을 1200으로 인해이있는 이드를 찾을 수 없습니다 eid는 0-100 사이입니다. 따라서 B + 트리에서 먼저 검색하여 디스크에 이러한 값이 없음을 보장하므로 블록 전송 및 검색이 디스크에 없습니다.

둘째, 100 개의 고유 한 eid 값이 있고 그 중 하나가 1200이라고 가정하면 B + tree는 eid = 1200에 대한 검색에서 성공합니다. 이러한 상황에서 값이 1200 인 리프의 포인터는 eid 값이 정렬 된 디스크 위치를 가리키며 포인팅 주소는 eid = 1200 인 첫 번째 주소입니다. 이 주소에서 시작하여, eid가 더 이상 1200이 될 때까지 데이터가 검색됩니다. 우리는 대략 100 개의 고유 한 eid 값이 있고 15000 개의 블록이 있기 때문에 대략 가정합니다.eid = 1200 인 튜플은 약 15000/100 = 150 블록입니다. 인덱스가 기본 키이므로 값이 정렬 된 것을 알기 때문에 총 블록 수를 나누었습니다. 따라서 eid의 첫 번째 1200 값이있는 주소를 알고있는 경우 eid 속성이 다른 값을 가지지 않는 한 다음 튜플에도 eid = 1200이 있다는 것을 절대적으로 확신합니다. 따라서 1 차 인덱스가 eid이고 1 회 탐색만으로 충분하다면 검색을 시작할 때 디스크를 다시 검색 할 필요가 없으므로 eid가 디스크에서 다른 값을 가질 때까지 튜플을 순차적으로 검색 할 수 있기 때문에 150 블록이 전송됩니다.

비슷한 양상에서 금액에 대한 기본 지수가 있고 amount = [31, 50] 인 값을 원할 경우 (15000/50) * 20 = 6000 블록을 전송해야합니다. 우리는 50 개의 다른 금액 값을 가질 수 있기 때문에 50으로 나누었습니다. 그리고 우리는이 50 개의 값 중 1 개가 아니라 20 개의 값을 검색하기 때문에 20으로 나누기를 곱했습니다. 따라서이 20 개의 다른 값은 6000 개의 튜플에있을 수 있습니다. 다시 한 번 탐색하면 충분합니다. 시작 주소에서 검색을 시작할 때 순차적으로 튜플을 찾습니다.

색인이 보조 색인 인 경우 더 이상 값이 디스크에서 정렬되었다고 말할 수 없습니다. B + 트리의 리프 노드에서 포인터는 디스크에있는 값의 실제 위치에 대한 포인터가 들어있는 버킷을 가리 킵니다. 먼저 주소 버킷으로 이동 한 다음 거기에서 직접 디스크를 방문합니다. 따라서 첫 번째 검색은 B + 트리에서 버킷까지, 그리고 버킷에서 디스크까지입니다. 최악의 경우, 원하는 모든 값을 완전히 다른 블록에 배치 할 수 있습니다. 따라서 우리가 정의한 값을 포함하는 총 튜플 수만큼 블록을 전송해야 할 수도 있습니다.

보조 색인 eid가 있고 값이 0-100 사이 인 경우 eid = 1200에 해당 값이 없으므로 다시 I/O가 없습니다. 그러나 eid 값에 대한 두 번째 가정을 다시 작성하면 eid 값이 1200 인 1000000/100 = 10000 개의 튜플이 있다고 가정합니다. 최악의 경우 10000 개의 블록을 전송해야합니다. 튜플 중 비 순차적으로 오는 것은 다른 블록에 있습니다. 다시 한번 버킷이 가리키는 디스크상의 위치를 ​​찾기 위해 10000 회의 탐색이 필요합니다.

금액에 보조 색인이 있고 그 중 20 개가 필요한 경우이 값은 대략 (1000000/50) * 20 = 400000 튜플에 있습니다. 최악의 경우 다시 블록이 전송 될 때 가정하면 400000 블록을 전송해야 할 수도 있습니다. 다음에 원하는 튜플이 마지막으로 전송 된 블록에 절대로 존재하지 않습니다. 그러한 상황에 대해 우리는 위의 이유를 강조하면서 최악의 경우 400000 블록 전송과 400000 탐색이 필요할 것입니다.

색인 금액을 검색하는 동안 eid = 1200을 선택할 수도 있고 그 반대로도 선택할 수 있습니다. 따라서 우리는 두 번째 조건 인 index => 30에서 검색하는 동안 eid = 1200을 찾고 eid = 1200에서 검색하는 동안 amount> = 30을 찾고 있습니다.

다시이 쿼리는 대략적인 것이며 일반적으로 쿼리를 만드는 동안 블록 전송 및 검색의 기본 사항을 설명하는 최악의 결과입니다. 데이터 전송이 디스크에서 주 메모리 및 사용자에게 어떻게 처리되는지에 대한 기본적인 개념을 제공합니다.

Answer 2

나는이 질문을 마무리하기 위해 투표를했지만, 나는 의견을 내기에는 너무 긴 의견을 남기고 싶다.

기본 질문 인 "블록 전송 수를 계산하고 쿼리를 완료하는 데 필요한 작업을 찾는 방법은 무엇입니까?"는 불확정합니다. 이러한 작업의 수는 데이터베이스의 상태에 따라 다릅니다. 특히 데이터 페이지와 인덱스 페이지가 이미 메모리에 캐시되어 있는지 여부.

주어진 진술에 대해 나는 만 세계의 99.999 %가 알아야 할 중요한 것이 payment(eid, amount, cid)의 색인이 최적의 색인이라고 생각합니다. 인덱스의 처음 두 요소 (, 그 순서는)는 where 절을 지원합니다. 마지막으로 인덱스를 사용하여 쿼리를 처리 할 수 ​​있으므로 원본 데이터 테이블을 사용할 필요가 없습니다. 특정 유형의 색인은 완전히 중요하지 않습니다.