search

paust-team / paust-db

GNU General Public License v3.0
6 stars 5 forks source link

Design Query Plan #124

Open elon0823 opened 5 years ago

elon0823 commented 5 years ago

현재 meta data 를 Query 하고 real data 를 Fetch 하는 과정은 Query->Fetch / Query->Fetch 만 하는 시나리오로 한정하여 구현이 되어있는 상태입니다. 앞으로 paust-db 가 나아갈 방향은 하나의 Query문을 통해 Fetch 처리하는 것이 아닌 Query->Query->Query->Fetch / Query->Query->Fetch 같은 형식이 되어야 합니다. 때문에 하나의 Query에 한개의 Query Obj가 담기는 구조가 아닌 여러 Query Obj 가 담겨 처리하는 구조를 같이 고민하면 좋을 것 같습니다.

1dennispark commented 5 years ago

Query Plan

FST 기반의 Query Plan for Ranged Query

  1. Timeseries에서 FST 정의

    • State (t_n) : 약 m초 단위 timestamp에서 n번째 시간
    • Arc (data) : Arc는 State 간의 Edge 역할
      • Data Group의 label을 갖고 있음

  2. FST Construction

    • m초 단위로 들어오는 Data를 Group을 지정하고 레이블링함.
    • 기본적으로 m초 단위로 t_n+1을 찍고 t_n+1 ~ t_n 사이의 Arc를 생성하고 Data Group의 레이블을을 지정함.

  3. Ranged Query가 발생하면 다음을 수행

    • Ranged Query에서 start timestamp와 stop timestamp를 각각 index로 변경
      • m초 단위로 생성하였을 때 n = (timestamp - t_1) / m, t_n = t_1 + m * n
      • start timestamp -> (start timestamp - t_1) / m -> b
      • stop timestamp -> (stop timestamp - t_1) / m -> e
    • FST에서 b를 Start로 e를 Final로 지정하여 Shortest Path를 수행.
      • Shortest Path의 결과물로 나온 FST를 visit 하도록 Iterator를 만들고 session에 저장하여 Client에서 탐색할 수 있도록 함.
      • 이후 b ~ e를 잇는 Arc를 생성하고 FST의 visit 하는 모든 Arc를 저장
      • 만약 이미 존재한다면, 해당 Arc의 weight에 +1 함.

  4. Ranged Query에서 weight가 가장 낮은 Arc를 찾고 Prune을 수행함.

1dennispark commented 5 years ago

현재 여기서 개발 중...

kwjooo commented 5 years ago

@co1god m초 단위를 알려주는 trigger는 tendermint block생성이고 Data group은 block에 대한 정보(ex. blockheight)를 의미하는게 맞나요?

1dennispark commented 5 years ago

block에 대한 정보라기 보다는 음... 그냥 데이터의 키 그룹이라고 생각하면 될것같습니다. 근데 아직 이 부분이 명확하진 않아요