16 · 쿼리 실행: 세그먼트 스캔과 커서 페이지네이션

"최근 1시간 동안 alice가 건드린 문서를 최신순으로 20건 보여줘" — 이 한 줄 질문을 처리하는 경로를 따라가 봅시다. 어디서 스캔을 건너뛰고, 어떻게 커서가 다음 페이지를 가리키며, 왜 느린 쿼리가 빠른 쓰기를 막지 않는지가 보입니다. DB의 table scan vs index scan, LIMIT/OFFSET vs keyset pagination과 비교하면 설계 의도가 더 선명해집니다.

당신이 아는 것: table scan, index scan, OFFSET vs keyset

DB에서 쿼리 플랜은 크게 두 가지입니다. table scan(heap scan): 테이블 전체를 읽고 필터를 적용합니다. index scan: 보조 인덱스에서 조건에 맞는 행 주소를 먼저 꺼낸 뒤, 그 주소로 테이블을 직접 조회합니다.

페이지네이션도 마찬가지입니다. LIMIT 20 OFFSET 1000은 앞 1000건을 읽고 버립니다 — O(offset) 비용이 뒤로 갈수록 불어납니다. 대신 keyset pagination(커서 기반)은 마지막으로 받은 행의 키를 기억해 두고, WHERE id > 마지막id LIMIT 20처럼 정확히 다음 건부터 가져옵니다. 어느 페이지든 O(1) 비용.

쿼리 선언: LogQuery

사용자는 LogQuery를 만들어서 전달합니다. 모든 조건은 AND로 묶입니다.

crates/quipu-core/src/query.rspub struct LogQuery {
    pub from_micros: Option<u64>,   // 시간 범위 (inclusive)
    pub to_micros:   Option<u64>,
    pub method:      Option<String>, // HTTP 메서드
    pub url_prefix:  Option<String>,
    pub actor:       Option<TargetFilter>, // 행위자 조건
    pub targets:     Vec<TargetFilter>,  // 타깃 조건들 (AND)
    pub custom:      BTreeMap<String, Value>,
    pub limit:       Option<usize>,
    pub order:       Order,              // Asc | Desc (기본 Desc=최신순)
    pub cursor:      Option<String>,     // keyset 커서
}

TargetFilter에는 MatchMode가 있습니다 — Exact(정확 일치), ExactCi(대소문자 무시), Prefix(접두사), Contains(부분문자열). 각 모드는 15장 인덱싱의 인덱스 타입과 짝을 이룹니다.

3단계 실행 경로

쿼리를 실행하면 ReadSnapshot::query_page()가 세 단계를 밟습니다.

단계 1: 레지스트리 인덱스 조회

targets 필터가 있으면, 먼저 레지스트리 인덱스에서 조건에 맞는 모든 entity_id를 찾고, 그 엔티티 버전들이 등장하는 log_id 집합을 관계(relation) 로그에서 추출합니다. 여러 타깃 필터는 교집합(AND)으로 좁혀집니다.

crates/quipu-core/src/store.rs (ReadSnapshot)fn resolve_filters(&mut self, q: &LogQuery) -> Result<ResolvedFilters> {
    let mut allowed_by_target: Option<HashSet<Uid>> = None;
    for f in &q.targets {
        let ids = self.log_ids_for_filter(f, q.from_micros, q.to_micros)?;
        allowed_by_target = Some(match allowed_by_target {
            Some(prev) => prev.intersection(&ids).copied().collect(), // AND
            None => ids,
        });
    }
    // actor 조건도 비슷하게...
}

타깃 필터가 없으면 이 단계를 통째로 건너뜁니다. 있으면 log_id 집합을 미리 확보하여 스캔 중 행별로 집합 멤버십만 확인하면 됩니다.

단계 2: PositionedScan — 세그먼트 가지치기와 시간 필터

로그 스캔의 핵심은 PositionedScan입니다. 이 구조체는 세 수준의 최적화를 담당합니다.

세그먼트 프루닝: 각 sealed 세그먼트는 min_ts / max_ts를 사이드카(.meta 파일)에 기록해 두었습니다. from_micros / to_micros와 비교해 범위 밖인 세그먼트는 파일 자체를 열지 않습니다. "최근 1시간" 쿼리가 1년치 세그먼트를 건너뛰는 것이 이 덕분입니다.

커서 프루닝: 이전 페이지의 마지막 위치(세그먼트 seq, 레코드 idx)를 저장한 커서가 있으면, 그 위치 이전 세그먼트 전체를 건너뜁니다.

Desc 방향: 파일 포맷이 순방향 프레임이라 직접 역방향 읽기는 불가합니다. 대신 한 세그먼트를 앞에서부터 읽어 버퍼에 쌓고, 버퍼를 뒤에서부터 꺼냅니다. 메모리는 한 세그먼트 크기(max_segment_bytes, 기본 64 MB)에 의해 상한이 결정됩니다.

crates/quipu-core/src/storage/table.rs (PositionedScan)fn prune(&self, s: &SegmentSlice) -> bool {
    // 시간 범위 밖인 세그먼트는 열지도 않는다
    if s.max_ts < self.from || s.min_ts > self.to { return true; }
    // 커서로 소비된 쪽 세그먼트도 건너뜀
    match self.after {
        Some(p) if !self.desc && s.seq < p.seq => true,
        Some(p) if  self.desc && s.seq > p.seq => true,
        _ => false,
    }
}

단계 3: QueryPage — 커서와 렌더링

스캔이 limit+1번째 히트를 만나면 즉시 멈추고 more = true로 표시합니다. 마지막으로 수집된 레코드의 물리 위치(Position)가 커서로 인코딩됩니다.

crates/quipu-core/src/query.rsconst CURSOR_LEN: usize = 1 + 1 + 8 + 8; // version + order + seq + idx

pub(crate) fn encode_cursor(order: Order, pos: Position) -> String {
    let mut b = [0u8; CURSOR_LEN];
    b[0] = CURSOR_V1;
    b[1] = (order == Order::Desc) as u8;
    b[2..10].copy_from_slice(&pos.seq.to_le_bytes()); // 세그먼트 번호
    b[10..18].copy_from_slice(&pos.idx.to_le_bytes()); // 세그먼트 내 인덱스
    URL_SAFE_NO_PAD.encode(b)
}

커서는 URL-safe base64로 인코딩된 불투명 토큰입니다. 클라이언트는 이걸 다음 요청의 LogQuery::cursor에 넣을 뿐, 해석하지 않습니다. 서버가 디코딩해서 "이 위치부터 다시 시작"합니다.

느린 쿼리가 빠른 쓰기를 막지 않는 이유

DB에서 느린 전체 테이블 스캔은 공유 버퍼 풀과 I/O를 독점해 다른 트랜잭션을 느리게 만들 수 있습니다. Quipu-Log는 이 문제를 스냅샷으로 완전히 분리합니다.

crates/quipu-core/src/store.rspub fn snapshot(&mut self) -> Result<ReadSnapshot> {
    Ok(ReadSnapshot {
        keys: self.cfg.keys.clone(),
        registries: self.registries.iter().map(|(k, v)| (k.clone(), v.idx.clone())).collect(),
        logs: self.logs.slices()?,     // 경로 + 바이트 경계만 복사
        relations: self.relations.slices()?,
    })
}

snapshot()은 레지스트리 인덱스(HashMap 클론)와 세그먼트 경로 목록만 복사합니다. 실제 파일 데이터는 복사하지 않습니다. 이 ReadSnapshot은 Send라서 다른 스레드에서 스캔해도 됩니다. 스냅샷 이후의 append는 새 레코드 / 새 세그먼트에만 가고, 스냅샷이 잡은 경계 밖이라 스캔에 보이지 않습니다.

이것이 14장 읽기 스냅샷과 MVCC에서 다룬 "읽기가 쓰기를 막지 않는" 원리가 쿼리 경로에서도 그대로 적용되는 예입니다.

QueryPage의 observability: segments_scanned

응답 구조 QueryPage에는 segments_scanned 필드가 있습니다.

crates/quipu-core/src/query.rspub struct QueryPage {
    pub logs: Vec<LogView>,
    pub next_cursor: Option<String>,
    /// 이 쿼리가 실제로 연 세그먼트 파일 수 — 프루닝 효과의 관측 지표.
    pub segments_scanned: u64,
}

"최근 1시간" 쿼리인데 segments_scanned가 전체 세그먼트 수와 같다면, 시간 범위가 인덱스로 표현되지 못하고 있다는 신호입니다(레코드 타임스탬프가 단조 증가하지 않는 경우, DLQ 재투입 등). 이 숫자로 쿼리 성능을 진단할 수 있습니다.

정리

• 쿼리는 세 단계: 인덱스로 log_id 집합 추출 → 시간 범위 프루닝으로 세그먼트 가지치기 → 순차 스캔 + limit 종료.
• keyset 커서는 마지막 레코드의 물리 위치(세그먼트 seq, 레코드 idx)를 담아, OFFSET처럼 앞 N건을 읽을 필요 없이 어느 페이지에서나 O(1)로 시작합니다.
• 커서는 append-only 덕분에 스냅샷을 가로질러 유효합니다 — 레코드는 영원히 같은 물리 위치에 있습니다.
• ReadSnapshot 클론으로 쿼리와 쓰기가 독립적으로 진행되어, 느린 전체 스캔이 emit을 차단하지 않습니다.