# Goal ## Subgoal 1 We need a more accurate algorithm to compute split point. Currently, in `compute_split_points`, we only sample the first fragment for split points, however, this may lead to skewed splits under skewed workloads. Consider the following case, it is not correct to use 5000 as the split point. ```text [1..10000], [9000..10000], [10000..11000], [11000..12000], [12000..13000] ``` Instead, the split point should be a weighted average across multiple fragments. We introduce a `split_point_scan_size_ratio` parameter to decide how many fragments to scan: - Only scan non-base(delta) fragments, and scan them **in reverse order**. - When calculating scanned size / total size, multiply `FragProperty.size` by `SplittableFrag.p`. - The "total size" for the ratio is the sum of **all** non-base fragments' bytes (each multiplied by `p`). - Keep scanning until `scanned_size / total_size` reaches `split_point_scan_size_ratio`. - `split_point_scan_size_ratio` has default value of `0.7`. For each scanned fragment `i`, compute: - `split_point_i`: this fragment's representative split handle (see "A corner case" for the trimming/estimation rules). - `row_count_i`: `FragProperty.count` (row count) multiplied by `SplittableFrag.p` (no additional scaling/estimation). This yields the following tuples (split point and row count from each fragment): ``` [(split_point_1, row_count_1), (split_point_2, row_count_2), ...] ``` Then we compute the final split point as the weighted average of `split_point_i`, weighted by `row_count_i`. For "weighted average of split points", we **do not** decode keys into numbers. Instead, we treat them as big-endian base-256 byte arrays and compute: - Normalize all contributing split handles by **right-padding `0x00`** to the same length `L` (where `L` is the maximum split handle length). - Let `base` be the **minimum** split handle (after normalization). For each split handle `k_i`, compute `delta_i = k_i - base` using big-number subtraction on the byte arrays (base-256, big-endian), then compute the weighted average: - `avg_delta = sum(delta_i * row_count_i) / sum(row_count_i)` (integer division / truncate). - `result = base + avg_delta`. - Compute `result` as exactly `L` bytes. You may **right-trim** trailing `0x00` bytes to produce a shorter (more compact) split handle. Do not trim into an empty byte string. - This weighted interpolation does not need to be extremely precise: if one `row_count` is overwhelmingly larger than others (e.g. `10000` vs `1`), the smaller one can effectively be ignored due to integer truncation. Intuition: after the normalization step, you can think of each candidate split handle as a point on a line ordered by byte-string order (for fixed-length big-endian bytes, lexicographical order matches numeric order). If all `row_count_i` are equal, the result is the **arithmetic mean** of these points (not necessarily equal to the "middle element" in the sorted candidates). With weights, it becomes a **weighted mean** (center-of-mass), so the final split handle moves closer to candidates with larger `row_count_i`. Also note that `avg_delta` is bounded by the min/max candidates, so `result` is always within `[min_candidate, max_candidate]`; although we use base-256 "big-number" arithmetic (with carry), the final addition does not overflow beyond `L` bytes. If you right-trim trailing `0x00`, it stays effectively the same point under the same right-padding normalization. ### Clarifications - `split_handles` is currently only one element in production, but the algorithm must support **multiple** `split_handles`. - `compute_split_points` returns a `Vec`, but for now it will only contain **one** split point (2-way split only; do not split into >2 parts yet). - The implementation will involve multiple base-256, big-endian "big-number byte array" operations (add/sub/mul/div, weighted average, range span ratios). Extract these into reusable util functions and add dedicated unit tests for the util layer. ### A corner case when computing `split_handles` **IN A FRAGMENT** The `split_handles` provided in the properties of each fragment contains `N` handles that can split the fragment evenly into `N+1` parts. Currently, we only split the shard in half, so ideally, for each fragment, we only need to find the middle handle and use it to split the fragment. However, if a shard was split before, and then split again before a compaction occurred, some fragments may have larger range bounds, causing `split_handles` to potentially fall outside the range. So we must use part of `split_handles` which only reflects the real range that the fragment contribute to the shard. For example, when split, we can only use the middle of `[c,f,g]`, because range `[b..c]` doesn't belong to the shard. ``` shard range = [c..g] split_handles = [b,c,f,g] ``` The following two cases are harder: - Case 1 There is no `d` in split handles. ``` shard range = [d..f] split_handles = [b,c,f,g] ``` - Case 2 All split handles are out of the shard range. ``` shard range = [d..f] split_handles = [c] ``` In these cases, we can only compute the split handle by estimation, under the assumption that the keys are uniformly distributed over the given range. If after trimming to shard range a fragment has an **even** number of usable `split_handles`, compute the fragment's split handle by estimation (i.e. use `midpoint` between the two middle handles). If the corner case logic is triggered, `row_count_i` is still computed as `FragProperty.count` (row count) multiplied by `SplittableFrag.p` (no additional scaling/estimation). ### Musts - Ask me if you don't understand any part of this task. You don't make decisions on your own. - You must follow the programming style defined in `STYLE.md`. ### Tests - You must implement tests to ensure that the "Musts" are met. - You must follow the "Testing Guidelines" in `AGENTS.md`, but you don't need to actually run them. - You must implement a series of unit tests in `src/common/shard.rs`, to cover all cases mentioned. - You run test with `export CARGO_TARGET_DIR=./target-codex`.