[DB] Distributed Database - ②

지난 글에 이어 Distributed Database에서 query를 어떻게 수행하고, join 연산을 어떻게 효율적으로 수행하는가에 대해 다룬다.

1. Distributed DB Queries

• 분산DB의 경우 Data의 저장 방식에 따라 query 수행이 달라진다.

※ DDBMS의 Data 저장 방식

• Fragmentation(분할) : Horizontal or Vertical
• Replication(복제) : Synchronous or Asynchronous

SELECT AVG(S.age) FROM Sailors S WHERE S.rating > 3 AND S.rating < 7

1) Horizontally Fragmented

• rating < 5 tuples => 서울
• rating >= 5 tuples => 부산
  rating 4를 찾기 위해 서울 site와 rating 5,6을 찾기 위해 부산 site를 모두 접근 & 각자 site에서 SUM(age)와 COUNT(age)를 계산해서 취합해야함

2) Vertically Fragmented

• sid, rating, tid => 서울
• sname, age, tid => 부산
  tid를 기반으로 서울 site와 부산 site를 조인한 후 쿼리 수행

3) Replicated

• Sailors 테이블이 서울과 부산에 동일하게 복제된 경우
  => local로 가져오는데 드는 비용(shiping cost)을 고려하여 1개의 site를 선택

2. Distributed Joins

• Sailors table(500page, 80 tuples/page) => 서울
• Reserves table(1000page, 100 tuples/page) => 부산
  S ⋈ R (s is outer, R is inner)

ver1. Page nested loop join

cost = 500D + 1000 x 500 x (D+S)
D : cost to read/write
S : shiping cost

ver2. Ship to one site
Ship reserves table to 서울

cost = 1000S + 4500D(3 X (500+1000))

3. Semi Join

• Semi join을 통해 Shiping cost 절감
  e.g. sid(join 컬럼) = 4bytes(int)라 가정
  S : 40000 tuples
  R : 100000 tuples

1. 서울 site에 Sailors 테이블을 조인속성(sid,PK)에 대해 프로젝션 수행
2. 결과를 부산으로 보냄 (즉 , sid 컬럼만 보냄)
3. 부산에서는 2-결과를 Reserve 테이블과 조인
4. 3-결과를 반환 (즉, S.sid = R.sid인 것만 보냄)
   약 16만개 bytes를 보내게됨
5. reduction을 서울로 보냄
6. 서울에서는 Reserve의 reduction과 Sailors 조인
   => shiping cost 감소

4. Bloom Join

• k size bit=vector를 사용
  e.g. 1000bit라 가정 시 1000bit만 보내면 됨

1. 서울 site에서 모든 조인컬럼(sid)을 0~k-1 bit로 hash
   (즉, sid의 hash 값이 0부터 k-1 사이에 존재)
   000110010 (bit-vector)를 부산으로 보냄
2. 부산 site에서 Reserve 테이블의 조인 컬럼에 대해 마찮가지로 hash를 수행하여 1-결과(bit-vector)의 '1'로 매핑된다면 "매칭"되었다는 뜻
3. 부산 site에서 k size bit vecotr를 보냄
   => 훨씬 저렴해짐

※ 결국, Semi join과 Bloom join은 여러 사이트에 존재하는 table을 조인할 때 shiping cost를 줄이고자 함.(semi join과 bloom join)