手元に20万行のCSVがある。列ごとに集計したい。
BigQueryに入れるほどではない。Excelは開くだけで機嫌が悪くなる。オンラインのCSVツールは
アップロードを要求してくるが、中身は顧客データなので上げたくない。pandasを立ち上げるのも、
「この列のユニーク数だけ知りたい」には大げさすぎる。
結局やりたいのは1行だ。
SELECT city, COUNT(*) FROM data GROUP BY city ORDER BY 2 DESC
これがブラウザの中だけで動けば、アップロードの問題は消える。サーバーが無ければ、
送信先も無い。というわけでSQLエンジンを書いた。738行、依存ゼロ、<script> タグ1つで動く。
作ってみると、詰まったところがほぼ全部「CSVには型がない」に還元できたので、その話を書く。
全体の形
素直な3段構成にした。
SQL文字列
→ tokenize() 文字列 → トークン列
→ Parser.parse() トークン列 → AST（再帰下降）
→ run() AST + 行データ → 結果テーブル
対応しているのは、人がデータファイルに対して実際に打つ形だけ。
SELECT city, COUNT(*) AS n, AVG(amount) AS avg
FROM data
WHERE status = 'shipped' AND amount > 100
GROUP BY city
HAVING n > 10
ORDER BY n DESC
LIMIT 20
JOINは無い。サブクエリも無い。ファイルは1つしか開いていないので FROM の中身は読み飛ばす。
SELECT ... FROM data の data は飾りで、何と書いても同じものを見る。
再帰下降パーサは教科書どおりなので、面白いのはここから先だった。
罠1: CSVには型がない
CSVパーサが返してくるのは、全部文字列である。"100" であって 100 ではない。
つまり WHERE amount > 100 を評価する時点で、amount が数値なのか
「100個入り」みたいな文字列なのかを、エンジンが決めなければならない。
列全体をサンプリングして型を推論する手もあるが、CSVは平気で
amount 列に 1,200 や 未定 や N/A を混ぜてくる。列に型を1つ与えると、必ず裏切られる。
そこで列に型を持たせるのをやめて、比較のたびに両辺を見て決めることにした。
var NUM_RE = /^-?(?:\d+\.?\d*|\.\d+)(?:[eE][-+]?\d+)?$/;
function asNumber(v) {
if (typeof v === 'number') return v;
if (isBlank(v)) return null;
var s = String(v).trim();
return NUM_RE.test(s) ? parseFloat(s) : null;
}
function compare(a, b) {
if (isBlank(a) || isBlank(b)) return null; // NULL との比較は真でも偽でもない
var x = asNumber(a), y = asNumber(b);
if (x !== null && y !== null) return x < y ? -1 : x > y ? 1 : 0; // 両方数値 → 数値比較
var sa = String(a), sb = String(b);
return sa < sb ? -1 : sa > sb ? 1 : 0; // それ以外 → 文字列比較
}
両辺が数値に見えるときだけ数値として比較し、そうでなければ文字列として比較する。
"100" > "20" は数値比較で true。"apple" > "100" は文字列比較になる。
parseFloat を直接使わないのが要点で、parseFloat("100円") は 100 を返してしまう。
正規表現で全体が数値であることを確かめてからでないと、"100円" = 100 が成立する。
空文字はNULLである
もう1つ決めたのは、空セルをNULLとして扱うこと。
function isBlank(v) { return v === null || v === undefined || v === ''; }
これは厳密にはSQLではない。SQLでは空文字列とNULLは別物だからだ。
だがCSVに ,, と書いてある時、人間が意味しているのは「空文字列」ではなく「値が無い」である。
表計算ソフトの空セルと同じ扱いにするのが、驚きが少ない。
この判断が効いてくるのが集計で、SQLと同じく集計関数はNULLを飛ばす。
var v = evalExpr(a.arg, rows[i], ctx, null);
if (isBlank(v)) continue; // aggregates skip NULLs, as in SQL
count++;
AVG(amount) は、空セルを0として数えない。0を混ぜると平均が静かに狂う。
COUNT(*) は行を数え、COUNT(amount) は値のある行だけを数える。ここもSQLに合わせた。
罠2: GROUP BY のキーを , で作ってはいけない
GROUP BY city, status を実装するとき、素朴にやるとこう書きたくなる。
var key = keyParts.join(','); // これは壊れる
壊れる。CSVの値にカンマが入るからだ。
city = "Tokyo,Shibuya" status = "shipped" → "Tokyo,Shibuya,shipped"
city = "Tokyo" status = "Shibuya,shipped" → "Tokyo,Shibuya,shipped"
別々のグループが同じキーになって、静かに合算される。
エラーは出ない。数字がちょっと違うだけなので、気づかない。
そこで、CSVのテキストにまず現れないバイトを区切りに使った。
var keyParts = ast.groupBy.map(function (g) {
var v = evalExpr(g, filtered[r], ctx, null);
return v === null ? '\x00' : String(v);
});
var key = keyParts.join('\x01');
\x01 で連結し、NULLは \x00 で表す。
NULLを空文字で表すと、今度は空セルのグループと空文字列のグループが衝突する。
別の番兵が要る。
副作用として file コマンドがこのファイルを data と判定するようになったが、実害は無い。
罠3: ORDER BY total が「そんな列は無い」と言う
テストを書いていて踏んだ、実際のバグ。
SELECT city, SUM(amount) AS total FROM data GROUP BY city ORDER BY total DESC
これが No such column: total で落ちた。
当然で、total は元データの列名ではない。SELECT が作り出した名前である。
評価器は行の中から total という列を探して、見つけられない。
SQLの実行順序が FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY である以上、
ORDER BY は SELECT より後なのでエイリアスを見られる。HAVING も同様に扱う実装が多い。
対処は、評価する前にASTを書き換えて、エイリアス参照を元の式に差し戻すこと。
/* ORDER BY and HAVING may refer to a name introduced in SELECT
(`SELECT SUM(x) AS total ... ORDER BY total`). Rewrite those references
into the expression they stand for before evaluating. */
function resolveAliases(node, aliases) {
if (!node || typeof node !== 'object') return node;
if (node.k === 'col') {
var lower = node.name.toLowerCase();
if (Object.prototype.hasOwnProperty.call(aliases, lower)) return aliases[lower];
return node;
}
var copy = {};
Object.keys(node).forEach(function (key) {
var v = node[key];
if (Array.isArray(v)) copy[key] = v.map(function (n) { return resolveAliases(n, aliases); });
else if (v && typeof v === 'object' && 'k' in v) copy[key] = resolveAliases(v, aliases);
else copy[key] = v;
});
return copy;
}
ORDER BY total の total ノードが、SUM(amount) の部分木に置き換わる。
1つ気をつけたのは、同名の実在する列があったらそちらを優先すること。
function aliasMap(ast, colIndex) {
var map = {};
ast.select.forEach(function (s) {
if (s.star || !s.alias) return;
var lower = s.alias.toLowerCase();
// a real column of the same name wins, as it would in SQL
var clash = Object.keys(colIndex).some(function (c) { return c.toLowerCase() === lower; });
if (!clash) map[lower] = s.expr;
});
return map;
}
SELECT foo AS bar と書いたときに bar 列が元から存在したら、ORDER BY bar は元の列を指す。
これはSQL標準の挙動に合わせただけだが、合わせておかないと後で必ず事故る。
罠4: AVG が 550.1643000000001 を返す
これは浮動小数の話で、SQLとは関係ないのだが、体験としては一番目立つ。
AVG(amount) は割り算なので、二進小数の丸め誤差がそのまま出る。
550.1643000000001 と表示された瞬間、道具として信用されなくなる。
かといって固定桁で丸めると、今度は 0.0000012 が 0.00 になって消える。
桁数を値の大きさで変えることにした。
function present(v) {
if (v === null || v === undefined) return '';
if (typeof v === 'number') {
if (!isFinite(v)) return '';
if (Number.isInteger(v)) return String(v);
var abs = Math.abs(v);
var digits = abs >= 1000 ? 2 : abs >= 1 ? 4 : 6;
var s = v.toFixed(digits);
return s.indexOf('.') !== -1 ? s.replace(/\.?0+$/, '') : s;
}
return String(v);
}
整数はそのまま。1000以上は2桁、1以上は4桁、それ未満は6桁まで見せて、末尾の0は落とす。
表示だけを変えていて、値は丸めていないのが大事なところ。
ORDER BY は生の値で並べる。表示のために計算結果を壊してはいけない。
測った
20万行、4列。WHERE で1/3に絞り、8グループに GROUP BY して、
COUNT / AVG / SUM を計算し、HAVING で絞り、ORDER BY で並べる:
SELECT city, COUNT(*) AS n, AVG(amount) AS avg, SUM(amount) AS total
FROM data
WHERE status = 'shipped' AND amount > 100
GROUP BY city HAVING n > 10 ORDER BY total DESC LIMIT 20
行数 200,000
中央値 77 ms (5回、最速 74 / 最遅 84)
Node 22、M系Mac。ブラウザでも同じ桁で動く。
速いのは、賢いことを何もしていないからだと思う。インデックスは張らないし、
クエリの並べ替えもしない。全行を1回舐めてMapに放り込むだけで、20万行ならそれで足りる。
数百万行を超えたら、素直にデータベースを使うべきところ。
テストは49件。WHERE のあとが空、閉じていない文字列リテラル、
NULLを含む集計、エイリアスの衝突あたりを埋めている。
コード
MITで置いてある。SQLエンジンは sql.js の1ファイル。
CSVを開くビューア（parse.js / table.js）も同じリポジトリにあって、
こちらは100万行でもDOMには30行しか置かない作りにしてある。
全体を通して fetch も XMLHttpRequest も使っていない。
CIで出荷スクリプトを grep して、通信コードが混ざったらビルドを落とすようにしてある。
主張が本当かどうかは、ページを開いてから機内モードにして、ファイルを落とせば確かめられる。
まとめ
SQLエンジンを書くとき、面倒なのはパーサだと思っていた。実際に面倒だったのは値の扱いだった。
CSVには型が無い。だから
- 比較のたびに両辺を見て、数値か文字列かを決める
- 空セルはNULLとして扱い、集計から外す
- グループキーは、データに出ないバイトで連結する
- 表示のためだけに丸め、値そのものは丸めない
型のある世界から来ると全部当たり前に見えるが、
その当たり前を全部自分で決めないといけないのがCSVだった、という話。