Fix logical error in topK dynamic filtering when the sort column contains a Nullable - #113406
Fix logical error in topK dynamic filtering when the sort column contains a Nullable#113406groeneai wants to merge 3 commits into
Conversation
…ains a Nullable FunctionTopKFilter::getReturnTypeImpl declares UInt8 unconditionally, but executeVectorized returns whatever the lessOrEquals/greaterOrEquals it delegates to resolves to. FunctionComparison::getReturnTypeImpl propagates Nullable transitively out of tuple elements, so for a sort column that contains a Nullable without being Nullable the fast path produces Nullable(UInt8) and the columnMatchesType guard in ExpressionActions throws LOGICAL_ERROR. The guard meant to route such columns to the safe path tested only top level nullability, and DataTypeTuple does not override IDataType::isNullable(). Test the resolved comparison type where it is already computed and fall back to executeGeneral, which builds a ColumnUInt8 directly and cannot diverge. Keying on the resolved type rather than on the argument's structure is deliberate: a structural predicate such as hasNullable is also true for Array(Nullable(T)) and Map(K, Nullable(V)), whose comparisons resolve to plain UInt8 and work correctly today, so it would silently disable use_top_k_dynamic_filtering for them. executeGeneral also applies nulls_direction, which the lessOrEquals fast path did not, so the general path is both safe and more correct for these types. It is row at a time, but it now runs only for arguments that throw today, and Nullable and collated columns already took it unconditionally. Found by the AST fuzzer on an unrelated PR, STID 1611-483a, reachable from ordinary DDL with no opt-in setting since use_top_k_dynamic_filtering defaults to true. ClickHouse#100742 was an incomplete earlier fix for the same STID: it enumerated the two reported types, Dynamic and Variant, instead of keying on the causal property, so the Tuple carrier remained. Its regression test is extended here with the Tuple, Tuple-of-LowCardinality(Nullable) and NULL bearing arms. The LowCardinality arm pins max_threads = 1 because without it the threshold is not always set before the remaining parts are read, and the arm only reaches the filter in about seven runs out of ten.
The three arms added for the Tuple carriers could pass while covering nothing, and the NULL arm could not observe NULL ordering at all. tests/clickhouse-test randomizes query_plan_max_limit_for_top_k_optimization over [0, 1, 10, 100, 1000, 100000]. The value 1 makes tryOptimizeTopK return early at optimizeTopK.cpp:99 for a LIMIT 5 query, so no __topKFilter prewhere is installed and the arm never reaches the fixed code, in roughly one CI run in six. Pin the setting per query to 100, the form already used by 04205_top_k_dynamic_filtering_variable_length. Each arm also gets an EXPLAIN presence assertion in the count() > 0 ... LIKE '%__topKFilter%' form, so a silently declined optimization is caught rather than passing quietly. The NULL arm used a distinct first tuple element, and ColumnTuple::compareAtImpl returns on the first differing element, so the Nullable element was never compared and nulls_direction was inert: NULLS LAST and NULLS FIRST produced byte-identical output. Make the first element repeat so the Nullable element decides the order. ASC NULLS LAST and ASC NULLS FIRST now differ, and the rows tied at each boundary are identical, so the output does not depend on which tied row is picked. max_threads = 1 on the tuple and NULL arms for the reason already documented on the sibling LowCardinality arm: with several readers the threshold tracker is not always set before the remaining parts are read. Measured against a binary with the guard reverted, the arms aborted 18/20 and 19/20 without it and 20/20 with it, and the reference is byte-identical either way. SYSTEM STOP MERGES keeps the three inserts as three parts, since a single part never sets the tracker. Removing the pin flips the EXPLAIN assertion from 1 to 0 on all three arms, which is what shows it is load bearing. No source change; the binary is unchanged.
Internal second-model review (2 rounds, 2 gate passes, 0 open findings)Every change here was reviewed by a second model independently of the one that wrote Round 1 — source accepted, tests rejected as not measuring the fix
💡 ❌ One reviewer finding was withdrawn with evidence rather than actioned (discarded Round 2 — jointly clean on code and testsBoth gate passes at the final commit returned 0 findings. The reviewer re-derived One objection the reviewer raised against itself was refuted by measurement: an
A jointly disclosed, deliberately unfixed residual is noted in the description: a |
Pre-PR validation gate (a-i)
Suite runs: 46 of the 47 |
|
cc @george-larionov @KochetovNicolai, could you review this? |
|
Workflow [PR], commit [f2d8b9c] Summary: ⏳
AI ReviewSummaryThis PR fixes the Findings❌ Blockers
Final VerdictNot ready to merge until the vectorized path stops evaluating nested-null composite carriers with a hardcoded |
| auto elem_compare = compare_function->build(args); | ||
| /// getReturnTypeImpl always declares UInt8, so a comparison resolving to anything else | ||
| /// (a Nullable nested in a Tuple makes it Nullable(UInt8)) must not be returned here. | ||
| if (!isUInt8(elem_compare->getResultType())) |
There was a problem hiding this comment.
UInt8 is not a strong enough predicate for "safe to stay vectorized" here. For non-tuple composite columns the delegated comparison goes through FunctionComparison::executeGenericIdenticalTypes / GenericComparisonImpl, and that path hardcodes a.compareAt(..., 1) (src/Functions/FunctionsComparison.h:643-664, src/Functions/FunctionsComparison.h:1268-1305). So Array(Nullable(...)) / Map(...Nullable...) are still compared as nested NULLS LAST regardless of the query's actual nulls_direction, while executeGeneral and the sorter honor nulls_direction.
That leaves a wrong-result surface open on the exact carriers this guard deliberately keeps on the fast path. A minimal trace is Array(Nullable(UInt8)) with ORDER BY arr ASC NULLS FIRST LIMIT 1 SETTINGS use_top_k_dynamic_filtering = 1, use_top_k_dynamic_filtering_for_variable_length_types = 1: if one part publishes [1] as the threshold, a later [NULL] row is evaluated by lessOrEquals using compareAt(..., 1), so [NULL] <= [1] is false and the row is dropped even though the sort would rank [NULL] before [1]. I think we need to either thread nulls_direction into the generic comparison path or conservatively fall back to executeGeneral for nested-null composite carriers, not just for non-UInt8 result types.
There was a problem hiding this comment.
Confirmed, and both citations check out. GenericComparisonImpl does hardcode the direction argument as 1 in all four members (FunctionsComparison.h:643-664), and SortDescription.h:51 documents 1 as "NULLs and NaNs are greater", so the generic path is permanently NULLS LAST.
I measured it rather than reasoning about it. Fixture is 3 parts with SYSTEM STOP MERGES and NULLs only in the last part, so the threshold is published from non-NULL parts first; max_threads = 1 and query_plan_max_limit_for_top_k_optimization = 100 pinned, and an EXPLAIN + LIKE '%__topKFilter%' row reads 1 in every arm so none of them is vacuous. Filter on versus use_top_k_dynamic_filtering = 0 on the same binary, 5 runs each:
| carrier | query | filter on | filter off | |
|---|---|---|---|---|
Array(Nullable(UInt64)) |
ASC NULLS FIRST LIMIT 1 |
[100] |
[NULL] |
row dropped |
Array(Nullable(UInt64)) |
ASC NULLS LAST LIMIT 1 |
[100] |
[100] |
agree |
Map(String, Nullable(UInt64)) |
ASC NULLS FIRST LIMIT 1 |
{'k':100} |
{'k':NULL} |
row dropped |
Array(Nullable(UInt64)) |
DESC NULLS LAST LIMIT 1 |
[3099] |
[3099] |
agree |
Array(Nullable(UInt64)) |
DESC NULLS FIRST LIMIT 1 |
[NULL] |
[NULL] |
agree |
So the defect is narrower than stated: it needs direction == 1 && nulls_direction == -1. Both DESC directions are safe because greaterOrEquals against a NULL-as-greatest threshold keeps every NULL row, which is over-inclusive and cannot lose one. The NULLS LAST row agreeing is the control that shows the probe discriminates. A top-level Nullable(UInt64) column, which takes executeGeneral at :85, returns \N both ways, which localises this to the fast path rather than to the tracker or the sorter.
The important part of your comment is what it says about this PR's write-up, and you are right there too. The body claimed those two carriers "work today". That was measured with an abort-only oracle, which by construction cannot see a wrong result. I have corrected the body and row (g) of the validation gate comment: the trade-off for rejecting a structural predicate is performance against a pre-existing correctness gap, not a free win.
I am not fixing it here. The same fixture gives byte-identical output on this branch, on the pristine master snapshot and on my own base build, and this PR's guard cannot reach these carriers at all: their comparison resolves to plain UInt8, so isUInt8(...) is true and they keep the fast path exactly as before. The diff is unchanged and still only converts an abort into a correct answer for the Tuple carrier, where it also fixes nulls_direction as a side effect: Tuple(UInt64, Nullable(UInt64)) with the Nullable element deciding the order aborts on unpatched master and returns the correct (0,NULL) under ASC NULLS FIRST with the fix.
On your two remedies I agree with the second. Threading nulls_direction through GenericComparisonImpl changes a path every types_equal composite comparison reaches, and a bare [NULL] <= [1] returning 0 is defensible on its own; that is a much bigger semantic change than this needs. Falling back to executeGeneral is local and provably honors the hint. It should key on the general property rather than on isArray/isMap, and hasNullable (src/DataTypes/hasNullable.h:8) already sees through Array, Tuple, Map and LowCardinality(Nullable). Narrowing the fallback to the one broken direction pair is worth measuring, since routing all of them to the row-at-a-time path is a regression for the three directions that are correct today.
Separate PR, and I will link it here.
Build profile diff (arm_release)Comparing ✅ No significant changes. Binary sizes
Only the stripped binary is compared: the official master build keeps debug symbols while PR builds strip them, so the other binaries differ by construction. Compile time of recompiled translation units7 translation units recompiled, 7 s compile time in total, 7 of them have a recent master baseline. |
CI finish ledger - 72113bcEvery failure below has an owner: a fixing PR (mine or external), or a full-effort fix task CI is fully finished on this head: 174 check-runs, 0 queued or in progress, 156 success and
Session id: cron:our-pr-ci-monitor:20260805-083000 |
…/fix-topkfilter-nested-nullable
Related: #113029
Closes: #117013
Changelog category (leave one):
Changelog entry (a user-readable short description of the changes that goes into CHANGELOG.md):
Fix
Unexpected return type from __topKFilterlogical error raised byORDER BY ... LIMITover a MergeTree table with more than one part when the sort column contains aNullableelement, for exampleTuple(UInt64, Nullable(UInt64)).use_top_k_dynamic_filteringis enabled by default, so no opt-in setting was required to hit this.Description
__topKFilterdeclares its return type asUInt8, but its vectorized fast path returns whatever the comparison it delegates to resolves to. When a sort column contains aNullablewithout beingNullable, tuple comparison propagates that nullability outwards and yieldsNullable(UInt8), whichExpressionActionsrejects. The guard routing to the safe path tested only top level nullability, andDataTypeTuple::isNullable()is false.The fix tests the resolved comparison type where it is already computed and falls back to the general path when it is not
UInt8. That path builds aColumnUInt8directly, so it cannot diverge. Keying on the resolved type rather than the argument's structure keeps the optimization forArray(Nullable(T))andMap(K, Nullable(V)), which resolve to plainUInt8. Correcting an earlier claim of mine: those two are not otherwise correct, because their generic comparison hardcodes NULLs as greatest, soASC NULLS FIRSTdrops a nested NULL row. That is pre-existing on master and out of scope; a separate fix follows.hasEmptyTuplefrom #114182 gates the same function before the comparison is built, which empty tuples need because building one throws; this guard runs after, so the two are complementary.Found by the AST fuzzer on an unrelated PR, STID 1611-483a AST fuzzer (amd_tsan). #100742 was an incomplete earlier fix for the same STID: it enumerated the two reported types, so the
Tuplecarrier remained. Its test is extended here.Validation, re-run on the merged tree: both shapes in #117013 abort a debug server on default settings and return the expected rows with the fix, while
use_top_k_dynamic_filtering = 0is clean on both arms. Reverting only the guard reddens this PR's test; #114182's own test passes either way. The general path is row at a time, but runs only for arguments that throw today, whichNullableand collated columns already do.Workflow [PR]
Sync PR [sync-upstream/pr/113406]