[
https://issues.apache.org/jira/browse/TAJO-2059?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15146950#comment-15146950
]
ASF GitHub Bot commented on TAJO-2059:
--------------------------------------
Github user jihoonson commented on a diff in the pull request:
https://github.com/apache/tajo/pull/945#discussion_r52862828
--- Diff:
tajo-storage/tajo-storage-hdfs/src/main/java/org/apache/tajo/storage/index/bst/BSTIndex.java
---
@@ -794,42 +794,79 @@ private int binarySearch(Tuple[] arr, Tuple key, int
startPos, int endPos) {
int offset = -1;
int start = startPos;
int end = endPos;
+ int prevCenter = -1;
//http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6412541
int centerPos = (start + end) >>> 1;
if (arr.length == 0) {
LOG.error("arr.length: 0, loadNum: " + loadNum + ", inited: " +
inited.get());
+ return -1;
}
+
+ correctable = false;
+ if (arr.length == 1) {
+ int comp = comparator.compare(arr[0], key);
+
+ if (comp < 0) {
+ return 0;
+ } else if (comp > 0) {
+ return -1;
+ }
+
+ correctable = true;
+ return 0;
+ }
+
while (true) {
- if (comparator.compare(arr[centerPos], key) > 0) {
- if (centerPos == 0) {
- correctable = false;
- break;
- } else if (comparator.compare(arr[centerPos - 1], key) < 0) {
- correctable = false;
- offset = centerPos - 1;
+ if (end - start == 1) {
+ int comp;
+ // prevCenter should be either end or start
+ if (end == prevCenter) {
+ comp = comparator.compare(arr[start], key);
+
+ if (comp == 0) {
+ correctable = true;
+ offset = start;
+ } else if (comp < 0) {
+ offset = start;
+ }
break;
} else {
- end = centerPos;
- centerPos = (start + end) / 2;
- }
- } else if (comparator.compare(arr[centerPos], key) < 0) {
- if (centerPos == arr.length - 1) {
- correctable = false;
- offset = centerPos;
- break;
- } else if (comparator.compare(arr[centerPos + 1], key) > 0) {
- correctable = false;
- offset = centerPos;
+ if (end == arr.length) {
--- End diff --
In this method ```binarySearch()```, ```endPos``` is intended as an
exclusive end position. It looks that codes in this block need to consider this
intention.
> Binary search in BST reader does compare too frequently
> -------------------------------------------------------
>
> Key: TAJO-2059
> URL: https://issues.apache.org/jira/browse/TAJO-2059
> Project: Tajo
> Issue Type: Improvement
> Components: Storage
> Affects Versions: 0.11.0
> Reporter: Jongyoung Park
> Assignee: Jongyoung Park
>
> Current binary search logic do comparing twice each iteration.
> It should be refined.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
