데이터베이스 : 13장 Data Storage Structures

1. 파일 구조

1) File Organization

• 데이터베이스는 collection of files로서 저장된다.
  각 file은 sequence of records(= tuple)이다.
  한 record는 sequence of fields(= attribute)이다.
• 하나의 접근 방식 → 이 사례는 구현이 가장 쉬우며, 이후에 vairable length record를 고려함
  • reocrd size는 fixed라고 가정
  • 각 file에는 하나의 특정 타입의 record만 가짐
  • 서로 다른 relation에는 서로 다른 file이 사용됨
• record가 disk block보다 작다고 가정

2) Fixed-Length Records

• 간단한 접근 방식
  • 레코드 i를 byte n * (i - 1)로 시작하여 저장(여기서 n은 각 record의 크기)
    → record 0부터 시작할 경우 byte n*i로 시작
  • record 접근이 간단하지만 record가 block을 교차할 수 있음
    • Modification(수정) : record가 block boundary를 넘지 않도록 해야함

(1)  Deletion of record i

1. move records i + 1, ..., n to i, ..., n-1

    - Record 3을 삭제

2. move record n to i

    - Record 3을 삭제하고 Record 11와 교채

3. do not move reccords, but link all free records on a free list
    - record를 이동하지 않고 free list에서 모든 free record를 연결

3) Variable-Length Records

• Variable-Length record는 데이터베이스 시스템에서 여러가지 방식으로 발생함
  • file에서 multiple record type을 저장
  • 문자열(varchar)와 같이 하나 이상의 필드에 대해 변수 길이를 허용하는 record type
  • repeating field를 허용하는 record type(일부 이전 데이터 모델에서 사용됨)
• 속성이 순서대로 저장됨
• fixed size(offset, length)로 표시되는 Variable length attribute(모든 fixed length attribute 이후에 저장되는 실제 데이터 포함)
• Null value는 null-value bitmap으로 표시됨

(1) Slotted Page Structure

• Slotted page header는 다음으로 구성됨
  • record entry 수
  • block의 free space의 끝
  • 각 record의 위치 및 크기
• record를 page 내에서 이동하여 free space없이 연속적으로 유지할 수 있음
  → header에 있는 entry는 반드시 업데이트해야 함
• 포인터는 reocrd를 직접 가리켜서는 안되며 header에 있는 record entry를 가리켜야 함

(2) Storing Large Objects

• 예시 : blob/clob types → record와 같이 저장하는 것보다 별도의 파일로 저장하는 것이 더 나음
• Record는 page보다 작아야 함
• 대안
  1. file system에 file로 저장
  2. 데이터베이스에서 관리하는 file로 저장
  3. 여러 개의 tupe로 분할하여 별되의 relation으로 저장(안 다룰 예정)
     • PostgreSQL TOAST

4) Organization of Records in Files

1. Heap : 공간이 있는 파일의 모든 위치에 record를 배치할 수 있음
2. Sequential : 각 record의 search key 값을 기준으로 record를 순차적으로 저장
3. multitable clustering file organizaiton에서는 여러 relation의 record를 동일한 파일에 저장할 수 있음
   • Motivation : 관련 record를 동일한 block에 저장하여 I/O를 최소화함
4. B*-tree file organization → 14장에서
5. Hashing : search key에서 계산된 Hash function → 결과는 record를 file의 어느 block에 배치해야 하는지 지정

(1) Heap File Organization

• free space가 있는 file의 모든 위치에 record를 배치할 수 잇음
• record는 일반적으로 한 번 할당되면 이동하지 않음
• file 내에서 free space를 효율적으로 찾을 수 잇는 것이 중요
• Free-space map
  • block당 1개의 entry가 있는 array
    → 각 entry는 byte 단위로 몇 비트이며, 사용 가능한 block의 일부를 기록함
  • 아래 예에서 block당 3비트, value를 8로 나눈 값은 사용 가능한 block의 비율을 나타냄
  • second-level-free-space map을 가질 수 있음 → 개수가 많을 때 해당 방법 사용
  • 아래 예에서 각 entry는 1st-level-free-space map의 4개 entry에서 최대를 저장함

1st-level-free-space map

second-level-free-space map

• 디스크에서 주기적으로 기록된 free space map, 일부 entry에 대해 wrong(old)값을 갖는 것이 좋음(탐지나 수정될 수 있음)

(2) Sequential File Organization

• 전체 파일을 순차적으로 처리해야 하는 응용프로그램에 적합
• 파일의 record는 search-key로 정렬됨

• Deletion : pointer chain 사용
• Insertion : record를 삽입할 위치를 찾음
  • free space가 있다면 그곳에 삽입
  • free space가 없는 경우 overflow block에 record 삽입
  • 두 경우 모두 pointer chain 을 업데이트해야 함
• sequential 순서를 복원하기 위해 때때로 file을 재구성한다.

32222는 overflow blcok에 들어감

(3) Multitable Clustering File Organization

• Multitable Clustering File Organizaiton을 사용하여 하나의 파일에 여러 relation을 저장

• department ⋈ instructor와 관련된 쿼리 및 단일 department와 해당 instructor와 관련된 쿼리에 유용
  ex) select * from instructor where dept_name = 'Comp.Sci.'
• department만 관련된 쿼리에 적합하지 않음
  ex) select * from department
• variable size record의 결과
• pointer chian을 추가하여 특정 relation의 record를 연결할 수 있음

5) Data Dictionary Storage

(1) Partitioning

• Table partitioning : relation에 있는 record는 별도로 저장되는 더 작은 relation으로 분할할 수 있다.
• 예시) transaction relation은 transcation_2018, transaction_2019 등으로 구분할 수 있음
• 트랜잭션에 기록된 쿼리는 모든 partion의 record에 액세스해야 함
  • 쿼리에 year=2019와 같은 선택 항목이 없는 경우(이 경우 필요한 partion이 하나만 있음)
• Partitioning
  • free space management와 같은 일부 운영 비용 절감
  • 서로 다른 저장 장치에 서로 다른 partition을 저장할 수 있음
    • 예시)  SSD의 올해 트랜잭션 PARTION, 자기 디스크의 오래된 연도 트랜잭션 파티션

(3) Data Dictionary Storage

• Data dictionary(system catalog로 불림)는 metadata, 즉 데이터에 대한 데이터를 저장
  • realtion에  대한 정보
    • names of relations
    • 각 relation의 속성의 names, types and lengths
    • view의 name과 definition
    • 무결성 제약 조건
  • 암호를 포함한 사용자 및 계정 정보
  • 통계 및 기술 데이터
    • 각 relation의 tuple 수
  • 실제 파일 구성 정보
    • relation 저장 방법(sequential/hash/...)
    • relation의 물리적 위치
  • index에 대한 정보

(4) Relational Representation of System Metadata

• disk의 relational representation
• 메모리에서 효율적인 접근을 위해 설계된 특수 data structure

6) Database Buffer

(1)  Storage Access

• block은 저장공간 할당과 data 전송의 단위
• 데이터베이스 시스템은 디스크와 메모리 간의 block 전송 횟수를 최소화하려고 함
• 메인 메모리에 가능한 많은 블록을 유지하여 디스크 접근 수를 줄일 수 있음
• Buffer : 디스크 block 복사본을 저장하는 데 사용할 수 있는 main memory의 일부
• Buffer manager : main memory에서 buffer 공간을 할당하는 역할을 하는 subsystem

(2) Buffer Manager

• 프로그램은 디스크에서 차단이 필요할 때 buffer manager를 호출
  • block이 이미 buffer에 있는 경우 buffer manager는 main memory에 있는 block의 주소를 반환
  • block이 버퍼에 없으면 buffer manager
    • block에 대한 버퍼 공간을 할당
      • 필요한 경우 새 block을 위한 공간을 확보하기 위해 다른 block을 교체(throwing out : 폐기)
      • 디스크에 기록된 block은 디스크에서 가장 최근에 기록/fetch한 이후 수정된 경우에만 교체
    • 디스크에서 버퍼로 block을 읽고 main memory에 있는 block의 주소를 requester에게 반환
• Buffer replacement strategy(이후에 다룸)
• Pinned block : 디스크에 다시 쓸 수 없는 메모리 block
  • Pin은 block에서 데이터 읽기/쓰기 전에 설정
  • Unpin은 읽기/쓰기 완료될 때 설정
  • Multiple concurrent pin/upin operation 가능
    • pin count를 유지하고 pin count = 0인 경우에만 버퍼 블록을 제거할 수 있음
• Shared and exclusive locks on buffer
  • 동시 작업이 page 내용을 이동/재구성할 때 읽기를 방지하고 한 번에 하나의 이동/재구성만 보장하는 데 필요
  • reader는 shared lock을 얻고, block에 대한 업데이트에는 exclusive lock이 필요
  • Locking rules
    • 한번에 하나의 프로세스만 exclusive lock을 얻을 수 있음
    •  shared lock은 exclusive lock과 동시에 사용할 수 없음
    • Multiple 프로세스에 동시에 shared lock이 부여될 수 있음

(3) Buffer-Replacement Policies

• 대부분의 운영 체제는 가장 최근에 사용되지 않은 block을 대체(LRU 전략)
  • LRU에 대한 아이디어 : block 참조의 과거 패턴을 미래 참조의 예측 변수로 사용
  • LRU는 일부 쿼리에 좋지 않을 수 잇음
• 쿼리에는 명확한  access pattern(sequential scan같은)이 있으며 데이터베이스 시스템은 사용자 쿼리의 정보를 사용하여 향후 참조를 예측할 수 잇음
• 쿼리 optimizer가 제공하는 replacement strategy에 대한 힌트가 있는 mixed strategy가 좋음
• LRU에 대한 잘못된 access pattern의 예 : 중첩 루트에 의한 2개의 relation 및 s의 조인을 계산할 때
  for each tuple tr of r do
       for each tuple ts of s do
           if the tuples tr and ts match ...
• Toss-immediate strategy : block의 최종 tuple이 처리되는 즉시 해당 block이 차지하는 공간을 확보
  → 위 예시의 r에 대해 유리
• Most recently used(MRU) strategy : 시스템은 현재 처리 중인 block을 pin으로 고정해야 한다. 해당 block의 최종 tuple이 처리된 후 block은 고정되지 않고 가장 최근에 사용된 block이 됨
• buffer manager는 요청이 특정 relation를 참조할 확률에 대한 statistical(통계적) 정보를 사용할 수 있음
  • ex) data dictionary는 자주 접근됨 → Huuristic(경험적인 지식) : data dictionary block을 메인 메모리 버퍼에 보관
• 운영 체제 또는 버퍼 관리자가 쓰기 순서를 변경할 수 잇음
  • disk의 데이터 구조가 손상될 수 있음
    • 예시) 디스크에 block이 누락된 block의 링크된 목록
    • 파일 시스템은 일관성 검사를 수행하여 이러한 상황을 탐지
  • 쓰기 순서를 신중하게 지정하면 이러한 많은 문제를 피할 수 있음
• 버퍼 관리자는 복구 목적으로 block의 forced output(강제 출력)을 지원
• Nonvolatile write buffer는 비휘발성 RAM 또는 Flash buffer에 즉시 block을 기록하여 disk 쓰기 속도를 높임
  • disk arm 이동을 최소화하기 위해 쓰기 순서 변경 가능
• Log disk : block update의 순차적 log를 작성하는 데 사용되는 디스크
  • 비휘발성 RAM과 동일하게 사용
    • 검색이 필요하지 않기 때문에 log disk에 쓰는 속도가 매우 빠름
• Journaling file system이 NVRAM 또는 log disk에 순서대로 데이터 쓰기
  • Journaling없이 reordering : 파일 시스템 데이터 손상 위험

7) Column-Orietned Storage

(1) Column-Oriented Storage

• columnar representation이라고도 함
• relation의 각 속성을 개별적으로 저장
• 예시

• 장점
  • 일부 속성만 접근하는 경우 IO 감소
  • CPU 캐시 성능 향상
  • 향상된 압축 기능(compression)
  • 현대 CPU 아키텍처의 Vector processing
• 단점
  • columnar representation을 통한 tuple 재구성 비용
  • tupe 삭제 및 업데이트 비용
  • 압축 해제(decompression) 비용
  • 일반 쿼리에 대해서 불리할 수 있음 → ex) select * from instructor where id = '77888'
• row-oriented representation보다 의사 결정 지원에 더 효율적
• 트랜잭션 처리에 적한한 Traditional row-oriented representation
• 일부 데이터베이스는 두 개의 표현 모두 지원
  • hybrid row/column stores라고 불림

Vector processing : CPU 아키텍처로 조건을 체크할 때 여러 개를 한 번에 처리 할 수 있다.