JOIN의 원리

NL(Nested Loop) , Merge 조인

 

USE BaseballData;

SET STATISTICS TIME ON;
SET STATISTICS IO ON;
SET STATISTICS PROFILE ON;

-- 조인 원리
	-- 1) Nested Loop (NL) 조인
	-- 2) Merge(병합) 조인
	-- 3) Hash(해시) 조인


-- Nested Loop 
SELECT top 5*
FROM players AS p
	INNER JOIN salaries AS s
	ON p.playerID = s.playerID;
	-- 상단 players에서 하나하나 salaries의 playerID를 비교하여 찾는 작업
	-- 효율이 떨어질 수 있지만, top 5 같이 끊을 수 있는 작업에서 빠르게 작동시킬 수 있음.

-- Hash
SELECT*
FROM salaries AS s
	INNER JOIN teams AS t
	ON s.teamID = t.teamID;


-- Merge
SELECT*
FROM players AS p
	INNER JOIN salaries AS s
	ON p.playerID = s.playerID;
-- 1단계) Sort(이미 정렬되어 있으면 Skip)
-- 2단계) One-To-Many (players(Outer)는 중복이 없다.)
--		  Many-TO-Many 경우 최악의 경우 시간복잡도 O(N*M)
--		  하지만 어쩔 수 없이 써야한다면 Many-To-Many를 사용하기도 한다.
-- 3단계) 서로 비교한다. 
	-- 2개의 테이블에서 0번째 값을 하나하나 비교한다.
	-- 만약 비교해서 같다면 픽업, 같지 않다면 서로 비교하여 작은 쪽이 다음 인덱스의 값으로 이동한다.

/*
최악의 경우 O(N + M) 비교할 데이터 N과 M
단, Outer가 unique해야 함 (One-To-Many)
c# 구현 부분
int p = 0; (players테이블의 인덱스 위치)
int s = 0; (salaries테이블의 인덱스 위치)
List<int> result = new List<int>();
while(p < players.Count && s < salaries.Count)
{
	if(players[p].playerId == salaries[s].playerId)
	{
		result.Add(players[p].playerId);
		s++;
	}
	else if(players[p].playerId < salaries[s].playerId)
	{
		p++;
	}
	else
	{
		s++;
	}
}
*/

 

 

 

Hash 조인

 

 

USE Northwind;

SET STATISTICS TIME ON;
SET STATISTICS IO ON;
SET STATISTICS PROFILE ON;

-- 조인 원리
	-- 1) Nested Loop (NL) 조인
	-- 2) Merge(병합) 조인
	-- 3) Hash(해시) 조인

SELECT* INTO TestOrders FROM Orders;
SELECT* INTO TestCustomers FROM Customers;

SELECT* FROM TestOrders; -- 테이블 수 830
SELECT* FROM TestCustomers; -- 테이블 수 91

--HASH

SELECT*
FROM TestOrders AS o
	INNER JOIN TestCustomers AS c
	ON o.CustomerID = c.CustomerID;

/*
	임시적 해쉬테이블을 생성 후, 사용하는 방식.
	Dictionary<int, Customers> hash = new Dictionary<int, Salary>();
	foreach(Customers c in CustomerID)
		hash.Add(c.customerId, c);

	List<int> result = new List<int>();
	foreach (Orders o in oreder)
	{
		if(hash.ContainsKey(o.customerId))
			result.Add(o.customerId);
	}

	해쉬테이블을 만드는 방법은 배열에 직접적 할당이기 때문에 메모리 할당에 과부하가 걸릴 수 있다.
	그러므로, 상대적으로 테이블 수가 적은 쪽을 해쉬테이블로 만든다.

	--> TestCustomers을 해쉬테이블로 만들어 활용한다.

	-- Hash
	1) 정렬이 필요하지 않다 => 데이터가 너무 많아서 Merge가 부담스러울 때, Hash가 대안이 될 수 있다.
	2) 인덱스 유무에 영향을 맏지 않는다.
		NL/Merge에 비해 확실한 장점
		HashTable 만드는 비용을 무시하면 안 됨 (수행빈도가 많으면 -> 결국 Index)
	3) 랜덤 엑세스 위주로 수행되지 않는다.
	4) 데이터 수가 적은 쪽을 HashTable로 만든는 것이 유리하다
*/