강의 75

[database] DB Lock

본 게시글은서울대학교 데이터사이언스대학원 이상원 교수님의데이터사이언스 응용을 위한 빅데이터 및 지식관리시스템 수업을학습을 목적으로 재구성하였습니다 이제 본 수업의 마지막 챕터인16. Transaction Management이다이 챕터는 크게 Lock Manager와 Recovery Manager로 나뉘는데이번 시간에는 lock manager를 위주로 배운다 우리가 transaction을 할 때마다 concurrency control도 해야하고프로그램이 언제 죽을지 모르기 때문에 recovery control도 해야한다그래서 위 ppt에서 양 옆에 lock manager(concurreny control)recovery manager가 각각 존재하고있다 위는 transaction sample이다은행에..

강의/database 2025.06.03

[system programming] Debugging

본 게시글은서울대학교 데이터사이언스대학원 성효진 교수님의데이터사이언스 응용을 위한 컴퓨팅 시스템 강의를학습을 목적으로 재구성하였습니다이번 수업시간에서는 디버깅에 대해서 다룬다시스템 프로그래밍보다는 약간 소프트웨어 엔지니어링 적인 주제인데쉽다고 여길 수도 있기 때문에디버깅할 때 그냥 이렇게 하면 좋구나~하는 정보를 얻는 느낌으로약간 가볍게 들어도 좋다고 한다 디버깅에 대해 알아보자 우선 기본적인 디버깅의 정의에 대해 배우고만약 scientific한 debugging에 대해 배우고 싶다면마지막에 소개된 책을 읽으라고 하셨다이 scientific debugging이란 과학적으로무언가를 검증하는 가설을 세우고 가설을 검증하는과학적인 방식으로 디버깅을 하는 것인데좀 더 체계적인 디버깅 방법이라고 한다 tools..

[system programming] parallel programming

본 게시글은서울대학교 데이터사이언스대학원 성효진 교수님의데이터사이언스 응용을 위한 컴퓨팅 시스템 강의를학습을 목적으로 재구성하였습니다저번시간에 이어서 남은 병렬 프로그래밍 부분을마무리 해보려고 한다 병렬 실행은 잘못 수행하면 더 많은 오버헤드가 발생해서수행 시간이 더 오래 걸릴 수가 있다이러한 부분은 실제로 연구가 많이 진행되고 있는 부분이다 위 ppt에서 T0이 병렬 실행을 해서 생길 수밖에 없는 오버헤드 값인데load imbalance, communication, excess work가 원인이 된다 mapping은 static mapping과 dynamic mapping으로 구분 가능하다 task queue에 있는 데이터를 스케줄 하는 시점에어디에 mapping할지 이런 것들을 동적으로 결정할 수가 ..

[system programming] program optimization & parallel programming

본 게시글은서울대학교 데이터사이언스대학원 성효진 교수님의데이터사이언스 응용을 위한 컴퓨팅 시스템 강의를학습을 목적으로 재구성하였습니다 저번 시간에 이어서compile optimization에 대해서 계속 해보려고한다 타일링도 굉장히 중요한 최적화 기법 중에 하나이다기본적으로 배열을 순차적으로 처음부터 끝까지nesting을 하는 것이 일반적인데타일링은 처음부터 끝까지 도는게 아니고tile이라고 하는 작은 iteration으로 쪼갠다음에하나하나 차근차근 또 도는 방식이다loop을 나누는 개념이라고 생각하면 편하다 타일링의 에씨이다B는 block size인데 타일의 크기이다이러한 타일링을 하는 가장 큰 이유는 바로cache locality 때문이다 만약 내가 코드를 병렬로 실행한다고 하면내가 타일링을 했..

[database] simpleDB로 buffermanager에서 LRU 알고리즘 구현하기

이번 수업 과제로DB의 buffer cache에서hit ratio를 높이기 위한 대표적인 알고리즘인LRU를 구현하는 과제를 받았다simpleDB란?simpleDB란 작은 규모의 database를 빌드해볼 수 있는간단한 database 구현 프로젝트이다 java와 c++ 버전이 있다고 하는데본 과제에서는 c++ 버전을 사용하였다 https://github.com/rotaki/simpledb GitHub - rotaki/simpledb: A C++ version of SimpleDB originally written in Java by Edward Sciore. The structure of SimpleDB is exA C++ version of SimpleDB originally written in Jav..

강의/database 2025.05.27

[database] Physical Query Algorithm & Query Optimization

본 게시글은서울대학교 데이터사이언스대학원 이상원 교수님의데이터사이언스 응용을 위한 빅데이터 및 지식관리시스템 수업을학습을 목적으로 재구성하였습니다이번 시간에 배울 내용이다 우리는 이 수업 아주 초반에모든 쿼리는 사실 관계대수라고 하는 연산자로부터 나왔다는 것을 배웠는데사실 관계대수는 같아도실제로 어떻게 구현되는지인 physical algorithm은 달라질 수 있다 따라서 현재 어떤 상황인지에 따라 best algorithm을 구현해야하는데오늘 배울 내용은 이것에 관한 내용이다 수업의 초반부에 배웠던 내용이다이런 논리적 연산자들을물리적으로 어떻게 구현할 것인가에 대한 내용이다 이러한 내용을 쿼리를 어떻게 처리할 것인가를 다루는 내용이라query processing 혹은 query evaluation이..

강의/database 2025.05.26

[database] External Sorting

본 게시글은서울대학교 데이터사이언스대학원 이상원 교수님의데이터사이언스 응용을 위한 빅데이터 및 지식관리시스템 수업을학습을 목적으로 재구성하였습니다이번 시간에 배울 내용은external sorting에 대한 내용이다 external sort는 정확하게 어떤 것이고그냥 sort랑은 뭐가 다른걸까?뒤로가면서 궁금증을 풀어보자 이번 챕터를 공부하면서 이해해야 하는 내용은 위와 같다sorting은 DBMS에서 왜 중요하며in memory sorting과 external sorting은 어떤 것일까? 그리고 external sorting의 대표 알고리즘인external merge sort에 대해 살펴보고B+Tree와 다른 sorting들도 살펴보자 그렇다면 우선 우리가 sorting을 왜 배워야하는지 간단하게 ..

강의/database 2025.05.25

[database] B+Tree Index의 insertion과 deletion (+hash indexing)

본 게시글은서울대학교 데이터사이언스대학원 이상원 교수님의데이터사이언스 응용을 위한 빅데이터 및 지식관리시스템 수업을학습을 목적으로 재구성하였습니다이전 시간에 배운 tree based index structure에서B+Tree에 대해서 좀 더 자세히 살펴보자우선은 inserting과 deletion이다 저번 시간에 DB index가 어떻게 값을 찾는지 배웠다각 data는 search key인 50000과뒤에 몇 번째 block의 몇 번째 slot에해당 record가 존재하는지를 의미한다 따라서 tree에서 검색해야할 key를 찾고해당 record를 찾아가는 구조를 갖고있다 따라서 data가 새로 insertion되너가 deletion될 때B+Tree의 경우 tree의 구조가 변경되게된다 B+Tree에 ..

강의/database 2025.05.25

[database] Tree-Structured Indexes (ISAM과 B+ Tree)

본 게시글은서울대학교 데이터사이언스대학원 이상원 교수님의데이터사이언스 응용을 위한 빅데이터 및 지식관리시스템 수업을학습을 목적으로 재구성하였습니다중간에 학회준비 때문에 급하게 올인한다고수업 내용 정리를 못했다..그래서 학회가 끝난 뒤에 몰아서 하려했는데양도 너무 많고 기억도 잘 안나서 쉽지 않은 것 같다 ㅎㅎ..그래도 어떧ㅎ게든 차근차근 해보려한다 이번 내용은 Database에서 index를 처리하는 법이고가장 대표적인 tree-structured indexes구조이다 RDBMS의 전체 시스템에서Files and Access Methods 부분에 해당한다 access method에는전체를 scanning하는full scanning과 index기반 method가 있다 본 내용을 통해 우리가 알아야하는..

강의/database 2025.05.25

[system programming] program optimization (compiler와 최적화 기법)

본 게시글은서울대학교 데이터사이언스대학원 성효진 교수님의데이터사이언스 응용을 위한 컴퓨팅 시스템 강의를학습을 목적으로 재구성하였습니다이번 시간에 정리할 내용은프로그램 최적화에 관련된 내용이다 컴파일 언어에서는 컴파일러가 우리가 작성한 코드를자체적으로 최적화를 해주는 역할을 한다그렇다면 컴파일러는 어떤 방법으로 최적화를 진행할까?또한 컴파일러 이외에우리가 코드 레벨에서 코드를 작성할 때어떻게하면 최적화된 코드를 작성할 수 있을까?이 프로그램 최적화는 이와 관련된 내용이다 이런 컴파일러의 최적화 과정을 이해해야우리가 어떻게 프로그램을 짜야하는지 알 수 있다고 한다 이번 시간에 배울 목차이다 우리가 보통 알고리즘을 공부할 때는asymptotic complexity라고 해서흔히 빅오 표기법으로 시간 복잡도를 ..