[2023-08-15] Intro to Database Systems 10강 - Sorting & Aggregation Algorithms

[jonyejin]

📌 개요

• 시간: 2023-08-15(화) 21:00
• 자료: 10강 Sorting & Aggregation Algorithms
• 참여자: 펭귄, 그루트, 렉사, 나강

✍️ 준비

아래 양식을 복사해 스터디 준비를 완료해주세요!

## 💬 생각

<!--강의를 듣고 생각한 내용을 3줄 내로 간단히 정리해주세요!-->

- ...

## ❓ 질문

<!--공부하면서 궁금한 점을 작성해주세요!-->

- ...

## 📚 참고 자료

<!--공부하면서 같이 공부한 자료를 첨부 및 공유해주세요!-->

- [...](...)

[CoodingPenguin]

💬 생각

• 여기까지 듣고나서 드는 생각은 해결해야 하는 어떤 문제가 있고, 이를 적절한 자료구조와 알고리즘을 선택해서 해결하는 느낌이다.
  • 근본 전공은 컴퓨터구조, 알고리즘, 자료구조인 듯..
• 정렬할 때 값(Value)를 저장하는 방식으로는 Early Materialization(튜플 자체를 저장)과 Late Materialization(Record ID만 저장)이 있다.
• 집계 방식으로는 Sorting과 Hashing이 있다.

❓ 질문

• 2-Way External Merge Sort에서 Number of Passes에서 $1 + [\log_2 N]$에서 $1$이 의미하는 바를 이해 못했다.
  • N-Way External Merge Sort 부분의 Number of Passes도 설명 부탁드립니다..
• External Hashing Aggregate 방식의 Phase 2는 Aggregation 결과를 나타내기 위한 단계인지?
  • 원래 예시인 distinct 값만 구하는 것 Phase 1인 Partition만 있어도 될 것 같아서 물어봅니다.
  • Phase 1은 고유한 값의 개수만큼 파티션이 생기는 것이라 보면 될지?

📚 참고 자료

• External Sort | CUBRID INSIDE

[jonyejin]

📝 내용

• 오늘은 좀 재미있어보이는 Query Executor을 다룬다!
• 왜 정렬해야하는가?
• 인메모리 정렬
• top-N heap sort(ORDER BY + LIMIT)
• External Merge Sort
  • 정렬 -> 합치기
  • 2-way external merge sort
  • double buffering optimization
  • comparison optimization
  • B+Tree써서 정렬하기
• Aggregations

[Nagunt]

💬 생각

• Query를 어떻게 실행하는가? 를 배웠다.
• Query는 정렬되어야 하는 경우가 있다. (ORDER BY)
  그런 경우가 아니더라도, 속도 향상 이나 여러 기능들에 사용하기 위해서 정렬된 상태로 결과값을 가져오는 것이 필요할 수 있다.
• Top-N Heap Sort
• External Merge Sort
• Aggregations

📚 참고 자료

• External Merge Sort에 대해서

[IamGroooooot]

💬 생각

여러 최적화 기법에 관해 배웠다.

• Memory에 Fit이 되냐 안 되냐에서 따라서 다른 전략을 선택해야 한다.
  • 실제로 메모리에 코드가 어떻게 메모리에 올라가며 실행이되는지 좀 더 면밀하게 파악할 수 있도록 노력해야 겠다는 생각이 듦.
• Sorted Run을 할 때 실제 value로 가져가는 것이 early 혹은 lazy하게 할 수 있을 배웠는데 key 여러 작업을 다한 다음에 나중에 필요할 때 Tuple을 fetch하는 Late materialization이 Columnar에서 유리하다는 것이 납득이 되며 흥미로웠음. 이런식으로 불필요한 data fetching 막을 수 있구나 싶었음.
• 2-way merge에서 워커가 블록 IO를 블록하지 않게 더블 버퍼링을 통해 prefetch하고 비동기적으로 write할 수 있도록 간단하게 최적화하는 기법을 배웠다.
• Comparison Optimizaton에서는 suffix truncation에서 같은 것만 full string comparison을 하는 등 여러 흑마술(최적화 기법)을 공부하는 기분이었다.
• Aggregation의 구현 선택지를 두개로 나눠서 설명하는 것이 흥미로웠다. 여기서도 랜덤 IO을 최대한 회피하려는 관점에서 설명하는데 모든 상황에서 맞다고 일반화하지 않도록 조심해야 할 듯.
  1. hashing은 sorting에서 유리 (특히, disk가 느릴 때)
     = cheaper, ephemeral, ordering 안 할 때 유리
  2. sorting

❓ 질문

• suffix truncation을 쓰는 부분을 알면 대충 디비 안에 어떤 데이터들이 있는지 유추할 수 있을 것임.
  • 그러면 민감 정보 같은 것은 오히려 DB에서 최적화해서 search하는 것을 배제하고 의도적으로 고의적으로 해야하나 싶음.
• 최적화의 방식을 분석하다 보면 얼마나 빨라지느냐에 따라 DB 데이터를 대충 파악할 수 있지 않을까? 이런 취약점이나 이런 보안은 디비 구현의 관심사가 아닌가 궁금함.
  • 애플리케이션 레벨에서 이런 것을 챙기다보면 보안이랑 최적화도 trade-off가 있을 것 같음..
• 여기서 쓰는 hashing의 cost는 매우 가볍나?? 뭔가 여기서 자주 일어나는 연산이나 변환에 관해서 회로 레벨에서 최적화된 전용 하드웨어 가속기를 달면 더 빨라질 수 있지 않을까..