Repository navigation
ESQL: Remove O(n^2) from DROP foo* - #154716
Conversation
Analyzer.dropResolver resolved DROP wildcard.* patterns into an ArrayList and then called resolvedProjections.removeIf(resolved::contains), which is O(n) per lookup times O(n) elements to scan: O(n^2) overall. Against a real CCS query with `| DROP lost.*` over a merged field-caps schema of ~700,000 fields (OTel attribute explosion across 7,606 indices), this made the analysis phase take ~3.73 hours. Fix: copy `resolved` into a HashSet before the removeIf call. Attribute equality/hashing is keyed by NameId, so this is safe, and it turns the inner lookup into O(1), making the whole operation O(n). Also added benchmarks/src/main/java/org/elasticsearch/benchmark/esql/ AnalysisBenchmark.java (analysis / logicalOptimization / fullPipeline benchmarks parameterized by fieldCount and plan=keep|drop) to make the quadratic-vs-linear scaling reproducible and to guard against regression.
O(n^2) from DROP foo*
|
Pinging @elastic/es-analytical-engine (Team:Analytics) |
|
Hi @nik9000, I've created a changelog YAML for you. |
🔍 Preview links for changed docs⏳ Building and deploying preview... View progress This comment will be updated with preview links when the build is complete. |
ℹ️ Important: Docs version tagging👋 Thanks for updating the docs! Just a friendly reminder that our docs are now cumulative. This means all 9.x versions are documented on the same page and published off of the main branch, instead of creating separate pages for each minor version. We use applies_to tags to mark version-specific features and changes. Expand for a quick overviewWhen to use applies_to tags:✅ At the page level to indicate which products/deployments the content applies to (mandatory) What NOT to do:❌ Don't remove or replace information that applies to an older version 🤔 Need help?
|
| // so, remove things that are in common | ||
| resolvedProjections.removeIf(resolved::contains); | ||
| Set<? extends NamedExpression> resolvedSet = new HashSet<>(resolved); | ||
| resolvedProjections.removeIf(resolvedSet::contains); |
There was a problem hiding this comment.
Should we collect to a LinkedHashSet in first place instead of copying?
There was a problem hiding this comment.
It's actually a huge change to do LinkedHashSet. At least, to do it in any way that'd help.
| @BenchmarkMode(Mode.AverageTime) | ||
| @OutputTimeUnit(TimeUnit.MILLISECONDS) | ||
| @State(Scope.Benchmark) | ||
| public class AnalysisBenchmark { |
There was a problem hiding this comment.
Out of curiosity, how much faster did this become?
There was a problem hiding this comment.
I can find it for you. O(n^2) left so.... depend on the input size
There was a problem hiding this comment.
I also wonder if it is worth moving this example to org.elasticsearch.benchmark._nightly.esql.QueryPlanningBenchmark?
It runs periodically and it already have some infra setting up many attributes.
There was a problem hiding this comment.
analysis 100 from 0.026 -> 0.025 ms/op
analysis 100 sort 0.348 -> 0.329 ms/op
analysis 100 drop_sort 0.357 -> 0.362 ms/op
fullPipeline 100 from 0.035 -> 0.034 ms/op
fullPipeline 100 sort 0.423 -> 0.415 ms/op
fullPipeline 100 drop_sort 0.485 -> 0.457 ms/op
logicalOptimization 100 from 0.009 -> 0.008 ms/op
logicalOptimization 100 sort 0.038 -> 0.041 ms/op
logicalOptimization 100 drop_sort 0.059 -> 0.059 ms/op
analysis 100000 from 37.661 -> 36.913 ms/op
analysis 100000 sort 47.561 -> 46.790 ms/op
analysis 100000 drop_sort 26960.619 -> 78.841 ms/op
fullPipeline 100000 from 49.466 -> 48.058 ms/op
fullPipeline 100000 sort 61.719 -> 70.408 ms/op
fullPipeline 100000 drop_sort 25543.589 -> 109.739 ms/op
logicalOptimization 100000 from 15.170 -> 17.946 ms/op
logicalOptimization 100000 sort 22.083 -> 19.261 ms/op
logicalOptimization 100000 drop_sort 19.955 -> 14.472 ms/op
There was a problem hiding this comment.
rest of the query execution.
In the example I bumped into last night planning the drop command took 3.8 hours and the query execution took a few milliseconds.
Removes an `O(n^2)` from `DROP` when it applies to a pattern. A friend of mine has an index pattern with 700,000 fields. It's a mistake. He shouldn't have 700,000 fields. But we shouldn't `O(n^2)` anyway. One mistake shouldn't cause double suffering.
Removes an `O(n^2)` from `DROP` when it applies to a pattern. A friend of mine has an index pattern with 700,000 fields. It's a mistake. He shouldn't have 700,000 fields. But we shouldn't `O(n^2)` anyway. One mistake shouldn't cause double suffering.
* ESQL: Remove `O(n^2)` from `DROP foo*` (#154716) Removes an `O(n^2)` from `DROP` when it applies to a pattern. A friend of mine has an index pattern with 700,000 fields. It's a mistake. He shouldn't have 700,000 fields. But we shouldn't `O(n^2)` anyway. One mistake shouldn't cause double suffering. * Remove AnalysisBenchmark from 8.19 backport The benchmark references APIs that don't exist on 8.19 (Utils, PromqlFunctionRegistry, QuerySettings, etc.). The actual fix in Analyzer.java is self-contained.
…g attributes (#154818) This is a follow up from #154716. It's targeting mainly queries like `DROP f1,f2,f3,....fn` and `KEEP f1,f2,f3,....fn` at resolution (analysis) time by building once per resolving tree node and only when the child output exceeds 128 attributes a `Map` of [attribute name, list of attributes with that name] of that node's children output. Then, as the tree scan visits each `UnresolvedAttribute`, it resolves via a single `Map.get(name)` instead of an `Objects.equals(name, attr.name())` **scan over all attributes**.
Removes an
O(n^2)fromDROPwhen it applies to a pattern. A friend of mine has an index pattern with 700,000 fields. It's a mistake. He shouldn't have 700,000 fields. But we shouldn'tO(n^2)anyway. One mistake shouldn't cause double suffering.