inter & range Command

이번 포스트에서는 set, zset(sorted set) 자료구조에서 inter, union 어떻게 동작하는지 알아봅니다 

우선 무식하게 주어진 key의 value들을 다 읽어가면서 check, check 하면서 진행할것같다...라는 생각을 가지고

소스를 보기 시작했습니다.  어? 진짜네요;;;   set, zset 거의 동일합니다. set 기준 으로 설명하겠습니다. 

inter명령어 입니다.
sinterGenericCommand( reply할 client, set 첫 포인터, set자료구조의 갯수, 결과 저장할 set)
마지막 인자는 sinterstore명령어에서 사용하겠죠?

흐름은 아래와 같습니다.

(마지막이 key3이 아니라 key4;;;)

set[0]을 기준으로 set[1~-setnum-1]들이 크기순으로 오름차순으로 정렬된 상태까지 왔습니다.

크기순으로 정렬한 이유는 inter이기 때문에 아무래도 크기가 작으면 겹칠수 있는게 적다보니 일찍 break가 될 확률이
높기 때문에 했네요. 정말 볼때마다....한없이 작아집니다.;; 다음은 아래와 같은 흐름을 반복합니다.

다음은 union입니다.

위에 두번째 그림까지 진행을 합니다.

union은 inter와는 다르게 sunion, sunionstore 상관없이 dstset변수를 만들어서 이 변수에 결과를 저장한뒤, reply를
합니다.  sunionstore라면 dstset을 저장하고 sunion이라면 dstset을 reply하고 decrRefCount(dstset) 합니다.

마지막 diff입니다. 이건 재미있게도 두개의 알고리즘이 있습니다.

우선 두개의 알고리즘에 대해 알아 보겠습니다.
첫번째는 inter에서 본것처럼 s[0]을 기준으로 잡고 j = 1..setnum에 데이타가 있나 없나 비교를 해서
마지막에  j == setnum이면 dstset에 value를넣는 방식입니다.

두번재는 j = 0..setnum 반복문을 돌면서, j == 0 이면 dstset에 value를 저장하고 j != 0이면 dstset에 value를 제거합니다.

첫번재는  set[0]의 value크기만큼 돌면서 해당 value가 set[1..setnum-1]에 있는지 없는지 판단하고,
두번째는 뭐 가릴것 없이 모든 set의 value들을 다 탐색하는겁니다.

이 두개의 알고리즘 중 어떤걸 사용할지에 대한 판단은 아래와 같습니다.

Bit에서는 뭉탱뭉탱으로 하기라도 했지, set, zset의 inter, union은 시간복잡도가 높습니다. slowlog로 테스트로
해보고 서비스하시는게 좋을것 같네요 ; )

t_set.c에  #define REDIS_OP_INTER 2 ㅋㅋㅋ  복붙을 해서라도 내 작품을 만들자~!!!

Google에서 union algorithm, intersection algorithm 검색하니까 뭐좀 나오던데, 똑똑하신분들이.....흠흠