2121use std:: collections:: { BTreeSet , HashMap , HashSet } ;
2222use std:: fmt:: { Display , Formatter } ;
2323use std:: hash:: Hash ;
24+ use std:: sync:: atomic:: { AtomicUsize , Ordering } ;
2425use std:: sync:: { Arc , LazyLock , OnceLock } ;
2526
2627use crate :: error:: { _plan_err, _schema_err, DataFusionError , Result } ;
@@ -108,6 +109,12 @@ pub type DFSchemaRef = Arc<DFSchema>;
108109/// let schema: &Schema = df_schema.as_arrow();
109110/// assert_eq!(schema.fields().len(), 1);
110111/// ```
112+ /// Number of by-name probes a schema takes on the linear path before it is
113+ /// worth building [`DFSchema::name_index`]. Building allocates per distinct
114+ /// field name, so a schema looked up only a couple of times is cheaper to
115+ /// scan.
116+ const NAME_INDEX_PROBE_THRESHOLD : usize = 8 ;
117+
111118pub struct DFSchema {
112119 /// Inner Arrow schema reference.
113120 inner : SchemaRef ,
@@ -116,10 +123,13 @@ pub struct DFSchema {
116123 field_qualifiers : Vec < Option < TableReference > > ,
117124 /// Stores functional dependencies in the schema.
118125 functional_dependencies : FunctionalDependencies ,
119- /// Lazily built accelerator for name lookups: maps a field name to the
120- /// ascending list of indices carrying it. Purely derived from `inner`, so
121- /// it takes no part in equality or `Debug`.
126+ /// Accelerator for name lookups: maps a field name to the ascending list
127+ /// of indices carrying it. Built only once a schema has been probed often
128+ /// enough to pay for it (see `NAME_INDEX_PROBE_THRESHOLD`). Purely derived
129+ /// from `inner`, so it takes no part in equality or `Debug`.
122130 name_index : OnceLock < HashMap < String , Vec < usize > > > ,
131+ /// How many times this schema has been probed by name while unindexed.
132+ name_probes : AtomicUsize ,
123133}
124134
125135impl std:: fmt:: Debug for DFSchema {
@@ -143,6 +153,7 @@ impl Clone for DFSchema {
143153 field_qualifiers : self . field_qualifiers . clone ( ) ,
144154 functional_dependencies : self . functional_dependencies . clone ( ) ,
145155 name_index : OnceLock :: new ( ) ,
156+ name_probes : AtomicUsize :: new ( 0 ) ,
146157 }
147158 }
148159}
@@ -165,6 +176,7 @@ impl DFSchema {
165176 field_qualifiers : vec ! [ ] ,
166177 functional_dependencies : FunctionalDependencies :: empty ( ) ,
167178 name_index : OnceLock :: new ( ) ,
179+ name_probes : AtomicUsize :: new ( 0 ) ,
168180 }
169181 }
170182
@@ -204,6 +216,7 @@ impl DFSchema {
204216 field_qualifiers : qualifiers,
205217 functional_dependencies : FunctionalDependencies :: empty ( ) ,
206218 name_index : OnceLock :: new ( ) ,
219+ name_probes : AtomicUsize :: new ( 0 ) ,
207220 } ;
208221 dfschema. check_names ( ) ?;
209222 Ok ( dfschema)
@@ -221,6 +234,7 @@ impl DFSchema {
221234 field_qualifiers : vec ! [ None ; field_count] ,
222235 functional_dependencies : FunctionalDependencies :: empty ( ) ,
223236 name_index : OnceLock :: new ( ) ,
237+ name_probes : AtomicUsize :: new ( 0 ) ,
224238 } ;
225239 dfschema. check_names ( ) ?;
226240 Ok ( dfschema)
@@ -240,6 +254,7 @@ impl DFSchema {
240254 field_qualifiers : vec ! [ Some ( qualifier) ; schema. fields. len( ) ] ,
241255 functional_dependencies : FunctionalDependencies :: empty ( ) ,
242256 name_index : OnceLock :: new ( ) ,
257+ name_probes : AtomicUsize :: new ( 0 ) ,
243258 } ;
244259 schema. check_names ( ) ?;
245260 Ok ( schema)
@@ -255,6 +270,7 @@ impl DFSchema {
255270 field_qualifiers : qualifiers,
256271 functional_dependencies : FunctionalDependencies :: empty ( ) ,
257272 name_index : OnceLock :: new ( ) ,
273+ name_probes : AtomicUsize :: new ( 0 ) ,
258274 } ;
259275 dfschema. check_names ( ) ?;
260276 Ok ( dfschema)
@@ -277,6 +293,7 @@ impl DFSchema {
277293 field_qualifiers : qualifiers,
278294 functional_dependencies : self . functional_dependencies . clone ( ) ,
279295 name_index : OnceLock :: new ( ) ,
296+ name_probes : AtomicUsize :: new ( 0 ) ,
280297 } )
281298 }
282299
@@ -346,6 +363,7 @@ impl DFSchema {
346363 field_qualifiers : new_qualifiers,
347364 functional_dependencies : FunctionalDependencies :: empty ( ) ,
348365 name_index : OnceLock :: new ( ) ,
366+ name_probes : AtomicUsize :: new ( 0 ) ,
349367 } ;
350368 new_self. check_names ( ) ?;
351369 Ok ( new_self)
@@ -405,6 +423,7 @@ impl DFSchema {
405423 // The fields just changed, so the name index no longer describes this
406424 // schema. Drop it and let the next lookup rebuild it.
407425 self . name_index = OnceLock :: new ( ) ;
426+ self . name_probes = AtomicUsize :: new ( 0 ) ;
408427 }
409428
410429 /// Get a list of fields for this schema
@@ -426,35 +445,66 @@ impl DFSchema {
426445 ( self . field_qualifiers [ i] . as_ref ( ) , self . field ( i) )
427446 }
428447
429- /// Lazily built map from field name to the ascending indices carrying it.
430- fn name_index ( & self ) -> & HashMap < String , Vec < usize > > {
431- self . name_index . get_or_init ( || {
448+ /// Map from field name to the ascending indices carrying it, or `None`
449+ /// while this schema has not been probed enough to justify building it.
450+ ///
451+ /// Building the map allocates per distinct field name, which costs more
452+ /// than several linear scans. Most schemas produced during planning are
453+ /// looked up once or twice, so paying that up front is a net loss; the
454+ /// schemas that dominate are the ones probed once per column. Counting
455+ /// probes lets both cases win: one-shot lookups keep scanning, repeated
456+ /// lookups switch over and amortise the build.
457+ fn name_index ( & self ) -> Option < & HashMap < String , Vec < usize > > > {
458+ if let Some ( index) = self . name_index . get ( ) {
459+ return Some ( index) ;
460+ }
461+ if self . name_probes . fetch_add ( 1 , Ordering :: Relaxed ) < NAME_INDEX_PROBE_THRESHOLD {
462+ return None ;
463+ }
464+ Some ( self . name_index . get_or_init ( || {
432465 let mut map: HashMap < String , Vec < usize > > =
433466 HashMap :: with_capacity ( self . inner . fields ( ) . len ( ) ) ;
434467 for ( idx, field) in self . inner . fields ( ) . iter ( ) . enumerate ( ) {
435468 map. entry ( field. name ( ) . to_owned ( ) ) . or_default ( ) . push ( idx) ;
436469 }
437470 map
438- } )
471+ } ) )
439472 }
440473
441474 pub fn index_of_column_by_name (
442475 & self ,
443476 qualifier : Option < & TableReference > ,
444477 name : & str ,
445478 ) -> Option < usize > {
446- // Every arm below requires the field name to match, so only indices
447- // carrying `name` can match. Look those up instead of scanning the
448- // whole schema, then apply the qualifier rules in index order so the
449- // first match is still the one returned.
450- let candidates = self . name_index ( ) . get ( name) ?;
451- candidates. iter ( ) . copied ( ) . find ( |& idx| {
452- match ( qualifier, self . field_qualifiers [ idx] . as_ref ( ) ) {
479+ let matches_qualifier =
480+ |idx : usize | match ( qualifier, self . field_qualifiers [ idx] . as_ref ( ) ) {
481+ // field to lookup is qualified.
482+ // current field is qualified and not shared between relations, compare both
483+ // qualifier and name.
453484 ( Some ( q) , Some ( field_q) ) => q. resolved_eq ( field_q) ,
485+ // field to lookup is qualified but current field is unqualified.
454486 ( Some ( _) , None ) => false ,
487+ // field to lookup is unqualified, no need to compare qualifier
455488 ( None , Some ( _) ) | ( None , None ) => true ,
456- }
457- } )
489+ } ;
490+
491+ // Every arm above also requires the field name to match, so once the
492+ // index exists only the indices carrying `name` can match. Either way
493+ // the first match in index order is the one returned.
494+ match self . name_index ( ) {
495+ Some ( index) => index
496+ . get ( name) ?
497+ . iter ( )
498+ . copied ( )
499+ . find ( |& idx| matches_qualifier ( idx) ) ,
500+ None => self
501+ . inner
502+ . fields ( )
503+ . iter ( )
504+ . enumerate ( )
505+ . find ( |( idx, f) | f. name ( ) == name && matches_qualifier ( * idx) )
506+ . map ( |( idx, _) | idx) ,
507+ }
458508 }
459509
460510 /// Find the index of the column with the given qualifier and name,
@@ -543,17 +593,21 @@ impl DFSchema {
543593 & self ,
544594 name : & str ,
545595 ) -> Vec < ( Option < & TableReference > , & FieldRef ) > {
546- // Fields are looked up by name far more often than schemas are built,
547- // so go through the name index rather than scanning every field.
548- self . name_index ( )
549- . get ( name)
550- . map ( |indices| {
551- indices
552- . iter ( )
553- . map ( |& idx| self . qualified_field ( idx) )
554- . collect ( )
555- } )
556- . unwrap_or_default ( )
596+ match self . name_index ( ) {
597+ Some ( index) => index
598+ . get ( name)
599+ . map ( |indices| {
600+ indices
601+ . iter ( )
602+ . map ( |& idx| self . qualified_field ( idx) )
603+ . collect ( )
604+ } )
605+ . unwrap_or_default ( ) ,
606+ None => self
607+ . iter ( )
608+ . filter ( |( _, field) | field. name ( ) == name)
609+ . collect ( ) ,
610+ }
557611 }
558612
559613 /// Find all fields that match the given name and convert to column
@@ -909,6 +963,7 @@ impl DFSchema {
909963 inner : self . inner ,
910964 functional_dependencies : self . functional_dependencies ,
911965 name_index : OnceLock :: new ( ) ,
966+ name_probes : AtomicUsize :: new ( 0 ) ,
912967 }
913968 }
914969
@@ -920,6 +975,7 @@ impl DFSchema {
920975 inner : self . inner ,
921976 functional_dependencies : self . functional_dependencies ,
922977 name_index : OnceLock :: new ( ) ,
978+ name_probes : AtomicUsize :: new ( 0 ) ,
923979 }
924980 }
925981
@@ -1192,6 +1248,7 @@ impl TryFrom<SchemaRef> for DFSchema {
11921248 field_qualifiers : vec ! [ None ; field_count] ,
11931249 functional_dependencies : FunctionalDependencies :: empty ( ) ,
11941250 name_index : OnceLock :: new ( ) ,
1251+ name_probes : AtomicUsize :: new ( 0 ) ,
11951252 } ;
11961253 // Without checking names, because schema here may have duplicate field names.
11971254 // For example, Partial AggregateMode will generate duplicate field names from
@@ -1254,6 +1311,7 @@ impl ToDFSchema for Vec<Field> {
12541311 field_qualifiers : vec ! [ None ; field_count] ,
12551312 functional_dependencies : FunctionalDependencies :: empty ( ) ,
12561313 name_index : OnceLock :: new ( ) ,
1314+ name_probes : AtomicUsize :: new ( 0 ) ,
12571315 } ;
12581316 Ok ( dfschema)
12591317 }
@@ -1545,6 +1603,54 @@ mod tests {
15451603 }
15461604 }
15471605
1606+ /// The scanning path and the indexed path must agree. A schema only
1607+ /// switches over after `NAME_INDEX_PROBE_THRESHOLD` probes, so both are
1608+ /// live in production and a divergence would be data dependent.
1609+ #[ test]
1610+ fn name_index_and_scan_paths_agree ( ) {
1611+ let t1 = TableReference :: bare ( "t1" ) ;
1612+ let t2 = TableReference :: partial ( "s" , "t2" ) ;
1613+ let probes: Vec < ( Option < & TableReference > , & str ) > = vec ! [
1614+ ( None , "a" ) ,
1615+ ( Some ( & t1) , "a" ) ,
1616+ ( Some ( & t2) , "a" ) ,
1617+ ( Some ( & t1) , "missing" ) ,
1618+ ( None , "c" ) ,
1619+ ( Some ( & t2) , "d" ) ,
1620+ ( None , "\u{1f600} " ) ,
1621+ ] ;
1622+
1623+ // A fresh schema per probe never reaches the threshold, so each of
1624+ // these is answered by the scan.
1625+ let scanned: Vec < Option < usize > > = probes
1626+ . iter ( )
1627+ . map ( |( q, name) | ambiguous_schema ( ) . index_of_column_by_name ( * q, name) )
1628+ . collect ( ) ;
1629+
1630+ // One schema probed past the threshold answers from the index.
1631+ let indexed_schema = ambiguous_schema ( ) ;
1632+ for _ in 0 ..=NAME_INDEX_PROBE_THRESHOLD {
1633+ let _ = indexed_schema. index_of_column_by_name ( None , "a" ) ;
1634+ }
1635+ assert ! (
1636+ indexed_schema. name_index. get( ) . is_some( ) ,
1637+ "schema should have switched to the index by now"
1638+ ) ;
1639+ let indexed: Vec < Option < usize > > = probes
1640+ . iter ( )
1641+ . map ( |( q, name) | indexed_schema. index_of_column_by_name ( * q, name) )
1642+ . collect ( ) ;
1643+
1644+ assert_eq ! ( scanned, indexed) ;
1645+ for ( ( q, name) , got) in probes. iter ( ) . zip ( & scanned) {
1646+ assert_eq ! (
1647+ * got,
1648+ reference_index_of_column_by_name( & ambiguous_schema( ) , * q, name) ,
1649+ "both paths disagree with the reference for {q:?} {name}"
1650+ ) ;
1651+ }
1652+ }
1653+
15481654 /// `merge` mutates a schema in place, so a cache populated beforehand
15491655 /// must not survive it: the merged-in fields have to be visible to every
15501656 /// later lookup.
@@ -1918,6 +2024,7 @@ mod tests {
19182024 field_qualifiers : vec ! [ None ; arrow_schema_ref. fields. len( ) ] ,
19192025 functional_dependencies : FunctionalDependencies :: empty ( ) ,
19202026 name_index : OnceLock :: new ( ) ,
2027+ name_probes : AtomicUsize :: new ( 0 ) ,
19212028 } ;
19222029 let df_schema_ref = Arc :: new ( df_schema. clone ( ) ) ;
19232030
@@ -1965,6 +2072,7 @@ mod tests {
19652072 field_qualifiers : vec ! [ None ; schema. fields. len( ) ] ,
19662073 functional_dependencies : FunctionalDependencies :: empty ( ) ,
19672074 name_index : OnceLock :: new ( ) ,
2075+ name_probes : AtomicUsize :: new ( 0 ) ,
19682076 } ;
19692077
19702078 assert_eq ! ( df_schema. inner. metadata( ) , schema. metadata( ) )
0 commit comments