fix: reconstruct protobuf schema fields in linear time#7766
Merged
Conversation
Contributor
📝 WalkthroughWalkthroughSchema reconstruction now validates parent relationships through fallible APIs, propagates errors across Rust and Python deserialization paths, adds regression coverage, and introduces a benchmark for wide nested schemas. ChangesSchema reconstruction and error propagation
Estimated code review effort: 4 (Complex) | ~45 minutes Sequence Diagram(s)sequenceDiagram
participant Protobuf
participant Deserializer
participant SchemaTryFrom
participant Schema
Protobuf->>Deserializer: provide encoded schema fields
Deserializer->>SchemaTryFrom: convert protobuf fields
SchemaTryFrom->>SchemaTryFrom: validate parent relationships
SchemaTryFrom->>Schema: materialize reconstructed schema
Schema-->>Deserializer: return schema or error
Suggested reviewers: 🚥 Pre-merge checks | ✅ 4 | ❌ 1❌ Failed checks (1 warning)
✅ Passed checks (4 passed)
✨ Finishing Touches📝 Generate docstrings
🧪 Generate unit tests (beta)
Comment |
github-actions
Bot
added
A-python
Codecov Report❌ Patch coverage is 📢 Thoughts on this report? Let us know! |
Xuanwo
marked this pull request as ready for review
July 14, 2026 06:10
![coderabbitai[bot]](https://avatars.githubusercontent.com/in/347564?s=60&v=4){kind=small}
Contributor
There was a problem hiding this comment.
Actionable comments posted: 3
🤖 Prompt for all review comments with AI agents
Verify each finding against current code. Fix only still-valid issues, skip the
rest with a brief reason, keep changes minimal, and validate.
Inline comments:
In `@python/python/tests/test_schema.py`:
- Around line 66-73: Add context to
test_lance_schema_from_protos_rejects_missing_parent by replacing the
hand-encoded field_proto literal with an encoded Field protobuf message where
practical; otherwise document each wire-format byte segment and its
corresponding name, id, parent_id, and logical_type field. Preserve the test’s
missing-parent setup and expected ValueError assertion.
In `@rust/lance-file/benches/schema.rs`:
- Around line 20-29: Add a doc comment to wide_two_leaf_structs documenting that
-1 denotes the root parent, each struct occupies a three-ID block containing one
parent and two leaves, and fields are emitted in pre-order. Keep the benchmark
fixture logic unchanged.
In `@rust/lance-file/src/datatypes.rs`:
- Around line 102-125: Add a concise doc comment to first_field_index_by_id
documenting that it performs pre-order depth-first traversal and returns the
first matching node, preserving legacy tie-breaking when duplicate field IDs
exist.
🪄 Autofix (Beta)
Fix all unresolved CodeRabbit comments on this PR:
- Push a commit to this branch (recommended)
- Create a new PR with the fixes
ℹ️ Review info
⚙️ Run configuration
Configuration used: Path: .coderabbit.yaml
Review profile: ASSERTIVE
Plan: Pro Plus
Run ID: e27f9c01-5466-4882-a91b-90a5207d911c
📒 Files selected for processing (9)
python/python/tests/test_schema.pypython/src/schema.rsrust/lance-file/Cargo.tomlrust/lance-file/benches/schema.rsrust/lance-file/src/datatypes.rsrust/lance-file/src/previous/format/metadata.rsrust/lance-file/src/reader.rsrust/lance-table/src/format/manifest.rsrust/lance/src/dataset/transaction.rs
westonpace
approved these changes
Jul 14, 2026
westonpace
left a comment
westonpace
left a comment
Member
There was a problem hiding this comment.
Just one nit that we might want to use TryFrom
| /// assert_eq!(schema.metadata["owner"], "lance"); | ||
| /// # Ok::<(), lance_core::Error>(()) | ||
| /// ``` | ||
| pub fn try_into_schema(self) -> Result<Schema> { |
Member
There was a problem hiding this comment.
Why not impl TryFrom<FieldsWithMeta> for Schema?
| /// assert_eq!(schema.fields[0].name, "value"); | ||
| /// # Ok::<(), lance_core::Error>(()) | ||
| /// ``` | ||
| pub fn try_to_schema(&self) -> Result<Schema> { |
Member
There was a problem hiding this comment.
Same question. Why not TryFrom?
Comment on lines
+137
to
+139
| /// Parent fields must appear before their children. Duplicate field IDs are | ||
| /// retained for backwards compatibility, and parent references use the | ||
| /// legacy first depth-first match. |
Member
There was a problem hiding this comment.
Can you expand on the last two sentences here a bit?
Suggested change
| /// Parent fields must appear before their children. Duplicate field IDs are | |
| /// retained for backwards compatibility, and parent references use the | |
| /// legacy first depth-first match. | |
| /// Parent fields must appear before their children. Some historical | |
| /// manifests may have duplicate ids. If so, we will fall back to the | |
| /// legacy behavior which is to pick the first instance of the id as | |
| /// the parent of a field. |
Comment on lines
+208
to
+224
| let mut fields_by_node = Vec::with_capacity(nodes.len()); | ||
| fields_by_node.resize_with(nodes.len(), || None); | ||
| for (node_index, mut node) in nodes.into_iter().enumerate().rev() { | ||
| node.field.children.reserve(node.child_indices.len()); | ||
| for child_index in node.child_indices { | ||
| let child = fields_by_node | ||
| .get_mut(child_index) | ||
| .and_then(Option::take) | ||
| .ok_or_else(|| { | ||
| Error::internal(format!( | ||
| "Schema field arena node {child_index} was not materialized before its parent" | ||
| )) | ||
| })?; | ||
| node.field.children.push(child); | ||
| } | ||
| fields_by_node[node_index] = Some(node.field); | ||
| } |
Member
There was a problem hiding this comment.
I like the forward - backward traversal, clever 😄
Collaborator
Author
|
The failure is not related. |
This was referenced Jul 14, 2026
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Why
Schema decoding currently rebuilds a tree from flat protobuf fields by calling
mut_field_by_idfor every child. Each lookup traverses the partially built tree, making wide schemas O(N²). The same conversion is used by raw file schema decoding and dataset manifest decoding; on the 65,536-physical-column fixture the lookup dominated profiles.Solution
Build fields into an input-ordered arena, resolve unique parent IDs through an ID-to-node map, then materialize children in reverse arena order. Valid schemas preserve root and child order with O(total fields) time and memory. Malformed duplicate IDs retain the legacy first depth-first parent match; missing or forward parents now return errors through
TryFrom<&Fields>andTryFrom<FieldsWithMeta>.The reader, manifest, transaction, and Python protobuf boundaries now propagate this error (
ValueErrorin Python). Wide/deep correctness coverage and a Criterion scaling benchmark cover 1,024 through 65,536 physical columns.Read-path impact
Raw/self-describing opens still fetch and decode file schema but reconstruct it linearly. Dataset manifest opens pay the same linear conversion once. Known-schema metadata-index fragment reads continue to skip the file schema buffer entirely; only their full-metadata fallback decodes and benefits from this change.
Performance
Measured on the same
m7i.4xlargeEC2 host inus-east-2with Rust 1.97.0 and the repository'srelease-with-debugprofile. The fixture contains 32,768 two-leaf structs: 65,536 physical columns and 98,304 protobuf schema nodes. The valid-schema baseline restores the previous per-childmut_field_by_idlookup; the benchmark variants otherwise use identical code and fixture shapes.Pure reconstruction uses three measured samples for each variant:
Across the endpoints, the empirical scaling exponent drops from 2.17 to 1.06, discriminating quadratic-like from linear growth on this fixture.
End-to-end values are medians of three baseline samples and ten fixed samples. Read bytes, I/O counts, and observed result counts match before and after for every row.
Known-schema metadata opens bypass reconstruction and serve as an unaffected control:
The control ranges overlap, and their absolute median differences are 0.062–2.233 ms. Affected end-to-end paths save 16.79–17.93 seconds per open on this fixture.
This is independent of indexed metadata structural projection.
Summary by CodeRabbit