hive-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (Jira)" <j...@apache.org>
Subject [jira] [Work logged] (HIVE-25061) PTF: Improve ValueBoundaryScanner
Date Fri, 30 Jul 2021 11:52:00 GMT

     [ https://issues.apache.org/jira/browse/HIVE-25061?focusedWorklogId=631565&page=com.atlassian.jira.plugin.system.issuetabpanels:worklog-tabpanel#worklog-631565
]

ASF GitHub Bot logged work on HIVE-25061:
-----------------------------------------

                Author: ASF GitHub Bot
            Created on: 30/Jul/21 11:51
            Start Date: 30/Jul/21 11:51
    Worklog Time Spent: 10m 
      Work Description: pgaref commented on a change in pull request #2225:
URL: https://github.com/apache/hive/pull/2225#discussion_r679833993



##########
File path: ql/src/java/org/apache/hadoop/hive/ql/udf/ptf/ValueBoundaryScanner.java
##########
@@ -403,26 +418,13 @@ protected int computeStartPreceding(int rowIdx, PTFPartition p) throws
HiveExcep
       }
     }
 
-    Object rowVal = sortKey;
     int r = rowIdx;
 
-    // Use Case 4.
-    if ( expressionDef.getOrder() == Order.DESC ) {
-      while (r >= 0 && !isDistanceGreater(rowVal, sortKey, amt) ) {
-        Pair<Integer, Object> stepResult = skipOrStepBack(r, p);
-        r = stepResult.getLeft();
-        rowVal = stepResult.getRight();
-      }
-      return r + 1;
-    }
-    else { // Use Case 5.
-      while (r >= 0 && !isDistanceGreater(sortKey, rowVal, amt) ) {
-        Pair<Integer, Object> stepResult = skipOrStepBack(r, p);
-        r = stepResult.getLeft();
-        rowVal = stepResult.getRight();
-      }
-
-      return r + 1;
+    // Use Case 4,5
+    if (enableBinarySearch) {
+      return binarySearchBack(r, p, sortKey, amt, expressionDef.getOrder());

Review comment:
       I would pass rowId directly here for clarity

##########
File path: ql/src/java/org/apache/hadoop/hive/ql/udf/ptf/ValueBoundaryScanner.java
##########
@@ -664,6 +632,87 @@ public Object computeValue(Object row) throws HiveException {
    */
   public abstract boolean isEqual(Object v1, Object v2);
 
+  protected int binarySearchBack(int r, PTFPartition p, Object sortKey, int amt,
+      Order order) throws HiveException {
+    boolean isOrderDesc = order.equals(Order.DESC);
+    Object rowVal = sortKey;
+
+    int rMin = -1;  // tracks lowest possible number fulfilling the range requirement
+    int rMax = r; // tracks highest possible number fulfilling the range requirement
+
+    boolean isDistanceGreater = true;
+    while (true) {

Review comment:
       I usually avoid while true loops -- would refactor this to rMin < rMax and return
rMin outside the loop

##########
File path: ql/src/java/org/apache/hadoop/hive/ql/udf/ptf/ValueBoundaryScanner.java
##########
@@ -664,6 +632,87 @@ public Object computeValue(Object row) throws HiveException {
    */
   public abstract boolean isEqual(Object v1, Object v2);
 
+  protected int binarySearchBack(int r, PTFPartition p, Object sortKey, int amt,
+      Order order) throws HiveException {
+    boolean isOrderDesc = order.equals(Order.DESC);
+    Object rowVal = sortKey;
+
+    int rMin = -1;  // tracks lowest possible number fulfilling the range requirement
+    int rMax = r; // tracks highest possible number fulfilling the range requirement
+
+    boolean isDistanceGreater = true;
+    while (true) {
+      if (rMin == rMax) {
+        return rMin;
+      }
+      isDistanceGreater =
+          isDistanceGreater(isOrderDesc ? rowVal : sortKey, isOrderDesc ? sortKey : rowVal,
amt);
+      if (!isDistanceGreater && r == 0) {
+        return 0;
+      }
+      if (isDistanceGreater) {
+        rMin = r + 1;
+      } else {
+        rMax = r;
+      }
+      r = rMin + (rMax - rMin) / 2;
+      rowVal = computeValueUseCache(r, p);
+    }
+  }
+
+  private int linearSearchBack(int r, PTFPartition p, Object sortKey, int amt,
+      Order order) throws HiveException {
+    boolean isOrderDesc = order.equals(Order.DESC);
+    Object rowVal = sortKey;
+    while (r >= 0 && !isDistanceGreater(isOrderDesc ? rowVal : sortKey,
+        isOrderDesc ? sortKey : rowVal, amt)) {
+      Pair<Integer, Object> stepResult = skipOrStepBack(r, p);
+      r = stepResult.getLeft();
+      rowVal = stepResult.getRight();
+    }
+    return r + 1;
+  }
+
+  protected int binarySearchForward(int r, PTFPartition p, Object sortKey, int amt,
+      Order order) throws HiveException {
+    boolean isOrderDesc = order.equals(Order.DESC);
+    Object rowVal = sortKey;
+    int rMin = r;  // tracks lowest possible number fulfilling the range requirement
+    int rMax = p.size(); // tracks highest possible number fulfilling the range requirement

Review comment:
       maybe rMax = p.size()-1 ?

##########
File path: ql/src/java/org/apache/hadoop/hive/ql/udf/ptf/ValueBoundaryScanner.java
##########
@@ -664,6 +632,87 @@ public Object computeValue(Object row) throws HiveException {
    */
   public abstract boolean isEqual(Object v1, Object v2);
 
+  protected int binarySearchBack(int r, PTFPartition p, Object sortKey, int amt,
+      Order order) throws HiveException {
+    boolean isOrderDesc = order.equals(Order.DESC);
+    Object rowVal = sortKey;
+
+    int rMin = -1;  // tracks lowest possible number fulfilling the range requirement

Review comment:
       maybe start with rMin=0?

##########
File path: ql/src/java/org/apache/hadoop/hive/ql/udf/ptf/ValueBoundaryScanner.java
##########
@@ -664,6 +632,87 @@ public Object computeValue(Object row) throws HiveException {
    */
   public abstract boolean isEqual(Object v1, Object v2);
 
+  protected int binarySearchBack(int r, PTFPartition p, Object sortKey, int amt,

Review comment:
       maybe rename r to something like mid or rowId?

##########
File path: ql/src/java/org/apache/hadoop/hive/ql/udf/ptf/ValueBoundaryScanner.java
##########
@@ -664,6 +632,87 @@ public Object computeValue(Object row) throws HiveException {
    */
   public abstract boolean isEqual(Object v1, Object v2);
 
+  protected int binarySearchBack(int r, PTFPartition p, Object sortKey, int amt,
+      Order order) throws HiveException {
+    boolean isOrderDesc = order.equals(Order.DESC);
+    Object rowVal = sortKey;
+
+    int rMin = -1;  // tracks lowest possible number fulfilling the range requirement
+    int rMax = r; // tracks highest possible number fulfilling the range requirement
+
+    boolean isDistanceGreater = true;
+    while (true) {
+      if (rMin == rMax) {
+        return rMin;
+      }
+      isDistanceGreater =
+          isDistanceGreater(isOrderDesc ? rowVal : sortKey, isOrderDesc ? sortKey : rowVal,
amt);
+      if (!isDistanceGreater && r == 0) {

Review comment:
       Looks to me that is !isDistanceGreater and r/mid ==0 -> rMax will become rMin and
will terminate in next iteration.
   Any particular reason we add this here?

##########
File path: ql/src/java/org/apache/hadoop/hive/ql/udf/ptf/ValueBoundaryScanner.java
##########
@@ -664,6 +632,87 @@ public Object computeValue(Object row) throws HiveException {
    */
   public abstract boolean isEqual(Object v1, Object v2);
 
+  protected int binarySearchBack(int r, PTFPartition p, Object sortKey, int amt,
+      Order order) throws HiveException {
+    boolean isOrderDesc = order.equals(Order.DESC);
+    Object rowVal = sortKey;
+
+    int rMin = -1;  // tracks lowest possible number fulfilling the range requirement
+    int rMax = r; // tracks highest possible number fulfilling the range requirement
+
+    boolean isDistanceGreater = true;
+    while (true) {
+      if (rMin == rMax) {
+        return rMin;
+      }
+      isDistanceGreater =
+          isDistanceGreater(isOrderDesc ? rowVal : sortKey, isOrderDesc ? sortKey : rowVal,
amt);
+      if (!isDistanceGreater && r == 0) {
+        return 0;
+      }
+      if (isDistanceGreater) {
+        rMin = r + 1;
+      } else {
+        rMax = r;
+      }
+      r = rMin + (rMax - rMin) / 2;
+      rowVal = computeValueUseCache(r, p);
+    }
+  }
+
+  private int linearSearchBack(int r, PTFPartition p, Object sortKey, int amt,
+      Order order) throws HiveException {
+    boolean isOrderDesc = order.equals(Order.DESC);
+    Object rowVal = sortKey;
+    while (r >= 0 && !isDistanceGreater(isOrderDesc ? rowVal : sortKey,
+        isOrderDesc ? sortKey : rowVal, amt)) {
+      Pair<Integer, Object> stepResult = skipOrStepBack(r, p);
+      r = stepResult.getLeft();
+      rowVal = stepResult.getRight();
+    }
+    return r + 1;
+  }
+
+  protected int binarySearchForward(int r, PTFPartition p, Object sortKey, int amt,
+      Order order) throws HiveException {
+    boolean isOrderDesc = order.equals(Order.DESC);
+    Object rowVal = sortKey;
+    int rMin = r;  // tracks lowest possible number fulfilling the range requirement
+    int rMax = p.size(); // tracks highest possible number fulfilling the range requirement
+
+    boolean isDistanceGreater = true;
+    while (true) {
+      if (rMin == rMax) {
+        return rMin;
+      }
+      isDistanceGreater =
+          isDistanceGreater(isOrderDesc ? sortKey : rowVal, isOrderDesc ? rowVal : sortKey,
amt);
+      if (!isDistanceGreater && r == p.size() - 1) {

Review comment:
       Just wondering -- p.size() is out of bounds right?

##########
File path: ql/src/java/org/apache/hadoop/hive/ql/udf/ptf/ValueBoundaryScanner.java
##########
@@ -664,6 +632,87 @@ public Object computeValue(Object row) throws HiveException {
    */
   public abstract boolean isEqual(Object v1, Object v2);
 
+  protected int binarySearchBack(int r, PTFPartition p, Object sortKey, int amt,
+      Order order) throws HiveException {
+    boolean isOrderDesc = order.equals(Order.DESC);
+    Object rowVal = sortKey;
+
+    int rMin = -1;  // tracks lowest possible number fulfilling the range requirement
+    int rMax = r; // tracks highest possible number fulfilling the range requirement
+
+    boolean isDistanceGreater = true;
+    while (true) {
+      if (rMin == rMax) {
+        return rMin;
+      }
+      isDistanceGreater =
+          isDistanceGreater(isOrderDesc ? rowVal : sortKey, isOrderDesc ? sortKey : rowVal,
amt);
+      if (!isDistanceGreater && r == 0) {
+        return 0;
+      }
+      if (isDistanceGreater) {
+        rMin = r + 1;
+      } else {
+        rMax = r;
+      }
+      r = rMin + (rMax - rMin) / 2;

Review comment:
       lets rename r to mid -- since its BS 




-- 
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: gitbox-unsubscribe@hive.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Issue Time Tracking
-------------------

    Worklog Id:     (was: 631565)
    Time Spent: 1h 40m  (was: 1.5h)

> PTF: Improve ValueBoundaryScanner
> ---------------------------------
>
>                 Key: HIVE-25061
>                 URL: https://issues.apache.org/jira/browse/HIVE-25061
>             Project: Hive
>          Issue Type: Improvement
>            Reporter: László Bodor
>            Assignee: László Bodor
>            Priority: Major
>              Labels: pull-request-available
>             Fix For: 4.0.0
>
>         Attachments: Screen Shot 2021-04-27 at 1.02.37 PM.png
>
>          Time Spent: 1h 40m
>  Remaining Estimate: 0h
>
> -First, I need to check whether TreeMap is really needed for our case.-
> It turned out a binary-ish search approach could help in range calculation, as we're
searching in an ordered set of values.



--
This message was sent by Atlassian Jira
(v8.3.4#803005)

Mime
View raw message