보미네

Hash Aggregate

나의 이전 두 글에서, stream aggregate 연산자를 다루었다. Stream aggregate 는 scalar aggregtates 와 group by 컬럼에 인덱스가 제공되거나 정렬이 필요한 aggregations 에 좋다. (예를들어, order by 절이 있는경우)

다른 또 하나의 aggregation 연산자는 hash aggregate 이다. 이것은 hash join과 비슷하다. 이것은 정렬순서를 유지할 필요가 없고, 메모리가 필요하며, 블럭된다 (즉, 이것은 모든 입력행을 다 처리하기 전까지 어떠한 결과도 만들지 않는다.). Hash aggregate 는 매우 큰 입력셋에서 효과적이다.

Here is pseudo-code for the hash aggregate algorithm:(Hash aggregate 알고리즘을 위한 슈도 코드)

for each input row
  begin
    calculate hash value on group by column(s)
    check for a matching row in the hash table
    if we do not find a match
      insert a new row into the hash table
    else
      update the matching row with the input row
  end
output all rows in the hash table

stream aggregate 가 한번에 한개의 group 값을 계산하는것에 반해 hash aggregate 는 전체 그룹을 동시에 계산한다. 이러한 그룹을 저장하기위해 hash table 을 사용한다. 각각의 새로운 입력행에 대해 hash table 을 체크하고, 입력된 행이 기존 그룹이 있는지 체크한다. 존재하면 해당 그룹을 간단히 업데이트 한다. 존재하지 않으면 새로운 그룹을 만든다. 입력되는 행이 정렬되어 있지 않기 때문에 입력되는 모든 행은 어떠한 그룹에도 속할 수 있다. 그러므로, 입력된 모든 행의 처리가 끝나기 전에 어떠한 결과값도 출력할 수 없다.

Memory and spilling (메모리와 넘침)

hash join 처럼 hash aggregate 는 메모리를 필요로 한다. hash aggregate 를 실행하기 전에, SQL Server 는 cadinality 예측에 기반해 얼마나 많은 메모리가 쿼리 실행에 필요한지 예측하게 된다. hash join 에서 각각의 빌드 입력을 저장한다. 그러므로, 전체 필요한 메모리는 빌드 입력의 행수와 사이즈에 비례한다. join 의 출력 cadinality 와 join 되는 행수는 join 의 메모리 필요량과 상관 없다.

hash aggregate 에서, 각각의 그룹에 하나의 행을 입력한다. 그러므로, 전체 메모리 요구량은 출력 그룹의 수나 행수에 비례한다. 만약 unique 값이 몇개 없고 group 이 몇개 되지 않는다면 메모리를 작게쓰고, 많은 unique 값이 있고, 그룹 컬럼의 개수가 많으면, 많은 메모리를 필요로 한다.

그래서, 메모리가 부족하면 어떤일이 일어날까? hash join 에서 메모리가 부족하면, tempdb 를 사용하게 된다. 부분적으로 aggregated 된 결과를 포함해 하나 이상의 bucket 이나 파티션을 디스크로 넘긴다. 이러한 행에 대해 aggregate 를 다시 시도하지 않지만, 이것들을 다시 hash 해 여러 bucket 이나 파티션으로 나누어야 한다. 모든 입력 그룹에 대해 처리가 끝나면, 메모리 내 그룹의 결과를 출력한다. 그리고, 메모리에서 넘친 부분을 다시 읽어 알고리즘을 반복 실행한다. 메모리에서 넘친 행이 여러 파티션으로 나누어지면, 각각의 파티션 수를 작게해 이러한 알고리즘이 여러번 반복되는 비효율을 줄인다.

주의할 점은, 중복 행이 hash join 에서는 큰 문제이다. 이것은 hash bucket 의 사이즈를 다르게 해 데이터 스큐(skew)를 유발하고, 크기가 고정된 작은 부분으로 나누기 어렵게 한다. 그러나 이러한 중복 행이 hash aggregation 에서는 유리하다. 왜냐하면, 하나의 그룹으로 축약되기 때문이다.

Example (예제)

옵티마이저는 테이블이 많은행과 많은 그룹을 가지면 hash aggregation 을 선호한다. 예를들어 100개의 행과 10개 그룹이 있으면 stream aggregate 를 한다.

create table t (a int, b int, c int)
 

set nocount on
declare @i int
set @i = 0
while @i < 100
  begin
    insert t values (@i % 10, @i, @i * 3)
    set @i = @i + 1
  end

select sum(b) from t group by a
  |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0) THEN NULL ELSE [Expr1011] END))
       |--Stream Aggregate(GROUP BY:([t].[a]) DEFINE:([Expr1010]=COUNT_BIG([t].[b]), [Expr1011]=SUM([t].[b])))
            |--Sort(ORDER BY:([t].[a] ASC))
                 |--Table Scan(OBJECT:([t]))

그러나, 1000개의 행과 100개의 그룹이 있으면 hash aggregate 를 한다.

truncate table t
 

declare @i int
set @i = 100
while @i < 1000
  begin
    insert t values (@i % 100, @i, @i * 3)
    set @i = @i + 1
  end
 

select sum(b) from t group by a
  |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0) THEN NULL ELSE [Expr1011] END))
       |--Hash Match(Aggregate, HASH:([t].[a]), RESIDUAL:([t].[a] = [t].[a]) DEFINE:([Expr1010]=COUNT_BIG([t].[b]), [Expr1011]=SUM([t].[b])))
            |--Table Scan(OBJECT:([t]))

group by 컬럼을 hash 했다. 나머지 비교 연산자(residual predicate)는 hash aggreate 가 hash 값 충돌이 발생 할 때 입력행을 hash table 에서 비교 할 때 사용된다.

hash aggregate 는 정렬이 필요없는 것도 볼 수 있다. 정렬은 hash aggregate 보다 더 많은 메모리를 필요로 한다. 왜냐하면,정렬은 1000개의 행을 정렬해야 하고 hash aggregate 는 100 개의 그룹값만 가지면 되기 때문이다. 하지만, 쿼리에서 order by 를 명시적으로 요구하면, 다시 stream aggregate 를 하는 것을 볼 수 있다.

select sum(b) from t group by a order by a
  |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0) THEN NULL ELSE [Expr1011] END))
       |--Stream Aggregate(GROUP BY:([t].[a]) DEFINE:([Expr1010]=COUNT_BIG([t].[b]), [Expr1011]=SUM([t].[b])))
            |--Sort(ORDER BY:([t].[a] ASC))
                 |--Table Scan(OBJECT:([t]))

만약, 테이블이 충분히 크고, 그룹의 수가 작으면, 옵티마이저는 hash aggregate 를 수행하고 결과를 다시 정렬하는 것이 비용 효율적이다 라고 판단한다. 예를 들자면, 10000 개의 행을 가지고 100개의 그룹을 가지면, 10000개의 행을 정렬하기보다 옵티마이저는 100개의 그룹을 hash 하고 정렬하게 된다.

truncate table t

set nocount on
declare @i int
set @i = 0
while @i < 10000
  begin
    insert t values (@i % 100, @i, @i * 3)
    set @i = @i + 1
  end

select sum(b) from t group by a order by a
  |--Sort(ORDER BY:([t].[a] ASC))
       |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0) THEN NULL ELSE [Expr1011] END))
            |--Hash Match(Aggregate, HASH:([t].[a]), RESIDUAL:([t].[a] = [t].[a]) DEFINE:([Expr1010]=COUNT_BIG([t].[b]), [Expr1011]=SUM([t].[b])))
                 |--Table Scan(OBJECT:([t]))

Distinct

stream aggregate 와 유사하게 hash aggregate 가 distinct 연산에도 사용될 수 있다.

select distinct a from t
  |--Hash Match(Aggregate, HASH:([t].[a]), RESIDUAL:([t].[a] = [t].[a]))
       |--Table Scan(OBJECT:([t]))

좀 더 흥미있는 것은

select sum(distinct b), sum(distinct c) from t group by a
  |--Hash Match(Inner Join, HASH:([t].[a])=([t].[a]), RESIDUAL:([t].[a] = [t].[a]))
       |--Compute Scalar(DEFINE:([t].[a]=[t].[a]))
       |    |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1018]=(0) THEN NULL ELSE [Expr1019] END))
       |         |--Hash Match(Aggregate, HASH:([t].[a]), RESIDUAL:([t].[a] = [t].[a]) DEFINE:([Expr1018]=COUNT_BIG([t].[b]), [Expr1019]=SUM([t].[b])))
       |              |--Hash Match(Aggregate, HASH:([t].[a], [t].[b]), RESIDUAL:([t].[a] = [t].[a] AND [t].[b] = [t].[b]))
       |                   |--Table Scan(OBJECT:([t]))
       |--Compute Scalar(DEFINE:([t].[a]=[t].[a]))
            |--Compute Scalar(DEFINE:([Expr1005]=CASE WHEN [Expr1020]=(0) THEN NULL ELSE [Expr1021] END))
                 |--Hash Match(Aggregate, HASH:([t].[a]), RESIDUAL:([t].[a] = [t].[a]) DEFINE:([Expr1020]=COUNT_BIG([t].[c]), [Expr1021]=SUM([t].[c])))
                      |--Hash Match(Aggregate, HASH:([t].[a], [t].[c]), RESIDUAL:([t].[a] = [t].[a] AND [t].[c] = [t].[c]))
                           |--Table Scan(OBJECT:([t]))

이 실행계획은 논리적으로 저번 글에서 본 stream aggregate 와 같다. 하지만 정렬과, stream aggregate 와 merge join 한 대신에 hash aggregate 와 hash join 을 사용했다. 두개의 hash aggregate 가 중복을 제거하고 (하나는 distinct b 다른 하나는 distinct c) 두개의 hash aggregate 를 사용해 두개의 sum 값을 구했다. hash join 은 두 결과를 붙여서 마지막 결과를 만들었다.

Hints

"order group" 과 "hash group" 쿼리 힌트를 기술해 stream aggregate 와 hash aggregate 를 강제화 할 수 있다. 이러한 힌트는 전체 쿼리에서 모든 aggregation 연산자에 영향을 준다.

select sum(b) from t group by a option(order group)
select sum(b) from t group by a option(hash group)

Sql profiler

SQL 프로파일러를 사용해 hash join 이나 hash aggregate 메모리 초과를 검출 할 수 있다. ("Error and Warnings" 이벤트 클레서에서) "Hash Warning" 이벤트. 메모리 초과는 I/O 를 유발하고 성능에 좋지않는 영향을 준다. BOL 에서 이 이벤트에 대한 더 많은 정보를 얻을 수 있다.

by Craig Freedman

TVF 는 2가지가 있습니다.

inline TVF (Table Value Function) 과 Multi-statement TVF 로 나뉘며,

1. inlene TVF 는 parameterized view 와 동일하며,

2. multi-statement TVF 는 Table 변수를 지정하고, 여러 문장으로 나눈 while 이라던지 필요한 연산을 하고 결과값을 table 변수에 넣어서 출력 합니다. 그럼 성능이 좋을까요? 성능이 좋을리 없겠죠 table 변수는 통계정보가 없기 때문에, SQL 엔진은 cadinality 정보를 얻어 optimize 과정에서 효율화를 못하게 됩니다. 상대적으로 비효율적인 플랜은 나쁜 성능으로 이어지기도 합니다. 고의로 이러한 과정이 필요한 경우도 있을 것이고 그것이 성능이 좋아지는 경우도 있겠지만 이 두 차이를 이해하신다면, 경우에 따라서 어떤것을 써야 할 지 선택 할 수 있으리라 봅니다.

TVF 가 주요하게 성능을 향상시키는 경우는 배열 형태의 변수를 다른 프로시저로 전달해야 하는데, 하나하나 procedure 를 호출하는 것 보다 한번에 다 담아서 한번에 Call 하게 된다면 엄청난 성능향상이 있겠죠 이런 여러 차이점이 있으니 이것이 이것보다 좋아요 라고 말하기 보다는 It depends 라고 말하게 되지요...

TVF 가 특별하게 resultset cache 기능이 없는한 TVF 로 만드는 것은 의미가 없어 보입니다. 프로시저로 통일하고 적절하게 table 형태의 변수가 필요한 경우에만 사용

쿼리의 실행 방법을 이해하고 필요없이 사용된 many-to-many join 을 query 재작성을 통해 one-to-many 조인을 이용해 값을 구하는 방법을 보여준다. one-to-many 조인은 temp 를 사용하지 않고, many-to-many join 은 temp 를 사용하기에 결과 양이 많아지면 i/o 성능에 문제가 생기기도 한다. 그러나, 실행계획을 이해하라고 글을 번역해 놓은것이지 성능을 높이기 위해 이러한 방법을 쓰라는 것은 아니다. 성능 튜닝은 다른 방법이 더욱 효율적일 수 있다.


Stream Aggregate

GROUP BY 절이 있을때, 보통 aggregate 를 수행하기 위해 SQL Server 는 두개의 물리 연산자를 가지고 있다. 하나는 저번주

에 보았던 stream aggregate 이다. 나머지 하나는 hash aggregate 이다. 이번 포스트에서는 stream aggregate 의 동작을 자

세히 살펴 보겠다.

The algorithm (알고리즘) -_- 이런건 번역하는게 이상하지만....

Stream aggregate 는 group by 컬럼(들)의 정렬된(sort) 데이터에 의존한다. 만약 하나 이상의 컬럼들이 그룹되면, 해당 모

든 컬럼들의 어떤 정렬 순서를 선택한다. 예를들면, 컬럼 a b 를 그룹하면, (a, b) 나 (b, a) 로 정렬할 수 있다. 이 정렬은

group by 컬럼을 위한 같은값을 가지는 행의 집합이 서로 인접하게 만들어 준다.

이것은 stream aggregate 알고리즘을 위한 슈도코드이다.

clear the current aggregate results
clear the current group by columns
for each input row
  begin
    if the input row does not match the current group by columns
      begin
        output the aggregate results
        clear the current aggregate results
        set the current group by columns to the input row
      end
    update the aggregate results with the input row
  end

예를들어 sum 값을 계산한다고 가정하면, 각각의 입력행에 대해 입력된 행이 현재 그룹에 속하면, (즉, 입력행의 group by

컬럼(들)이 이전행의 group by 결과와 같으면) 현재 계산중인 total 값에 적당한 값을 sum 해 업데이트 한다.  입력값이 새

로운 그룹에 속하면 (즉, 입력행의 group by 컬럼(들)이 이전행의 group by 결과와 같지 않으면) 현재의 sum 값을 출력하고

sum 값을 0 으로 초기화 하고 새로운 그룹값 계산을 시작한다.

Simple examples (간단한 예제)

create table t (a int, b int, c int)
 
select sum(c) from t group by a, b
  |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0) THEN NULL ELSE [Expr1011] END))
       |--Stream Aggregate(GROUP BY:([t].[b], [t].[a]) DEFINE:([Expr1010]=COUNT_BIG([t].[c]), [Expr1011]=SUM([t].

[c])))
            |--Sort(ORDER BY:([t].[b] ASC, [t].[a] ASC))
                 |--Table Scan(OBJECT:([t]))

이것은 aggregate 하기전에 sort 가 필요하다는 점을 제외하면, 우리가 예전에 봤던 scalar aggregate SUM 과 기본적으로 같

은 플랜이다. (scalar aggregate 를 전체 행에 대해 하나의 큰 그룹으로 생각 할 수 있다. 그러므로 하나의 scalar

aggregate 는 행을 다른 그룹으로 넣을 필요가 없으므로, sort 가 필요 없다.)

Stream aggregate 는 입력된 행의 정렬순서를 유지한다. 그래서, 만약 group by 컬럼으로 정렬을 요청하거나 group by 컬럼

의 일부로 정렬을 요구하면, 다시 정렬할 필요가 없다.

select sum(c) from t group by a, b order by a
 
  |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0) THEN NULL ELSE [Expr1011] END))
       |--Stream Aggregate(GROUP BY:([t].[a], [t].[b]) DEFINE:([Expr1010]=COUNT_BIG([t].[c]), [Expr1011]=SUM([t].

[c])))
            |--Sort(ORDER BY:([t].[a] ASC, [t].[b] ASC))
                 |--Table Scan(OBJECT:([t]))

위 실행계획은 바로위 실행계획에 비해 정렬컬럼만 반대로 바뀌었다. 이전 쿼리는 "(a,b)" 나 "(b,a)"로 정렬을 기술하지 않

았다. 이번에는 쿼리에 order by 절이 있고 컬럼 a 로 정렬을 요구했으므로 쿼리에서 컬럼 a 로 정렬을 먼저했다.

만약 우리가 적절한 인덱스가 있다면, 정렬이 필요없다.

create clustered index tab on t(a,b)
 
select sum(c) from t group by a, b
  |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0) THEN NULL ELSE [Expr1011] END))
       |--Stream Aggregate(GROUP BY:([t].[a], [t].[b]) DEFINE:([Expr1010]=COUNT_BIG([t].[c]), [Expr1011]=SUM([t].

[c])))
            |--Clustered Index Scan(OBJECT:([t].[tab]), ORDERED FORWARD)

select distinct

다음 쿼리를 생각해 보자

select sum(distinct b) from t group by a
각각의 group 에서 컬럼 b 의 중복값을 제거가 필요하다. 이전 포스트에서, 이러한 방법중 하나인 sort distinct 를 이용하는 방법을 보았다. 하지만 적절한 인덱스가 있으면, stream aggregate 를 이용해서 중복값을 제거 할 수 있다.

  |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0) THEN NULL ELSE [Expr1011] END))
       |--Stream Aggregate(GROUP BY:([t].[a]) DEFINE:([Expr1010]=COUNT_BIG([t].[b]), [Expr1011]=SUM([t].[b])))
            |--Stream Aggregate(GROUP BY:([t].[a], [t].[b]))
                 |--Clustered Index Scan(OBJECT:([t].[tab]), ORDERED FORWARD)

최상위의 aggregate 를 하는동안 최하위의 stream aggregate 는 중복값을 제거한다.

Multiple distincts (다중 distinct)

마지막으로 다음 쿼리를 생각해 보자

select sum(distinct b), sum(distinct c) from t group by a
 
  |--Merge Join(Inner Join, MANY-TO-MANY MERGE:([t].[a])=([t].[a]), RESIDUAL:([t].[a] = [t].[a]))
       |--Compute Scalar(DEFINE:([t].[a]=[t].[a]))
       |    |--Compute Scalar(DEFINE:([Expr1005]=CASE WHEN [Expr1018]=(0) THEN NULL ELSE [Expr1019] END))
       |         |--Stream Aggregate(GROUP BY:([t].[a]) DEFINE:([Expr1018]=COUNT_BIG([t].[c]), [Expr1019]=SUM([t].[c])))
       |              |--Sort(DISTINCT ORDER BY:([t].[a] ASC, [t].[c] ASC))
       |                   |--Clustered Index Scan(OBJECT:([t].[tab]))
       |--Compute Scalar(DEFINE:([t].[a]=[t].[a]))
            |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1020]=(0) THEN NULL ELSE [Expr1021] END))
                 |--Stream Aggregate(GROUP BY:([t].[a]) DEFINE:([Expr1020]=COUNT_BIG([t].[b]), [Expr1021]=SUM([t].[b])))
                      |--Stream Aggregate(GROUP BY:([t].[a], [t].[b]))
                           |--Clustered Index Scan(OBJECT:([t].[tab]), ORDERED FORWARD)

이전 글에서 살펴본 다중 scalar distinct 예제에서 살펴본 것과 같이, 이 쿼를를 두개의 부분으로 나누어 볼 수 있다. 각 distinct set 에서 하나는, distinct 한 c 값을 구하기 위해 sum(distinct c) 는 정렬이 필요하고, 반면 sum(distinct b) 값을 구할때는 clustered index 와 stream aggregate 를 이용해 정렬없이 구했다. 그리고 마지막 결과를 구하기 위해 group by 컬럼 a 에 대한 각각의 sum 값을 merge join 했다. merge join 을 사용한 것은 각각의 두 입력이 이미 group by 컬럼에 대해  이미 정렬되어 있기 때문이다. (compute scalar 연산인 [t].[a] = [t].[a]”는 내부 목적으로 필요하므로 무시하면 된다.)

aggregate 값은 unique를 보장하기 때문에 one-to-many merge join 이 사용되어야 하고, many-to-many 방법을 사용할 필요가 없다. 이것은 약간의 성능 문제이지 정확도 문제는 아니다. 쿼리를 명시적 join 으로 다시 작성하면 one-to-many join 을 얻을 수 있다.

select sum_b, sum_c
from
  (select a, sum(distinct b) as sum_b from t group by a) r
  join
  (select a, sum(distinct c) as sum_c from t group by a) s
  on r.a = s.a
 
  |--Merge Join(Inner Join, MERGE:([t].[a])=([t].[a]), RESIDUAL:([t].[a]=[t].[a]))
       |--Compute Scalar(DEFINE:([Expr1009]=CASE WHEN [Expr1020]=(0) THEN NULL ELSE [Expr1021] END))
       |    |--Stream Aggregate(GROUP BY:([t].[a]) DEFINE:([Expr1020]=COUNT_BIG([t].[c]), [Expr1021]=SUM([t].[c])))
       |         |--Sort(DISTINCT ORDER BY:([t].[a] ASC, [t].[c] ASC))
       |              |--Clustered Index Scan(OBJECT:([t].[tab]))
       |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1022]=(0) THEN NULL ELSE [Expr1023] END))
            |--Stream Aggregate(GROUP BY:([t].[a]) DEFINE:([Expr1022]=COUNT_BIG([t].[b]), [Expr1023]=SUM([t].[b])))
                 |--Stream Aggregate(GROUP BY:([t].[a], [t].[b]))
                      |--Clustered Index Scan(OBJECT:([t].[tab]), ORDERED FORWARD)

Next ...
다음번 포스트에는 다른 aggregation 연산자에 대해서 살펴보겠다. (hash aggregate)

by Craig Freedman