Repository navigation
SQL planning slow with huge IN filters #7904
Description
Activity
Calcite has default value of DEFAULT_IN_SUB_QUERY_THRESHOLD as 20. If length of values of in clause exceeds this config calcite will not convert
intoorand convert in to a semi join of table.
However druid set this config as MAX_VALUE in PlannerFactory . If there is no special purpose of setting it as MAX_VALUE, maybe we could try using default value and see whether still has this performance problem. What do you think? @gianmI think right now the Druid planner rules can not convert that kind of structure into a Druid query. Maybe if they could, then that approach would work. (However there might still be a performance issue if a user specified a ton of OR conditions rather than using IN?)
I did some looking into this and found not just one, but a few different root causes. Here they are, in order of how much they contributed to query planning time (most to least):
- Calcite has an O(N^2) OR simplification step in
RexSimplify.simplifyOr: https://issues.apache.org/jira/browse/CALCITE-3178. This was the biggest contributor, and a hacky workaround of simply disabling this step cut the planning time down to ~8s. - Druid's
Expressions.toSimpleLeafFilterunconditionally attempts to check every "leaf" filter (non-boolean) to see if it's a time floor filter, for purposes of potentially convertingFLOOR(__time TO DAY) = Xinto a range filter. This imposes a few seconds of overhead, which could be eliminated by only checking leaf filters that look like they might be time floors (their operator matchesFLOOR,TIME_FLOOR, orCAST(x AS DATE)). - Druid's
CombineAndSimplifyBoundsbuilds aTreeRangeSet<BoundValue>out of every equality or bound leaf filter, to see if they can be simplified. Algorithmic complexity looks fine from a quick glance at the method, but there is overhead imposed by the fact thatBoundValue.compareTo, which is called internally and often by the TreeRangeSet, always compares bounds as Strings. For numeric bounds involves a lot of wasteful converting of numbers and strings back and forth. This is only an issue when the bounds are numeric, but, in the case of my test query, they were (it was a long-typed column). - Calcite's parser also seems to take a while (1–2s) to read through the SQL. Possibly sql support for dynamic parameters #6974 would help with that, if it allows constructs like
col IN (?)where?is an array.
Profiling indicates that if all of the above were addressed, query planning time should come down to more acceptable levels.
- Calcite has an O(N^2) OR simplification step in
By the way, the native query equivalent of my test query runs in about 900ms.
Affected Version
0.14.2
Description
When running a SQL query with an IN clause with ~14k elements, planning on the broker took quite a long time (over a minute). A lot of time seems to be spent in areas of Calcite code that look like the following (I saw this pattern repeat over lots of thread dumps). Maybe some algorithmic blowup when there are a lot of OR conditions, which is what a big IN would get translated to.