Avoid going too in-depth while computing join order #17904
Conversation
bf67662 to
25d111e
Compare
|
One problem might be that I am not sure if the added C++ test is too demanding say on Windows. Let's see. I can also just remove it. |
Cutoff to 25 is arbitrary, in duckdb-wasm with stack of 64KB it would have gone up to 80+ (depending on implementation details / compiler optimization level), but high enough that should not really influence actual plans. There might be better solution, and cutoff might even be made customizable, so that different situation might warrant different behaviours (and better testing). This has been tested bailing out at level 3, just to check system could handle bailing out. Test is added that concatenates `select 1 as num` with 500 times `union all select 1 as num`. Both with and without this PR the test can be passed, but adding a limit on depth significantly increases the reachable depth. Experimenting with higher numbers (together with `SET max_expression_depth = x` to actually have the statement be parseable), will show a path to further improve in this area.
25d111e to
c43444f
Compare
|
One observation, for the case of UNION ALL, is that it might be re-grouped from After some more thoughts, I think preventing going too much in depth might make sense in any case, while we might want to reorder the plans before getting there. |
|
Let's put this on 50 at least? Or maybe 100 and use a different value for WASM? 25 seems very "reachable" and might randomly degrade actual queries people are running. |
|
@carlopi I have some data files and 250 queries (these are randomly generated and obnoxiously complicated with deep joins and what not) that I thought I'd pass along - in case it helps you with this PR. The datafiles have a number of duckdb database files and a start.sql script that attaches the files with specific names. |
Amazing! I am not sure I will get them to run on this, mostly since they are not trivial to plug-in our test infrastructure, but would maybe make sense to expose those as a sqllogic tests? That would make it easier to get access to try them. They could even become a test-only extension, then in development it's trivial plug them, and there can be a |
I would then probably prefer 50 everywhere OR making this depending on variable that can be set by users/clients. 100 + override Wasm side also fine. Meanwhile I am running our test and benchmark suite with additional logging to detect very deep plans, I have found outliers are:
I will update when more results came in, for example regression is run at https://github.com/carlopi/duckdb/actions/runs/15626527270/job/44021730739 |
|
I ended up setting to 100 the threshold, and raising the stack size in Wasm. Those combined make so that:
I will double check properly Wasm size again, but I think with 100 we should good for now, while this can be looked again for 1.4 with more time. |
|
Discussed with @Mytherin, looking into changing from fixed value to |
|
Changed to use config's |
|
Thanks! |
Avoid going too in-depth while computing join order (duckdb/duckdb#17904)
Avoid going too in-depth while computing join order (duckdb/duckdb#17904) Co-authored-by: krlmlr <krlmlr@users.noreply.github.com>
Visit in-depth up to
max_expression_depthrecursion levels (in the plan tree), and stop keeping original plans for deeper nodes. This makes so that changingmax_expression_depthwill make possible to control the complexity of optimizations performed.Clients such as duckdb-wasm that might have a premium on stack space (due to 32bit nature) might lower the setting to avoid incurring in stackoverflow-connected problems.
Weaker point is that at the moment is hard to test this, it has been done manually by changing the code like:
but it's hard to do from the system as such, and that might be a code smell.
Fixes duckdb/duckdb-wasm#1954 and other similar issues (more visible in duckdb-wasm but somehow still relevant in native).