diff options
Diffstat (limited to 'docs/research')
| -rw-r--r-- | docs/research/091-queries.md | 110 |
1 files changed, 110 insertions, 0 deletions
diff --git a/docs/research/091-queries.md b/docs/research/091-queries.md new file mode 100644 index 0000000..84cab90 --- /dev/null +++ b/docs/research/091-queries.md @@ -0,0 +1,110 @@ +# 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의 다음).** |