# 091 — 질의: 검증된 프로그램으로 SQLite보다 빠르게

2026-09-28. 외부 피드백 002의 둘째 항목(범용성)의 나머지 절반. [090](090-tables.md)이 표 크기의 상태와 여러 표에 걸친 트랜잭션을
세웠다면, 여기서는 그 표에 임의의 질의를 던진다. SQLite가 하는 집계, 조인, 상관 부질의를 같은 데이터에서 같은 답으로 겨룬다.

착수 기준:

- 바꿀 결정: 질의를 SQL 같은 별도 언어와 계획기로 줄지, 앱과 같은 검증된 모듈(aup의 보기)로 줄지. 별도 언어는 두지 않는다.
  질의는 앱의 상태 선언 위에 보기를 더한 모듈이고, 노드가 검증한 뒤 스냅숏에서 돈다. 빠르게 하는 일은 런타임이 모듈을 읽고
  스스로 한다(인덱스 선언이 없다).
- 최소 확인: pgbench의 표(10만 계좌, 지점 10, 창구 100, 이체 2만)에 네 질의 — 지점별 합계(GROUP BY), 걸러 세기, 세 표 조인,
  자기 조인 순위(상관 부질의) — 를 Pure와 SQLite 3.46.1에 같은 행으로 던지고, 답이 같은지 확인한 뒤 잰다. 빠르게 한 경로는
  항목별로 돈 결과와 결함까지 비트 단위로 같아야 한다.
- 중단 기준: 빠른 경로가 의미(결과, 결함의 종류와 위치, 합의 덧셈 순서)를 하나라도 바꾸면 그 경로를 쓰지 않는다.

## 질의

`PUT /queries/이름`이 `aup query 앱 질의`로 만든 모듈을 받는다. 노드는 그것을 검증하고, 상태 배치가 앱과 같은지, 그 이름의 보기가
있는지 본다. `GET /queries/이름?from=&count=`는 마지막 저장의 스냅숏에서 그 보기를 보인다. 쓰기는 기다리지 않고, 질의는 쓰기를
기다리지 않는다. 열 안의 fold는 그 열의 행을 읽을 수 있다(`OUTER_ROW`). 곧 상관 부질의다.

```aup
view per_branch = each b in branches {
  bid = b.bid
  total = sum(a.balance for a in accounts where a.bid == b.bid)
  accounts = count(a in accounts where a.bid == b.bid)
}
view ranks = each a in accounts where a.balance > 4900 {
  aid = a.aid
  richer = count(b in accounts where b.balance > a.balance)
}
```

## 찾은 것

처음 잰 값에서 Pure는 네 질의 모두 SQLite보다 느렸다. 지점별 합계 398 ms(SQLite 45 ms), 걸러 세기 14.5 ms(6.1 ms), 조인
3.3 ms(1.6 ms)였고, 순위는 9.2초가 걸려 연결 제한 시간(10초)에 걸렸다. 샘플러([sample.c](../../benchmarks/sample.c))가 이유를
셋으로 보여 줬다.

- **항목이 제각각의 할당이었다.** 잎은 항목의 포인터를 들었고, 항목마다 필드의 셀이 따로 할당되어 있었다. HTTP로 만든 목록은
  할당이 힙에 흩어져, 같은 세기가 재시작해 순서대로 읽어 들인 뒤(4.6 ms)의 세 배였다. 행마다 캐시 미스 하나다.
- **fold가 행마다 인터프리터를 불렀다.** 블록을 행마다 한 번 재귀 호출로 돌렸고, 필드 하나를 읽을 때마다 위치로 잎을 찾았다.
  시간의 54%가 인터프리터, 38%가 위치 찾기였다.
- **열 안의 fold가 행마다 목록 전체를 읽었다.** 지점 10개면 계좌를 20번 읽고, 부자 계좌 404개면 4,040만 번 비교한다. SQLite도
  인덱스가 없으면 같은 일을 한다(2.8초).

## 한 것

**잎이 항목을 필드별로 든다(`core/module-list.c`).** 잎 하나가 항목 32개의 셀을 필드마다 나란히 둔다. 수는 binary64 배열, 텍스트는
바이트 범위다. 항목에는 제 할당이 없다. 쓰기 시 복사는 잎 단위로 옮겨 갔다. 바꿀 때 잎까지의 경로를 복사하고, 텍스트는 공유한
채 둔다. 텍스트는 항목이 들던 공유 스탬프를 대신 든다. 스냅숏이 읽을 수 있는 텍스트는 풀지 않고 은퇴시킨다. 목록 끝에서의
분할은 가득 찬 잎을 그대로 두어, 끝에서 자라는 목록(이력, 키 순서로 채운 키 목록)은 잎이 가득 찬다. 3수 1텍스트 계좌 하나가
약 130바이트(할당과 잎의 포인터)에서 잎 안의 41바이트가 됐다. `pure_list_run`과 `pure_list_next`는 잎의 열을 차례로 준다.
경로를 들고 다음 잎으로 가며, 그다음 잎을 미리 가져온다(복사된 잎은 메모리에서 멀리 떨어져 있다).

**fold와 필터를 잎 하나씩 돌린다(`core/module.c`).** 로드할 때, 블록의 모든 명령이 레인 형태를 가진 fold(수와 인덱스만 쓰고
분기와 텍스트가 없다)와 표 필터에 표시를 한다. 그런 블록은 잎의 항목 모두에 대해 한 번에 돈다. 값은 항목마다 하나(잎의 열을
제자리에서 읽거나, 스택 깊이마다 한 줄에 계산), 항목의 위치, 또는 모두에 하나다. 모두에 같은 값으로 찾는 조회(바깥 행의 필드
같은)는 잎마다가 아니라 fold마다 한 번 한다.

레인은 인터프리터가 계산할 것만 계산한다. 어떤 항목이 결함을 낼 수 있으면(0으로 나누기, 유한하지 않은 결과, 없는 키, 끝을
넘은 인덱스, 거꾸로 된 clamp, 정수가 아닌 이동) 그 잎 전체를 항목별로 다시 돈다. 그래서 fold는 전과 똑같이 결함을 내고, 필터는
그 항목을 빼며, 항목은 순서대로 fold에 들어가 합은 전과 같은 순서로 더해진다.

**열 안의 fold는 목록을 한 번 지나 모든 행에 답한다.** 로드할 때, 레인으로 도는 열 안의 fold가 "항목의 필드를 행이 주는 키와
비교하고, 나머지는 목록·항목·상수만 읽는" 모양이면 표시를 한다(`PureShape`).

- **그룹:** 필드가 키와 같다. 앱은 fold와 목록의 판마다 한 번의 통과를 둔다. 비교를 참으로 두고 키 계산을 건너뛰어 블록을 잎
  하나씩 돌리고, 항목을 필드 값의 그룹에 fold한다. 곧 해시 집계다.
- **순위:** 필드가 키에 대해 어떤 순서인지 세는 count(다른 조건 없음). 통과는 필드 값을 기수 정렬하고, 행마다 이분 탐색한다.

행은 제 키만 돌려 찾는다. 통과는 같은 목록을 묻는 두 번째 행에서 만든다. 한 번만 묻는 fold는 한 번 훑는다. 답은 fold 그대로다.
항목은 그룹에 순서대로 들어가 합의 덧셈 순서가 같다. 키가 결함을 내면 그 행은 fold를 쓰인 대로 돌린다(그러면 쓰인 대로 결함을
내거나, 항목이 없으면 내지 않는다). 통과 중 어떤 항목이 결함을 내면 모든 행이 쓰인 대로 돈다.

**검사.** `core/test-module.c`의 `lane_folds`는 300판 동안 무작위로, 타입이 맞는 fold를 만든다. 보기에, 표의 열(그 행을 읽는)에,
결과를 상태에 적는 핸들러에 넣고, 무작위 필터와 무작위 목록을 준다. 같은 모듈을 계획을 끈 채로 항목별로 돌린 것과 모든 보기,
행, 셀, 이벤트의 결과·결함 종류·결함 명령이 비트 단위로 같아야 한다. fold 3,600개가 모두 레인으로 돌고, 그중 그룹 185개와 순위
127개가 모양을 받아 통과 98개가 만들어진다. 결함 1,120건이 같다. `list_trees`는 이제 잎을 차례로 걷는 것도 모델과 대조한다
(세 층, 공유 사본 포함). ASan·UBSan 빌드에서도 통과하고, `make check`와 Vega의 검사도 통과한다.

## 장치가 말한 것

같은 데이터, 같은 답([queries.py](../../benchmarks/bank/queries.py),
[원시 결과](../../research/experiments/017-queries/2026-09-28-bank-queries-linux-aarch64.jsonl)). Pure는 HTTP와 JSON을 포함하고,
SQLite는 파이썬에서 C 라이브러리로 부른다(프로세스 안, RAM). 중앙값, ms.

| 질의 | 처음 | 필드별 잎 | 잎 단위 | 통과 | SQLite | SQLite+인덱스 |
|---|---:|---:|---:|---:|---:|---:|
| 지점별 합계와 수(행 10) | 398 | 210 | 16.2 | **4.9** | 45.0 | 14.3 |
| 잔액이 양수인 계좌 수 | 14.5 | 4.7 | 1.1 | **1.05** | 5.9 | 0.16 |
| 큰 이체와 그 계좌·창구(행 212) | 3.3 | 1.5 | 0.77 | **0.48** | 1.47 | 1.51 |
| 부자 계좌마다 더 부자인 수(행 404) | 9,206 | 5,340 | 268 | **6.8** | 2,840 | 7.6 |

"SQLite+인덱스"는 DBA가 이 질의들을 위해 더할 인덱스(잔액, 지점과 잔액)를 만들고 ANALYZE한 뒤다. Pure에는 인덱스가 없다.
질의의 모양만 보고 스스로 계획한다. pgbench의 표 그대로의 SQLite보다는 3–420배 빠르고, 인덱스를 준 SQLite보다도 계좌 수 세기만
빼고 빠르다. 그 하나는 SQLite가 인덱스의 범위를 세는 동안 Pure는 10만 행을 훑는다(0.16 대 1.05 ms, 그중 HTTP가 약 0.15 ms).

잎 단위 평가는 항목당 약 5 ns(순서대로 놓인 잎)에서 7 ns(흩어진 잎)다. 통과가 없는 순위는 행 404개 × 10만 항목을 268 ms에
끝낸다. SQLite의 같은 비교 루프보다 10배 빠르다.

## 다음

- **통과를 요청 사이에 둔다.** 통과는 요청 하나의 읽기 앱에 있다. 목록이 바뀌지 않은 동안의 다음 요청(대시보드)은 다시 만든다.
  목록의 판으로 열쇠를 삼아 질의 모듈에 두면, 열 밖의 fold(계좌 수 세기)도 순위 통과로 O(log n)이 된다.
- **긴 질의를 연결 스레드 밖으로.** 질의는 소유자(쓰기)를 막지 않지만, 받은 연결 스레드의 다른 요청은 그동안 기다린다. 질의
  일꾼과 실행량 상한이 필요하다.
- **정렬과 그룹의 문법.** 지금 GROUP BY는 그룹 목록 위의 상관 fold로 쓴다. `order by`, 계산한 키의 `distinct`, 필터 안의 fold
  (EXISTS)가 다음이다.
- **대량 적재와 쓰기 증폭(090의 다음).**