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-23880) Bloom filters can be merged in a parallel way in VectorUDAFBloomFilterMerge
Date Wed, 12 Aug 2020 08:45:00 GMT

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

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

                Author: ASF GitHub Bot
            Created on: 12/Aug/20 08:44
            Start Date: 12/Aug/20 08:44
    Worklog Time Spent: 10m 
      Work Description: abstractdog commented on a change in pull request #1280:
URL: https://github.com/apache/hive/pull/1280#discussion_r469102366



##########
File path: ql/src/java/org/apache/hadoop/hive/ql/exec/vector/expressions/aggregates/VectorUDAFBloomFilterMerge.java
##########
@@ -77,6 +75,211 @@ public void reset() {
       // Do not change the initial bytes which contain NumHashFunctions/NumBits!
       Arrays.fill(bfBytes, BloomKFilter.START_OF_SERIALIZED_LONGS, bfBytes.length, (byte)
0);
     }
+
+    public boolean mergeBloomFilterBytesFromInputColumn(BytesColumnVector inputColumn,
+        int batchSize, boolean selectedInUse, int[] selected, Configuration conf) {
+      // already set in previous iterations, no need to call initExecutor again
+      if (numThreads == 0) {
+        return false;
+      }
+      if (executor == null) {
+        initExecutor(conf, batchSize);
+        if (!isParallel) {
+          return false;
+        }
+      }
+
+      // split every bloom filter (represented by a part of a byte[]) across workers
+      for (int j = 0; j < batchSize; j++) {
+        if (!selectedInUse && inputColumn.noNulls) {
+          splitVectorAcrossWorkers(workers, inputColumn.vector[j], inputColumn.start[j],
+              inputColumn.length[j]);
+        } else if (!selectedInUse) {
+          if (!inputColumn.isNull[j]) {
+            splitVectorAcrossWorkers(workers, inputColumn.vector[j], inputColumn.start[j],
+                inputColumn.length[j]);
+          }
+        } else if (inputColumn.noNulls) {
+          int i = selected[j];
+          splitVectorAcrossWorkers(workers, inputColumn.vector[i], inputColumn.start[i],
+              inputColumn.length[i]);
+        } else {
+          int i = selected[j];
+          if (!inputColumn.isNull[i]) {
+            splitVectorAcrossWorkers(workers, inputColumn.vector[i], inputColumn.start[i],
+                inputColumn.length[i]);
+          }
+        }
+      }
+
+      return true;
+    }
+
+    private void initExecutor(Configuration conf, int batchSize) {
+      numThreads = conf.getInt(HiveConf.ConfVars.TEZ_BLOOM_FILTER_MERGE_THREADS.varname,
+          HiveConf.ConfVars.TEZ_BLOOM_FILTER_MERGE_THREADS.defaultIntVal);
+      LOG.info("Number of threads used for bloom filter merge: {}", numThreads);
+
+      if (numThreads < 0) {
+        throw new RuntimeException(
+            "invalid number of threads for bloom filter merge: " + numThreads);
+      }
+      if (numThreads == 0) { // disable parallel feature
+        return; // this will leave isParallel=false
+      }
+      isParallel = true;
+      executor = Executors.newFixedThreadPool(numThreads);
+
+      workers = new BloomFilterMergeWorker[numThreads];
+      for (int f = 0; f < numThreads; f++) {
+        workers[f] = new BloomFilterMergeWorker(bfBytes, 0, bfBytes.length);
+      }
+
+      for (int f = 0; f < numThreads; f++) {
+        executor.submit(workers[f]);
+      }
+    }
+
+    public int getNumberOfWaitingMergeTasks(){
+      int size = 0;
+      for (BloomFilterMergeWorker w : workers){
+        size += w.queue.size();
+      }
+      return size;
+    }
+
+    public int getNumberOfMergingWorkers() {

Review comment:
       yeah, only for logging, it was for validating my executor shutdown correctness...that
can be misleading, I'm removing it 




----------------------------------------------------------------
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.

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


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

    Worklog Id:     (was: 469596)
    Time Spent: 4h  (was: 3h 50m)

> Bloom filters can be merged in a parallel way in VectorUDAFBloomFilterMerge
> ---------------------------------------------------------------------------
>
>                 Key: HIVE-23880
>                 URL: https://issues.apache.org/jira/browse/HIVE-23880
>             Project: Hive
>          Issue Type: Improvement
>            Reporter: László Bodor
>            Assignee: László Bodor
>            Priority: Major
>              Labels: pull-request-available
>         Attachments: lipwig-output3605036885489193068.svg
>
>          Time Spent: 4h
>  Remaining Estimate: 0h
>
> Merging bloom filters in semijoin reduction can become the main bottleneck in case of
large number of source mapper tasks (~1000, Map 1 in below example) and a large amount of
expected entries (50M) in bloom filters.
> For example in TPCDS Q93:
> {code}
> select /*+ semi(store_returns, sr_item_sk, store_sales, 70000000)*/ ss_customer_sk
>             ,sum(act_sales) sumsales
>       from (select ss_item_sk
>                   ,ss_ticket_number
>                   ,ss_customer_sk
>                   ,case when sr_return_quantity is not null then (ss_quantity-sr_return_quantity)*ss_sales_price
>                                                             else (ss_quantity*ss_sales_price)
end act_sales
>             from store_sales left outer join store_returns on (sr_item_sk = ss_item_sk
>                                                                and sr_ticket_number =
ss_ticket_number)
>                 ,reason
>             where sr_reason_sk = r_reason_sk
>               and r_reason_desc = 'reason 66') t
>       group by ss_customer_sk
>       order by sumsales, ss_customer_sk
> limit 100;
> {code}
> On 10TB-30TB scale there is a chance that from 3-4 mins of query runtime 1-2 mins are
spent with merging bloom filters (Reducer 2), as in:  [^lipwig-output3605036885489193068.svg]

> {code}
> ----------------------------------------------------------------------------------------------
>         VERTICES      MODE        STATUS  TOTAL  COMPLETED  RUNNING  PENDING  FAILED
 KILLED
> ----------------------------------------------------------------------------------------------
> Map 3 ..........      llap     SUCCEEDED      1          1        0        0       0
      0
> Map 1 ..........      llap     SUCCEEDED   1263       1263        0        0       0
      0
> Reducer 2             llap       RUNNING      1          0        1        0       0
      0
> Map 4                 llap       RUNNING   6154          0      207     5947       0
      0
> Reducer 5             llap        INITED     43          0        0       43       0
      0
> Reducer 6             llap        INITED      1          0        0        1       0
      0
> ----------------------------------------------------------------------------------------------
> VERTICES: 02/06  [====>>----------------------] 16%   ELAPSED TIME: 149.98 s
> ----------------------------------------------------------------------------------------------
> {code}
> For example, 70M entries in bloom filter leads to a 436 465 696 bits, so merging 1263
bloom filters means running ~ 1263 * 436 465 696 bitwise OR operation, which is very hot codepath,
but can be parallelized.



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

Mime
View raw message