[HANA] Delta merge-2 (internal)

■ Delta (Differential Buffer) 개요

• 배경

  • Inserting new tuples directly into a compressed structure can be expensive

    • Sorted structure인 경우 특히 더~

    • 신규 데이터에 의해 Dictionary의 변경이 발생 가능
    • Attribute vector도 변경 가능
  • 실제 사례는 아래 참고
    • Insert Only Operation 참조 (https://ivans-story.tistory.com/m/54)

• Delta (Differential Buffer)

  • 신규 데이터는 Delta 영역에 저장됨

  • Dictionary에 바로 저장이 되어야 하나 Main store와의 병합 시 속도를 위해서 Fast search가 가능한 구조 이용함

    • Cache Sensitive B+ Tree (CSB+ Tree)

      
    • L2-Delta를 얘기하는 것임

• • 추가적인 Memory가 필요함
    • Compression이 적용되지 않음
    • 추가적인 CSB+ Tree 구조가 필요함

 

 

---

 

■ Merge Operation을 확인하기 전

• Tuple lifetime in Column Store

  • Step-0
    
    

  • Step-1
    
  • Step-2
    
• Tuple Lifetime
  • Main store와 Delta store에 동시에 존재함
  • Reorganization의 단계를 줄이기 위해서 Validation check를 위한 1-bit Flag를 적용
  • Invalidated tuple은 Reorganization이 수행될 때까지는 Table 내에 존재하게 됨

 

 

 

 

---

 

■ Merge Process

• Merge Overview
  
  • can be executed asynchronously
  • has as little impact as possible on all other operation
  • does not block any OLTP or OLAP transactions
  • Merge는 단일 테이블 단위로 Trigger됨
    • Amount of tuples in buffer
    • Cost model to 
      • Schedule
      • Task query cost into account
    • Manually
      
      
• 해결을 위해 새로운 영역을 생성
  • a new empty delta 영역
  • a copy of the main store (최소 Table이 필요한 Memory의 2배가 필요함)

          

 

• 수행 단계
  
  

  • Lock Delta-merge store(Differential buffer) and Main store 

  • Create a new empty Delta-merge store

  • Current Validity vectors are copied from old to new (Main store, Delta-merge store) 

    • Update로 인한 Old version

    • Deleted version

  • → Delete/Update의 실제적 반영

• Step-1) Prepare Merge Phase

 

• • Step-2) Attribute Merge Phase

• • 1. Combine Dictionaries
       1. Combine dictionaries (Delta-merge store and Main store)
          • Optionally remove unused values
          • Sort merge 방식으로 수행 됨
          • Main store의 Dictionary는 이미 Sorting 되어 있음
          • Delta-merge store의 Dictionary는 CSB+ tree에 저장되어 있음
            → Sorted dictionary 값을 쉽게 가져올 수 있음
       2. Mapping structure 생성 
          • (기존 위치 → 신규 위치 변경 용, Delta-merge store and Main store)
            
            
    2. Combine Attributes
       1. Main store의 Attributes 아래에 Delta-merge store의 Attribute 추가
       2. 위의 (b)에서 생성된 Mapping structure를 이용해서 Conversion  시킴

                           

 

• • Step-3) Commit Merge Phase
    • Table에 대한 Write Lock 생성 
      • Ensures that all running queries are finished before the switch to the new main store 
    • the valid tuple vector that was copied in the prepare phase is applied to the actual vector to mark invalidated rows. 
    • 새로 생성된 Store로 교체

 

• • Example (간략버전)
    

 

 

• • Example 
    • Pre-Step-0 : 초기 상태
      
    • Pre-Step-1 : Update 1
      
    • Pre-Step-2 : Update 2
      
    • Pre-Step-3 : Update 3
      
    • Step-1 : Validity Detection
    • Step-2 : Dictionary Merge
    • Step-3 : New Main Column
    • Result