skyjump's blog

hash-based indexes는 equality selection에 가장 좋은 인덱스.
range search는 성능이 아주 않좋아 사용하지 않는다.

static hash
primary bucket pages가 고정, 연속적으로 할당되어 있다. 절대 해제되지 않고, 필요하면 오버플로우 페이지를 만든다.
hash값으로 data entry가 들어갈 버켓을 정한다.

dynamic hashing
extensible hashing, linear hashing

extensible hashing
버켓을 가리키는 디렉토리를 사용한다.
버켓이 가득차면 디렉토리 크기를 2배로 하고, 오버플로우 된 버켓에 있는 데이터엔트리들을 분산시킨다.
하지만 버켓이 가득찬다고 해서 항상 디렉토리 크기가 2배가 되는 것이 아니다.
오버플로우된 버켓의 데이터엔트리가 분산될 때, global depth, local depth를 비교해서 local depth가 커질경우 디렉토리 크기를 2배로 늘리고, global depth도 1 커진다.
global depth는 엔트리가 어떤 버켓에 속할지 구분할 때 필요한 최대 bit의 갯수이다.
local depth는 이 버켓에 속한 엔트리들을 구분하는데 이용되는 bit수이다.
최소유효비트로 구별하는 것의 좋은 점 : 디렉토리가 2배가 될때 그냥 이전 디렉토리를 복사하고, 분산되는 버켓부분의 포인터만 수정해준다.
데이터 엔트리를 삭제할 때, bucket이 비면 합칠 수 있다. 그리고 모든 directory element가 분산되기 전처럼 같은 bucket을  가리키면 디렉토리가 반으로 줄어든다.

linear hashing
여러개의 hash function을 이용.
hi+1 은 hi의 해시값 범위의 두배이다.
overflow page를 사용한다.
나눌 버켓을 round-robin으로 차례대로 정한다.
한 라운드의 버켓의 수는 라운드 시작할 때 존재하는 버켓의 수(NR)이다.
각 라운드를 level이라고 한다.
한 라운드를 끝내면 버켓의 수는 시작할 때보다 2배가 되며(점진적으로 증가)
level이 하나 증가하고, 해쉬함수도 다음 것을 사용한다.
나눠지는 시점을 적재률로도 할 수 있고, 아니면 오버플로우 될 때로 할 수 있다.
찾기 할 때 해쉬값이 이전에 나눠진 버켓을 가리킬 때에는 다음 단계 해쉬값을 사용한다.
입력할 때 level 또는 level+1의 해시함수의 값을 통해 버켓을 찾고 버켓이 가득 찼을 경우 오버플로우 페이지가 생기고,
나눠지는 시점을 오버플로우가 발생될 때로 했다면, 이번 차례의 버켓을 level+1의 해쉬함수를 이용하여 엔트리들을 분할 한다.



 
 

인덱싱의 3가지 방법. 이전 노트 참고.

Tree-structured indexing은 범위를 만족하는 것을 찾는 것(range search)과 일치하는 것을 찾는 것(equality search), 둘 다 쓰일 수 있다. 
ISAM은 정적인 구조, B+ tree는 삽입, 삭제에 유연한 동적인 구조.

ISAM
leaf page가 data entries를 포함하고 있고, 오버플로우 페이지를 갖는다.
파일생성과정 : leaf pages가 연속적으로 할당되고, 서치키에 의해 정렬된다.  인덱스 페이지가 할당되고, 오버플로우 페이지를 위한 공간을 할당한다.
삭제시 overflow 페이지가 비게되면 할당 해제.
삽입과 삭제는 leaf page에만 영향을 미친다. non-leaf page는 안변한다.

B+tree
삽입, 삭제가 logF N이다. 트리의 높이 균형을 유지한다.
루트 빼고 페이지의 최소 적재률(50%)를 유지한다. 각 노드는 d<= m  <= 2d의 entry를 포함한다. d를 order라고 한다.
data entry에 삽입할 때 공간이 없으면 노드를 분할. 중간 값이 부모노드로 복사되어 새로 생긴 노드를 가리킨다.
하지만 index entry에 삽입할 때는 중간값이 복사되지 않고 이동된다.
split되면 높이가 하나 커진다.
삭제
삭제하고 나서  최소적재율보다 작으면 이웃노드에서 엔드리들을 가져오가나(re-distribute),이게 안되면 이웃노드랑 결합(merge)한다.
data entry가 merge될 때

platters가 돈다.
arm assembly가안팎으로 움직이면서 헤드를 원하는 track 위에 올려놓는다.
헤드들 밑에 놓은 트랙들은 cylinder라고 한다.
한번에 one head만 읽고 쓸 수 있다.
block size는 여러개의 sector size이다.

seek time : arm으로 head를 원하는 트랙위에 위치시키는데 걸리는 시간.
rotational delay : 원하는 block에 도착할때까지 회전하는 시간.
transfer time: data 전송시간
i/o cost를 줄이려면 seek time과  rotational delay를 줄인다.
파일의 block들을 디스크에 연속적으로 저장한다.
같은 트랙의 블락 -> 같은 실린더의 블락 -> 인접한 실린더의 블락 순으로.
연속적인 스캔을 할 때, 미리 몇개의 페이지를 메모리로 불러오는 pre-fetching은 성능항상에 도움이 된다.

RAID
여러개의 디스크를 사용해서 하나의 큰 디스크로 추상화.
성능항상과 신뢰성을 위해 사용.
data striping(data를 쪼개서 저장), redundancy(fail을 대비해서 데이터를 중복해서 저장)
 
Disk space management
페이지를 할당하고 해제하는 역할.
페이지를 읽고 쓰는 역할을 한다.

buffer management
메인메모리의 크기가 상대적으로 디스크보다 작기때문에
메인메모리에 버퍼풀을 유지. 디스크로부터 필요한 프래임을 가져온다.
replacement policy를 통해 어떤 페이지가 교체될 것인지 정한다.
교체될 때 교체되는 frame이 수정되었을 경우(dirty) 디스크에 반드시 쓴다.
새로 불러온 페이지는 pin count를 하나 증가시킨다. 다른 사용자가 그 페이지를 요청할 때 pin count는 하나씩 증가한다.
pin count가 0인 것들만 교체할 수 있다.

buffer replacement policy
LRU, Clock, MRU등이 쓰인다.
LRU가 항상좋은 것은 아니다.
스캔을 할 때, 버퍼풀에 10개 프레임이 있고, 스캔할 파일의 페이지 수가 11개 일때,
파일을 스캔할 때마다 모든 페이지를 디스크로부터 읽어야 하는 문제가 발생한다. (sequential flooding)

왜 OS 파일 시스템을 사용하지 않고 독자적인 파일 시스템을 사용하는가?
OS에 독립적으로 동작하기 위해서.
그리고  DB 연산들은 패턴이 있어서 다음에 어떤 페이지가 올지 예측할 수 있다. 그래서 page를 미리 불러올 수 있다. (pre-fetch)
 
Record format
레코드길이가 고정일 경우.
system catalog에 필드 사이즈 정보가 저장되어서, 이를 참조하여 특정 필드의 위치를 계산할 수 있다.
필드사이즈가 고정이 아닐 경우
필드 사이에 특별한 문자를 넣어서 필드를 구별하는 방법이 있다. 특정 필드 찾아내려면 레코드를 처음부터 읽어야 한다.
필드앞에 각 필드의 위치 정보를 담은 디렉토리를 사용하는 방법이 있다. 약간의 공간 오버헤드가 있지만 특정 필드를 찾기 쉽다.

page format
record id = <page id, slot #>
1) 레코드 길이가 고정일 때
i) 레코드들을 연속적인 slot에 모아두는 방법. 삭제될 때 마지막 slot이 삭제되는 slot으로 이동. 이동되는 레코드가 외부에서 참조될 때 문제.
ii) 비트맵을 유지하는 방법. 
2) 레코드 길이가 고정이 아닐 때
레코드 오프셋, 레코드 길이로 구성된 slot directory를 만든다. rid를 바꾸지 않고도 record들을 이동할 수 있다.

DBMS의 윗 레벨에서는 페이지와 블락을 모른다. 레코드와 레코드의 집합인 파일을 안다.

unordered(heap) file

레코드들이 어떻게 파일로 구성되느냐에 따라 DBMS의 성능이 달라진다.
인덱스는 search key로 record id를 찾을 수 있게 해주는 자료구조이다.
버퍼메니져가 disk로 부터 페이지를 메모리로 fetch한다. file, index layer가 버퍼메니저에게 요청.


파일구성 방법
힙 파일:  순서가 렌덤하게 레코드들이 파일에 저장. 모든 레코드들을 스캔할때 적절한 방법.
sorted files: 레코드들을 순서대로 접근할 때 좋은 방법.
인덱스 : 레코드들을 트리나 해쉬로 구성. search key 필드로 검색할 때 효율적인 검색이 가능하다. sorted files보다 레코드 삽입, 수정, 삭제가 빠르다.

인덱스
search key에 의해 파일 접근을 빠르게 할 수 있다.
search key는 relation의 field들의 subset이다.
search key는 key(primary key, candidate key)와는 관련이 없다. 즉 unique하지 않을 수 있다.

data entry
data entry : 인덱스 파일에 저장되어 있고. 이걸로 데이터 레코드를 찾을 수 있다.
data entry를 저장하는 세가지 방법.
1. key value와 data record로 구성.
2. key value와 data record id로 구성.
3. key value와 data record id의 list로 구성.
1번 방법으로는 index를 하나밖에 이용 못한다. 아니면 레코드데이터가 중복되어야 한다. 레코드데이터가 크면 페이지 많이 차지한다.
2번과 3번은 data entry가 데이터레코드의 포인터를 가지고 있기 때문에 파일 구성에 독립적이고, 1번보다 사이즈가 작다. 특히 3번은 2번보다 더 사이즈가 작지만 data entry들의 길이가 가변적이다.(search key가 고정 사이즈이더라도!)

인덱스 분류
primary index : primary key를 포함하는 search key.
secondary index : 그 외 인덱스들
unique index: candidate key를 포함하는 search key.

clustered : 데이터 레코드의 순서가 그 파일의 인덱스의 데이터 엔트리 순서와 비슷하거나 같도록 구성할 때.
1번은 clustered.
2번을 사용했을 때 clustered로 만들어주려면 heap 파일 정렬. 레코드가 삽입될 때 overflow 페이지가 필요할수도 있다. 그래서 data 레코드들이 완전히 sort되어 있다고 말할 수 없고 sort에 가깝다라고 말할 수 있다.

Hash-based index
index는 bucket들의 모임
bucket: primary page하나랑 0개 이상의 overflow pages.
hash function으로 레코드가 속할 버켓을 구한다.
레코드의 search key값을 이용한다.

B+ tree
루트에서 단말 노드에 이르는 모든 경로의 길이가 같은 인덱스 구조.
leaf page는 data entry를 포함하고, 양옆의 leaf들과 연결되어 있다.
non leaf page는 index entry들을 포함하고 찾는 data entry가 어디있는지 알려준다.
fan-out : 비단말노드에서 자식의 평균 수.
fan-out이 클 수록 빨리 찾을 수 있다. index entry 사이즈가 작을 수록 fan-out이 커진다.


 

UNION : 합집합
INTERSECT : 교집합
EXCEPT : 차집합
위 세개는 중복이 포함되지 않는다.

IN : A IN B, A가 B에 속하면
NOT IN: IN 반대.

EXISTS : IN과 비슷. 서브쿼리의 결과가 공집합인지 아닌지 점검. 아니면 서브쿼리 결과를 바탕으로 메인쿼리 재계산.
UNIQUE: 서브쿼리의 인스턴스의 튜플의 갯수가 2개이상이 아닌지 검사. 하나이거나 0개일 때 TRUE.

ANY :  서브쿼리가 반환하는 튜플 중에 하나라도 만족하면 참.
ALL : 서브쿼리가 반환하는 모든 튜플을 만족하면 참.
IN과 ANY가 같고
NOT IN과 <>ALL이 같은 의미.
 
메인쿼리의 각 튜플에 대해 서브쿼리를 적용.

Group by : 그룹별로 묶기.
Having by : 조건을 만족하는 것들만 묶기.
group by를 사용할 때 select 절에 나오는 열이 group by절에 있는 열에 포함이 되어야 한다. 포함되지 않으면 그 열의 값이 여러개를 가질 것이고 select문에서 어떤 것을 출력해야 될지 모르므로. 키로 그룹을 묶으면 가능하다.

Outer join
equijoin에서 조건을 만족하지 못하는 튜플은 결과에서 못본다. 값이 없는 것도 결과에서 보기 위해 사용한다.
널값도 나올 수 있다.

테이블 제약 조건
한 행이 삽입되거나 수정될 때 check 제약 조건의 조건식이 계산된다.

도메인 제약조건
Integer같은 도메인을 정의할 수 있다.
 distinct type: 같은 Integer를 기반으로 하더라도 type이 다르면 비교를 못하도록 하기 위해 사용.

assertion
여러 테이블이 동시에 관련된 제약조건일 때 사용.

트리거
데이터베이스를 관찰하고 있다가 변경되면 자동으로 실행되는 프로시저.
 

Entity : 실세계에서 다른 객체들로부터 구분될 수 있는 객체.
entity set: 같은 종류의 entity들의 집합.
attributes : 하나의 객체가 attributes 집합을 사용하여 객체를 기술한다.
각 에트리뷰트는 domain 값을 지정한다.
각 객체 집합에서 키를 선택한다.
키 : 한 객체를 유일하게 식별할 수 있는 최소 어트리뷰트의 집합.

SELECT status FROM my_contacts
GROUP BY status
ORDER BY status;

ORDER BY는 항상 맨 마지막에 온다.

문자열 추출
UPDATE my_contacts
SET interests = SUBSTR(interests, LENGTH(interest1)+2); 

 
3개 쿼리는 같은 결과
1)
CREATE TABLE profession
(
    id INT(11) NOT NULL AUTO_INCREMENT PRIMARY KEY,
    profession varchar(20)
);
INSERT INTO profession (profession)
    SELECT profession FROM my_contacts
    GROUP BY profession
    ORDER BY profession

2)
CREATE TABLE profession AS
    SELECT profession FROM my_contacts
    GROUP BY profession
    ORDER BY profession;
ALTER TABLE profession
ADD COLUMN id INT NOT NULL AUTO_INCREMENT FIRST,
ADD PRIMARY KEY (id);

3)
CREATE TABLE profession
(
    id INT(11) NOT NULL AUTO_INCREMENT PRIMARY KEY,
    profession varchar(20)
) AS
    SELECT profession FROM my_contacts
    GROUP BY profession
    ORDER BY profession

테이블에서 원자적이지 않은 열을 새로운 테이블로 옮기기.

데이터베이스 내의 데이터(열들과 테이블들), 그리고 데이터들 사이의 연결 방식에 대한 표현을 스키마라고 한다.

테이블의 연결
테이블을 연결하기 위해서는 테이블에 기본키와 같은 유일한 열이 필요하다.
테이블은 참조키를 통해 다른 테이블의 기본키를 가리킨다.
참조키에서 참조하는 기본키를 부모키(parent key)라고도 한다.
참조키는 한 테이블의 열들이 다른 테이블의 열과 연결 되도록 하는데 사용할 수 있다.
기본키는 null일 수 없지만 참조키는 null일 수 있다.(부모 테이블의 기본키(primary key)를 안가리키는 것) 
제약조건(constraint)를 사용해서 null을 갖게 하지 못하도록 할 수 있다.
참조키는 유일할 필요가 없다.

참조키 제약조건
부모 테이블에 존재하는 키의 값만을 넣을 수 있도록 할 수 있다. 참조 무결성(referential integrity)
기본키가 있는 테이블에서 행을 지우거나 바꾸려고 할 때 제약조건으로 인해 삭제 수정이 맘대로 안된다.
참조키의 값이 부모 테이블의 기본키일 필요는 없지만 그 값이 유일(unique)해야 한다.

UNIQUE 키워드
열의 값이 유일하도록.

참조키가 있는 테이블 생성

UPDATE에 CASE사용 (SELECT, INSERT, DELETE에도 사용할 수 있다)
category 열에 조건에 따라 다른 값 넣기
UPDATE movie_table
SET category
CASE
    WHEN drama = 'T' THEN 'drama'
    WHEN comedy = 'T' THEN 'comedy'
    WHEN cartoon = 'T' AND rating='G' THEN 'family'
    ELSE 'misc'
END; 

하나의 열로 순서매기기
SELECT title, category
FROM movie_table
WHERE
category = 'family'
ORDER BY title;

여러 열을 사용하여 정렬 할 수 있다.
ORDER BY category, purchased, title;

내림차순 정렬
ORDER BY purchased DESC;

SUM함수
SELECT SUM(sales)
FROM cookie_sales;

평균함수
AVG(column);

GROUP BY
first_name으로 그룹을 짓고 각 그룹별로 SUM을 하기
SELECT first_name, SUM(sales)
FROM cookie_sales
GROUP BY first_name
ORDER BY SUM(sales) DESC;

MIN과 MAX함수
SELECT first_name MAX(sales)
FROM cookie_sales
GROUP BY first_name;
 
열의 행 수 반환
SELECT COUNT(sale_date)
FROM cookie_sales;

DISTINCT 키워드
중복된 값을 없애기
SELECT COUNT(DISTINCT sale_date) 
FROM cookie_sales; 

결과의 갯수를 제한하기
first_name으로 그룹을 짓고 각 그룹별 합을 구하고 합들을 내림차순으로 정렬하고 정렬된 값들 중에 2개를 보여준다.
SELECT first_name, SUM(sales)
FROM cookie_sales
GROUP BY first_name
ORDER BY SUM(sales) DESC
LIMIT 2;

두번째만 보여주기
LIMIT m,n (m은 시작 번호(0부터 시작), n은 보여줄 결과 갯수)
LIMIT 1,1