<div id="readability-page-1" class="page"><div>
  <main>
    <h3 id="데이터베이스에서-정렬이-중요한-이유">데이터베이스에서 정렬이 중요한 이유</h3>
<hr>
<ul>
<li>
<p>(DISTINCT, GROUP BY, ORDER BY, UNION)와 같은 많은 SQL 에서 정렬을 사용한다. 또한 조인을 할 때도 소트 머지 조인 같은 방법으로 조인을 한다.</p>
</li>
<li>
<p>만약 100GB의 데이터를 1GB의 램으로 정렬을 하려고 하면 어떻게 해야하는가? 버추얼 메모리를 사용하면 안되는가?</p>
</li>
<li>
<p>버추얼 메모리를 사용하면 실제 물리적인 양보다 더 많거나 심지어는 메모리 용량에 제한 받지 않는 것 처럼 사용할 수 있다. 또한 버추얼 메모리는 메모리 주소에 대한 참조를 디스크 입출력으로 변환하고 정렬을 시도할 떄 끔찍한 성능을 보여줄 것이다.</p>
</li>
</ul>
<h3 id="메인-메모리를-사용하지-않는-정렬-방법">메인 메모리를 사용하지 않는 정렬 방법</h3>
<hr>
<ul>
<li>
<ol>
<li>스트리밍 방식으로 데이터를 메인 메모리로 전송하는 방법</li>
</ol>
</li>
<li>
<ol start="2">
<li>데이터를 나누고 (메인 메모리 크기로) 그리고 나서 정복하는 방법</li>
</ol>
</li>
</ul>
<h4 id="스트리밍-방식">스트리밍 방식</h4>
<p><strong>싱글 버퍼링</strong></p>
<p><img src="https://dl.dropbox.com/s/sxuj6m8huk3k6cq/Screen%20Shot%202022-01-05%20at%2018.46.57.png" alt=""></p>
<ul>
<li>데이터가 인풋 버퍼에서 아웃풋 버퍼로 이동하고 중간에 데이터를 변환하는 함수가 있는 형태이다.</li>
</ul>
<p><strong>더블 버퍼링</strong></p>
<p><img src="https://dl.dropbox.com/s/bb1f75kfux9w623/Screen%20Shot%202022-01-05%20at%2018.54.18.png" alt=""></p>
<ul>
<li>
<p>계산하는 부분과 I/O를 처리하는 부분을 두 개의 스레드에서 처리하는 것이다. I/O 작업은 블록킹 되므로 백그라운드에서 동작한다.</p>
</li>
<li>
<p>더블 버퍼링 방식은 정렬 뿐만 아니라, 스트리밍에서 많이 사용한다.</p>
</li>
</ul>
<h3 id="정렬과-해싱">정렬과 해싱</h3>
<hr>
<p><img src="https://dl.dropbox.com/s/ckb4obngpes8yd9/Screen%20Shot%202022-01-05%20at%2019.11.30.png" alt=""></p>
<ul>
<li>
<p>정렬 : 정렬 키 값을 기준으로 정렬된 파일을 반환한다.</p>
</li>
<li>
<p>해싱 : 동일한 해시 값을 가진 2개의 레코드가 다른 해시 값을 가진 레코드로 분리되지 않도록 파일을 정렬함. 일치하는 레코드는 항상 연속적으로 저장된다.</p>
</li>
</ul>
<h3 id="정렬-2---way">정렬 2 - WAY</h3>
<hr>
<p><img src="https://dl.dropbox.com/s/5rw81otbgj8kjcm/Screen%20Shot%202022-01-05%20at%2019.21.11.png" alt=""></p>
<ul>
<li>페이지를 읽고, 정렬하고 다시 저장하는 방식이다. 더블 버퍼링과는 상관이 없다.</li>
</ul>
<h3 id="정렬---외부-정렬">정렬 - 외부 정렬</h3>
<hr>
<p><img src="https://dl.dropbox.com/s/kphuwzz714t1e2h/Screen%20Shot%202022-01-05%20at%2019.40.12.png" alt=""></p>
<ul>
<li>외부 정렬 방식은 처음에 버퍼 크기 만큼 나누고 나서, 이를 서로 병합하는 과정을 가진다.</li>
</ul>
<p><img src="https://dl.dropbox.com/s/bvf6z7y0ymrq59p/Screen%20Shot%202022-01-05%20at%2019.41.52.png" alt=""></p>
<ul>
<li>예를 들어서 다음과 같은 데이터가 있다고 가정을 하였을 때 각 버퍼 크기 만큼 나눈후에, 정렬을 한다.</li>
</ul>
<p><img src="https://dl.dropbox.com/s/upt2q3dfkgcj2po/Screen%20Shot%202022-01-05%20at%2019.43.10.png" alt=""></p>
<ul>
<li>그리고 나서 정렬된 버퍼끼리 병합을 하는데, 버퍼 상위에 있는 데이터를 화살표로 가리키면서 서서히 내려온다. 이렇게 하면 정렬된 데이터를 얻게 된다.</li>
</ul>
<h3 id="해싱">해싱</h3>
<hr>
<ul>
<li>
<p>해싱은 정렬이 필요하지 않은 경우에 사용되는 방법이다. 중복을 제거하거나 GROUP BY를 사용할 때 말이다.</p>
</li>
<li>
<p>GROUP BY에 따른 집계를 할 때 키에 따른 데이터의 집합이 필요한 것이지 정렬이 필요한 것은 아니기 때문이다.</p>
</li>
<li>
<p>해싱의 경우에도 두 단계로 나누어 진다. 바로 분할과 정복이다.</p>
</li>
</ul>
<h4 id="분할-divide">분할 (DIVIDE)</h4>
<p><img src="https://dl.dropbox.com/s/v1ugskoc2ob104y/Screen%20Shot%202022-01-05%20at%2020.16.43.png" alt=""></p>
<ul>
<li>해시 함수에 의해서 각 값은 버킷에 담기게 된다.</li>
</ul>
<h4 id="정복-conquer">정복 (CONQUER)</h4>
<p><img src="https://dl.dropbox.com/s/yol3mhiq9lfa5k8/Screen%20Shot%202022-01-05%20at%2020.14.54.png" alt=""></p>
<ul>
<li>해시 테이블에 담긴 값을 다시 해싱을 하여 분류한다.</li>
</ul>
<h3 id="참고-문헌">참고 문헌</h3>
<hr>
<ul>
<li><a href="https://www.youtube.com/watch?v=yookWzvnic0&amp;list=PLzzVuDSjP25Qpsaf7GxFDBEWwvQKCkCVl&amp;index=1">CS186Berkeley</a></li>
</ul>

    <a href="../../../../"> &gt;&gt; Home</a>
  </main>
</div></div>

Home on 개발자 이동욱

Lee Dong Wook

데이터베이스에서 정렬이 중요한 이유
(DISTINCT, GROUP BY, ORDER BY, UNION)와 같은 많은 SQL 에서 정렬을 사용한다. 또한 조인을 할 때도 소트 머지 조인 같은 방법으로 조인을 한다.
만약 100GB의 데이터를 1GB의 램으로 정렬을 하려고 하면 어떻게 해야하는가? 버추얼 메모리를 사용하면 안되는가?
버추얼 메모리를 사용하면 실제 물리적인 양보다 더 많거나 심지어는 메모리 용량에 제한 받지 않는 것 처럼 사용할 수 있다. 또한 버추얼 메모리는 메모리 주소에 대한 참조를 디스크 입출력으로 변환하고 정렬을 시도할 떄 끔찍한 성능을 보여줄 것이다.
메인 메모리를 사용하지 않는 정렬 방법
스트리밍 방식으로 데이터를 메인 메모리로 전송하는 방법
데이터를 나누고 (메인 메모리 크기로) 그리고 나서 정복하는 방법
스트리밍 방식
싱글 버퍼링
데이터가 인풋 버퍼에서 아웃풋 버퍼로 이동하고 중간에 데이터를 변환하는 함수가 있는 형태이다.
더블 버퍼링
계산하는 부분과 I/O를 처리하는 부분을 두 개의 스레드에서 처리하는 것이다. I/O 작업은 블록킹 되므로 백그라운드에서 동작한다.
더블 버퍼링 방식은 정렬 뿐만 아니라, 스트리밍에서 많이 사용한다.
정렬과 해싱
정렬 : 정렬 키 값을 기준으로 정렬된 파일을 반환한다.
해싱 : 동일한 해시 값을 가진 2개의 레코드가 다른 해시 값을 가진 레코드로 분리되지 않도록 파일을 정렬함. 일치하는 레코드는 항상 연속적으로 저장된다.
정렬 2 - WAY
페이지를 읽고, 정렬하고 다시 저장하는 방식이다. 더블 버퍼링과는 상관이 없다.
정렬 - 외부 정렬
외부 정렬 방식은 처음에 버퍼 크기 만큼 나누고 나서, 이를 서로 병합하는 과정을 가진다.
예를 들어서 다음과 같은 데이터가 있다고 가정을 하였을 때 각 버퍼 크기 만큼 나눈후에, 정렬을 한다.
그리고 나서 정렬된 버퍼끼리 병합을 하는데, 버퍼 상위에 있는 데이터를 화살표로 가리키면서 서서히 내려온다. 이렇게 하면 정렬된 데이터를 얻게 된다.
해싱
해싱은 정렬이 필요하지 않은 경우에 사용되는 방법이다. 중복을 제거하거나 GROUP BY를 사용할 때 말이다.
GROUP BY에 따른 집계를 할 때 키에 따른 데이터의 집합이 필요한 것이지 정렬이 필요한 것은 아니기 때문이다.
해싱의 경우에도 두 단계로 나누어 진다. 바로 분할과 정복이다.
분할 (DIVIDE)
해시 함수에 의해서 각 값은 버킷에 담기게 된다.
정복 (CONQUER)
해시 테이블에 담긴 값을 다시 해싱을 하여 분류한다.
참고 문헌
CS186Berkeley

데이터베이스 소팅과 해싱에 대해서 정리

댓글