Skip to content

Commit aabab11

Browse files
committed
perf: build the name index only for repeatedly probed schemas
Building the index allocates a `String` and a `Vec` per distinct field name, which costs more than several linear scans. Planning creates a very large number of schemas that are looked up once or twice, so paying that up front is a net loss for them: `sql_planner` showed roughly 25% slower logical planning across narrow-schema cases, and even `logical_select_one_from_700` regressed, since `SELECT c1 FROM t700` does a single lookup but was paying for a 700-entry map. Count by-name probes instead and only build the index once a schema has been probed more than `NAME_INDEX_PROBE_THRESHOLD` times, keeping the original scan until then. One-shot lookups no longer pay anything, while the schemas that dominate the wide cases, probed once per column, still switch over and amortise the build. `name_index_and_scan_paths_agree` pins that both paths answer identically: it probes fresh schemas once each so they stay on the scan, probes one schema past the threshold so it switches, asserts the index was actually built, and compares both against the linear-scan reference.
1 parent cea1b11 commit aabab11

1 file changed

Lines changed: 135 additions & 27 deletions

File tree

‎datafusion/common/src/dfschema.rs‎

Lines changed: 135 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@
2121
use std::collections::{BTreeSet, HashMap, HashSet};
2222
use std::fmt::{Display, Formatter};
2323
use std::hash::Hash;
24+
use std::sync::atomic::{AtomicUsize, Ordering};
2425
use std::sync::{Arc, LazyLock, OnceLock};
2526

2627
use 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+
111118
pub 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

125135
impl 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

Comments
 (0)