indexes (edX stanfordOnline databases: Adbanced Topics in SQL)

* indexes = indices

 

* Users don't access indexes; they're used underneath by the query execution engine.

indexes might allow the query execution engine to speed up processing

T.A에 인덱스가 있으면 T.A에 'cow'값이 있는 튜플을 알려달라고 할 때,

전체 테이블을 스캐닝하지 않고 3과 7 튜플을 반환한다.

 

두 개 칼럼에 대해서 인덱스를 지정할 수도 있다.

condition에 자주 사용되는 어트리뷰트에 대해 인덱스를 설계하는 것이 중요하다

 

인덱스의 자료 구조

(1) 균형 트리

구현 형태: B tree, B+tree

 

attribute = value

attribute < value

value_1 <= attribute <= value_2

형태의 조건으로 질의할 때 도움된다.

 

logarithmic running time

 

(2) hash tables

 

more or less constant running time

equality conditions가 사용된다면, 해시 테이블이 성능상 더 낫다

Hash-based indexes can only be used for equality conditions.

1) sName이 인덱스라면,

sName이 'Mary'인 튜플을 빠르게 찾고,
각 튜플의 GPA 값이 3.9 초과인지 확인할 것

 

2) GPA가 인덱스라면,

GPA가 3.9 초과인 학생을 먼저 찾고,

그 다음 이름이 Mary인 사람을 찾는다.

 

3) sName, GPA 둘 다 인덱스라면,

sName이 Mary이고, GPA가 3.9 초과인 학생을 동시에 찾는다.

 

Join 쿼리 실행과 인덱스를 활용한 성능 최적화

🧩 인덱스를 활용한 쿼리 실행 전략

1. Apply 테이블의 SID에 인덱스가 있는 경우
   • Student 테이블을 스캔
   • 각 학생의 SID로 Apply 테이블에서 일치하는 튜플을 빠르게 조회
2. Student 테이블의 SID에 인덱스가 있는 경우
   • Apply 테이블을 스캔
   • 각 Apply 튜플의 SID로 Student 테이블에서 일치하는 튜플을 인덱스로 조회
3. 양쪽 모두에 인덱스가 있는 경우
   • 두 테이블을 각각 인덱스 순서로 정렬하여
   • Merge Join처럼 병합하면서 SID가 일치하는 튜플을 효율적으로 찾을 수 있음

 

Select * From Student, Apply, College
Where Student.sID = Apply.sID and Apply.cName = College.cName
And Student.GPA > 1.5 And College.cName < 'Cornell'

Student.sID, College.cName

most useful indexes for speeding up query execution

 

Explanation

An index on Student.sID can be used for its join condition and an index on College.cName can be used for both its join condition and 'cName < Cornell.' An index on Student.GPA is unlikely to be helpful since most students satisfy GPA > 1.5. Indexing both Apply.cName and College.cName helps with only one join condition.

 

 

⚙️ 추가 조건이 있는 경우

• 조건이 복잡해질수록 인덱스를 사용하는 전략이 다양해짐
• 이와 같은 다양한 실행 계획은 쿼리 플래닝(Query Planning) 및 **쿼리 최적화(Query Optimization)**에 해당

 

🧠 핵심 포인트

• 인덱스는 조인 성능을 극적으로 개선할 수 있음
• 인덱스의 정렬 속성을 활용하면 **정렬 병합 조인(Merge Join)**도 가능
• 효율적인 쿼리 실행을 위해 데이터베이스 시스템은 쿼리 최적화를 수행함
  → **선언적 언어(SQL)**로 작성된 쿼리를 내부적으로 효율적으로 실행할 수 있게 해줌
• An index on an attribute R.A may be useful whenever a query has a selection condition on R.A, or does a join involving R.A.

 

📚 인덱스(Index)의 장점과 단점, 그리고 설계 전략

---

✅ 인덱스의 장점

• 쿼리 성능을 매우 빠르게 향상시킬 수 있다.
• 선언형 쿼리 언어(SQL)를 효율적으로 실행할 수 있게 한다.
• 정렬된 상태로 접근 가능 → merge join 등 최적화된 연산 수행 가능

---

⚠️ 인덱스의 단점 (세 가지, 덜 중요한 것에서 중요한 순으로)

1. 공간 차지 (경미한 단점)
   • 인덱스는 추가적인 저장 공간이 필요
   • 최근 디스크 가격이 낮아 크게 문제되지 않음
2. 생성 비용 (중간 정도 단점)
   • 인덱스를 만들 때 시간이 오래 걸림
   • 데이터 로딩 시 또는 나중에 추가할 경우
   • 하지만 만들어 두면 대부분 쿼리가 빨라지므로 보통 투자할 가치 있음
3. 유지 관리 비용 (가장 큰 단점)
   • 데이터 변경 시마다 인덱스를 동기화해야 함
   • 갱신이 잦은 데이터베이스에서는 인덱스 유지 비용이 큼
   • 읽기보다 쓰기가 많은 환경에서는 인덱스가 오히려 성능 저하 요인이 될 수 있음

---

⚙️ 인덱스 설계 시 고려할 요소

• 테이블 크기 (클수록 인덱스 효율 증가)
• data distributions
  • the index helps us find specific data values quickly
• 쿼리 vs 업데이트 빈도
  → 읽기 작업 많으면 인덱스 유리, 쓰기 작업 많으면 손해일 수 있음

---

🤖 물리적 설계 도우미 (Physical Design Advisor)

physical design: determine which indexes to build on a database

• 입력: 데이터베이스, 워크로드(sets of queries and updates that are expected to be performed on the database, frequency)

design advisor는 전체 데이터베이스를 보는게 아니라, 데이터베이스의 통계를 본다.

테이블이 얼마나 큰지, 데이터 분포가 어떤지

• 출력: 최적의 인덱스 조합 (to speed update the overall workload)

 

physical design advisors는 query optimizer에 많이 의존한다.

 

query optimizer

takes a query and figures out how to execute it

어떤 인덱스를 사용할지, which order things will be done in

execution plan별 비용을 추정하고, best execution plan with estimated cost를 반환한다

• 현재 존재하는 인덱스, 테이블 통계, 쿼리를 바탕으로
  가능한 실행 계획을 시뮬레이션하고 가장 저렴한 비용을 추정

 

physical design advisors 작동 방식

1. 다양한 인덱스 조합을 실험적으로 가정 (experiments with different set-ups of indexes)
2. 쿼리 옵티마이저에게 각 조합에 대한 실행 계획과 비용을 추정하게 함
3. 비용이 가장 낮은 인덱스 조합을 추천 (the benefits of having the index outweigh the drawbacks of having that index in terms of the workload and using the costs that were estimated by the query optimizer)

※ 실제 쿼리를 실행하지 않고, 쿼리 옵티마이저의 추정값 기반으로 판단

🛠️ 직접 인덱스를 설계해야 할 경우

• 시스템에 Design Advisor가 없다면,
  직접 쿼리 패턴과 빈도, 갱신 횟수를 고려해 인덱스를 만들어야 함

---

📝 SQL 인덱스 관련 문법

• CREATE INDEX name ON table(attr)
• 여러 속성 조합 인덱스도 가능
• UNIQUE 지정 시 해당 속성의 값이 유일해야 함
• DROP INDEX name으로 삭제 가능

---

🔚 요약

• 인덱스는 데이터베이스 성능 향상에 핵심적
• 하지만 디스크 공간, 생성 비용, 유지 비용 등 트레이드오프가 존재
• 쿼리 중심 설계를 위해 인덱스를 신중히 선택해야 함
• 적절한 인덱스 설계는 성능을 수십 배 향상시킬 수 있음

Q. Consider a table storing temperature readings taken by sensors:

   Temps(sensorID, time, temp)

Assume the pair of attributes [sensorID,time] is a key. Consider the following query:

   select * from Temps
   where sensorID = 'sensor541'
   and time = '05:11:02'

Consider the following scenarios:

A - No index is present on any attribute of Temps

B - An index is present on attribute sensorID only

C - An index is present on attribute time only

D - Separate indexes are present on attributes sensorID and time

E - A multi-attribute index is present on (sensorID,time)

Suppose table Temps has 50 unique sensorIDs and each sensorID has exactly 20 readings. Furthermore there are exactly 10 readings for every unique time in Temps.

For each scenario A-E, determine the maximum number of tuples that might be accessed to answer the query, assuming one "best" index is used whenever possible. (Don't count the number of index accesses.) Which of the following combinations of values is correct?

 

A.

시나리오 최대 튜플 접근 수

A	1000
B	20
C	10
D	10
E	1

 

Problem Explanation

The query has an equality condition on both the sensorID and time attributes of Temps. Since [sensorID,time] is a key, the query result contains either 0 or 1 tuples.

Scenario A: Since there are no indexes, all tuples of the table may need to be accessed to look for 'sensor541' and '05:11:02'. The number of tuples in Temps is 50 (unique sensorIDs) * 20 (number of readings per sensor) = 1000.

Scenario B: Using the index on sensorID, 20 readings will match the given sensorID, and all 20 tuples may need to be accessed to look for a matching time.

Scenario C: Using the index on time, 10 readings will match the given time, and all 10 tuples may need to be accessed to look for a matching sensorID.

Scenario D: Using the time index is better than using the sensorID index, so the time index is used and is the same as scenario C (10 tuples).

Scenario E: The index on [sensorID, time] will directly find the single matching tuple, if there is one.