russell@unturf.com
9934133dcf
Add 88 new defect entries to HIGH and MEDIUM tables:
HIGH: mysql-0001/0002, mariadb-0001, redis-0001/0002, valkey-0001/0002, openvpn-0001,
vlc-0001, prometheus-0001, otel-collector-0001, cockroachdb-0001..0004,
tidb-0001..0008, kubernetes-0001/0002, go-0001, kotlin-0002, scala-0001,
allegro5-0001, sdl2-0001, grafana-0001, clickhouse-0001, duckdb-0001,
mongodb-0001, envoy-0001, istio-0001, cilium-0001, linkerd2-0001,
linux-0001/0002/0003, tor-0002/0003, curl-0001, julia-0001, lua-0001,
perl5-0001, nats-0001, spring-0003/0004, tomcat-0001, onos-0002, odl-0002
MEDIUM: helm-0001, mariadb-0002, openssl-0001/0002, memcached-0001,
cassandra-0001..0004, flink-0001, storm-0001/0002, zookeeper-0001..0003,
pip-0001, gradle-0001, nginx-0001, haproxy-0001, caddy-0001, varnish-0001,
ffmpeg-0001, gstreamer-0001, raylib-0001, love2d-0001, php-0001/0002,
r-source-0001, cpython-0002, ruby-0001, rabbitmq-0003/0004, activemq-0001,
ovs-0001, onos-0003, odl-0002, jetty-0001
PDF: 976K
1.5 KiB
clickhouse-0001: ReplaceColumnTransformerNode::findReplacementExpression linear scan
Target: ClickHouse/ClickHouse
File: src/Analyzer/ColumnTransformers.cpp,
src/Analyzer/ColumnTransformers.h
Severity: MEDIUM
Pattern: CWE-407 — O(n) membership test inside loop → O(n²)
Description
ReplaceColumnTransformerNode stores replacement column names in
Names replacements_names (std::vector<std::string>).
findReplacementExpression(expression_name) performs an O(n) std::find
scan over replacements_names to look up the index of a replacement.
This function is called from QueryAnalyzer::resolveColumnsTransformers()
inside a nested double loop:
for each column in matched_expression_nodes_with_names: // O(C)
for each transformer in getColumnTransformers().getNodes(): // O(T)
replace_transformer->findReplacementExpression(column_name); // O(R)
Total: O(C × T × R) — cubic for queries that use SELECT * REPLACE (...).
In production schemas with wide tables (C = 200+) and compound REPLACE lists
(R = 20+), this becomes measurable.
Fix
Add a NameToIndexMap replacements_index (std::unordered_map<std::string, size_t>)
alongside replacements_names. Populate it on construction; use it in
findReplacementExpression for O(1) lookup.
See defects/clickhouse/patch/0001.patch.
Complexity
| Operation | Before | After |
|---|---|---|
findReplacementExpression |
O(R) | O(1) |
resolveColumnsTransformers total |
O(C·T·R) | O(C·T) |