alex-plekhanov commented on a change in pull request #9234:
URL: https://github.com/apache/ignite/pull/9234#discussion_r679241290
##########
File path:
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndex.java
##########
@@ -128,35 +127,41 @@ else if (ectx.rowHandler().get(firstCol, lower) != null
&& ectx.rowHandler().get
this.rows = rows;
this.upper = upper;
- idx = computeStartIdx(rows, lower) - 1;
+ idx = lower == null ? 0 : lowerBound(rows, lower);
}
/**
+ * Searches the lower bound (skipping duplicates) using a binary
search.
+ *
* @param rows List of rows.
- * @param lower Lower bound.
+ * @param target Lower bound.
* @return Lower bound position in the list.
*/
- private int computeStartIdx(List<Row> rows, @Nullable Row lower) {
- int fromIdx = lower == null ? -1 : Collections.binarySearch(rows,
lower, comp);
-
- if (fromIdx < 0)
- fromIdx = -fromIdx - 1;
- else {
- // Skip duplcates.
- while (fromIdx > 0 && comp.compare(rows.get(fromIdx - 1),
rows.get(fromIdx)) == 0)
- --fromIdx;
+ private int lowerBound(List<Row> rows, Row target) {
+ int low = 0, high = rows.size() - 1, idx = -1;
+
+ while (low <= high) {
+ int mid = (high - low) / 2 + low;
+
+ if (comp.compare(rows.get(mid), target) > 0)
+ high = mid - 1;
+ else if (comp.compare(rows.get(mid), target) == 0) {
Review comment:
Let's store the comparison result and check only the result here (avoid
double `compare` call)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
