1. CROSS JOIN 논리적으로 봤을 때 크로스 조인은 조인들 중에서 가장 단순한 형태이다. 크로스 조인은 카티전 곱(Cartesian Product) 이라는 하나의 논리적 쿼리 프로세싱 단계만 처리한다. 이 단계에서는 조인을 하기 위해 입력값으로 지정된 두 개의 테이블에 대해 연산을 해서 두 테이블 간의 카티전 곱 결과를 만들어낸다. 즉 하나의 입력 테이블에 있는 각 행은 다른 테이블의 각 행과 매칭된다. 따라서 하나의 테이블에 m개가 있고 다른 테이블에는 n개의 행이 있다면, 결과로는 m x n 개의 행이 만들어진다. CREATE TABLE dbo.TB_CUST( cust_no INT NOT NULL, cust_name NVARCHAR(100) NOT NULL CONSTRAINT PK_TB_CUS..
쿼리의 FROM 절은 논리적으로 가장 먼저 처리되는 부분으로, FROM 절 내에서 입력 테이블들간의 테이블 연산을 수행하게 된다. Microsoft SQL Server 에서는 네 종류의 테이블 연산자를 제공한다. JOIN, APPLY, PIVOT, UNPIVOT가 바로 이에 해당한다. JOIN 테이블 연산자는 표준 방식인데 비해 APPLY, PIVOT, UNPIVOT 은 T-SQL에만 있는 확장형 연산자들이다. 각 테이블 연산자들은 입력값으로 제공되는 테이블들을 대상으로 하며 논리적 쿼리 프로세싱 단계들을 적용한 다음, 테이블 형태의 결과를 반환한다. JOIN 테이블 연산자는 두 개의 입력 테이블을 대상으로 수행한다. 논리적으로 기본적인 조인 방식으로는 1) 크로스 조인(cross join) 2) 내부 ..
https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 해당 문제는 다익스트라 알고리즘을 사용하는 문제이다. 아래의 그림을 보며 이해해보자. 1 노드를 시작해서 4 노드로 가는 방법은 총 3가지 방법이 존재한다. 1) 1-> 4 로 바로 이동하는 방법이 존재한다. 해당 길을 이용하면 distance 는 15가 된다. 2) 1-> 2 -> 4 로 이동 하는 방법이 존재한다. 해당 경로를 이용하면 ..
https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 다익스트라 알고리즘을 응용하는 문제로 기본적인 정형화된 문제라기 보다는 생각을 깊이 해야 하는 문제이다. 예를 들어 1 번이 시작이고 5번(도착지라 가정)까지 COST 가 10 이하인 비용으로 최소 거리를 찾아야 한다고 가정해보자. 맨 처음으로 1 노드를 기준으로 인접한 노드의 COST 와 DISTANCE 를 탐색해준다. 또한 행렬표를 만들어서 특정 노드에서 ..
HASH JOIN 이란? 1. 기본 메커니즘 NL 조인은 인덱스를 이용한 조인 방식이므로 인덱스 구성에 따른 성능 차이가 심하다. 또한 인덱스를 아무리 완벽히 구성해도 랜덤 I/O 때문에 대량 데이터 처리에 불리하고 버퍼캐시 히트율에 따라 들쭉날쭉한 성능을 보인다. 소트 머지 조인과 해시 조인은 조인 과정에서 인덱스를 이용하지 않기 때문에 대량 데이터를 조인할 때 NL 조인보다 훨씬 빠르고, 일정한 성능을 보인다. 소트 머지 조인은 항상 양쪽 테이블을 정렬해야 하는데, 해시 조인은 그런 부담도 없다. 일반적으로 HASH JOIN은 아래의 알고리즘을 적용하여 조인을 수행한다. 작은 집합으로 해시 테이블을 생성하고 큰 집합을 읽으면서 해시 테이블을 탐색한다. 해시 테이블을 만드는데 사용되는 집합을 Bulid..
기본 매커니즘 병합(Merge) 조인은 소트 머지(Sort Merge) 조인으로 불리기도 한다. 소트 머지 조인은 조인에 참여하는 두 집합을 조인 키(컬럼) 순서대로 정렬(sort) 한 다음에 병합(merge) 한다. 인덱스에 의해 이미 조인 키 순서대로 정렬된 집합은 정렬 없이 곧바로 조인에 참여하게 된다. 일대다(One-to-Many) 관계를 맺고 있는 두 테이블 간에 병합 조인이 처리되는 과정을 pseudo 코드로 나타내면 아래와 같다. /*일대다 병합 조인 시*/ 양쪽 집합을 조인 키 순서대로 정렬한다. (* 인덱스를 통해 정렬된 집합을 곧바로 얻을 수 있는 쪽은 이 과정이 필요없다.) outer 집합에서 첫 번째 로우 o를 가져온다. inner 집합에서 첫 번째 로우 i를 가져온다. while(..
기본 매커니즘 중첩루프(Nested Loops) 조인은 가장 기본적인 조인 방식이며, 단어가 의미하는 것처럼 반복적으로 안쪽 테이블을 탐색한다. 여기서 바깥쪽에 있는 테이블을 outer table 이라고 부르고 안쪽에 있는 테이블을 inner table 이라고 부른다. 즉, outer table 을 기준으로 inner table 을 반복적으로 탐색하는 방식이라고 생각하면 된다 NL JOIN의 세부처리 1. 결합 대상 테이블 (TABLE A)에서 레코드를 하나씩 반복해가며 스캔. 이 테이블을 구동 테이블(driving table) 또는 외부 테이블(outer table)이라고 부른다. 다른 테이블(TABLE B)는 내부 테이블(inner table)이라고 부른다. 2. 구동 테이블의 레코드 하나마다 내부 ..
각 컴포넌트는 메모리 매니저를 사용해서 획득한 메모리 영역을 8Kb 단위로 구분해서 사용한다. 각 메모리 블록은 페이지라고 불린다. 버퍼 풀(버퍼캐시)은 대다수의 경우 SQL 서버가 확보한 메모리의 가장 많은 부분을 차지하는 영역으로, 데이터베이스의 데이터 페이지와 인덱스 페이지를 디스크에서 읽어들여 캐시하기 위해 사용된다. SQL 서버가 데이터를 조작하는 경우 버퍼 풀에 읽어들인 데이터를 사용한다. 그때 조작 대상 데이터를 취득하기 위해 매회 버퍼 풀 전체를 스캔하는 것은 아무리 고속 액세스가 가능한 메모리상의 조작이라고 해도 큰 오버헤드가 된다. 때문에 SQL 서버는 버퍼 풀에 데이터베이스를 배치할 때 해시 알고리즘을 사용한다. 각 데이터베이스가 가진 고유의 값을 토대로 해시값이 생성되고 해시 버킷이..
SQL 서버는 자기자신의 메모리 영역을 효율적으로 사용하기 위해 워크스페이스라 불리는 영역을 할당해서 관리한다. 워크스페이스는 다양한 용도별로 준비되는 영역이다. 워크스페이스의 사이즈 조정, 획득 및 내부 컴포넌트 할당 등의 메모리 관리 작업은 메모리 매니저라 불리는 컴포넌트가 담당한다. SQL 서버 프로세스의 내부에서는 유저의 요구와 내부 컴포넌트 등의 다양한 TASK가 실행되고 있다. 각 태스크는 다양한 처리를 실행하기 위해 메모리를 획득할 필요가 있다. 예를들면, 컴파일된 쿼리 실행 플랜을 메모리상에 배치하는 영역이 필요하다. 또는 클라이언트의 요구로 결과 세트의 정렬이 필요한 경우는 해당 TASK 영역이 메모리상에 필요하다. (이러한 용도 외에도 메모리를 필요로하는 수많은 T..
NUMA는 공유 메모리 아키텍쳐의 한 형태이다. 대다수의 경우 소규모 SMP(Symmetric Multiprocessing : 대칭형 멀티 프로세싱) 컴퓨터에 구현되어 있는 공유 메모리 아키텍처에서는 컴퓨터에 탑재되어 있는 모든 CPU가 메모리와 메모리 액세스에 사용하는 *버스를 공유하고 있다. *버스 : CPU와 메모리 사이에서 데이터를 교환하는 경로 SMP 아키텍처의 메모리와 버스 하나의 CPU가 메모리 액세스를 위해 버스를 점유하면 다른 CPU는 버스가 해제될 때까지 메모리 액세스를 할 수 없다. 때문에 내장되어 있는 CPU의 수가 늘수록 버스의 해제 대기 시간이 길어질 가능성이 있다. 또한 CPU 수의 증가에 의해 버스도 물리적으로 길어지기 때문에 그에 수반하여 메모리에 도달할 때까지 시간이 걸린..
