diff options
| -rw-r--r-- | CHECKPOINT.md | 1 | ||||
| -rw-r--r-- | README.md | 10 | ||||
| -rw-r--r-- | docs/research/091-queries.md | 110 | ||||
| -rw-r--r-- | research/experiments/017-queries/2026-09-28-bank-queries-linux-aarch64.jsonl | 4 |
4 files changed, 122 insertions, 3 deletions
diff --git a/CHECKPOINT.md b/CHECKPOINT.md index 21549e8..018ade0 100644 --- a/CHECKPOINT.md +++ b/CHECKPOINT.md @@ -19,6 +19,7 @@ | 성능(Pi 5) | 2026-09-27, 같은 기기에서 axum·drogon과 함께 쟀다. 문서 서버(한 스레드): 64 B GET 139k/s(CPU 1초당 140k; axum 127k·63k, drogon 147k·63k), 1 MiB GET 2,362/s(axum 1,304, drogon 754), 충돌 안전 PUT은 axum-atomic의 5.1–5.8배. 앱 서비스: 내구성 있는 쓰기 64연결 21.3k/s(axum·drogon 내구 약 200/s), 합계 GET 126k/s·두 스레드 153k(axum 136k, drogon 151k), 20행 페이지 두 스레드 148k(axum 93k, drogon 138k), 쓰기와 섞인 읽기 119k/s(axum·drogon 내구 1.1–1.4k/s). 유휴 RSS 2.3 MiB(axum 2.8, drogon 10.9), 최대 3.2–5.8 MiB(axum 6.6–9.7, drogon 11.9–78.8) | [075](docs/research/075-http-host-against-axum.md), [077](docs/research/077-apps-as-http-services.md), [080](docs/research/080-snapshot-reads.md), [081](docs/research/081-tail-records.md), [087](docs/research/087-small-reads-and-idle-memory.md) | | 표면과 메신저 | 사람을 위한 표면이 노드 안에서 돈다(`pure-serve --surface`): 마지막 저장의 스냅숏을 제자리에서 읽고, 친 키와 글자는 HTTP 요청과 같은 줄로 소유자에게 간다. Vega의 디스플레이·픽셀이 그 표면이다. 두 노드의 메신저(Vega `examples/messenger.aup`)는 서로에게 봉인·인증해 보내고, 한 줄이 상대 노드에 보이기까지 RAM 저장소에서 p50 0.79 ms·p99 1.1 ms, SD 카드에서 p50 3.5 ms(꼬리는 SD의 동기화) | [설계 010](docs/design/010-surfaces.md), [089](docs/research/089-messenger.md) | | 표 크기의 상태 | 목록이 영속 B+트리다(변경·키 탐색·저장본 위치 O(log n), 스냅숏 O(1), 1,600만 항목, 런타임 상태 1 GiB). pgbench의 TPC-B 같은 이체(세 표의 행과 이력, 한 트랜잭션)가 10만 계좌에서 RAM 24.5k/s(전: 3만 계좌 3.2k/s), SD 카드 내구 1,339/s(SQLite WAL FULL 84–153/s) | [090](docs/research/090-tables.md) | +| 질의 | 질의는 앱의 상태 위에 보기를 더한 모듈이다(`aup query`, `PUT·GET /queries/이름`). 검증한 뒤 스냅숏에서 돌고, 열 안의 fold가 그 행을 읽는다(상관 부질의). 잎이 항목을 필드별로 들고, fold와 필터는 잎 하나씩 돌며(결함이 날 잎만 항목별로), 열 안의 그룹·순위 fold는 목록을 한 번 지나 모든 행에 답한다. 10만 계좌에서 지점별 합계 4.9 ms(SQLite 45, 인덱스를 주면 14.3), 조인 0.48 ms(1.47), 자기 조인 순위 6.8 ms(2,840, 인덱스를 주면 7.6). Pure에는 인덱스 선언이 없다 | [091](docs/research/091-queries.md) | 키로 나눈 소유자와 저장을 넘길 스레드는 하지 않기로 했다. 이 장치는 동기화를 한 줄로 세워, 나누면 쓰기가 23% 줄고 넘겨도 기기의 일은 줄지 않는다([084](docs/research/084-parallel-syncs.md)). 대신 압축한 파일이 한 주기의 0을 미리 가져 커밋이 새 @@ -10,13 +10,17 @@ reads never wait for a sync. What an app sends is saved with its event and deliv batches, and a receiving app applies each message once; sealed to the receiver's key (HPKE, one session a wire, authenticated by the sender's key), no relay between them can read or change it, at the speed of unsealed sends. People use a node through surfaces it runs, reading its states where they are (Vega's display: a two-node messenger -shows a line on the other node's screen in about a millisecond). Measurements against axum and drogon on a Raspberry Pi 5 +shows a line on the other node's screen in about a millisecond). Queries are modules too: the app's states with views of +their own (`aup query`), verified when registered and shown from snapshots. Folds run a leaf of a list at a time and a +fold in a table's column is answered for every row from one pass over its list, so on pgbench's tables of 100,000 +accounts a group-by, a join and a correlated rank run 3–420x faster than on SQLite, and faster than SQLite given a +DBA's indexes but for one count, with no index declared. Measurements against axum and drogon on a Raspberry Pi 5 are in [075](docs/research/075-http-host-against-axum.md), [077](docs/research/077-apps-as-http-services.md), [080](docs/research/080-snapshot-reads.md), [081](docs/research/081-tail-records.md), [082](docs/research/082-json-in-place.md), [083](docs/research/083-delivery-over-http.md), [086](docs/research/086-sealed-sends.md), [087](docs/research/087-small-reads-and-idle-memory.md), -[088](docs/research/088-sealed-sessions.md), [089](docs/research/089-messenger.md) and -[090](docs/research/090-tables.md); the status table is +[088](docs/research/088-sealed-sessions.md), [089](docs/research/089-messenger.md), +[090](docs/research/090-tables.md) and [091](docs/research/091-queries.md); the status table is [CHECKPOINT.md](CHECKPOINT.md). The source follows the principle below, a small core with the rest selected around it 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의 다음).** diff --git a/research/experiments/017-queries/2026-09-28-bank-queries-linux-aarch64.jsonl b/research/experiments/017-queries/2026-09-28-bank-queries-linux-aarch64.jsonl new file mode 100644 index 0000000..4446efc --- /dev/null +++ b/research/experiments/017-queries/2026-09-28-bank-queries-linux-aarch64.jsonl @@ -0,0 +1,4 @@ +{"query": "per_branch", "rows": 10, "accounts": 100000, "pure_median_ms": 4.91, "pure_fastest_ms": 4.84, "sqlite_median_ms": 45.03, "sqlite_fastest_ms": 44.83, "sqlite_indexed_median_ms": 14.27, "sqlite_indexed_fastest_ms": 14.1} +{"query": "in_credit", "rows": 1, "accounts": 100000, "pure_median_ms": 1.05, "pure_fastest_ms": 0.93, "sqlite_median_ms": 5.9, "sqlite_fastest_ms": 5.87, "sqlite_indexed_median_ms": 0.16, "sqlite_indexed_fastest_ms": 0.16} +{"query": "large", "rows": 212, "accounts": 100000, "pure_median_ms": 0.48, "pure_fastest_ms": 0.45, "sqlite_median_ms": 1.47, "sqlite_fastest_ms": 1.47, "sqlite_indexed_median_ms": 1.51, "sqlite_indexed_fastest_ms": 1.47} +{"query": "ranks", "rows": 404, "accounts": 100000, "pure_median_ms": 6.79, "pure_fastest_ms": 6.76, "sqlite_median_ms": 2839.51, "sqlite_fastest_ms": 2837.71, "sqlite_indexed_median_ms": 7.6, "sqlite_indexed_fastest_ms": 7.5} |