[ TOPIC ]
data-structures
65 real merged PRs across 17 projects, ordered easiest to hardest. Read them in order to see how data-structures shows up in production code, then go deeper with the free papers and talks below.
[ 01 // REAL PRs ]
Next (mid) · 48
enhance: sort merged rerank results without per-comparison map lookups
This PR teaches how to optimize sorting by avoiding per-comparison map lookups, using struct-based sorting for performance, and demonstrates careful regression testing to ensure ordering correctness.
fix: only re-prioritize the compaction queue when the config changes
This PR teaches how to correctly synchronize and optimize a priority queue in a concurrent system, including subtle issues with function value comparison, atomic updates, and preventing data races.
[FIXED] JetStream: decDeliveryCount underflow treated messages as exhausting MaxDeliver
This PR teaches how to correctly manage counter state in a map to avoid underflow bugs and subtle key-presence errors, with thorough reasoning and a regression test that demonstrates both the bug and its fix.
fix: accumulate RetrieveResultCache size instead of recomputing it per merge
This PR teaches how to turn a quadratic-time accumulation pattern into a linear one by incrementally tracking the size of a merged protobuf message, with careful attention to what data is retained and how to conservatively estimate memory usage.
Hash the type-derived parameter in the ALP, FPC and GCD codecs
This PR teaches how subtle bugs can arise from missing type-derived parameters in cache keys, how to fix them by updating hash functions, and how to write robust, deterministic regression tests for such issues.
gh-154086: Fix flamegraph thread sample counts
This PR demonstrates how to extend a profiling data structure and its serialization to accurately track and display per-thread sample counts in a flamegraph visualization, including thoughtful filtering and testing.
enhance: [3.0] sort merged rerank results without per-comparison map lookups
This PR demonstrates how to optimize sorting by avoiding repeated map lookups in comparators, using struct slices and stable sorting, and shows how to rigorously test for behavioral equivalence and tuple alignment.
fix: [3.0] gate nested HYBRID high-cardinality STL_SORT on scalar index version
This PR teaches how to gate new index build strategies on versioning to ensure backward compatibility and safe rollbacks in distributed systems.
fix: break out of MoveCursorForSingleChunk once the batch is full
This PR teaches how a subtle off-by-one bug in cursor advancement within a chunked data structure can cause correctness and performance issues, and how to write targeted tests to catch and prevent such logic errors.
wireguard: Reconcile peers from node table
This PR demonstrates how to refactor event-driven resource management to a state reconciliation model, handling peer lifecycle and error cases robustly.
Fix cross-tier JetStream consumer counting for limits
This PR teaches how to correctly enforce resource limits in a distributed system by distinguishing between global and per-tier quotas, and demonstrates how to write targeted tests for subtle multi-tenant accounting bugs.
stream: normalize fused stateless transform results
This PR teaches how to robustly normalize and validate intermediate data between fused stateless stream transforms, ensuring consistent data types and error handling in both sync and async pipelines.
fs: fix glob early return skipping sibling entries
This PR teaches how to fix a subtle bug in a tree traversal algorithm by correctly using a cache to avoid skipping valid sibling entries, and demonstrates how to write a deterministic regression test for order-dependent bugs.
repl: keep entries added while history file is loading
This PR teaches how to correctly merge in-memory and persisted state in asynchronous workflows, ensuring no data loss and adding a regression test to verify the fix.
enhance: resolve the destination column by index in AppendFieldData
This PR demonstrates how to optimize a hot code path by replacing repeated map construction with fast-path index-based access, falling back to a map only when necessary, and includes clear benchmarking and robust testing.
fix: support vector output with order_by
This PR teaches how to handle late materialization of complex data types (like vectors) in query execution plans to support efficient ORDER BY queries with vector outputs.
Fix a crash when a primary-key range layer produces an empty pipe
This PR teaches how to robustly handle empty data structures in a complex data pipeline, prevent crashes from edge cases, and write focused regression tests to cover subtle distributed query execution bugs.
fix: treat unset IdField in zero-hit search results as empty in chain converter
This PR teaches how to robustly handle edge cases in data structures (specifically 'oneof' fields in protobufs) and demonstrates defensive error handling and regression testing for subtle, real-world bugs in distributed systems.
Fix ILLEGAL_TYPE_OF_ARGUMENT on nullable MySQL spatial columns
This PR teaches how to robustly map between differing database type systems, handle type system invariants, and write regression tests for subtle schema inference bugs.
dumpformat: fix corrupted DECIMAL values in dictionary-encoded parquet files
This PR teaches how shared buffer ownership in dictionary-encoded data can cause subtle data corruption, and how to fix it by copying data before in-place mutation.
Avoid deep copy of AccessRights in getGrantQueriesImpl when it is only read
This PR teaches how to optimize performance by avoiding unnecessary deep copies of complex data structures, with careful attention to when mutation is required and how to validate the change with targeted regression tests.
Fix logical error !raw_type->isNullable() in AND-compare chain optimization
This PR teaches how to robustly handle edge cases in query optimization involving nullable types, ensuring optimizer invariants and adding targeted regression tests to prevent logical errors.
Reject a lossy codec on columns backing keys and indexes
This PR teaches how to enforce data integrity by rejecting lossy compression codecs on key columns, including how to propagate and test such validation in a complex codebase.
lightning: optimize CSV field unescaping
This PR teaches how to replace a regular-expression-based string unescaping routine with a more efficient manual byte-scanning algorithm, including how to preserve edge-case behavior and add targeted benchmarks and tests.
Improve the detection of changed hooks
This PR demonstrates how to accurately track and test changes in complex and composite React hooks, including those that internally use multiple primitive hooks, to improve developer tooling and debugging.
[Perf Tracks] Don't enumerate typed array props in dev
This PR teaches how to avoid performance pitfalls when enumerating large typed arrays in JavaScript by recognizing their structure and handling them efficiently in developer tooling.
Prune row groups for column-constant OR
This PR teaches how to optimize query execution by pruning row groups using cross-column OR predicates and demonstrates careful test coverage and code review for correctness and maintainability.
Prune row groups when an IN-list covers the whole zonemap rangend add
This PR teaches how to use zonemap statistics and IN-list analysis to optimize query execution by pruning unnecessary row group scans, including careful handling of edge cases and robust testing.
Fix ASOF join over EXCEPT ALL / INTERSECT ALL children
This PR teaches how physical query planning can introduce hidden columns (like row numbers for bag semantics), why logical and physical operator types must be kept in sync, and how to write regression tests for subtle type mismatches in query execution.
Fix statistics propagation for window aggregate functions (#23663)
This PR teaches how to correctly propagate statistics for window aggregate functions in a query optimizer, including how to structure callbacks and tests for stats-dependent aggregates.
[CPUManager] Skip partially acquired cores during full cores allocation
This PR teaches how to robustly handle heterogeneous hardware topologies in CPU allocation logic by replacing naive integer division with per-structure queries, improving correctness and testability.
CPUMANAGER: spread CPUs across cores using topology
This PR teaches how to improve CPU allocation by spreading CPU assignments across physical cores using topology-aware round-robin selection, with comprehensive tests covering diverse CPU layouts.
buffer: pad aligned allocations by a multiple of 8
This PR teaches how careful memory alignment and buffer padding can prevent subtle bugs with typed array views and ensure correct low-level memory handling in JavaScript runtimes.
[lld][WebAssembly] Do not coalesce segments with differing flags in -r
This PR teaches how to avoid subtle data corruption by ensuring that segments with different flags are not incorrectly merged, illustrating careful use of composite keys in maps and the importance of preserving semantic distinctions in linker internals.
fix(v-model): re-sync select when model is overridden in change handler
Demonstrates robust synchronization of select element state with model updates including Set handling, with detailed regression tests and error recovery.
stream: drain pending writes before broadcast end
This PR teaches how to correctly handle end-of-stream and pending writes in a concurrent broadcast stream, ensuring all queued writes are drained before signaling completion and handling backpressure and errors robustly.
fix: invalidate stale offsets for re-added struct array fields [3.0]
This PR teaches how to safely handle schema evolution in data structures by invalidating stale offsets when struct array fields are dropped and re-added, and demonstrates robust testing for such edge cases.
node: Derive cluster-size intervals from table
This PR demonstrates how to refactor interval logic to depend on a shared data structure (node table) rather than a manager, improving modularity and testability.
GH-50801: [Python] Expose the `record_batch_reader_source` Acero node (RecordBatchReaderSourceNodeOptions)
This PR teaches how to expose a new C++ data source node to Python, including Cython bindings, Pythonic API design, and comprehensive testing of generator-backed streaming data sources.
planner: optimize duplicate removal for common-handle batch point get
This PR demonstrates how to efficiently deduplicate and filter values in-place in a batch processing context, replacing repeated slice deletion with a more optimal approach and validating the results with targeted tests.
executor, util: fix hash join v2 null build key
This PR teaches how to correctly handle NULL values in hash join algorithms to prevent subtle bugs, including how to write targeted regression tests for join edge cases.
fix(ui): show operation state on applications list page (cherry-pick release-3.5)
This PR demonstrates how to efficiently expose just enough API data for UI needs by projecting a presence marker instead of large payloads, and how to test such minimal projections.
Fix reservoir_quantile for DECIMAL types (preserve precision and supp…
This PR teaches how to extend an aggregate function to support additional types (DECIMALs), including careful handling of physical representations, serialization, and regression testing.
[WebAssembly] Fix __init_tls_base global in coop threading
This PR teaches how to correctly initialize and manage thread-local storage (TLS) base globals in WebAssembly modules, especially handling differences between PIC and non-PIC modes for cooperative threading.
[MLIR] Fix control-flow sinking through nested regions
This PR demonstrates how to correctly implement control-flow sinking in the presence of nested regions, highlighting the importance of dominance and region ancestry checks in compiler transformations.
quic: remove unused fin flag from blob reader wakeup
This PR teaches how to identify and safely remove redundant state and dead code in a cross-language (C++/JS) async data pipeline, ensuring correctness and simplifying logic.
fix(shared): correctly compare Map and Set values
This PR teaches how to implement deep equality comparison for complex data structures like Map and Set, including handling unordered entries and loose equality, with thorough test coverage.
fix(compiler-vapor): propagate component root through Transition
This PR demonstrates how to transparently handle wrapper components (like transitions) in a compiler's single-root detection logic and how to write regression tests for subtle class merging bugs.
Go deep (senior) · 17
tsdb: don't lose samples appended to a series removed by head GC
This PR teaches how to safely handle concurrent access and garbage collection of in-memory data structures to prevent silent data loss in a time series database.
Fix ConcurrentQueue.TryDequeue spuriously reporting empty during a segment freeze
This PR teaches how subtle memory ordering bugs in lock-free concurrent data structures can cause rare, hard-to-reproduce errors, and how to reason about and test for correct publication protocols.
Fix wrong `ORDER BY` results for `Merge` over `Distributed`
This PR teaches how distributed query engines must carefully preserve stream ordering to ensure correct results for ORDER BY and LIMIT, and how to write regression tests for subtle distributed query bugs.
Fix lazy materialization OOB and a Merge LOGICAL_ERROR from unused text index virtual columns
This PR teaches how to maintain invariants between query plan steps by pruning unused virtual columns after DAG rewrites, preventing subtle header mismatches that can cause out-of-bounds errors and logical failures in query engines.
Add multiplicity-aware combine support and fix LIST state combination
This PR teaches how to correctly handle aggregate state combination with multiplicities in query optimizations, especially for list-backed aggregates, and demonstrates robust testing and plan stability practices.
planner: fix countAfterAccess for IndexJoin in Skyline Pruning Comparison (#70791)
This PR teaches how to accurately estimate row counts for index join candidates in a query planner by adjusting for join key NDV, ensuring fair comparison and optimal index selection during skyline pruning.
planner: keep min/max row estimates aligned after correlated column split (#70793)
This PR demonstrates how to maintain consistent row estimate bounds for correlated index paths during query optimization to avoid incorrect pruning, including the reasoning and regression test coverage needed for robust planner changes.
planner: fix countAfterAccess for IndexJoin in Skyline Pruning Comparison
This PR teaches how to adjust row count estimation for index join selection in a query optimizer by accounting for join key NDV, ensuring fairer candidate comparison and demonstrating robust regression testing for plan choice correctness.
Fix generic virtual dispatch hang after multiple AssemblyLoadContext unloads
This PR teaches how subtle bugs in cache sentinel handling can cause memory leaks or stale data after unloading assemblies, and demonstrates robust regression testing and defensive coding in complex runtime systems.
Check column structure against the declared type in `collectOffsetsColumns`
This PR teaches how to proactively check and enforce structural compatibility between declared types and actual in-memory column data to prevent subtle runtime errors in complex, nested data structures.
Fix missing materialized-CTE gate when a `Merge` table has several children
This PR teaches how to safely manage and optimize materialized CTE ownership across multiple query plan branches to prevent subtle concurrency and correctness bugs in complex query engines.
Fix: Activity should hide portal contents
This PR teaches how to handle special cases in tree traversal algorithms (like portals in React's fiber tree), including optimizing with subtree flags and refactoring from iterative to recursive approaches.
[DAG] Add computeKnownBits(FREEZE(X)) handling
This PR teaches how to extend static analysis (known bits propagation) in a compiler's intermediate representation to correctly handle 'freeze' nodes, including subtle interactions with poison values and code generation consequences.
Reduce next-solver memory usage by interning CanonicalQueryInput
This PR demonstrates how interning a frequently-duplicated data structure can drastically reduce memory usage in a complex system, with practical tradeoffs and implementation details in a real compiler codebase.
[RISCV] Attach VLMAX range attribute for vsetvli/vsetvlimax in InstCombine
This PR teaches how to compute and attach precise value range metadata to target-specific intrinsics, enabling generic analyses to reason about their results without target-specific knowledge.
[SelectionDAG] Preserve CTTZ_ELTS lane count during expansion
This PR teaches how to correctly preserve logical vector lane counts during target-specific legalization in a compiler backend, avoiding subtle bugs in vectorized intrinsic lowering.
[CodeGenPrepare] Failure to hoist bitcast to legal type causes register splitting
This PR demonstrates how to hoist bitcast instructions in LLVM IR to reduce register pressure and avoid register splitting, including careful handling of edge cases and legality checks.
[ 02 // MUST-READ PAPERS ]
Free to read, ranked by citations.
- Space/time trade-offs in hash coding with allowable errorsBurton H. Bloom · Communications of the ACM · 19707,644 citationsfree PDF
- Skip lists: a probabilistic alternative to balanced treesWilliam W. Pugh · CACM · 1989
In this chapter three algorithms for insertion and deletion in skip lists are studied, which are much simpler and significantly faster than equivalent algorithms for balanced trees.
1,475 citationsfree PDF - The Adaptive Radix Tree: ARTful Indexing for Main-Memory DatabasesViktor Leis et al. · ICDE · 2013438 citationsfree PDF
[ 03 // FREE VIDEOS & TALKS ]
Ranked by views.
other topics