You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Make a faster way to check column existence in optimizer (not is_err()) #5309
For example, there is code that looks like this (call is_ok() or is_err()and totally discards the error with the string)
input_schema.field_from_column(col).is_ok()
This is problematic because they return a DataFusionError that not only has an allocated String but also often has gone through a lot of effort to construct a nice error message. You can see them appearing in the trace on #5157
As part of making the optimizer faster Related to #5157 we need to avoid these string allocations,
Thus I propose:
Add new functions for checking that return a bool rather than an error
Replace the use of is_err() with
Find the field with the given qualified column
For example,
implDFSchema{// existing function that returns Resultpubfnfield_from_column(&self,column:&Column) -> Result<&DFField>{...}// new function that returns bool <---- Add this new functionpubfnhas_column(&self,column:&Column) -> bool{...}}
And then replace in the code that have the pattern
input_schema.field_from_column(col).is_ok()
With
input_schema.has_column(col)
Describe the solution you'd like
Ideally someone would do this transition one function on DFSchema at a time (not one giant PR please 🙏 )
Describe alternatives you've considered
There are more involved proposals for larger changes to DFSchema but simply avoiding this check might help a lot
Additional context
I think this is a good first exercise as the desire is well spelled out and it is a software engineering exercise rather than requires deep datafusion expertise
I think returning enum will be same as returning result, because the caller also have to handle Ambiguous and return an Err.
Returning Result<bool> can also avoid str allocating in field_from_name().is_err(). The code will be like this:
if schema.had_column(col)? {...}
Maybe the key question is that do we need to check 'Ambiguous error' each time the had_column called? Actually we can just check Ambiguous err once at begin.
I'm not sure if my thinking is correct, need your advice @alamb 🤓
Thank you @matthewmturner -- I think this is a "tip of the iceberg" type bug where there are many places in the optimizzer that use DFSchema that could be made faster.
Thus I suggest if possible, taking some time to map out a plan to incrementally improve the situation over time
I tried reproducing your results with Instruments but wasnt able to get to the granularity that you had that showed DFSchema as being heavy.
However, I put together a flamegraph and came to similar conclusion. In the below image the blocks in purple are for my search of DFSchema. Of those, there was a lot of merge and field_with_qualified_name (which is often called by merge) - this appears to be consistent with your profiling. It also looks like all uses of DFSchema are during the optimization pass which is consistent with your observation.
Based on this, and how field_with_name / field_with_qualified_name are used within merge I think I may be able to simply replace them with has_column_with_unqualified_name / has_column_with_qualified_name which return booleans.
Im hoping, time permitting, to also do some memory / allocations profiling to make sure these types of change have the desired effect.
simply replace them with has_column_with_unqualified_name / has_column_with_qualified_name which return booleans.
The other thing to do would be to look into making DFSchema cheaper to copy/create, for example using an Arc instead of OwnedTableReference (much as @tustvold did for Field in arrow-rs's Fields) so that copying a DFField doesn't require copying around strings
@alamb sorry for delay here, I went down a rabbit hole of trying to get some good memory / allocation benchmarks as a i really wanted to be able measure / compare cause (allocations) instead of symptom (time). made good progress but dont want to hold this up any longer and can continue that work separately.
The low hanging fruit and what this issue was created for seems to be updating those function calls so I think I will start with that and separately we can look into updating how schemas are handled - if thats okay with you.
@alamb sorry for delay here, I went down a rabbit hole of trying to get some good memory / allocation benchmarks as a i really wanted to be able measure / compare cause (allocations) instead of symptom (time). made good progress but dont want to hold this up any longer and can continue that work separately.
The low hanging fruit and what this issue was created for seems to be updating those function calls so I think I will start with that and separately we can look into updating how schemas are handled - if thats okay with you.
@alamb
I've been looking into this more for places where we can replace unused results with booleans but nothing stuck out for that (let me know if you know or your intuition say otherwise). I've also been using the great analysis from @zeodotr in #7698 (comment) to guide some of my review.
A couple things:
I looked at optimization 6 from @zeodotr's list and I wasnt able to find columnize_expr as a hot spot in the context of creating physical plan (I tried reproducing on a wide table with several aggregates) which i believe is the use case they had (i didnt create 3000+ aggregates though like they have). it shows up as ~3% of cpu of creating unoptimized logical plan.
I profiled the benchmark for a simple query on a wide table (700 columns) and a significant amount of the cpu time is (~87%) is now coming from has_column_with_qualified_name (first screenshot below). 87% in the case of creating physical plan and 66% of creating unoptimized logical plan (second screenshot).
Given this seems to be hotspot for wide tables do you think best next step would be looking into improving lookup time by adding a btree (or whatever) or should we improve the foundation and work on updating the schema first? from what ive seen updating the schema may make adding the index easier so that may be a good start.
I profiled the benchmark for a simple query on a wide table (700 columns) and a significant amount of the cpu time is (~87%) is now coming from has_column_with_qualified_name (first screenshot below). 87% in the case of creating physical plan and 66% of creating unoptimized logical plan (second screenshot).
Given this seems to be hotspot for wide tables do you think best next step would be looking into improving lookup time by adding a btree (or whatever) or should we improve the foundation and work on updating the schema first? from what ive seen updating the schema may make adding the index easier so that may be a good start.
Yes I agree getting DFSchema into better shape (e.g. not actually copying so many things) would likely make this task easier
It also looks like has_column_with_qualified_name is always being called from DFSchema::merge I wonder if we can figure out why that needs to be called so much. My bet is that most of the callsites dont' actually add any new fields. Maybe we can quickly check if the pass didn't many any changes to the children, then there is no need to call DFSchema::merge
Or maybe we can find some way to quickly compare if two schemas are the same 🤔
Activity
suxiaogang223 commentedon Feb 17, 2023
i'm happy to do this🌝
ygf11 commentedon Feb 17, 2023
Seems it is relative to the pr #5287.
suxiaogang223 commentedon Feb 17, 2023
Yes, I think the method had_column also should distinguish FieldNotFound and Ambiguous reference error.
Maybe the new method should be
alamb commentedon Feb 17, 2023
The key for performance is not to return a
DataFusionErrorwith a allocated stringsuxiaogang223 commentedon Feb 17, 2023
Maybe we can use
assertto assume that the "Ambiguous reference error" should not happen inhad_column?alamb commentedon Feb 17, 2023
How about returning an enum like
?
suxiaogang223 commentedon Feb 17, 2023
I think returning enum will be same as returning result, because the caller also have to handle Ambiguous and return an
Err.Returning
Result<bool>can also avoid str allocating infield_from_name().is_err(). The code will be like this:Maybe the key question is that do we need to check 'Ambiguous error' each time the
had_columncalled? Actually we can just check Ambiguous err once at begin.I'm not sure if my thinking is correct, need your advice @alamb 🤓
alamb commentedon Feb 18, 2023
Not sure -- will try and check out #5328 shortly
matthewmturner commentedon Dec 29, 2023
@alamb i can pick this up
alamb commentedon Dec 30, 2023
Thank you @matthewmturner -- I think this is a "tip of the iceberg" type bug where there are many places in the optimizzer that use DFSchema that could be made faster.
Thus I suggest if possible, taking some time to map out a plan to incrementally improve the situation over time
matthewmturner commentedon Dec 30, 2023
@alamb Sounds good will do that
alamb commentedon Dec 30, 2023
#8665 (comment) might be instructive
matthewmturner commentedon Dec 30, 2023
@alamb aha i had plans to profile that exact thing as a starting point.
matthewmturner commentedon Dec 30, 2023
I tried reproducing your results with Instruments but wasnt able to get to the granularity that you had that showed DFSchema as being heavy.
However, I put together a flamegraph and came to similar conclusion. In the below image the blocks in purple are for my search of
DFSchema. Of those, there was a lot ofmergeandfield_with_qualified_name(which is often called bymerge) - this appears to be consistent with your profiling. It also looks like all uses of DFSchema are during the optimization pass which is consistent with your observation.Based on this, and how
field_with_name/field_with_qualified_nameare used within merge I think I may be able to simply replace them withhas_column_with_unqualified_name/has_column_with_qualified_namewhich return booleans.Im hoping, time permitting, to also do some memory / allocations profiling to make sure these types of change have the desired effect.
alamb commentedon Dec 31, 2023
The other thing to do would be to look into making DFSchema cheaper to copy/create, for example using an Arc instead of
OwnedTableReference(much as @tustvold did forFieldin arrow-rs'sFields) so that copying aDFFielddoesn't require copying around stringshttps://github.com/apache/arrow-datafusion/blob/848f6c395afef790880112f809b1443949d4bb0b/datafusion/common/src/dfschema.rs#L810
matthewmturner commentedon Jan 5, 2024
@alamb sorry for delay here, I went down a rabbit hole of trying to get some good memory / allocation benchmarks as a i really wanted to be able measure / compare cause (allocations) instead of symptom (time). made good progress but dont want to hold this up any longer and can continue that work separately.
The low hanging fruit and what this issue was created for seems to be updating those function calls so I think I will start with that and separately we can look into updating how schemas are handled - if thats okay with you.
matthewmturner commentedon Jan 5, 2024
Just from updating the
mergefunction we already see considerable improvementsalamb commentedon Jan 5, 2024
Sounds like a great plan -- thank you!
matthewmturner commentedon Jan 12, 2024
@alamb
I've been looking into this more for places where we can replace unused results with booleans but nothing stuck out for that (let me know if you know or your intuition say otherwise). I've also been using the great analysis from @zeodotr in #7698 (comment) to guide some of my review.
A couple things:
columnize_expras a hot spot in the context of creating physical plan (I tried reproducing on a wide table with several aggregates) which i believe is the use case they had (i didnt create 3000+ aggregates though like they have). it shows up as ~3% of cpu of creating unoptimized logical plan.has_column_with_qualified_name(first screenshot below). 87% in the case of creating physical plan and 66% of creating unoptimized logical plan (second screenshot).Given this seems to be hotspot for wide tables do you think best next step would be looking into improving lookup time by adding a btree (or whatever) or should we improve the foundation and work on updating the schema first? from what ive seen updating the schema may make adding the index easier so that may be a good start.
alamb commentedon Jan 12, 2024
Yes I agree getting DFSchema into better shape (e.g. not actually copying so many things) would likely make this task easier
It also looks like
has_column_with_qualified_nameis always being called fromDFSchema::mergeI wonder if we can figure out why that needs to be called so much. My bet is that most of the callsites dont' actually add any new fields. Maybe we can quickly check if the pass didn't many any changes to the children, then there is no need to call DFSchema::mergeOr maybe we can find some way to quickly compare if two schemas are the same 🤔
comphead commentedon Jul 9, 2024
I think this can be closed @alamb? The original issue was resolved and
has_columnreturns bool instead of errorcomphead commentedon Jul 9, 2024
@alamb i'm closing it, feel free to reopen it if needed