Ashwani Raina has posted comments on this change. ( http://gerrit.cloudera.org:8080/24615 )
Change subject: [tablet] Skip stable_sort for already sorted batch ...................................................................... Patch Set 2: (13 comments) http://gerrit.cloudera.org:8080/#/c/24615/2//COMMIT_MSG Commit Message: http://gerrit.cloudera.org:8080/#/c/24615/2//COMMIT_MSG@18 PS2, Line 18: This patch tracks an 'is_sorted' flag while building 'keys_and_indexes' : in the loop that already scans every op, flipping it to false on the : first out-of-order pair. When the flag survives to the end of the loop, : the stable_sort is skipped entirely, improving performance by a slight : margin if not significant. > I'm a bit skeptical since I'd expect that contemporary implementations of s Check my response at: https://gerrit.cloudera.org/#/c/24615/2/src/kudu/tablet/tablet.cc@1178 http://gerrit.cloudera.org:8080/#/c/24615/2//COMMIT_MSG@24 PS2, Line 24: Measured with 'kudu perf loadgen --use_upsert --num_rows_per_thread=5M' : on a single-tablet cluster, median of N=5 runs: > It would be great to see unit-level performance improvement for this for RE See my response at : https://gerrit.cloudera.org/#/c/24615/2/src/kudu/tablet/tablet.cc@1178 http://gerrit.cloudera.org:8080/#/c/24615/2//COMMIT_MSG@27 PS2, Line 27: sorted input batch > What sort of build was it? Please double-check it's a RELEASE, not a DEBUG It was most likely a DEBUG build. Updated the commit message with results from RELEASE build. http://gerrit.cloudera.org:8080/#/c/24615/2//COMMIT_MSG@29 PS2, Line 29: --use_random=false > nit: there is no need to customize this, it's false by defalt Done http://gerrit.cloudera.org:8080/#/c/24615/2//COMMIT_MSG@31 PS2, Line 31: -buffer_flush_watermark_pct=1.0 > nit: why to customize this at all? To mimic OLAP bulk ingest with production of large batches with proportionally bigger sort and speedup to make results detectable. http://gerrit.cloudera.org:8080/#/c/24615/2//COMMIT_MSG@32 PS2, Line 32: --keep_auto_table=false > nit: this is false by default already, can drop this useless customization Done http://gerrit.cloudera.org:8080/#/c/24615/2/src/kudu/tablet/tablet.cc File src/kudu/tablet/tablet.cc: http://gerrit.cloudera.org:8080/#/c/24615/2/src/kudu/tablet/tablet.cc@1154 PS2, Line 1154: const MonoTime bulk_check_start = MonoTime::Now(); > nit: bulk_check_start is computed unconditionally, but it's only consumed u Done http://gerrit.cloudera.org:8080/#/c/24615/2/src/kudu/tablet/tablet.cc@1175 PS2, Line 1175: if (is_sorted && !keys_and_indexes.empty() && : key < keys_and_indexes.back().first) { : is_sorted = false; : } > Might invoking std::is_sorted() to decide whether to call std::stable_sort( The loop already exists here to build keys_and_indexes, adding is_sorted logic inside is cheaper than calling std::is_sorted() after the loop. I ran some performance tests on standalone logic for three variants: 1. One branch per element, short-circuits after the first out-of-order pair — the current implementation. 2. Clean build loop with no per-element overhead; one O(N) scan over the finished vector via std::is_sorted before deciding whether to sort. 3. Baseline: no detection whatsoever; stable_sort runs unconditionally. The tests were performed on RELEASE build with: - Batch sizes: 100, 1K, 5K, 20K - Order: Sorted, Reverse, Random - Number of iterations: 200 to 20K Inline strategy (i.e. #1) wins with 7-10% improvement over 'post is_sorted' (i.e. #2) for large batch sizes, ~7x faster than 'always sort' (i.e. #3) for sorted input and large batch. For unsorted batches, all three variants are identical. http://gerrit.cloudera.org:8080/#/c/24615/2/src/kudu/tablet/tablet.cc@1179 PS2, Line 1179: keys_and_indexes.emplace_back(key, i); > No test accompanies the change. Given the correctness argument rests on "no Done http://gerrit.cloudera.org:8080/#/c/24615/2/src/kudu/tablet/tablet.cc@1203 PS2, Line 1203: sort_us = (MonoTime::Now() - sort_start).ToMicroseconds(); > +1: I don't see a reason to keep this as a metric for any reason beyond mea With just 2 metrics for unit test verification purpose, there is no metric left. http://gerrit.cloudera.org:8080/#/c/24615/2/src/kudu/tablet/tablet.cc@1203 PS2, Line 1203: sort_us = (MonoTime::Now() - sort_start).ToMicroseconds(); > The commit message says these metrics exist "so that the sort-skip optimisa Except for two (used in unit tests for verification purpose), removed other three metrics. http://gerrit.cloudera.org:8080/#/c/24615/2/src/kudu/tablet/tablet.cc@1211 PS2, Line 1211: if (is_sorted) { > q: a batch where every op was filtered out (has_result / orig_result_from_l Good catch! Have added a check to avoid the unnecessary inflation of counter. http://gerrit.cloudera.org:8080/#/c/24615/2/src/kudu/tablet/tablet.cc@1211 PS2, Line 1211: if (is_sorted) { > For what purpose would anybody use these new metrics in production? Except for two (used in unit tests for verification purpose), removed other three metrics. -- To view, visit http://gerrit.cloudera.org:8080/24615 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I28d3f5ebdf7e3f13f04ffe8d35417a98c370fcf7 Gerrit-Change-Number: 24615 Gerrit-PatchSet: 2 Gerrit-Owner: Ashwani Raina <[email protected]> Gerrit-Reviewer: Alexey Serbin <[email protected]> Gerrit-Reviewer: Ashwani Raina <[email protected]> Gerrit-Reviewer: Kudu Jenkins (120) Gerrit-Reviewer: Marton Greber <[email protected]> Gerrit-Comment-Date: Mon, 31 Aug 2026 13:46:14 +0000 Gerrit-HasComments: Yes
