You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by "Akshat-Jain (via GitHub)" <gi...@apache.org> on 2024/07/30 19:59:51 UTC

[PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Akshat-Jain opened a new pull request, #16823:
URL: https://github.com/apache/druid/pull/16823

   ### Description
   
   This PR simplifies `WindowOperatorQueryFrameProcessor` to run all operators on all the rows instead of creating smaller RACs per `partition by` key.
   
   Currently, we are creating individual RACs per `partition by` key, and running all the operators on the individual RACs, which is inefficient. We are anyway running all the operators on the entire set of rows when empty over clause is present, so it made sense to just switch to that approach entirely.
   
   As part of this change, a lot of unnecessary fields and logic has been removed from the related classes.
   
   <hr>
   
   ##### Key changed/added classes in this PR
    * `WindowOperatorQueryFrameProcessor`
    * `WindowOperatorQueryFrameProcessorFactory`
    * `WindowOperatorQueryKit`
   
   <hr>
   
   This PR has:
   
   - [x] been self-reviewed.
   - [ ] added documentation for new or modified features or behaviors.
   - [ ] a release note entry in the PR description.
   - [ ] added Javadocs for most classes and all non-trivial methods. Linked related entities via Javadoc links.
   - [ ] added or updated version, license, or notice information in [licenses.yaml](https://github.com/apache/druid/blob/master/dev/license.md)
   - [x] added comments explaining the "why" and the intent of the code wherever would not be obvious for an unfamiliar reader.
   - [ ] added unit tests or modified existing tests to cover new code paths, ensuring the threshold for [code coverage](https://github.com/apache/druid/blob/master/dev/code-review/code-coverage.md) is met.
   - [ ] added integration tests.
   - [ ] been tested in a test Druid cluster.
   


-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1730022708


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -533,4 +464,65 @@ private boolean comparePartitionKeys(ResultRow row1, ResultRow row2, List<String
     }
     return match == partitionColumnNames.size();
   }
+
+  private void makeRowSupplierFromFrameCursor()
+  {
+    final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
+    final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
+    for (int i = 0; i < fieldSuppliers.length; i++) {
+      final ColumnValueSelector<?> selector =
+          frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
+      fieldSuppliers[i] = selector::getObject;
+    }
+    rowSupplierFromFrameCursor = () -> {
+      final ResultRow row = ResultRow.create(fieldSuppliers.length);
+      for (int i = 0; i < fieldSuppliers.length; i++) {
+        row.set(i, fieldSuppliers[i].get());
+      }
+      return row;
+    };
+  }
+
+  /**
+   * This method is responsible for the logic of batching the PARTITION BY keys.
+   * If we can add the current rows (currentBatchOfRacs) to the rows pending processing (batchOfRacsPendingProcessing) without violating the maxRowsMaterialized constraint, do it.
+   * If we cannot, we process the rows pending processing (batchOfRacsPendingProcessing), and add the current rows to it which would then be processed in future.
+   */
+  private void processBatchOfRacsPendingProcessingIfNeeded()
+  {
+    if (currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized) {
+      processBatchOfRacsPendingProcessing();
+    }
+
+    batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);

Review Comment:
   On further thoughts, we can change the approach to use a single Arraylist, and maintain the last PARTITION BY boundary index, and add a new method `MapOfColumnsRowsAndColumns.fromResultRowTillIndex()` so that we don't have to separately create the sublist to pass to `MapOfColumnsRowsAndColumns.fromResultRow()`.
   
   I ended up making the changes locally for this, the diff looks like the following:
   
   ```diff
   diff --git a/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java b/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java
   index 9945274bc5..c89a732c01 100644
   --- a/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java
   +++ b/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java
   @@ -94,13 +94,8 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
      // Type strategies are pushed in the same order as column types in frameReader.signature()
      private final NullableTypeStrategy[] typeStrategies;
    
   -  // currentBatchOfRacs holds the current rows being read from the frame.
   -  private final ArrayList<ResultRow> currentBatchOfRacs;
   -
   -  // batchOfRacsPendingProcessing holds the rows read from the frame that are pending processing.
   -  // These get processed when we either reach the end of input channel, or when we meet the criteria in shouldProcessPendingBatch() method.
   -  // Until then, this accumulates rows from currentBatchOfRacs.
   -  private final ArrayList<ResultRow> batchOfRacsPendingProcessing;
   +  private final ArrayList<ResultRow> rowsToProcess;
   +  private int lastPartitionIndex = -1;
    
      public WindowOperatorQueryFrameProcessor(
          WindowOperatorQuery query,
   @@ -123,8 +118,7 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
        this.query = query;
        this.frameRowsAndCols = new ArrayList<>();
        this.resultRowAndCols = new ArrayList<>();
   -    this.currentBatchOfRacs = new ArrayList<>();
   -    this.batchOfRacsPendingProcessing = new ArrayList<>();
   +    this.rowsToProcess = new ArrayList<>();
        this.maxRowsMaterialized = maxRowsMaterializedInWindow;
        this.partitionColumnNames = partitionColumnNames;
    
   @@ -244,8 +237,8 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
            makeRowSupplierFromFrameCursor();
          } else if (inputChannel.isFinished()) {
            // Handle any remaining data.
   -        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
   -        processBatchOfRacsPendingProcessing();
   +        lastPartitionIndex = rowsToProcess.size() - 1;
   +        processRowsUpToLastPartition();
            return ReturnOrAwait.returnObject(Unit.instance());
          } else {
            return ReturnOrAwait.runAgain();
   @@ -256,20 +249,17 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
          final ResultRow currentRow = rowSupplierFromFrameCursor.get();
          if (outputRow == null) {
            outputRow = currentRow;
   -        currentBatchOfRacs.add(currentRow);
   +        rowsToProcess.add(currentRow);
          } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
            // Add current row to the same batch of rows for processing.
   -        currentBatchOfRacs.add(currentRow);
   -        ensureMaxRowsInAWindowConstraint(currentBatchOfRacs.size());
   -        if (shouldProcessPendingBatch()) {
   +        rowsToProcess.add(currentRow);
   +        if (rowsToProcess.size() > maxRowsMaterialized) {
              // We don't want to materialize more than maxRowsMaterialized rows at any point in time, so process the pending batch.
   -          processBatchOfRacsPendingProcessing();
   +          processRowsUpToLastPartition();
            }
   +        ensureMaxRowsInAWindowConstraint(rowsToProcess.size());
          } else {
   -        if (shouldProcessPendingBatch()) {
   -          processBatchOfRacsPendingProcessing();
   -        }
   -        copyAndClearCurrentBatch();
   +        lastPartitionIndex = rowsToProcess.size() - 1;
            outputRow = currentRow.copy();
            return ReturnOrAwait.runAgain();
          }
   @@ -486,35 +476,6 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
        };
      }
    
   -  /**
   -   * Process {@link #batchOfRacsPendingProcessing}.
   -   */
   -  private void processBatchOfRacsPendingProcessing()
   -  {
   -    if (batchOfRacsPendingProcessing.isEmpty()) {
   -      return;
   -    }
   -    RowsAndColumns singleRac = MapOfColumnsRowsAndColumns.fromResultRow(
   -        batchOfRacsPendingProcessing,
   -        frameReader.signature()
   -    );
   -    ArrayList<RowsAndColumns> rowsAndColumns = new ArrayList<>();
   -    rowsAndColumns.add(singleRac);
   -    runAllOpsOnMultipleRac(rowsAndColumns);
   -    batchOfRacsPendingProcessing.clear();
   -  }
   -
   -  private boolean shouldProcessPendingBatch()
   -  {
   -    return currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized;
   -  }
   -
   -  private void copyAndClearCurrentBatch()
   -  {
   -    batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
   -    currentBatchOfRacs.clear();
   -  }
   -
      private void ensureMaxRowsInAWindowConstraint(int numRowsInWindow)
      {
        if (numRowsInWindow > maxRowsMaterialized) {
   @@ -524,4 +485,23 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
          ));
        }
      }
   +
   +  private void processRowsUpToLastPartition()
   +  {
   +    if (lastPartitionIndex == -1) {
   +      return;
   +    }
   +
   +    RowsAndColumns singleRac = MapOfColumnsRowsAndColumns.fromResultRowTillIndex(
   +        rowsToProcess,
   +        frameReader.signature(),
   +        lastPartitionIndex
   +    );
   +    ArrayList<RowsAndColumns> rowsAndColumns = new ArrayList<>();
   +    rowsAndColumns.add(singleRac);
   +    runAllOpsOnMultipleRac(rowsAndColumns);
   +
   +    rowsToProcess.subList(0, lastPartitionIndex + 1).clear();
   +    lastPartitionIndex = -1;
   +  }
    }
   diff --git a/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java b/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java
   index 42972f9340..29f092f674 100644
   --- a/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java
   +++ b/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java
   @@ -84,11 +84,16 @@ public class MapOfColumnsRowsAndColumns implements RowsAndColumns
      }
    
      public static MapOfColumnsRowsAndColumns fromResultRow(ArrayList<ResultRow> objs, RowSignature signature)
   +  {
   +    return fromResultRowTillIndex(objs, signature, objs.size() - 1);
   +  }
   +
   +  public static MapOfColumnsRowsAndColumns fromResultRowTillIndex(ArrayList<ResultRow> objs, RowSignature signature, int index)
      {
        final Builder bob = builder();
        if (!objs.isEmpty()) {
   -      Object[][] columnOriented = new Object[objs.get(0).length()][objs.size()];
   -      for (int i = 0; i < objs.size(); ++i) {
   +      Object[][] columnOriented = new Object[objs.get(0).length()][index + 1];
   +      for (int i = 0; i <= index; ++i) {
            for (int j = 0; j < objs.get(i).length(); ++j) {
              columnOriented[j][i] = objs.get(i).get(j);
            }
   
   ```
   
   All tests pass with the above diff. Let me know if this approach seems better to you compared to the current changes of the PR, I just need to update some comments before pushing this to the PR.



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1711007159


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -56,8 +58,10 @@
 public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
 {
   private static final Logger log = new Logger(WindowOperatorQueryFrameProcessor.class);
+  private final WindowOperatorQuery query;
 
   private final List<OperatorFactory> operatorFactoryList;
+  private final ObjectMapper jsonMapper;

Review Comment:
   I added them back because of https://github.com/apache/druid/pull/16854, to avoid unnecessary merge conflicts. I would have to add them back in the other PR otherwise. 



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "kgyrtkirk (via GitHub)" <gi...@apache.org>.
kgyrtkirk commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1705541775


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -137,205 +103,44 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
+     * We add all the RACs to a single ConcatRowsAndColumns and pass it to the list of operators to process.
      *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
      */
 
-    if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
-      if (inputChannel.canRead()) {
-        final Frame frame = inputChannel.read();
-        convertRowFrameToRowsAndColumns(frame);
-      } else if (inputChannel.isFinished()) {
-        runAllOpsOnMultipleRac(frameRowsAndCols);
-        return ReturnOrAwait.returnObject(Unit.instance());
-      } else {
-        return ReturnOrAwait.awaitAll(inputChannels().size());
-      }
-      return ReturnOrAwait.runAgain();
+    // Bring all data to a single executor for processing.

Review Comment:
   I believe the current approach will enforce that at most a window with `MAX_ROWS_MATERIALIZED_IN_WINDOW` can be processed (on a single worker). I believe later we will enhance this to be able to stream these things - which will naturally relax these checks a bit.
   
   I believe we are doing everything for the execution engine by specifying the columns it may spread the data - if the partition number or something should be increased there; I believe that shouldn't be visible around here as other pieces may benefit from such a logic.
   
   I think if we want to improve on that - we could possibly do that in a separate followup.



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "kgyrtkirk (via GitHub)" <gi...@apache.org>.
kgyrtkirk commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1726514628


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***
+
+     In this scenario, we need to process rows for each PARTITION BY group together, but we can batch multiple PARTITION BY keys into the same RAC before passing it to the operators for processing.
+     Batching is fine since the operators list would have the required NaivePartitioningOperatorFactory to segregate each PARTITION BY group during the processing.
+
+     The flow for this scenario can be summarised as following:
+     1. Frame Reading and Cursor Initialization: We start by reading a frame from the inputChannel and initializing frameCursor to iterate over the rows in that frame.
+     2. Row Comparison: For each row in the frame, we decide whether it belongs to the same PARTITION BY group as the previous row.
+                        This is determined by comparePartitionKeys() method.
+                        Please refer to the Javadoc of that method for further details and an example illustration.
+        2.1. If the PARTITION BY columns of current row matches the PARTITION BY columns of the previous row,
+             they belong to the same PARTITION BY group, and gets added to currentBatchOfRacs.
+             If the number of total rows materialized exceed maxRowsMaterialized, we process the pending batch via processBatchOfRacsPendingProcessing() method.
+        2.2. If they don't match, then we have reached a partition boundary.
+             In this case, we process the rows so far *if needed* via processBatchOfRacsPendingProcessingIfNeeded() method.
+             Please refer to the Javadoc of that method for further details.
+     3. End of Input: If the input channel is finished, any remaining rows in currentBatchOfRacs are processed.
+
+     *Illustration of Row Comparison step*
+
+     Let's say we have window_function() OVER (PARTITION BY A ORDER BY B) in our query, and we get 3 frames in the input channel to process.
+
+     Frame 1
+     A, B
+     1, 2
+     1, 3
+     2, 1 --> PARTITION BY key (column A) changed from 1 to 2.
+     2, 2
+
+     Frame 2
+     A, B
+     3, 1 --> PARTITION BY key (column A) changed from 2 to 3.
+     3, 2
+     3, 3
+     3, 4
+
+     Frame 3
+     A, B
+     3, 5
+     3, 6
+     4, 1 --> PARTITION BY key (column A) changed from 3 to 4.
+     4, 2
+
+     *Why batching?*
+     We batch multiple PARTITION BY keys for processing together to avoid the overhead of creating different RACs for each PARTITION BY keys, as that would be unnecessary in scenarios where we have a large number of PARTITION BY keys, but each key having a single row.
+
+     *Future thoughts: https://github.com/apache/druid/issues/16126*
+     Current approach with R&C and operators materialize a single R&C for processing. In case of data with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause.
+     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data. We might think to reimplement them in the MSQ way so that we do not have to materialize so much data.
      */
 
     if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
+      // Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY.
       if (inputChannel.canRead()) {
         final Frame frame = inputChannel.read();
         convertRowFrameToRowsAndColumns(frame);
+        return ReturnOrAwait.runAgain();
       } else if (inputChannel.isFinished()) {
         runAllOpsOnMultipleRac(frameRowsAndCols);
         return ReturnOrAwait.returnObject(Unit.instance());
       } else {
         return ReturnOrAwait.awaitAll(inputChannels().size());
       }
-      return ReturnOrAwait.runAgain();
-    } else {
-      // Aha, you found a PARTITION BY and maybe ORDER BY TO
-      // PARTITION BY can also be on multiple keys
-      // typically the last stage would already partition and sort for you
-      // figure out frame boundaries and convert each distinct group to a rac
-      // then run the windowing operator only on each rac
-      if (frameCursor == null || frameCursor.isDone()) {
-        if (readableInputs.isEmpty()) {
-          return ReturnOrAwait.awaitAll(1);
-        } else if (inputChannel.canRead()) {
-          final Frame frame = inputChannel.read();
-          frameCursor = FrameProcessors.makeCursor(frame, frameReader);
-          final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
-          final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
-          for (int i = 0; i < fieldSuppliers.length; i++) {
-            final ColumnValueSelector<?> selector =
-                frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
-            fieldSuppliers[i] = selector::getObject;
-
-          }
-          rowSupplierFromFrameCursor = () -> {
-            final ResultRow row = ResultRow.create(fieldSuppliers.length);
-            for (int i = 0; i < fieldSuppliers.length; i++) {
-              row.set(i, fieldSuppliers[i].get());
-            }
-            return row;
-          };
-        } else if (inputChannel.isFinished()) {
-          // reaached end of channel
-          // if there is data remaining
-          // write it into a rac
-          // and run operators on it
-          if (!objectsOfASingleRac.isEmpty()) {
-            if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-              throw new MSQException(new TooManyRowsInAWindowFault(objectsOfASingleRac.size(), maxRowsMaterialized));
-            }
-            RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-                objectsOfASingleRac,
-                frameReader.signature()
-            );
-            runAllOpsOnSingleRac(rac);
-            objectsOfASingleRac.clear();
-          }
-          return ReturnOrAwait.returnObject(Unit.instance());
-        } else {
-          return ReturnOrAwait.runAgain();
-        }
-      }
-      while (!frameCursor.isDone()) {
-        final ResultRow currentRow = rowSupplierFromFrameCursor.get();
-        if (outputRow == null) {
-          outputRow = currentRow;
-          objectsOfASingleRac.add(currentRow);
-        } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
-          // if they have the same partition key
-          // keep adding them after checking
-          // guardrails
-          objectsOfASingleRac.add(currentRow);
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-        } else {
-          // key change noted
-          // create rac from the rows seen before
-          // run the operators on these rows and columns
-          // clean up the object to hold the new rows only
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-          RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-              objectsOfASingleRac,
-              frameReader.signature()
-          );
-          runAllOpsOnSingleRac(rac);
-          objectsOfASingleRac.clear();
-          outputRow = currentRow.copy();
-          return ReturnOrAwait.runAgain();
-        }
-        frameCursor.advance();
+    }
+
+    // Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY
+    if (frameCursor == null || frameCursor.isDone()) {
+      if (readableInputs.isEmpty()) {
+        return ReturnOrAwait.awaitAll(1);
+      } else if (inputChannel.canRead()) {
+        final Frame frame = inputChannel.read();
+        frameCursor = FrameProcessors.makeCursor(frame, frameReader);
+        makeRowSupplierFromFrameCursor();
+      } else if (inputChannel.isFinished()) {
+        // Handle any remaining data.
+        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
+        processBatchOfRacsPendingProcessing();
+        return ReturnOrAwait.returnObject(Unit.instance());
+      } else {
+        return ReturnOrAwait.runAgain();
       }
     }
-    return ReturnOrAwait.runAgain();
-  }
 
-  /**
-   * @param singleRac Use this {@link RowsAndColumns} as a single input for the operators to be run
-   */
-  private void runAllOpsOnSingleRac(RowsAndColumns singleRac)
-  {
-    Operator op = new Operator()
-    {
-      @Nullable
-      @Override
-      public Closeable goOrContinue(Closeable continuationObject, Receiver receiver)
-      {
-        receiver.push(singleRac);
-        if (singleRac.numRows() > maxRowsMaterialized) {
-          throw new MSQException(new TooManyRowsInAWindowFault(singleRac.numRows(), maxRowsMaterialized));
+    while (!frameCursor.isDone()) {
+      final ResultRow currentRow = rowSupplierFromFrameCursor.get();
+      if (outputRow == null) {
+        outputRow = currentRow;
+        currentBatchOfRacs.add(currentRow);
+      } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {

Review Comment:
   we don't necessarily (and preffereably) need to have the partitioning exposed here.
   Doing `comparePartitionKeys` here for each row will not perform really well
   Instead of a `comparePartitionKeys` the comparision/paritioning should happen inside the operators.
   
   I think the previous approach was better (put everything into a single rac);
   As later we could limit the input racs to some size and write a `GlueingPartitioningOperator` - which could make sure that the outputs are rows belonging to the same partition ; meanwhile making sure that if there is an in-partition cut it will be able to handle that too.
   
   



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "cryptoe (via GitHub)" <gi...@apache.org>.
cryptoe commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1729792008


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***
+
+     In this scenario, we need to process rows for each PARTITION BY group together, but we can batch multiple PARTITION BY keys into the same RAC before passing it to the operators for processing.
+     Batching is fine since the operators list would have the required NaivePartitioningOperatorFactory to segregate each PARTITION BY group during the processing.
+
+     The flow for this scenario can be summarised as following:
+     1. Frame Reading and Cursor Initialization: We start by reading a frame from the inputChannel and initializing frameCursor to iterate over the rows in that frame.
+     2. Row Comparison: For each row in the frame, we decide whether it belongs to the same PARTITION BY group as the previous row.
+                        This is determined by comparePartitionKeys() method.
+                        Please refer to the Javadoc of that method for further details and an example illustration.
+        2.1. If the PARTITION BY columns of current row matches the PARTITION BY columns of the previous row,
+             they belong to the same PARTITION BY group, and gets added to currentBatchOfRacs.
+             If the number of total rows materialized exceed maxRowsMaterialized, we process the pending batch via processBatchOfRacsPendingProcessing() method.
+        2.2. If they don't match, then we have reached a partition boundary.
+             In this case, we process the rows so far *if needed* via processBatchOfRacsPendingProcessingIfNeeded() method.
+             Please refer to the Javadoc of that method for further details.
+     3. End of Input: If the input channel is finished, any remaining rows in currentBatchOfRacs are processed.
+
+     *Illustration of Row Comparison step*
+
+     Let's say we have window_function() OVER (PARTITION BY A ORDER BY B) in our query, and we get 3 frames in the input channel to process.
+
+     Frame 1
+     A, B
+     1, 2
+     1, 3
+     2, 1 --> PARTITION BY key (column A) changed from 1 to 2.
+     2, 2
+
+     Frame 2
+     A, B
+     3, 1 --> PARTITION BY key (column A) changed from 2 to 3.
+     3, 2
+     3, 3
+     3, 4
+
+     Frame 3
+     A, B
+     3, 5
+     3, 6
+     4, 1 --> PARTITION BY key (column A) changed from 3 to 4.
+     4, 2
+
+     *Why batching?*
+     We batch multiple PARTITION BY keys for processing together to avoid the overhead of creating different RACs for each PARTITION BY keys, as that would be unnecessary in scenarios where we have a large number of PARTITION BY keys, but each key having a single row.
+
+     *Future thoughts: https://github.com/apache/druid/issues/16126*
+     Current approach with R&C and operators materialize a single R&C for processing. In case of data with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause.
+     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data. We might think to reimplement them in the MSQ way so that we do not have to materialize so much data.
      */
 
     if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
+      // Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY.
       if (inputChannel.canRead()) {
         final Frame frame = inputChannel.read();
         convertRowFrameToRowsAndColumns(frame);
+        return ReturnOrAwait.runAgain();
       } else if (inputChannel.isFinished()) {
         runAllOpsOnMultipleRac(frameRowsAndCols);
         return ReturnOrAwait.returnObject(Unit.instance());
       } else {
         return ReturnOrAwait.awaitAll(inputChannels().size());
       }
-      return ReturnOrAwait.runAgain();
-    } else {
-      // Aha, you found a PARTITION BY and maybe ORDER BY TO
-      // PARTITION BY can also be on multiple keys
-      // typically the last stage would already partition and sort for you
-      // figure out frame boundaries and convert each distinct group to a rac
-      // then run the windowing operator only on each rac
-      if (frameCursor == null || frameCursor.isDone()) {
-        if (readableInputs.isEmpty()) {
-          return ReturnOrAwait.awaitAll(1);
-        } else if (inputChannel.canRead()) {
-          final Frame frame = inputChannel.read();
-          frameCursor = FrameProcessors.makeCursor(frame, frameReader);
-          final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
-          final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
-          for (int i = 0; i < fieldSuppliers.length; i++) {
-            final ColumnValueSelector<?> selector =
-                frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
-            fieldSuppliers[i] = selector::getObject;
-
-          }
-          rowSupplierFromFrameCursor = () -> {
-            final ResultRow row = ResultRow.create(fieldSuppliers.length);
-            for (int i = 0; i < fieldSuppliers.length; i++) {
-              row.set(i, fieldSuppliers[i].get());
-            }
-            return row;
-          };
-        } else if (inputChannel.isFinished()) {
-          // reaached end of channel
-          // if there is data remaining
-          // write it into a rac
-          // and run operators on it
-          if (!objectsOfASingleRac.isEmpty()) {
-            if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-              throw new MSQException(new TooManyRowsInAWindowFault(objectsOfASingleRac.size(), maxRowsMaterialized));
-            }
-            RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-                objectsOfASingleRac,
-                frameReader.signature()
-            );
-            runAllOpsOnSingleRac(rac);
-            objectsOfASingleRac.clear();
-          }
-          return ReturnOrAwait.returnObject(Unit.instance());
-        } else {
-          return ReturnOrAwait.runAgain();
-        }
-      }
-      while (!frameCursor.isDone()) {
-        final ResultRow currentRow = rowSupplierFromFrameCursor.get();
-        if (outputRow == null) {
-          outputRow = currentRow;
-          objectsOfASingleRac.add(currentRow);
-        } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
-          // if they have the same partition key
-          // keep adding them after checking
-          // guardrails
-          objectsOfASingleRac.add(currentRow);
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-        } else {
-          // key change noted
-          // create rac from the rows seen before
-          // run the operators on these rows and columns
-          // clean up the object to hold the new rows only
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-          RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-              objectsOfASingleRac,
-              frameReader.signature()
-          );
-          runAllOpsOnSingleRac(rac);
-          objectsOfASingleRac.clear();
-          outputRow = currentRow.copy();
-          return ReturnOrAwait.runAgain();
-        }
-        frameCursor.advance();
+    }
+
+    // Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY
+    if (frameCursor == null || frameCursor.isDone()) {
+      if (readableInputs.isEmpty()) {
+        return ReturnOrAwait.awaitAll(1);
+      } else if (inputChannel.canRead()) {
+        final Frame frame = inputChannel.read();
+        frameCursor = FrameProcessors.makeCursor(frame, frameReader);
+        makeRowSupplierFromFrameCursor();
+      } else if (inputChannel.isFinished()) {
+        // Handle any remaining data.
+        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
+        processBatchOfRacsPendingProcessing();
+        return ReturnOrAwait.returnObject(Unit.instance());
+      } else {
+        return ReturnOrAwait.runAgain();
       }
     }
-    return ReturnOrAwait.runAgain();
-  }
 
-  /**
-   * @param singleRac Use this {@link RowsAndColumns} as a single input for the operators to be run
-   */
-  private void runAllOpsOnSingleRac(RowsAndColumns singleRac)
-  {
-    Operator op = new Operator()
-    {
-      @Nullable
-      @Override
-      public Closeable goOrContinue(Closeable continuationObject, Receiver receiver)
-      {
-        receiver.push(singleRac);
-        if (singleRac.numRows() > maxRowsMaterialized) {
-          throw new MSQException(new TooManyRowsInAWindowFault(singleRac.numRows(), maxRowsMaterialized));
+    while (!frameCursor.isDone()) {
+      final ResultRow currentRow = rowSupplierFromFrameCursor.get();
+      if (outputRow == null) {
+        outputRow = currentRow;
+        currentBatchOfRacs.add(currentRow);
+      } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
+        // Add current row to the same batch of rows for processing.
+        currentBatchOfRacs.add(currentRow);
+        ensureMaxRowsInAWindowConstraint(currentBatchOfRacs.size());
+        if (currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized) {
+          // We don't want to materialize more than maxRowsMaterialized rows at any point in time, so process the pending batch.
+          processBatchOfRacsPendingProcessing();

Review Comment:
   ~The check on line 264 is repeated inside the method. I think it should be removed from line 264 no ?~
   I understand why you need the check in 264. so that multiple iterations donot clear of the current batch. 
   The code flow is a bit convoluted IMHO. 
   I suggest do the following: 
   Create a method call shouldProcess and move the check in line 264 there. 
   
   so the flow would look like 
   
   ```
    currentBatchOfRacs.add(currentRow);
    ensureMaxRowsInAWindowConstraint(currentBatchOfRacs.size());
    if(shouldProcess()){
     processBatchOfRacsPendingProcessing();
     copyAndClearCurrentBatch(); // is there an approach where we can avoid this. Swapping buffers maybe
     }
   }    
   ```
   
   
   On line 269:
   
   ```
   else{
   
   if(shouldProcess()){
   processBatchOfRacsPendingProcessing();
   }
   copyAndClearCurrentBatch();
   outputRow = currentRow.copy();
           return ReturnOrAwait.runAgain();
   ```
      



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1730754117


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -533,4 +464,65 @@ private boolean comparePartitionKeys(ResultRow row1, ResultRow row2, List<String
     }
     return match == partitionColumnNames.size();
   }
+
+  private void makeRowSupplierFromFrameCursor()
+  {
+    final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
+    final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
+    for (int i = 0; i < fieldSuppliers.length; i++) {
+      final ColumnValueSelector<?> selector =
+          frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
+      fieldSuppliers[i] = selector::getObject;
+    }
+    rowSupplierFromFrameCursor = () -> {
+      final ResultRow row = ResultRow.create(fieldSuppliers.length);
+      for (int i = 0; i < fieldSuppliers.length; i++) {
+        row.set(i, fieldSuppliers[i].get());
+      }
+      return row;
+    };
+  }
+
+  /**
+   * This method is responsible for the logic of batching the PARTITION BY keys.
+   * If we can add the current rows (currentBatchOfRacs) to the rows pending processing (batchOfRacsPendingProcessing) without violating the maxRowsMaterialized constraint, do it.
+   * If we cannot, we process the rows pending processing (batchOfRacsPendingProcessing), and add the current rows to it which would then be processed in future.
+   */
+  private void processBatchOfRacsPendingProcessingIfNeeded()
+  {
+    if (currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized) {
+      processBatchOfRacsPendingProcessing();
+    }
+
+    batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);

Review Comment:
   @cryptoe @LakshSingla As discussed offline, I've pushed the above approach to the PR. Please have a look, thanks!
   
   Also, I verified the behavior of `list.sublist(a,b).clear()`, it works as we expect it to (brings the later elements to the start, effectively resizes the list):
   <img width="2276" alt="image" src="https://github.com/user-attachments/assets/08d6783a-5da9-4e13-aaf3-3ee65f3f1b67">
   



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1729875334


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -533,4 +464,65 @@ private boolean comparePartitionKeys(ResultRow row1, ResultRow row2, List<String
     }
     return match == partitionColumnNames.size();
   }
+
+  private void makeRowSupplierFromFrameCursor()
+  {
+    final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
+    final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
+    for (int i = 0; i < fieldSuppliers.length; i++) {
+      final ColumnValueSelector<?> selector =
+          frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
+      fieldSuppliers[i] = selector::getObject;
+    }
+    rowSupplierFromFrameCursor = () -> {
+      final ResultRow row = ResultRow.create(fieldSuppliers.length);
+      for (int i = 0; i < fieldSuppliers.length; i++) {
+        row.set(i, fieldSuppliers[i].get());
+      }
+      return row;
+    };
+  }
+
+  /**
+   * This method is responsible for the logic of batching the PARTITION BY keys.
+   * If we can add the current rows (currentBatchOfRacs) to the rows pending processing (batchOfRacsPendingProcessing) without violating the maxRowsMaterialized constraint, do it.
+   * If we cannot, we process the rows pending processing (batchOfRacsPendingProcessing), and add the current rows to it which would then be processed in future.
+   */
+  private void processBatchOfRacsPendingProcessingIfNeeded()
+  {
+    if (currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized) {
+      processBatchOfRacsPendingProcessing();
+    }
+
+    batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);

Review Comment:
   I thought about this. Having an approach where we use a single ArrayList, and maintain the last PARTITION BY boundary index also has the same issue, as we would need to collect all rows until that index into a new ArrayList before sending it to the list of operators.
   
   > is there an approach where we can avoid this. Swapping buffers maybe
   
   Can you elaborate more on swapping buffers approach? We would still have to copy the contents of the buffer into a new ArrayList before sending it to the list of operators (hence degenerating into the `last PARTITION BY boundary index` alternative approach I described above, IIUC)
   
   Also, since we anyway have the next step to move to a GlueingPartitioningOperator approach, I feel we shouldn't invest too much time into designing and over-engineering this patch, and keep things simple for the time being. (as GlueingPartitioningOperator approach would get rid of this logic entirely from this layer, and would solve this concern) - Thoughts?



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1726386755


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***

Review Comment:
   Why is separate handling required for OVER() without a PARTITION BY? Afaict, batching should be sufficient for both scenarios. 



##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***
+
+     In this scenario, we need to process rows for each PARTITION BY group together, but we can batch multiple PARTITION BY keys into the same RAC before passing it to the operators for processing.
+     Batching is fine since the operators list would have the required NaivePartitioningOperatorFactory to segregate each PARTITION BY group during the processing.
+
+     The flow for this scenario can be summarised as following:
+     1. Frame Reading and Cursor Initialization: We start by reading a frame from the inputChannel and initializing frameCursor to iterate over the rows in that frame.
+     2. Row Comparison: For each row in the frame, we decide whether it belongs to the same PARTITION BY group as the previous row.
+                        This is determined by comparePartitionKeys() method.
+                        Please refer to the Javadoc of that method for further details and an example illustration.
+        2.1. If the PARTITION BY columns of current row matches the PARTITION BY columns of the previous row,
+             they belong to the same PARTITION BY group, and gets added to currentBatchOfRacs.
+             If the number of total rows materialized exceed maxRowsMaterialized, we process the pending batch via processBatchOfRacsPendingProcessing() method.
+        2.2. If they don't match, then we have reached a partition boundary.
+             In this case, we process the rows so far *if needed* via processBatchOfRacsPendingProcessingIfNeeded() method.
+             Please refer to the Javadoc of that method for further details.
+     3. End of Input: If the input channel is finished, any remaining rows in currentBatchOfRacs are processed.
+
+     *Illustration of Row Comparison step*
+
+     Let's say we have window_function() OVER (PARTITION BY A ORDER BY B) in our query, and we get 3 frames in the input channel to process.
+
+     Frame 1
+     A, B
+     1, 2
+     1, 3
+     2, 1 --> PARTITION BY key (column A) changed from 1 to 2.
+     2, 2
+
+     Frame 2
+     A, B
+     3, 1 --> PARTITION BY key (column A) changed from 2 to 3.
+     3, 2
+     3, 3
+     3, 4
+
+     Frame 3
+     A, B
+     3, 5
+     3, 6
+     4, 1 --> PARTITION BY key (column A) changed from 3 to 4.
+     4, 2
+
+     *Why batching?*
+     We batch multiple PARTITION BY keys for processing together to avoid the overhead of creating different RACs for each PARTITION BY keys, as that would be unnecessary in scenarios where we have a large number of PARTITION BY keys, but each key having a single row.
+
+     *Future thoughts: https://github.com/apache/druid/issues/16126*
+     Current approach with R&C and operators materialize a single R&C for processing. In case of data with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause.
+     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data. We might think to reimplement them in the MSQ way so that we do not have to materialize so much data.
      */
 
     if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
+      // Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY.
       if (inputChannel.canRead()) {
         final Frame frame = inputChannel.read();
         convertRowFrameToRowsAndColumns(frame);
+        return ReturnOrAwait.runAgain();
       } else if (inputChannel.isFinished()) {
         runAllOpsOnMultipleRac(frameRowsAndCols);
         return ReturnOrAwait.returnObject(Unit.instance());
       } else {
         return ReturnOrAwait.awaitAll(inputChannels().size());
       }
-      return ReturnOrAwait.runAgain();
-    } else {
-      // Aha, you found a PARTITION BY and maybe ORDER BY TO
-      // PARTITION BY can also be on multiple keys
-      // typically the last stage would already partition and sort for you
-      // figure out frame boundaries and convert each distinct group to a rac
-      // then run the windowing operator only on each rac
-      if (frameCursor == null || frameCursor.isDone()) {
-        if (readableInputs.isEmpty()) {
-          return ReturnOrAwait.awaitAll(1);
-        } else if (inputChannel.canRead()) {
-          final Frame frame = inputChannel.read();
-          frameCursor = FrameProcessors.makeCursor(frame, frameReader);
-          final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
-          final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
-          for (int i = 0; i < fieldSuppliers.length; i++) {
-            final ColumnValueSelector<?> selector =
-                frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
-            fieldSuppliers[i] = selector::getObject;
-
-          }
-          rowSupplierFromFrameCursor = () -> {
-            final ResultRow row = ResultRow.create(fieldSuppliers.length);
-            for (int i = 0; i < fieldSuppliers.length; i++) {
-              row.set(i, fieldSuppliers[i].get());
-            }
-            return row;
-          };
-        } else if (inputChannel.isFinished()) {
-          // reaached end of channel
-          // if there is data remaining
-          // write it into a rac
-          // and run operators on it
-          if (!objectsOfASingleRac.isEmpty()) {
-            if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-              throw new MSQException(new TooManyRowsInAWindowFault(objectsOfASingleRac.size(), maxRowsMaterialized));
-            }
-            RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-                objectsOfASingleRac,
-                frameReader.signature()
-            );
-            runAllOpsOnSingleRac(rac);
-            objectsOfASingleRac.clear();
-          }
-          return ReturnOrAwait.returnObject(Unit.instance());
-        } else {
-          return ReturnOrAwait.runAgain();
-        }
-      }
-      while (!frameCursor.isDone()) {
-        final ResultRow currentRow = rowSupplierFromFrameCursor.get();
-        if (outputRow == null) {
-          outputRow = currentRow;
-          objectsOfASingleRac.add(currentRow);
-        } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
-          // if they have the same partition key
-          // keep adding them after checking
-          // guardrails
-          objectsOfASingleRac.add(currentRow);
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-        } else {
-          // key change noted
-          // create rac from the rows seen before
-          // run the operators on these rows and columns
-          // clean up the object to hold the new rows only
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-          RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-              objectsOfASingleRac,
-              frameReader.signature()
-          );
-          runAllOpsOnSingleRac(rac);
-          objectsOfASingleRac.clear();
-          outputRow = currentRow.copy();
-          return ReturnOrAwait.runAgain();
-        }
-        frameCursor.advance();
+    }
+
+    // Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY
+    if (frameCursor == null || frameCursor.isDone()) {
+      if (readableInputs.isEmpty()) {
+        return ReturnOrAwait.awaitAll(1);
+      } else if (inputChannel.canRead()) {
+        final Frame frame = inputChannel.read();
+        frameCursor = FrameProcessors.makeCursor(frame, frameReader);
+        makeRowSupplierFromFrameCursor();
+      } else if (inputChannel.isFinished()) {
+        // Handle any remaining data.
+        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
+        processBatchOfRacsPendingProcessing();
+        return ReturnOrAwait.returnObject(Unit.instance());
+      } else {
+        return ReturnOrAwait.runAgain();
       }
     }
-    return ReturnOrAwait.runAgain();
-  }
 
-  /**
-   * @param singleRac Use this {@link RowsAndColumns} as a single input for the operators to be run
-   */
-  private void runAllOpsOnSingleRac(RowsAndColumns singleRac)
-  {
-    Operator op = new Operator()
-    {
-      @Nullable
-      @Override
-      public Closeable goOrContinue(Closeable continuationObject, Receiver receiver)
-      {
-        receiver.push(singleRac);
-        if (singleRac.numRows() > maxRowsMaterialized) {
-          throw new MSQException(new TooManyRowsInAWindowFault(singleRac.numRows(), maxRowsMaterialized));
+    while (!frameCursor.isDone()) {
+      final ResultRow currentRow = rowSupplierFromFrameCursor.get();
+      if (outputRow == null) {
+        outputRow = currentRow;
+        currentBatchOfRacs.add(currentRow);
+      } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {

Review Comment:
   What do you think about this flow:
   
   `maxRowsMaterialized` = 2
   
   Key: a, b, b, b
   
   | Stream element | batchOfRacsPendingProcessing | currentBatchOfRacs | Notes |
   |--------|--------|--------|--------|
   | a | - | a | - |
   | b | a | b | - |
   | b | b, b | - | Flush a, Move (b, b) to the pending processing RACs |
   | b | b, b | b | This passes `ensureMaxRowsInAWindowConstraint` because current batch has only one element, Flush the batchOfRacsPendingProcessing with 2 rows, move the currentBatchOfRacs to the pendingProcessing one |
   
   Would it get processed and flushed like this, or am I missing a check which ensures that this case doesn't happen?
   
   (a), (b, b), (b)
   
   



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "kgyrtkirk (via GitHub)" <gi...@apache.org>.
kgyrtkirk commented on PR #16823:
URL: https://github.com/apache/druid/pull/16823#issuecomment-2311823143

   sure; but I still feel like this was an unecessary side-step...as these will be just removed later
   either by using `GlobalSortTargetSizeShuffleSpec#targetSize` and/or an operator based approach
   
   note: a benchmark would be nice to help keep track how performant these queries are


-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "cryptoe (via GitHub)" <gi...@apache.org>.
cryptoe commented on PR #16823:
URL: https://github.com/apache/druid/pull/16823#issuecomment-2311648273

   @kgyrtkirk Should we go ahead and merge this and then raise a follow up PR for the glueing operator stuff. 


-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "cryptoe (via GitHub)" <gi...@apache.org>.
cryptoe commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1703579978


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -137,205 +103,44 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
+     * We add all the RACs to a single ConcatRowsAndColumns and pass it to the list of operators to process.
      *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
      */
 
-    if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
-      if (inputChannel.canRead()) {
-        final Frame frame = inputChannel.read();
-        convertRowFrameToRowsAndColumns(frame);
-      } else if (inputChannel.isFinished()) {
-        runAllOpsOnMultipleRac(frameRowsAndCols);
-        return ReturnOrAwait.returnObject(Unit.instance());
-      } else {
-        return ReturnOrAwait.awaitAll(inputChannels().size());
-      }
-      return ReturnOrAwait.runAgain();
+    // Bring all data to a single executor for processing.

Review Comment:
   Yes I meant increase number of partitions in the shuffle spec of the input stage, or set the number of rows per partition of the input stage to some X number which has less chance of going OOM. 



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "cryptoe (via GitHub)" <gi...@apache.org>.
cryptoe commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1701324231


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -137,205 +103,44 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
+     * We add all the RACs to a single ConcatRowsAndColumns and pass it to the list of operators to process.
      *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
      */
 
-    if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
-      if (inputChannel.canRead()) {
-        final Frame frame = inputChannel.read();
-        convertRowFrameToRowsAndColumns(frame);
-      } else if (inputChannel.isFinished()) {
-        runAllOpsOnMultipleRac(frameRowsAndCols);
-        return ReturnOrAwait.returnObject(Unit.instance());
-      } else {
-        return ReturnOrAwait.awaitAll(inputChannels().size());
-      }
-      return ReturnOrAwait.runAgain();
+    // Bring all data to a single executor for processing.

Review Comment:
   Probably a few things to check : 
   * Should we adjust the num rows per partition to some X number if window query is encountered. 
   * What are the guardrails if we go OOM. Can we fail gracefully instead of getting an annoying OOM error. 



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1703151384


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -137,205 +103,44 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
+     * We add all the RACs to a single ConcatRowsAndColumns and pass it to the list of operators to process.
      *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
      */
 
-    if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
-      if (inputChannel.canRead()) {
-        final Frame frame = inputChannel.read();
-        convertRowFrameToRowsAndColumns(frame);
-      } else if (inputChannel.isFinished()) {
-        runAllOpsOnMultipleRac(frameRowsAndCols);
-        return ReturnOrAwait.returnObject(Unit.instance());
-      } else {
-        return ReturnOrAwait.awaitAll(inputChannels().size());
-      }
-      return ReturnOrAwait.runAgain();
+    // Bring all data to a single executor for processing.

Review Comment:
   > Should we adjust the num rows per partition to some X number if window query is encountered.
   
   @cryptoe Do you mean by increasing the number of partitions in shuffleSpec of the previous stage? If not, can you please elaborate?



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1711027006


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -56,8 +58,10 @@
 public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
 {
   private static final Logger log = new Logger(WindowOperatorQueryFrameProcessor.class);
+  private final WindowOperatorQuery query;
 
   private final List<OperatorFactory> operatorFactoryList;
+  private final ObjectMapper jsonMapper;

Review Comment:
   >  I think the approach in that PR should be altered...so you may not need those fields
   
   We would still need those fields, even if we do the refactoring as suggested on the other PR.



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "cryptoe (via GitHub)" <gi...@apache.org>.
cryptoe commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1729793692


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -533,4 +464,65 @@ private boolean comparePartitionKeys(ResultRow row1, ResultRow row2, List<String
     }
     return match == partitionColumnNames.size();
   }
+
+  private void makeRowSupplierFromFrameCursor()
+  {
+    final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
+    final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
+    for (int i = 0; i < fieldSuppliers.length; i++) {
+      final ColumnValueSelector<?> selector =
+          frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
+      fieldSuppliers[i] = selector::getObject;
+    }
+    rowSupplierFromFrameCursor = () -> {
+      final ResultRow row = ResultRow.create(fieldSuppliers.length);
+      for (int i = 0; i < fieldSuppliers.length; i++) {
+        row.set(i, fieldSuppliers[i].get());
+      }
+      return row;
+    };
+  }
+
+  /**
+   * This method is responsible for the logic of batching the PARTITION BY keys.
+   * If we can add the current rows (currentBatchOfRacs) to the rows pending processing (batchOfRacsPendingProcessing) without violating the maxRowsMaterialized constraint, do it.
+   * If we cannot, we process the rows pending processing (batchOfRacsPendingProcessing), and add the current rows to it which would then be processed in future.
+   */
+  private void processBatchOfRacsPendingProcessingIfNeeded()
+  {
+    if (currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized) {
+      processBatchOfRacsPendingProcessing();
+    }
+
+    batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);

Review Comment:
   This is a fairly expensive call. 
   can we avoid this?
   



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1730022708


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -533,4 +464,65 @@ private boolean comparePartitionKeys(ResultRow row1, ResultRow row2, List<String
     }
     return match == partitionColumnNames.size();
   }
+
+  private void makeRowSupplierFromFrameCursor()
+  {
+    final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
+    final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
+    for (int i = 0; i < fieldSuppliers.length; i++) {
+      final ColumnValueSelector<?> selector =
+          frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
+      fieldSuppliers[i] = selector::getObject;
+    }
+    rowSupplierFromFrameCursor = () -> {
+      final ResultRow row = ResultRow.create(fieldSuppliers.length);
+      for (int i = 0; i < fieldSuppliers.length; i++) {
+        row.set(i, fieldSuppliers[i].get());
+      }
+      return row;
+    };
+  }
+
+  /**
+   * This method is responsible for the logic of batching the PARTITION BY keys.
+   * If we can add the current rows (currentBatchOfRacs) to the rows pending processing (batchOfRacsPendingProcessing) without violating the maxRowsMaterialized constraint, do it.
+   * If we cannot, we process the rows pending processing (batchOfRacsPendingProcessing), and add the current rows to it which would then be processed in future.
+   */
+  private void processBatchOfRacsPendingProcessingIfNeeded()
+  {
+    if (currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized) {
+      processBatchOfRacsPendingProcessing();
+    }
+
+    batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);

Review Comment:
   On further thoughts, we can change the approach to use a single Arraylist, and maintain the last PARTITION BY boundary index, and add a new method `MapOfColumnsRowsAndColumns.fromResultRowTillIndex()` so that we don't have to separately create the sublist to pass to `MapOfColumnsRowsAndColumns.fromResultRow()`.
   
   I ended up making the changes locally for this, putting the diff here in case it helps:
   
   ```diff
   diff --git a/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java b/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java
   index 9945274bc5..c89a732c01 100644
   --- a/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java
   +++ b/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java
   @@ -94,13 +94,8 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
      // Type strategies are pushed in the same order as column types in frameReader.signature()
      private final NullableTypeStrategy[] typeStrategies;
    
   -  // currentBatchOfRacs holds the current rows being read from the frame.
   -  private final ArrayList<ResultRow> currentBatchOfRacs;
   -
   -  // batchOfRacsPendingProcessing holds the rows read from the frame that are pending processing.
   -  // These get processed when we either reach the end of input channel, or when we meet the criteria in shouldProcessPendingBatch() method.
   -  // Until then, this accumulates rows from currentBatchOfRacs.
   -  private final ArrayList<ResultRow> batchOfRacsPendingProcessing;
   +  private final ArrayList<ResultRow> rowsToProcess;
   +  private int lastPartitionIndex = -1;
    
      public WindowOperatorQueryFrameProcessor(
          WindowOperatorQuery query,
   @@ -123,8 +118,7 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
        this.query = query;
        this.frameRowsAndCols = new ArrayList<>();
        this.resultRowAndCols = new ArrayList<>();
   -    this.currentBatchOfRacs = new ArrayList<>();
   -    this.batchOfRacsPendingProcessing = new ArrayList<>();
   +    this.rowsToProcess = new ArrayList<>();
        this.maxRowsMaterialized = maxRowsMaterializedInWindow;
        this.partitionColumnNames = partitionColumnNames;
    
   @@ -244,8 +237,8 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
            makeRowSupplierFromFrameCursor();
          } else if (inputChannel.isFinished()) {
            // Handle any remaining data.
   -        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
   -        processBatchOfRacsPendingProcessing();
   +        lastPartitionIndex = rowsToProcess.size() - 1;
   +        processRowsUpToLastPartition();
            return ReturnOrAwait.returnObject(Unit.instance());
          } else {
            return ReturnOrAwait.runAgain();
   @@ -256,20 +249,17 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
          final ResultRow currentRow = rowSupplierFromFrameCursor.get();
          if (outputRow == null) {
            outputRow = currentRow;
   -        currentBatchOfRacs.add(currentRow);
   +        rowsToProcess.add(currentRow);
          } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
            // Add current row to the same batch of rows for processing.
   -        currentBatchOfRacs.add(currentRow);
   -        ensureMaxRowsInAWindowConstraint(currentBatchOfRacs.size());
   -        if (shouldProcessPendingBatch()) {
   +        rowsToProcess.add(currentRow);
   +        if (rowsToProcess.size() > maxRowsMaterialized) {
              // We don't want to materialize more than maxRowsMaterialized rows at any point in time, so process the pending batch.
   -          processBatchOfRacsPendingProcessing();
   +          processRowsUpToLastPartition();
            }
   +        ensureMaxRowsInAWindowConstraint(rowsToProcess.size());
          } else {
   -        if (shouldProcessPendingBatch()) {
   -          processBatchOfRacsPendingProcessing();
   -        }
   -        copyAndClearCurrentBatch();
   +        lastPartitionIndex = rowsToProcess.size() - 1;
            outputRow = currentRow.copy();
            return ReturnOrAwait.runAgain();
          }
   @@ -486,35 +476,6 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
        };
      }
    
   -  /**
   -   * Process {@link #batchOfRacsPendingProcessing}.
   -   */
   -  private void processBatchOfRacsPendingProcessing()
   -  {
   -    if (batchOfRacsPendingProcessing.isEmpty()) {
   -      return;
   -    }
   -    RowsAndColumns singleRac = MapOfColumnsRowsAndColumns.fromResultRow(
   -        batchOfRacsPendingProcessing,
   -        frameReader.signature()
   -    );
   -    ArrayList<RowsAndColumns> rowsAndColumns = new ArrayList<>();
   -    rowsAndColumns.add(singleRac);
   -    runAllOpsOnMultipleRac(rowsAndColumns);
   -    batchOfRacsPendingProcessing.clear();
   -  }
   -
   -  private boolean shouldProcessPendingBatch()
   -  {
   -    return currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized;
   -  }
   -
   -  private void copyAndClearCurrentBatch()
   -  {
   -    batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
   -    currentBatchOfRacs.clear();
   -  }
   -
      private void ensureMaxRowsInAWindowConstraint(int numRowsInWindow)
      {
        if (numRowsInWindow > maxRowsMaterialized) {
   @@ -524,4 +485,23 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
          ));
        }
      }
   +
   +  private void processRowsUpToLastPartition()
   +  {
   +    if (lastPartitionIndex == -1) {
   +      return;
   +    }
   +
   +    RowsAndColumns singleRac = MapOfColumnsRowsAndColumns.fromResultRowTillIndex(
   +        rowsToProcess,
   +        frameReader.signature(),
   +        lastPartitionIndex
   +    );
   +    ArrayList<RowsAndColumns> rowsAndColumns = new ArrayList<>();
   +    rowsAndColumns.add(singleRac);
   +    runAllOpsOnMultipleRac(rowsAndColumns);
   +
   +    rowsToProcess.subList(0, lastPartitionIndex + 1).clear();
   +    lastPartitionIndex = -1;
   +  }
    }
   diff --git a/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java b/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java
   index 42972f9340..29f092f674 100644
   --- a/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java
   +++ b/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java
   @@ -84,11 +84,16 @@ public class MapOfColumnsRowsAndColumns implements RowsAndColumns
      }
    
      public static MapOfColumnsRowsAndColumns fromResultRow(ArrayList<ResultRow> objs, RowSignature signature)
   +  {
   +    return fromResultRowTillIndex(objs, signature, objs.size() - 1);
   +  }
   +
   +  public static MapOfColumnsRowsAndColumns fromResultRowTillIndex(ArrayList<ResultRow> objs, RowSignature signature, int index)
      {
        final Builder bob = builder();
        if (!objs.isEmpty()) {
   -      Object[][] columnOriented = new Object[objs.get(0).length()][objs.size()];
   -      for (int i = 0; i < objs.size(); ++i) {
   +      Object[][] columnOriented = new Object[objs.get(0).length()][index + 1];
   +      for (int i = 0; i <= index; ++i) {
            for (int j = 0; j < objs.get(i).length(); ++j) {
              columnOriented[j][i] = objs.get(i).get(j);
            }
   
   ```
   
   All tests pass with the above diff. Let me know if this approach seems better to you compared to the current changes of the PR, I just need to update some comments before pushing this to the PR.



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1726386755


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***

Review Comment:
   ~~Why is separate handling required for OVER() without a PARTITION BY? Afaict, batching should be sufficient for both scenarios.~~
   
   Ig that'll be slower



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "kgyrtkirk (via GitHub)" <gi...@apache.org>.
kgyrtkirk commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1711029033


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -56,8 +58,10 @@
 public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
 {
   private static final Logger log = new Logger(WindowOperatorQueryFrameProcessor.class);
+  private final WindowOperatorQuery query;
 
   private final List<OperatorFactory> operatorFactoryList;
+  private final ObjectMapper jsonMapper;

Review Comment:
   no I don't think we will not need them there; but if we do then we can add this commit to that PR or not?



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "kgyrtkirk (via GitHub)" <gi...@apache.org>.
kgyrtkirk commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1711023562


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -56,8 +58,10 @@
 public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
 {
   private static final Logger log = new Logger(WindowOperatorQueryFrameProcessor.class);
+  private final WindowOperatorQuery query;
 
   private final List<OperatorFactory> operatorFactoryList;
+  private final ObjectMapper jsonMapper;

Review Comment:
   please remove it and add back later if needed ; I think the approach in that PR should be altered...so you may not need those fields



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on PR #16823:
URL: https://github.com/apache/druid/pull/16823#issuecomment-2292772397

   Update: We had a discussion with @gianm and @cryptoe about this. We have 2 possible approaches to go with:
   1. One option is to keep the changes of this PR (create a single RAC per MSQ partition, instead of 1 RAC per `PARTITION BY` key), and use GlobalSortTargetSizeShuffleSpec with `targetSize=(Limits#MAX_ROWS_MATERIALIZED_IN_WINDOW) / 2` as an attempt to tune the number of partitions received by the workers in window stage, such that MSQ partitions received by workers in window stages contain less than the limit (100k rows) whenever possible.
   2. The problem with current implementation is that we're creating 1 RAC per `PARTITION BY` key. The suggestion was to batch multiple of these RACs together for processing in the `WindowOperatorQueryFrameProcessor` layer, and process them only when the "currentRac" has more than some threshold numRows. (essentially having 1 RAC per N `PARTITION BY` keys such that each RAC is sized closer to the limit)
   
   The conclusion was to go with approach (2). With approach (1), beyond a certain point, we would also hit a `TooManyPartitions` error (if we have more than 25000 partitions, i.e., if we're using 50k target size per partition, that is we have more than 1.25 billion rows). Doing a large number of partitions at the MSQ framework level will also have its own performance implication (each partition has its own set of files, etc).
   
    Hence, this PR needs to be worked upon, and I'm marking this PR as a draft PR until it's ready for review with the changes for approach (2) again.


-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "kgyrtkirk (via GitHub)" <gi...@apache.org>.
kgyrtkirk commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1711029033


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -56,8 +58,10 @@
 public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
 {
   private static final Logger log = new Logger(WindowOperatorQueryFrameProcessor.class);
+  private final WindowOperatorQuery query;
 
   private final List<OperatorFactory> operatorFactoryList;
+  private final ObjectMapper jsonMapper;

Review Comment:
   no I don't think we will them there; but if we do then we can add this commit to that PR or not?



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1711034212


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -56,8 +58,10 @@
 public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
 {
   private static final Logger log = new Logger(WindowOperatorQueryFrameProcessor.class);
+  private final WindowOperatorQuery query;
 
   private final List<OperatorFactory> operatorFactoryList;
+  private final ObjectMapper jsonMapper;

Review Comment:
   Sure, have reverted the commit. Will add these back in the other PR when this one's merged.



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "cryptoe (via GitHub)" <gi...@apache.org>.
cryptoe commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1729792008


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***
+
+     In this scenario, we need to process rows for each PARTITION BY group together, but we can batch multiple PARTITION BY keys into the same RAC before passing it to the operators for processing.
+     Batching is fine since the operators list would have the required NaivePartitioningOperatorFactory to segregate each PARTITION BY group during the processing.
+
+     The flow for this scenario can be summarised as following:
+     1. Frame Reading and Cursor Initialization: We start by reading a frame from the inputChannel and initializing frameCursor to iterate over the rows in that frame.
+     2. Row Comparison: For each row in the frame, we decide whether it belongs to the same PARTITION BY group as the previous row.
+                        This is determined by comparePartitionKeys() method.
+                        Please refer to the Javadoc of that method for further details and an example illustration.
+        2.1. If the PARTITION BY columns of current row matches the PARTITION BY columns of the previous row,
+             they belong to the same PARTITION BY group, and gets added to currentBatchOfRacs.
+             If the number of total rows materialized exceed maxRowsMaterialized, we process the pending batch via processBatchOfRacsPendingProcessing() method.
+        2.2. If they don't match, then we have reached a partition boundary.
+             In this case, we process the rows so far *if needed* via processBatchOfRacsPendingProcessingIfNeeded() method.
+             Please refer to the Javadoc of that method for further details.
+     3. End of Input: If the input channel is finished, any remaining rows in currentBatchOfRacs are processed.
+
+     *Illustration of Row Comparison step*
+
+     Let's say we have window_function() OVER (PARTITION BY A ORDER BY B) in our query, and we get 3 frames in the input channel to process.
+
+     Frame 1
+     A, B
+     1, 2
+     1, 3
+     2, 1 --> PARTITION BY key (column A) changed from 1 to 2.
+     2, 2
+
+     Frame 2
+     A, B
+     3, 1 --> PARTITION BY key (column A) changed from 2 to 3.
+     3, 2
+     3, 3
+     3, 4
+
+     Frame 3
+     A, B
+     3, 5
+     3, 6
+     4, 1 --> PARTITION BY key (column A) changed from 3 to 4.
+     4, 2
+
+     *Why batching?*
+     We batch multiple PARTITION BY keys for processing together to avoid the overhead of creating different RACs for each PARTITION BY keys, as that would be unnecessary in scenarios where we have a large number of PARTITION BY keys, but each key having a single row.
+
+     *Future thoughts: https://github.com/apache/druid/issues/16126*
+     Current approach with R&C and operators materialize a single R&C for processing. In case of data with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause.
+     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data. We might think to reimplement them in the MSQ way so that we do not have to materialize so much data.
      */
 
     if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
+      // Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY.
       if (inputChannel.canRead()) {
         final Frame frame = inputChannel.read();
         convertRowFrameToRowsAndColumns(frame);
+        return ReturnOrAwait.runAgain();
       } else if (inputChannel.isFinished()) {
         runAllOpsOnMultipleRac(frameRowsAndCols);
         return ReturnOrAwait.returnObject(Unit.instance());
       } else {
         return ReturnOrAwait.awaitAll(inputChannels().size());
       }
-      return ReturnOrAwait.runAgain();
-    } else {
-      // Aha, you found a PARTITION BY and maybe ORDER BY TO
-      // PARTITION BY can also be on multiple keys
-      // typically the last stage would already partition and sort for you
-      // figure out frame boundaries and convert each distinct group to a rac
-      // then run the windowing operator only on each rac
-      if (frameCursor == null || frameCursor.isDone()) {
-        if (readableInputs.isEmpty()) {
-          return ReturnOrAwait.awaitAll(1);
-        } else if (inputChannel.canRead()) {
-          final Frame frame = inputChannel.read();
-          frameCursor = FrameProcessors.makeCursor(frame, frameReader);
-          final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
-          final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
-          for (int i = 0; i < fieldSuppliers.length; i++) {
-            final ColumnValueSelector<?> selector =
-                frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
-            fieldSuppliers[i] = selector::getObject;
-
-          }
-          rowSupplierFromFrameCursor = () -> {
-            final ResultRow row = ResultRow.create(fieldSuppliers.length);
-            for (int i = 0; i < fieldSuppliers.length; i++) {
-              row.set(i, fieldSuppliers[i].get());
-            }
-            return row;
-          };
-        } else if (inputChannel.isFinished()) {
-          // reaached end of channel
-          // if there is data remaining
-          // write it into a rac
-          // and run operators on it
-          if (!objectsOfASingleRac.isEmpty()) {
-            if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-              throw new MSQException(new TooManyRowsInAWindowFault(objectsOfASingleRac.size(), maxRowsMaterialized));
-            }
-            RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-                objectsOfASingleRac,
-                frameReader.signature()
-            );
-            runAllOpsOnSingleRac(rac);
-            objectsOfASingleRac.clear();
-          }
-          return ReturnOrAwait.returnObject(Unit.instance());
-        } else {
-          return ReturnOrAwait.runAgain();
-        }
-      }
-      while (!frameCursor.isDone()) {
-        final ResultRow currentRow = rowSupplierFromFrameCursor.get();
-        if (outputRow == null) {
-          outputRow = currentRow;
-          objectsOfASingleRac.add(currentRow);
-        } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
-          // if they have the same partition key
-          // keep adding them after checking
-          // guardrails
-          objectsOfASingleRac.add(currentRow);
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-        } else {
-          // key change noted
-          // create rac from the rows seen before
-          // run the operators on these rows and columns
-          // clean up the object to hold the new rows only
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-          RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-              objectsOfASingleRac,
-              frameReader.signature()
-          );
-          runAllOpsOnSingleRac(rac);
-          objectsOfASingleRac.clear();
-          outputRow = currentRow.copy();
-          return ReturnOrAwait.runAgain();
-        }
-        frameCursor.advance();
+    }
+
+    // Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY
+    if (frameCursor == null || frameCursor.isDone()) {
+      if (readableInputs.isEmpty()) {
+        return ReturnOrAwait.awaitAll(1);
+      } else if (inputChannel.canRead()) {
+        final Frame frame = inputChannel.read();
+        frameCursor = FrameProcessors.makeCursor(frame, frameReader);
+        makeRowSupplierFromFrameCursor();
+      } else if (inputChannel.isFinished()) {
+        // Handle any remaining data.
+        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
+        processBatchOfRacsPendingProcessing();
+        return ReturnOrAwait.returnObject(Unit.instance());
+      } else {
+        return ReturnOrAwait.runAgain();
       }
     }
-    return ReturnOrAwait.runAgain();
-  }
 
-  /**
-   * @param singleRac Use this {@link RowsAndColumns} as a single input for the operators to be run
-   */
-  private void runAllOpsOnSingleRac(RowsAndColumns singleRac)
-  {
-    Operator op = new Operator()
-    {
-      @Nullable
-      @Override
-      public Closeable goOrContinue(Closeable continuationObject, Receiver receiver)
-      {
-        receiver.push(singleRac);
-        if (singleRac.numRows() > maxRowsMaterialized) {
-          throw new MSQException(new TooManyRowsInAWindowFault(singleRac.numRows(), maxRowsMaterialized));
+    while (!frameCursor.isDone()) {
+      final ResultRow currentRow = rowSupplierFromFrameCursor.get();
+      if (outputRow == null) {
+        outputRow = currentRow;
+        currentBatchOfRacs.add(currentRow);
+      } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
+        // Add current row to the same batch of rows for processing.
+        currentBatchOfRacs.add(currentRow);
+        ensureMaxRowsInAWindowConstraint(currentBatchOfRacs.size());
+        if (currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized) {
+          // We don't want to materialize more than maxRowsMaterialized rows at any point in time, so process the pending batch.
+          processBatchOfRacsPendingProcessing();

Review Comment:
   The check on line 264 is repeated inside the method. I think it should be removed. 



##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***
+
+     In this scenario, we need to process rows for each PARTITION BY group together, but we can batch multiple PARTITION BY keys into the same RAC before passing it to the operators for processing.
+     Batching is fine since the operators list would have the required NaivePartitioningOperatorFactory to segregate each PARTITION BY group during the processing.
+
+     The flow for this scenario can be summarised as following:
+     1. Frame Reading and Cursor Initialization: We start by reading a frame from the inputChannel and initializing frameCursor to iterate over the rows in that frame.
+     2. Row Comparison: For each row in the frame, we decide whether it belongs to the same PARTITION BY group as the previous row.
+                        This is determined by comparePartitionKeys() method.
+                        Please refer to the Javadoc of that method for further details and an example illustration.
+        2.1. If the PARTITION BY columns of current row matches the PARTITION BY columns of the previous row,
+             they belong to the same PARTITION BY group, and gets added to currentBatchOfRacs.
+             If the number of total rows materialized exceed maxRowsMaterialized, we process the pending batch via processBatchOfRacsPendingProcessing() method.
+        2.2. If they don't match, then we have reached a partition boundary.
+             In this case, we process the rows so far *if needed* via processBatchOfRacsPendingProcessingIfNeeded() method.
+             Please refer to the Javadoc of that method for further details.
+     3. End of Input: If the input channel is finished, any remaining rows in currentBatchOfRacs are processed.
+
+     *Illustration of Row Comparison step*
+
+     Let's say we have window_function() OVER (PARTITION BY A ORDER BY B) in our query, and we get 3 frames in the input channel to process.
+
+     Frame 1
+     A, B
+     1, 2
+     1, 3
+     2, 1 --> PARTITION BY key (column A) changed from 1 to 2.
+     2, 2
+
+     Frame 2
+     A, B
+     3, 1 --> PARTITION BY key (column A) changed from 2 to 3.
+     3, 2
+     3, 3
+     3, 4
+
+     Frame 3
+     A, B
+     3, 5
+     3, 6
+     4, 1 --> PARTITION BY key (column A) changed from 3 to 4.
+     4, 2
+
+     *Why batching?*
+     We batch multiple PARTITION BY keys for processing together to avoid the overhead of creating different RACs for each PARTITION BY keys, as that would be unnecessary in scenarios where we have a large number of PARTITION BY keys, but each key having a single row.
+
+     *Future thoughts: https://github.com/apache/druid/issues/16126*
+     Current approach with R&C and operators materialize a single R&C for processing. In case of data with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause.
+     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data. We might think to reimplement them in the MSQ way so that we do not have to materialize so much data.
      */
 
     if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
+      // Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY.
       if (inputChannel.canRead()) {
         final Frame frame = inputChannel.read();
         convertRowFrameToRowsAndColumns(frame);
+        return ReturnOrAwait.runAgain();
       } else if (inputChannel.isFinished()) {
         runAllOpsOnMultipleRac(frameRowsAndCols);
         return ReturnOrAwait.returnObject(Unit.instance());
       } else {
         return ReturnOrAwait.awaitAll(inputChannels().size());
       }
-      return ReturnOrAwait.runAgain();
-    } else {
-      // Aha, you found a PARTITION BY and maybe ORDER BY TO
-      // PARTITION BY can also be on multiple keys
-      // typically the last stage would already partition and sort for you
-      // figure out frame boundaries and convert each distinct group to a rac
-      // then run the windowing operator only on each rac
-      if (frameCursor == null || frameCursor.isDone()) {
-        if (readableInputs.isEmpty()) {
-          return ReturnOrAwait.awaitAll(1);
-        } else if (inputChannel.canRead()) {
-          final Frame frame = inputChannel.read();
-          frameCursor = FrameProcessors.makeCursor(frame, frameReader);
-          final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
-          final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
-          for (int i = 0; i < fieldSuppliers.length; i++) {
-            final ColumnValueSelector<?> selector =
-                frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
-            fieldSuppliers[i] = selector::getObject;
-
-          }
-          rowSupplierFromFrameCursor = () -> {
-            final ResultRow row = ResultRow.create(fieldSuppliers.length);
-            for (int i = 0; i < fieldSuppliers.length; i++) {
-              row.set(i, fieldSuppliers[i].get());
-            }
-            return row;
-          };
-        } else if (inputChannel.isFinished()) {
-          // reaached end of channel
-          // if there is data remaining
-          // write it into a rac
-          // and run operators on it
-          if (!objectsOfASingleRac.isEmpty()) {
-            if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-              throw new MSQException(new TooManyRowsInAWindowFault(objectsOfASingleRac.size(), maxRowsMaterialized));
-            }
-            RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-                objectsOfASingleRac,
-                frameReader.signature()
-            );
-            runAllOpsOnSingleRac(rac);
-            objectsOfASingleRac.clear();
-          }
-          return ReturnOrAwait.returnObject(Unit.instance());
-        } else {
-          return ReturnOrAwait.runAgain();
-        }
-      }
-      while (!frameCursor.isDone()) {
-        final ResultRow currentRow = rowSupplierFromFrameCursor.get();
-        if (outputRow == null) {
-          outputRow = currentRow;
-          objectsOfASingleRac.add(currentRow);
-        } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
-          // if they have the same partition key
-          // keep adding them after checking
-          // guardrails
-          objectsOfASingleRac.add(currentRow);
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-        } else {
-          // key change noted
-          // create rac from the rows seen before
-          // run the operators on these rows and columns
-          // clean up the object to hold the new rows only
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-          RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-              objectsOfASingleRac,
-              frameReader.signature()
-          );
-          runAllOpsOnSingleRac(rac);
-          objectsOfASingleRac.clear();
-          outputRow = currentRow.copy();
-          return ReturnOrAwait.runAgain();
-        }
-        frameCursor.advance();
+    }
+
+    // Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY
+    if (frameCursor == null || frameCursor.isDone()) {
+      if (readableInputs.isEmpty()) {
+        return ReturnOrAwait.awaitAll(1);
+      } else if (inputChannel.canRead()) {
+        final Frame frame = inputChannel.read();
+        frameCursor = FrameProcessors.makeCursor(frame, frameReader);
+        makeRowSupplierFromFrameCursor();
+      } else if (inputChannel.isFinished()) {
+        // Handle any remaining data.
+        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
+        processBatchOfRacsPendingProcessing();
+        return ReturnOrAwait.returnObject(Unit.instance());
+      } else {
+        return ReturnOrAwait.runAgain();
       }
     }
-    return ReturnOrAwait.runAgain();
-  }
 
-  /**
-   * @param singleRac Use this {@link RowsAndColumns} as a single input for the operators to be run
-   */
-  private void runAllOpsOnSingleRac(RowsAndColumns singleRac)
-  {
-    Operator op = new Operator()
-    {
-      @Nullable
-      @Override
-      public Closeable goOrContinue(Closeable continuationObject, Receiver receiver)
-      {
-        receiver.push(singleRac);
-        if (singleRac.numRows() > maxRowsMaterialized) {
-          throw new MSQException(new TooManyRowsInAWindowFault(singleRac.numRows(), maxRowsMaterialized));
+    while (!frameCursor.isDone()) {
+      final ResultRow currentRow = rowSupplierFromFrameCursor.get();
+      if (outputRow == null) {
+        outputRow = currentRow;
+        currentBatchOfRacs.add(currentRow);
+      } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
+        // Add current row to the same batch of rows for processing.
+        currentBatchOfRacs.add(currentRow);
+        ensureMaxRowsInAWindowConstraint(currentBatchOfRacs.size());
+        if (currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized) {
+          // We don't want to materialize more than maxRowsMaterialized rows at any point in time, so process the pending batch.
+          processBatchOfRacsPendingProcessing();

Review Comment:
   The check on line 264 is repeated inside the method. I think it should be removed from line 264 no ?



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "adarshsanjeev (via GitHub)" <gi...@apache.org>.
adarshsanjeev merged PR #16823:
URL: https://github.com/apache/druid/pull/16823


-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1732166201


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***
+
+     In this scenario, we need to process rows for each PARTITION BY group together, but we can batch multiple PARTITION BY keys into the same RAC before passing it to the operators for processing.
+     Batching is fine since the operators list would have the required NaivePartitioningOperatorFactory to segregate each PARTITION BY group during the processing.
+
+     The flow for this scenario can be summarised as following:
+     1. Frame Reading and Cursor Initialization: We start by reading a frame from the inputChannel and initializing frameCursor to iterate over the rows in that frame.
+     2. Row Comparison: For each row in the frame, we decide whether it belongs to the same PARTITION BY group as the previous row.
+                        This is determined by comparePartitionKeys() method.
+                        Please refer to the Javadoc of that method for further details and an example illustration.
+        2.1. If the PARTITION BY columns of current row matches the PARTITION BY columns of the previous row,
+             they belong to the same PARTITION BY group, and gets added to currentBatchOfRacs.
+             If the number of total rows materialized exceed maxRowsMaterialized, we process the pending batch via processBatchOfRacsPendingProcessing() method.
+        2.2. If they don't match, then we have reached a partition boundary.
+             In this case, we process the rows so far *if needed* via processBatchOfRacsPendingProcessingIfNeeded() method.
+             Please refer to the Javadoc of that method for further details.
+     3. End of Input: If the input channel is finished, any remaining rows in currentBatchOfRacs are processed.
+
+     *Illustration of Row Comparison step*
+
+     Let's say we have window_function() OVER (PARTITION BY A ORDER BY B) in our query, and we get 3 frames in the input channel to process.
+
+     Frame 1
+     A, B
+     1, 2
+     1, 3
+     2, 1 --> PARTITION BY key (column A) changed from 1 to 2.
+     2, 2
+
+     Frame 2
+     A, B
+     3, 1 --> PARTITION BY key (column A) changed from 2 to 3.
+     3, 2
+     3, 3
+     3, 4
+
+     Frame 3
+     A, B
+     3, 5
+     3, 6
+     4, 1 --> PARTITION BY key (column A) changed from 3 to 4.
+     4, 2
+
+     *Why batching?*
+     We batch multiple PARTITION BY keys for processing together to avoid the overhead of creating different RACs for each PARTITION BY keys, as that would be unnecessary in scenarios where we have a large number of PARTITION BY keys, but each key having a single row.
+
+     *Future thoughts: https://github.com/apache/druid/issues/16126*
+     Current approach with R&C and operators materialize a single R&C for processing. In case of data with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause.
+     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data. We might think to reimplement them in the MSQ way so that we do not have to materialize so much data.
      */
 
     if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
+      // Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY.
       if (inputChannel.canRead()) {
         final Frame frame = inputChannel.read();
         convertRowFrameToRowsAndColumns(frame);
+        return ReturnOrAwait.runAgain();
       } else if (inputChannel.isFinished()) {
         runAllOpsOnMultipleRac(frameRowsAndCols);
         return ReturnOrAwait.returnObject(Unit.instance());
       } else {
         return ReturnOrAwait.awaitAll(inputChannels().size());
       }
-      return ReturnOrAwait.runAgain();
-    } else {
-      // Aha, you found a PARTITION BY and maybe ORDER BY TO
-      // PARTITION BY can also be on multiple keys
-      // typically the last stage would already partition and sort for you
-      // figure out frame boundaries and convert each distinct group to a rac
-      // then run the windowing operator only on each rac
-      if (frameCursor == null || frameCursor.isDone()) {
-        if (readableInputs.isEmpty()) {
-          return ReturnOrAwait.awaitAll(1);
-        } else if (inputChannel.canRead()) {
-          final Frame frame = inputChannel.read();
-          frameCursor = FrameProcessors.makeCursor(frame, frameReader);
-          final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
-          final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
-          for (int i = 0; i < fieldSuppliers.length; i++) {
-            final ColumnValueSelector<?> selector =
-                frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
-            fieldSuppliers[i] = selector::getObject;
-
-          }
-          rowSupplierFromFrameCursor = () -> {
-            final ResultRow row = ResultRow.create(fieldSuppliers.length);
-            for (int i = 0; i < fieldSuppliers.length; i++) {
-              row.set(i, fieldSuppliers[i].get());
-            }
-            return row;
-          };
-        } else if (inputChannel.isFinished()) {
-          // reaached end of channel
-          // if there is data remaining
-          // write it into a rac
-          // and run operators on it
-          if (!objectsOfASingleRac.isEmpty()) {
-            if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-              throw new MSQException(new TooManyRowsInAWindowFault(objectsOfASingleRac.size(), maxRowsMaterialized));
-            }
-            RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-                objectsOfASingleRac,
-                frameReader.signature()
-            );
-            runAllOpsOnSingleRac(rac);
-            objectsOfASingleRac.clear();
-          }
-          return ReturnOrAwait.returnObject(Unit.instance());
-        } else {
-          return ReturnOrAwait.runAgain();
-        }
-      }
-      while (!frameCursor.isDone()) {
-        final ResultRow currentRow = rowSupplierFromFrameCursor.get();
-        if (outputRow == null) {
-          outputRow = currentRow;
-          objectsOfASingleRac.add(currentRow);
-        } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
-          // if they have the same partition key
-          // keep adding them after checking
-          // guardrails
-          objectsOfASingleRac.add(currentRow);
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-        } else {
-          // key change noted
-          // create rac from the rows seen before
-          // run the operators on these rows and columns
-          // clean up the object to hold the new rows only
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-          RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-              objectsOfASingleRac,
-              frameReader.signature()
-          );
-          runAllOpsOnSingleRac(rac);
-          objectsOfASingleRac.clear();
-          outputRow = currentRow.copy();
-          return ReturnOrAwait.runAgain();
-        }
-        frameCursor.advance();
+    }
+
+    // Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY
+    if (frameCursor == null || frameCursor.isDone()) {
+      if (readableInputs.isEmpty()) {
+        return ReturnOrAwait.awaitAll(1);
+      } else if (inputChannel.canRead()) {
+        final Frame frame = inputChannel.read();
+        frameCursor = FrameProcessors.makeCursor(frame, frameReader);
+        makeRowSupplierFromFrameCursor();
+      } else if (inputChannel.isFinished()) {
+        // Handle any remaining data.
+        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
+        processBatchOfRacsPendingProcessing();
+        return ReturnOrAwait.returnObject(Unit.instance());
+      } else {
+        return ReturnOrAwait.runAgain();
       }
     }
-    return ReturnOrAwait.runAgain();
-  }
 
-  /**
-   * @param singleRac Use this {@link RowsAndColumns} as a single input for the operators to be run
-   */
-  private void runAllOpsOnSingleRac(RowsAndColumns singleRac)
-  {
-    Operator op = new Operator()
-    {
-      @Nullable
-      @Override
-      public Closeable goOrContinue(Closeable continuationObject, Receiver receiver)
-      {
-        receiver.push(singleRac);
-        if (singleRac.numRows() > maxRowsMaterialized) {
-          throw new MSQException(new TooManyRowsInAWindowFault(singleRac.numRows(), maxRowsMaterialized));
+    while (!frameCursor.isDone()) {
+      final ResultRow currentRow = rowSupplierFromFrameCursor.get();
+      if (outputRow == null) {
+        outputRow = currentRow;
+        currentBatchOfRacs.add(currentRow);
+      } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {

Review Comment:
   As discussed offline, the next step would be GlueingPartitioningOperator.



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1722872965


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -137,205 +103,44 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
+     * We add all the RACs to a single ConcatRowsAndColumns and pass it to the list of operators to process.
      *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
      */
 
-    if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
-      if (inputChannel.canRead()) {
-        final Frame frame = inputChannel.read();
-        convertRowFrameToRowsAndColumns(frame);
-      } else if (inputChannel.isFinished()) {
-        runAllOpsOnMultipleRac(frameRowsAndCols);
-        return ReturnOrAwait.returnObject(Unit.instance());
-      } else {
-        return ReturnOrAwait.awaitAll(inputChannels().size());
-      }
-      return ReturnOrAwait.runAgain();
+    // Bring all data to a single executor for processing.

Review Comment:
   @cryptoe @kgyrtkirk I've made the changes as per https://github.com/apache/druid/pull/16823#issuecomment-2292772397, please have a look. Thanks!
   
   Closing this comment as it's not relevant anymore to the latest changes of the PR.



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1728726178


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***
+
+     In this scenario, we need to process rows for each PARTITION BY group together, but we can batch multiple PARTITION BY keys into the same RAC before passing it to the operators for processing.
+     Batching is fine since the operators list would have the required NaivePartitioningOperatorFactory to segregate each PARTITION BY group during the processing.
+
+     The flow for this scenario can be summarised as following:
+     1. Frame Reading and Cursor Initialization: We start by reading a frame from the inputChannel and initializing frameCursor to iterate over the rows in that frame.
+     2. Row Comparison: For each row in the frame, we decide whether it belongs to the same PARTITION BY group as the previous row.
+                        This is determined by comparePartitionKeys() method.
+                        Please refer to the Javadoc of that method for further details and an example illustration.
+        2.1. If the PARTITION BY columns of current row matches the PARTITION BY columns of the previous row,
+             they belong to the same PARTITION BY group, and gets added to currentBatchOfRacs.
+             If the number of total rows materialized exceed maxRowsMaterialized, we process the pending batch via processBatchOfRacsPendingProcessing() method.
+        2.2. If they don't match, then we have reached a partition boundary.
+             In this case, we process the rows so far *if needed* via processBatchOfRacsPendingProcessingIfNeeded() method.
+             Please refer to the Javadoc of that method for further details.
+     3. End of Input: If the input channel is finished, any remaining rows in currentBatchOfRacs are processed.
+
+     *Illustration of Row Comparison step*
+
+     Let's say we have window_function() OVER (PARTITION BY A ORDER BY B) in our query, and we get 3 frames in the input channel to process.
+
+     Frame 1
+     A, B
+     1, 2
+     1, 3
+     2, 1 --> PARTITION BY key (column A) changed from 1 to 2.
+     2, 2
+
+     Frame 2
+     A, B
+     3, 1 --> PARTITION BY key (column A) changed from 2 to 3.
+     3, 2
+     3, 3
+     3, 4
+
+     Frame 3
+     A, B
+     3, 5
+     3, 6
+     4, 1 --> PARTITION BY key (column A) changed from 3 to 4.
+     4, 2
+
+     *Why batching?*
+     We batch multiple PARTITION BY keys for processing together to avoid the overhead of creating different RACs for each PARTITION BY keys, as that would be unnecessary in scenarios where we have a large number of PARTITION BY keys, but each key having a single row.
+
+     *Future thoughts: https://github.com/apache/druid/issues/16126*
+     Current approach with R&C and operators materialize a single R&C for processing. In case of data with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause.
+     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data. We might think to reimplement them in the MSQ way so that we do not have to materialize so much data.
      */
 
     if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
+      // Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY.
       if (inputChannel.canRead()) {
         final Frame frame = inputChannel.read();
         convertRowFrameToRowsAndColumns(frame);
+        return ReturnOrAwait.runAgain();
       } else if (inputChannel.isFinished()) {
         runAllOpsOnMultipleRac(frameRowsAndCols);
         return ReturnOrAwait.returnObject(Unit.instance());
       } else {
         return ReturnOrAwait.awaitAll(inputChannels().size());
       }
-      return ReturnOrAwait.runAgain();
-    } else {
-      // Aha, you found a PARTITION BY and maybe ORDER BY TO
-      // PARTITION BY can also be on multiple keys
-      // typically the last stage would already partition and sort for you
-      // figure out frame boundaries and convert each distinct group to a rac
-      // then run the windowing operator only on each rac
-      if (frameCursor == null || frameCursor.isDone()) {
-        if (readableInputs.isEmpty()) {
-          return ReturnOrAwait.awaitAll(1);
-        } else if (inputChannel.canRead()) {
-          final Frame frame = inputChannel.read();
-          frameCursor = FrameProcessors.makeCursor(frame, frameReader);
-          final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
-          final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
-          for (int i = 0; i < fieldSuppliers.length; i++) {
-            final ColumnValueSelector<?> selector =
-                frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
-            fieldSuppliers[i] = selector::getObject;
-
-          }
-          rowSupplierFromFrameCursor = () -> {
-            final ResultRow row = ResultRow.create(fieldSuppliers.length);
-            for (int i = 0; i < fieldSuppliers.length; i++) {
-              row.set(i, fieldSuppliers[i].get());
-            }
-            return row;
-          };
-        } else if (inputChannel.isFinished()) {
-          // reaached end of channel
-          // if there is data remaining
-          // write it into a rac
-          // and run operators on it
-          if (!objectsOfASingleRac.isEmpty()) {
-            if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-              throw new MSQException(new TooManyRowsInAWindowFault(objectsOfASingleRac.size(), maxRowsMaterialized));
-            }
-            RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-                objectsOfASingleRac,
-                frameReader.signature()
-            );
-            runAllOpsOnSingleRac(rac);
-            objectsOfASingleRac.clear();
-          }
-          return ReturnOrAwait.returnObject(Unit.instance());
-        } else {
-          return ReturnOrAwait.runAgain();
-        }
-      }
-      while (!frameCursor.isDone()) {
-        final ResultRow currentRow = rowSupplierFromFrameCursor.get();
-        if (outputRow == null) {
-          outputRow = currentRow;
-          objectsOfASingleRac.add(currentRow);
-        } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
-          // if they have the same partition key
-          // keep adding them after checking
-          // guardrails
-          objectsOfASingleRac.add(currentRow);
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-        } else {
-          // key change noted
-          // create rac from the rows seen before
-          // run the operators on these rows and columns
-          // clean up the object to hold the new rows only
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-          RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-              objectsOfASingleRac,
-              frameReader.signature()
-          );
-          runAllOpsOnSingleRac(rac);
-          objectsOfASingleRac.clear();
-          outputRow = currentRow.copy();
-          return ReturnOrAwait.runAgain();
-        }
-        frameCursor.advance();
+    }
+
+    // Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY
+    if (frameCursor == null || frameCursor.isDone()) {
+      if (readableInputs.isEmpty()) {
+        return ReturnOrAwait.awaitAll(1);
+      } else if (inputChannel.canRead()) {
+        final Frame frame = inputChannel.read();
+        frameCursor = FrameProcessors.makeCursor(frame, frameReader);
+        makeRowSupplierFromFrameCursor();
+      } else if (inputChannel.isFinished()) {
+        // Handle any remaining data.
+        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
+        processBatchOfRacsPendingProcessing();
+        return ReturnOrAwait.returnObject(Unit.instance());
+      } else {
+        return ReturnOrAwait.runAgain();
       }
     }
-    return ReturnOrAwait.runAgain();
-  }
 
-  /**
-   * @param singleRac Use this {@link RowsAndColumns} as a single input for the operators to be run
-   */
-  private void runAllOpsOnSingleRac(RowsAndColumns singleRac)
-  {
-    Operator op = new Operator()
-    {
-      @Nullable
-      @Override
-      public Closeable goOrContinue(Closeable continuationObject, Receiver receiver)
-      {
-        receiver.push(singleRac);
-        if (singleRac.numRows() > maxRowsMaterialized) {
-          throw new MSQException(new TooManyRowsInAWindowFault(singleRac.numRows(), maxRowsMaterialized));
+    while (!frameCursor.isDone()) {
+      final ResultRow currentRow = rowSupplierFromFrameCursor.get();
+      if (outputRow == null) {
+        outputRow = currentRow;
+        currentBatchOfRacs.add(currentRow);
+      } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {

Review Comment:
   Thanks!



##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***
+
+     In this scenario, we need to process rows for each PARTITION BY group together, but we can batch multiple PARTITION BY keys into the same RAC before passing it to the operators for processing.
+     Batching is fine since the operators list would have the required NaivePartitioningOperatorFactory to segregate each PARTITION BY group during the processing.
+
+     The flow for this scenario can be summarised as following:
+     1. Frame Reading and Cursor Initialization: We start by reading a frame from the inputChannel and initializing frameCursor to iterate over the rows in that frame.
+     2. Row Comparison: For each row in the frame, we decide whether it belongs to the same PARTITION BY group as the previous row.
+                        This is determined by comparePartitionKeys() method.
+                        Please refer to the Javadoc of that method for further details and an example illustration.
+        2.1. If the PARTITION BY columns of current row matches the PARTITION BY columns of the previous row,
+             they belong to the same PARTITION BY group, and gets added to currentBatchOfRacs.
+             If the number of total rows materialized exceed maxRowsMaterialized, we process the pending batch via processBatchOfRacsPendingProcessing() method.
+        2.2. If they don't match, then we have reached a partition boundary.
+             In this case, we process the rows so far *if needed* via processBatchOfRacsPendingProcessingIfNeeded() method.
+             Please refer to the Javadoc of that method for further details.
+     3. End of Input: If the input channel is finished, any remaining rows in currentBatchOfRacs are processed.
+
+     *Illustration of Row Comparison step*
+
+     Let's say we have window_function() OVER (PARTITION BY A ORDER BY B) in our query, and we get 3 frames in the input channel to process.
+
+     Frame 1
+     A, B
+     1, 2
+     1, 3
+     2, 1 --> PARTITION BY key (column A) changed from 1 to 2.
+     2, 2
+
+     Frame 2
+     A, B
+     3, 1 --> PARTITION BY key (column A) changed from 2 to 3.
+     3, 2
+     3, 3
+     3, 4
+
+     Frame 3
+     A, B
+     3, 5
+     3, 6
+     4, 1 --> PARTITION BY key (column A) changed from 3 to 4.
+     4, 2
+
+     *Why batching?*
+     We batch multiple PARTITION BY keys for processing together to avoid the overhead of creating different RACs for each PARTITION BY keys, as that would be unnecessary in scenarios where we have a large number of PARTITION BY keys, but each key having a single row.
+
+     *Future thoughts: https://github.com/apache/druid/issues/16126*
+     Current approach with R&C and operators materialize a single R&C for processing. In case of data with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause.
+     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data. We might think to reimplement them in the MSQ way so that we do not have to materialize so much data.
      */
 
     if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
+      // Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY.
       if (inputChannel.canRead()) {
         final Frame frame = inputChannel.read();
         convertRowFrameToRowsAndColumns(frame);
+        return ReturnOrAwait.runAgain();
       } else if (inputChannel.isFinished()) {
         runAllOpsOnMultipleRac(frameRowsAndCols);
         return ReturnOrAwait.returnObject(Unit.instance());
       } else {
         return ReturnOrAwait.awaitAll(inputChannels().size());
       }
-      return ReturnOrAwait.runAgain();
-    } else {
-      // Aha, you found a PARTITION BY and maybe ORDER BY TO
-      // PARTITION BY can also be on multiple keys
-      // typically the last stage would already partition and sort for you
-      // figure out frame boundaries and convert each distinct group to a rac
-      // then run the windowing operator only on each rac
-      if (frameCursor == null || frameCursor.isDone()) {
-        if (readableInputs.isEmpty()) {
-          return ReturnOrAwait.awaitAll(1);
-        } else if (inputChannel.canRead()) {
-          final Frame frame = inputChannel.read();
-          frameCursor = FrameProcessors.makeCursor(frame, frameReader);
-          final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
-          final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
-          for (int i = 0; i < fieldSuppliers.length; i++) {
-            final ColumnValueSelector<?> selector =
-                frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
-            fieldSuppliers[i] = selector::getObject;
-
-          }
-          rowSupplierFromFrameCursor = () -> {
-            final ResultRow row = ResultRow.create(fieldSuppliers.length);
-            for (int i = 0; i < fieldSuppliers.length; i++) {
-              row.set(i, fieldSuppliers[i].get());
-            }
-            return row;
-          };
-        } else if (inputChannel.isFinished()) {
-          // reaached end of channel
-          // if there is data remaining
-          // write it into a rac
-          // and run operators on it
-          if (!objectsOfASingleRac.isEmpty()) {
-            if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-              throw new MSQException(new TooManyRowsInAWindowFault(objectsOfASingleRac.size(), maxRowsMaterialized));
-            }
-            RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-                objectsOfASingleRac,
-                frameReader.signature()
-            );
-            runAllOpsOnSingleRac(rac);
-            objectsOfASingleRac.clear();
-          }
-          return ReturnOrAwait.returnObject(Unit.instance());
-        } else {
-          return ReturnOrAwait.runAgain();
-        }
-      }
-      while (!frameCursor.isDone()) {
-        final ResultRow currentRow = rowSupplierFromFrameCursor.get();
-        if (outputRow == null) {
-          outputRow = currentRow;
-          objectsOfASingleRac.add(currentRow);
-        } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
-          // if they have the same partition key
-          // keep adding them after checking
-          // guardrails
-          objectsOfASingleRac.add(currentRow);
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-        } else {
-          // key change noted
-          // create rac from the rows seen before
-          // run the operators on these rows and columns
-          // clean up the object to hold the new rows only
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-          RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-              objectsOfASingleRac,
-              frameReader.signature()
-          );
-          runAllOpsOnSingleRac(rac);
-          objectsOfASingleRac.clear();
-          outputRow = currentRow.copy();
-          return ReturnOrAwait.runAgain();
-        }
-        frameCursor.advance();
+    }
+
+    // Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY
+    if (frameCursor == null || frameCursor.isDone()) {
+      if (readableInputs.isEmpty()) {
+        return ReturnOrAwait.awaitAll(1);
+      } else if (inputChannel.canRead()) {
+        final Frame frame = inputChannel.read();
+        frameCursor = FrameProcessors.makeCursor(frame, frameReader);
+        makeRowSupplierFromFrameCursor();
+      } else if (inputChannel.isFinished()) {
+        // Handle any remaining data.
+        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
+        processBatchOfRacsPendingProcessing();
+        return ReturnOrAwait.returnObject(Unit.instance());
+      } else {
+        return ReturnOrAwait.runAgain();
       }
     }
-    return ReturnOrAwait.runAgain();
-  }
 
-  /**
-   * @param singleRac Use this {@link RowsAndColumns} as a single input for the operators to be run
-   */
-  private void runAllOpsOnSingleRac(RowsAndColumns singleRac)
-  {
-    Operator op = new Operator()
-    {
-      @Nullable
-      @Override
-      public Closeable goOrContinue(Closeable continuationObject, Receiver receiver)
-      {
-        receiver.push(singleRac);
-        if (singleRac.numRows() > maxRowsMaterialized) {
-          throw new MSQException(new TooManyRowsInAWindowFault(singleRac.numRows(), maxRowsMaterialized));
+    while (!frameCursor.isDone()) {
+      final ResultRow currentRow = rowSupplierFromFrameCursor.get();
+      if (outputRow == null) {
+        outputRow = currentRow;
+        currentBatchOfRacs.add(currentRow);
+      } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {

Review Comment:
   Thanks, that helps! 



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1728713581


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***
+
+     In this scenario, we need to process rows for each PARTITION BY group together, but we can batch multiple PARTITION BY keys into the same RAC before passing it to the operators for processing.
+     Batching is fine since the operators list would have the required NaivePartitioningOperatorFactory to segregate each PARTITION BY group during the processing.
+
+     The flow for this scenario can be summarised as following:
+     1. Frame Reading and Cursor Initialization: We start by reading a frame from the inputChannel and initializing frameCursor to iterate over the rows in that frame.
+     2. Row Comparison: For each row in the frame, we decide whether it belongs to the same PARTITION BY group as the previous row.
+                        This is determined by comparePartitionKeys() method.
+                        Please refer to the Javadoc of that method for further details and an example illustration.
+        2.1. If the PARTITION BY columns of current row matches the PARTITION BY columns of the previous row,
+             they belong to the same PARTITION BY group, and gets added to currentBatchOfRacs.
+             If the number of total rows materialized exceed maxRowsMaterialized, we process the pending batch via processBatchOfRacsPendingProcessing() method.
+        2.2. If they don't match, then we have reached a partition boundary.
+             In this case, we process the rows so far *if needed* via processBatchOfRacsPendingProcessingIfNeeded() method.
+             Please refer to the Javadoc of that method for further details.
+     3. End of Input: If the input channel is finished, any remaining rows in currentBatchOfRacs are processed.
+
+     *Illustration of Row Comparison step*
+
+     Let's say we have window_function() OVER (PARTITION BY A ORDER BY B) in our query, and we get 3 frames in the input channel to process.
+
+     Frame 1
+     A, B
+     1, 2
+     1, 3
+     2, 1 --> PARTITION BY key (column A) changed from 1 to 2.
+     2, 2
+
+     Frame 2
+     A, B
+     3, 1 --> PARTITION BY key (column A) changed from 2 to 3.
+     3, 2
+     3, 3
+     3, 4
+
+     Frame 3
+     A, B
+     3, 5
+     3, 6
+     4, 1 --> PARTITION BY key (column A) changed from 3 to 4.
+     4, 2
+
+     *Why batching?*
+     We batch multiple PARTITION BY keys for processing together to avoid the overhead of creating different RACs for each PARTITION BY keys, as that would be unnecessary in scenarios where we have a large number of PARTITION BY keys, but each key having a single row.
+
+     *Future thoughts: https://github.com/apache/druid/issues/16126*
+     Current approach with R&C and operators materialize a single R&C for processing. In case of data with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause.
+     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data. We might think to reimplement them in the MSQ way so that we do not have to materialize so much data.
      */
 
     if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
+      // Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY.
       if (inputChannel.canRead()) {
         final Frame frame = inputChannel.read();
         convertRowFrameToRowsAndColumns(frame);
+        return ReturnOrAwait.runAgain();
       } else if (inputChannel.isFinished()) {
         runAllOpsOnMultipleRac(frameRowsAndCols);
         return ReturnOrAwait.returnObject(Unit.instance());
       } else {
         return ReturnOrAwait.awaitAll(inputChannels().size());
       }
-      return ReturnOrAwait.runAgain();
-    } else {
-      // Aha, you found a PARTITION BY and maybe ORDER BY TO
-      // PARTITION BY can also be on multiple keys
-      // typically the last stage would already partition and sort for you
-      // figure out frame boundaries and convert each distinct group to a rac
-      // then run the windowing operator only on each rac
-      if (frameCursor == null || frameCursor.isDone()) {
-        if (readableInputs.isEmpty()) {
-          return ReturnOrAwait.awaitAll(1);
-        } else if (inputChannel.canRead()) {
-          final Frame frame = inputChannel.read();
-          frameCursor = FrameProcessors.makeCursor(frame, frameReader);
-          final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
-          final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
-          for (int i = 0; i < fieldSuppliers.length; i++) {
-            final ColumnValueSelector<?> selector =
-                frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
-            fieldSuppliers[i] = selector::getObject;
-
-          }
-          rowSupplierFromFrameCursor = () -> {
-            final ResultRow row = ResultRow.create(fieldSuppliers.length);
-            for (int i = 0; i < fieldSuppliers.length; i++) {
-              row.set(i, fieldSuppliers[i].get());
-            }
-            return row;
-          };
-        } else if (inputChannel.isFinished()) {
-          // reaached end of channel
-          // if there is data remaining
-          // write it into a rac
-          // and run operators on it
-          if (!objectsOfASingleRac.isEmpty()) {
-            if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-              throw new MSQException(new TooManyRowsInAWindowFault(objectsOfASingleRac.size(), maxRowsMaterialized));
-            }
-            RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-                objectsOfASingleRac,
-                frameReader.signature()
-            );
-            runAllOpsOnSingleRac(rac);
-            objectsOfASingleRac.clear();
-          }
-          return ReturnOrAwait.returnObject(Unit.instance());
-        } else {
-          return ReturnOrAwait.runAgain();
-        }
-      }
-      while (!frameCursor.isDone()) {
-        final ResultRow currentRow = rowSupplierFromFrameCursor.get();
-        if (outputRow == null) {
-          outputRow = currentRow;
-          objectsOfASingleRac.add(currentRow);
-        } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
-          // if they have the same partition key
-          // keep adding them after checking
-          // guardrails
-          objectsOfASingleRac.add(currentRow);
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-        } else {
-          // key change noted
-          // create rac from the rows seen before
-          // run the operators on these rows and columns
-          // clean up the object to hold the new rows only
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-          RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-              objectsOfASingleRac,
-              frameReader.signature()
-          );
-          runAllOpsOnSingleRac(rac);
-          objectsOfASingleRac.clear();
-          outputRow = currentRow.copy();
-          return ReturnOrAwait.runAgain();
-        }
-        frameCursor.advance();
+    }
+
+    // Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY
+    if (frameCursor == null || frameCursor.isDone()) {
+      if (readableInputs.isEmpty()) {
+        return ReturnOrAwait.awaitAll(1);
+      } else if (inputChannel.canRead()) {
+        final Frame frame = inputChannel.read();
+        frameCursor = FrameProcessors.makeCursor(frame, frameReader);
+        makeRowSupplierFromFrameCursor();
+      } else if (inputChannel.isFinished()) {
+        // Handle any remaining data.
+        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
+        processBatchOfRacsPendingProcessing();
+        return ReturnOrAwait.returnObject(Unit.instance());
+      } else {
+        return ReturnOrAwait.runAgain();
       }
     }
-    return ReturnOrAwait.runAgain();
-  }
 
-  /**
-   * @param singleRac Use this {@link RowsAndColumns} as a single input for the operators to be run
-   */
-  private void runAllOpsOnSingleRac(RowsAndColumns singleRac)
-  {
-    Operator op = new Operator()
-    {
-      @Nullable
-      @Override
-      public Closeable goOrContinue(Closeable continuationObject, Receiver receiver)
-      {
-        receiver.push(singleRac);
-        if (singleRac.numRows() > maxRowsMaterialized) {
-          throw new MSQException(new TooManyRowsInAWindowFault(singleRac.numRows(), maxRowsMaterialized));
+    while (!frameCursor.isDone()) {
+      final ResultRow currentRow = rowSupplierFromFrameCursor.get();
+      if (outputRow == null) {
+        outputRow = currentRow;
+        currentBatchOfRacs.add(currentRow);
+      } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {

Review Comment:
   @LakshSingla Step 3 is incorrectly demonstrated in the above table.
   
   Rows are moved from `currentBatchOfRacs` to `batchOfRacsPendingProcessing` only in 2 scenarios:
   1. Input channel is finished.
   2. We encounted a PARTITION BY key change.
   
   Step 3 doesn't fall under the above 2 scenarios.
   
   Above example would look like following:
   | Stream Element  |  batchOfRacsPendingProcessing | currentBatchOfRacs  |  Notes |
   |---|---|---|---|
   |  a | -  | a  | -  |
   |  b | a  | b  | -  |
   |  b | -  | b, b  | Flush a.  |
   |  b | -  | b, b, b  | Error out because `currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized`  |
   
   
   ```java
        if (outputRow == null) {
           // code
         } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
           // code
             processBatchOfRacsPendingProcessing();
           }
         } else {
           processBatchOfRacsPendingProcessingIfNeeded();
           // code
         }
   ```
   Notice `processBatchOfRacsPendingProcessing()` vs `processBatchOfRacsPendingProcessingIfNeeded()` in the above flow. (in case the confusion stemmed because of this)
   
   Hope this clarifies.



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "cryptoe (via GitHub)" <gi...@apache.org>.
cryptoe commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1703579978


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -137,205 +103,44 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
+     * We add all the RACs to a single ConcatRowsAndColumns and pass it to the list of operators to process.
      *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
      */
 
-    if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
-      if (inputChannel.canRead()) {
-        final Frame frame = inputChannel.read();
-        convertRowFrameToRowsAndColumns(frame);
-      } else if (inputChannel.isFinished()) {
-        runAllOpsOnMultipleRac(frameRowsAndCols);
-        return ReturnOrAwait.returnObject(Unit.instance());
-      } else {
-        return ReturnOrAwait.awaitAll(inputChannels().size());
-      }
-      return ReturnOrAwait.runAgain();
+    // Bring all data to a single executor for processing.

Review Comment:
   Yes Increase number of partitions in the shuffle spec of the input stage. 



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1701466638


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -137,205 +103,44 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
+     * We add all the RACs to a single ConcatRowsAndColumns and pass it to the list of operators to process.
      *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
      */
 
-    if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
-      if (inputChannel.canRead()) {
-        final Frame frame = inputChannel.read();
-        convertRowFrameToRowsAndColumns(frame);
-      } else if (inputChannel.isFinished()) {
-        runAllOpsOnMultipleRac(frameRowsAndCols);
-        return ReturnOrAwait.returnObject(Unit.instance());
-      } else {
-        return ReturnOrAwait.awaitAll(inputChannels().size());
-      }
-      return ReturnOrAwait.runAgain();
+    // Bring all data to a single executor for processing.

Review Comment:
   @cryptoe Regarding the 2nd point: We have a query context parameter `maxRowsMaterializedInWindow`, and the following guardrail:
   
   ```java
   if (rac.numRows() > maxRowsMaterialized) {
          throw new MSQException(new TooManyRowsInAWindowFault(rac.numRows(), maxRowsMaterialized));
        }
   ```
   
   The default value of the above param is set to 100k in `Limits.java` file:
   ```java
   public static final int MAX_ROWS_MATERIALIZED_IN_WINDOW = 100_000;
   ```



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1706972367


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -438,24 +241,19 @@ public void cleanup() throws IOException
     FrameProcessors.closeAll(inputChannels(), outputChannels(), frameWriter);
   }
 
-  /**
-   * @return Number of rows flushed to the output channel
-   * @throws IOException
-   */
-  private long flushFrameWriter() throws IOException
+  private void flushFrameWriter() throws IOException

Review Comment:
   `runIncrementally()`'s contract states that we should emit a single frame and yield at a time. From what I understand, method is called in a loop and we emit all the rows at once. We should update this implementation to be more inline with its contract. This needn't be addressed immediately since the logic has existed for a while, but we should definitely clean this up. 



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1730022708


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -533,4 +464,65 @@ private boolean comparePartitionKeys(ResultRow row1, ResultRow row2, List<String
     }
     return match == partitionColumnNames.size();
   }
+
+  private void makeRowSupplierFromFrameCursor()
+  {
+    final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
+    final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
+    for (int i = 0; i < fieldSuppliers.length; i++) {
+      final ColumnValueSelector<?> selector =
+          frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
+      fieldSuppliers[i] = selector::getObject;
+    }
+    rowSupplierFromFrameCursor = () -> {
+      final ResultRow row = ResultRow.create(fieldSuppliers.length);
+      for (int i = 0; i < fieldSuppliers.length; i++) {
+        row.set(i, fieldSuppliers[i].get());
+      }
+      return row;
+    };
+  }
+
+  /**
+   * This method is responsible for the logic of batching the PARTITION BY keys.
+   * If we can add the current rows (currentBatchOfRacs) to the rows pending processing (batchOfRacsPendingProcessing) without violating the maxRowsMaterialized constraint, do it.
+   * If we cannot, we process the rows pending processing (batchOfRacsPendingProcessing), and add the current rows to it which would then be processed in future.
+   */
+  private void processBatchOfRacsPendingProcessingIfNeeded()
+  {
+    if (currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized) {
+      processBatchOfRacsPendingProcessing();
+    }
+
+    batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);

Review Comment:
   On further thoughts, we can change the approach to use a single Arraylist, and maintain the last PARTITION BY boundary index, and add a new method `MapOfColumnsRowsAndColumns.fromResultRowTillIndex()` so that we don't have to separately create the sublist to pass to `MapOfColumnsRowsAndColumns.fromResultRow()`.
   
   I ended up making the changes locally for this, the diff looks like the following:
   
   ```diff
   diff --git a/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java b/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java
   index 9945274bc5..54018893cc 100644
   --- a/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java
   +++ b/extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java
   @@ -94,13 +94,8 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
      // Type strategies are pushed in the same order as column types in frameReader.signature()
      private final NullableTypeStrategy[] typeStrategies;
    
   -  // currentBatchOfRacs holds the current rows being read from the frame.
   -  private final ArrayList<ResultRow> currentBatchOfRacs;
   -
   -  // batchOfRacsPendingProcessing holds the rows read from the frame that are pending processing.
   -  // These get processed when we either reach the end of input channel, or when we meet the criteria in shouldProcessPendingBatch() method.
   -  // Until then, this accumulates rows from currentBatchOfRacs.
   -  private final ArrayList<ResultRow> batchOfRacsPendingProcessing;
   +  private final ArrayList<ResultRow> rowsToProcess;
   +  private int lastPartitionIndex = 0;
    
      public WindowOperatorQueryFrameProcessor(
          WindowOperatorQuery query,
   @@ -123,8 +118,7 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
        this.query = query;
        this.frameRowsAndCols = new ArrayList<>();
        this.resultRowAndCols = new ArrayList<>();
   -    this.currentBatchOfRacs = new ArrayList<>();
   -    this.batchOfRacsPendingProcessing = new ArrayList<>();
   +    this.rowsToProcess = new ArrayList<>();
        this.maxRowsMaterialized = maxRowsMaterializedInWindow;
        this.partitionColumnNames = partitionColumnNames;
    
   @@ -244,8 +238,8 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
            makeRowSupplierFromFrameCursor();
          } else if (inputChannel.isFinished()) {
            // Handle any remaining data.
   -        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
   -        processBatchOfRacsPendingProcessing();
   +        lastPartitionIndex = rowsToProcess.size();
   +        processRowsUpToLastPartition();
            return ReturnOrAwait.returnObject(Unit.instance());
          } else {
            return ReturnOrAwait.runAgain();
   @@ -256,20 +250,16 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
          final ResultRow currentRow = rowSupplierFromFrameCursor.get();
          if (outputRow == null) {
            outputRow = currentRow;
   -        currentBatchOfRacs.add(currentRow);
   +        rowsToProcess.add(currentRow);
          } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
            // Add current row to the same batch of rows for processing.
   -        currentBatchOfRacs.add(currentRow);
   -        ensureMaxRowsInAWindowConstraint(currentBatchOfRacs.size());
   -        if (shouldProcessPendingBatch()) {
   +        rowsToProcess.add(currentRow);
   +        if (rowsToProcess.size() > maxRowsMaterialized) {
              // We don't want to materialize more than maxRowsMaterialized rows at any point in time, so process the pending batch.
   -          processBatchOfRacsPendingProcessing();
   +          processRowsUpToLastPartition();
            }
          } else {
   -        if (shouldProcessPendingBatch()) {
   -          processBatchOfRacsPendingProcessing();
   -        }
   -        copyAndClearCurrentBatch();
   +        lastPartitionIndex = rowsToProcess.size();
            outputRow = currentRow.copy();
            return ReturnOrAwait.runAgain();
          }
   @@ -486,35 +476,6 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
        };
      }
    
   -  /**
   -   * Process {@link #batchOfRacsPendingProcessing}.
   -   */
   -  private void processBatchOfRacsPendingProcessing()
   -  {
   -    if (batchOfRacsPendingProcessing.isEmpty()) {
   -      return;
   -    }
   -    RowsAndColumns singleRac = MapOfColumnsRowsAndColumns.fromResultRow(
   -        batchOfRacsPendingProcessing,
   -        frameReader.signature()
   -    );
   -    ArrayList<RowsAndColumns> rowsAndColumns = new ArrayList<>();
   -    rowsAndColumns.add(singleRac);
   -    runAllOpsOnMultipleRac(rowsAndColumns);
   -    batchOfRacsPendingProcessing.clear();
   -  }
   -
   -  private boolean shouldProcessPendingBatch()
   -  {
   -    return currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized;
   -  }
   -
   -  private void copyAndClearCurrentBatch()
   -  {
   -    batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
   -    currentBatchOfRacs.clear();
   -  }
   -
      private void ensureMaxRowsInAWindowConstraint(int numRowsInWindow)
      {
        if (numRowsInWindow > maxRowsMaterialized) {
   @@ -524,4 +485,22 @@ public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
          ));
        }
      }
   +
   +  private void processRowsUpToLastPartition() {
   +    if (lastPartitionIndex == 0) {
   +      return;
   +    }
   +
   +    RowsAndColumns singleRac = MapOfColumnsRowsAndColumns.fromResultRowTillIndex(
   +        rowsToProcess,
   +        frameReader.signature(),
   +        lastPartitionIndex
   +    );
   +    ArrayList<RowsAndColumns> rowsAndColumns = new ArrayList<>();
   +    rowsAndColumns.add(singleRac);
   +    runAllOpsOnMultipleRac(rowsAndColumns);
   +
   +    rowsToProcess.subList(0, lastPartitionIndex).clear();
   +    lastPartitionIndex = 0;
   +  }
    }
   diff --git a/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java b/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java
   index 42972f9340..3443166c0f 100644
   --- a/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java
   +++ b/processing/src/main/java/org/apache/druid/query/rowsandcols/MapOfColumnsRowsAndColumns.java
   @@ -84,11 +84,16 @@ public class MapOfColumnsRowsAndColumns implements RowsAndColumns
      }
    
      public static MapOfColumnsRowsAndColumns fromResultRow(ArrayList<ResultRow> objs, RowSignature signature)
   +  {
   +    return fromResultRowTillIndex(objs, signature, objs.size());
   +  }
   +
   +  public static MapOfColumnsRowsAndColumns fromResultRowTillIndex(ArrayList<ResultRow> objs, RowSignature signature, int index)
      {
        final Builder bob = builder();
        if (!objs.isEmpty()) {
   -      Object[][] columnOriented = new Object[objs.get(0).length()][objs.size()];
   -      for (int i = 0; i < objs.size(); ++i) {
   +      Object[][] columnOriented = new Object[objs.get(0).length()][index];
   +      for (int i = 0; i < index; ++i) {
            for (int j = 0; j < objs.get(i).length(); ++j) {
              columnOriented[j][i] = objs.get(i).get(j);
            }
   
   ```
   
   All tests pass with the above diff. Let me know if this approach seems better to you compared to the current changes of the PR, I just need to update some comments before pushing this to the PR.



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1729870393


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***
+
+     In this scenario, we need to process rows for each PARTITION BY group together, but we can batch multiple PARTITION BY keys into the same RAC before passing it to the operators for processing.
+     Batching is fine since the operators list would have the required NaivePartitioningOperatorFactory to segregate each PARTITION BY group during the processing.
+
+     The flow for this scenario can be summarised as following:
+     1. Frame Reading and Cursor Initialization: We start by reading a frame from the inputChannel and initializing frameCursor to iterate over the rows in that frame.
+     2. Row Comparison: For each row in the frame, we decide whether it belongs to the same PARTITION BY group as the previous row.
+                        This is determined by comparePartitionKeys() method.
+                        Please refer to the Javadoc of that method for further details and an example illustration.
+        2.1. If the PARTITION BY columns of current row matches the PARTITION BY columns of the previous row,
+             they belong to the same PARTITION BY group, and gets added to currentBatchOfRacs.
+             If the number of total rows materialized exceed maxRowsMaterialized, we process the pending batch via processBatchOfRacsPendingProcessing() method.
+        2.2. If they don't match, then we have reached a partition boundary.
+             In this case, we process the rows so far *if needed* via processBatchOfRacsPendingProcessingIfNeeded() method.
+             Please refer to the Javadoc of that method for further details.
+     3. End of Input: If the input channel is finished, any remaining rows in currentBatchOfRacs are processed.
+
+     *Illustration of Row Comparison step*
+
+     Let's say we have window_function() OVER (PARTITION BY A ORDER BY B) in our query, and we get 3 frames in the input channel to process.
+
+     Frame 1
+     A, B
+     1, 2
+     1, 3
+     2, 1 --> PARTITION BY key (column A) changed from 1 to 2.
+     2, 2
+
+     Frame 2
+     A, B
+     3, 1 --> PARTITION BY key (column A) changed from 2 to 3.
+     3, 2
+     3, 3
+     3, 4
+
+     Frame 3
+     A, B
+     3, 5
+     3, 6
+     4, 1 --> PARTITION BY key (column A) changed from 3 to 4.
+     4, 2
+
+     *Why batching?*
+     We batch multiple PARTITION BY keys for processing together to avoid the overhead of creating different RACs for each PARTITION BY keys, as that would be unnecessary in scenarios where we have a large number of PARTITION BY keys, but each key having a single row.
+
+     *Future thoughts: https://github.com/apache/druid/issues/16126*
+     Current approach with R&C and operators materialize a single R&C for processing. In case of data with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause.
+     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data. We might think to reimplement them in the MSQ way so that we do not have to materialize so much data.
      */
 
     if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
+      // Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY.
       if (inputChannel.canRead()) {
         final Frame frame = inputChannel.read();
         convertRowFrameToRowsAndColumns(frame);
+        return ReturnOrAwait.runAgain();
       } else if (inputChannel.isFinished()) {
         runAllOpsOnMultipleRac(frameRowsAndCols);
         return ReturnOrAwait.returnObject(Unit.instance());
       } else {
         return ReturnOrAwait.awaitAll(inputChannels().size());
       }
-      return ReturnOrAwait.runAgain();
-    } else {
-      // Aha, you found a PARTITION BY and maybe ORDER BY TO
-      // PARTITION BY can also be on multiple keys
-      // typically the last stage would already partition and sort for you
-      // figure out frame boundaries and convert each distinct group to a rac
-      // then run the windowing operator only on each rac
-      if (frameCursor == null || frameCursor.isDone()) {
-        if (readableInputs.isEmpty()) {
-          return ReturnOrAwait.awaitAll(1);
-        } else if (inputChannel.canRead()) {
-          final Frame frame = inputChannel.read();
-          frameCursor = FrameProcessors.makeCursor(frame, frameReader);
-          final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
-          final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
-          for (int i = 0; i < fieldSuppliers.length; i++) {
-            final ColumnValueSelector<?> selector =
-                frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
-            fieldSuppliers[i] = selector::getObject;
-
-          }
-          rowSupplierFromFrameCursor = () -> {
-            final ResultRow row = ResultRow.create(fieldSuppliers.length);
-            for (int i = 0; i < fieldSuppliers.length; i++) {
-              row.set(i, fieldSuppliers[i].get());
-            }
-            return row;
-          };
-        } else if (inputChannel.isFinished()) {
-          // reaached end of channel
-          // if there is data remaining
-          // write it into a rac
-          // and run operators on it
-          if (!objectsOfASingleRac.isEmpty()) {
-            if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-              throw new MSQException(new TooManyRowsInAWindowFault(objectsOfASingleRac.size(), maxRowsMaterialized));
-            }
-            RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-                objectsOfASingleRac,
-                frameReader.signature()
-            );
-            runAllOpsOnSingleRac(rac);
-            objectsOfASingleRac.clear();
-          }
-          return ReturnOrAwait.returnObject(Unit.instance());
-        } else {
-          return ReturnOrAwait.runAgain();
-        }
-      }
-      while (!frameCursor.isDone()) {
-        final ResultRow currentRow = rowSupplierFromFrameCursor.get();
-        if (outputRow == null) {
-          outputRow = currentRow;
-          objectsOfASingleRac.add(currentRow);
-        } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
-          // if they have the same partition key
-          // keep adding them after checking
-          // guardrails
-          objectsOfASingleRac.add(currentRow);
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-        } else {
-          // key change noted
-          // create rac from the rows seen before
-          // run the operators on these rows and columns
-          // clean up the object to hold the new rows only
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-          RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-              objectsOfASingleRac,
-              frameReader.signature()
-          );
-          runAllOpsOnSingleRac(rac);
-          objectsOfASingleRac.clear();
-          outputRow = currentRow.copy();
-          return ReturnOrAwait.runAgain();
-        }
-        frameCursor.advance();
+    }
+
+    // Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY
+    if (frameCursor == null || frameCursor.isDone()) {
+      if (readableInputs.isEmpty()) {
+        return ReturnOrAwait.awaitAll(1);
+      } else if (inputChannel.canRead()) {
+        final Frame frame = inputChannel.read();
+        frameCursor = FrameProcessors.makeCursor(frame, frameReader);
+        makeRowSupplierFromFrameCursor();
+      } else if (inputChannel.isFinished()) {
+        // Handle any remaining data.
+        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
+        processBatchOfRacsPendingProcessing();
+        return ReturnOrAwait.returnObject(Unit.instance());
+      } else {
+        return ReturnOrAwait.runAgain();
       }
     }
-    return ReturnOrAwait.runAgain();
-  }
 
-  /**
-   * @param singleRac Use this {@link RowsAndColumns} as a single input for the operators to be run
-   */
-  private void runAllOpsOnSingleRac(RowsAndColumns singleRac)
-  {
-    Operator op = new Operator()
-    {
-      @Nullable
-      @Override
-      public Closeable goOrContinue(Closeable continuationObject, Receiver receiver)
-      {
-        receiver.push(singleRac);
-        if (singleRac.numRows() > maxRowsMaterialized) {
-          throw new MSQException(new TooManyRowsInAWindowFault(singleRac.numRows(), maxRowsMaterialized));
+    while (!frameCursor.isDone()) {
+      final ResultRow currentRow = rowSupplierFromFrameCursor.get();
+      if (outputRow == null) {
+        outputRow = currentRow;
+        currentBatchOfRacs.add(currentRow);
+      } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
+        // Add current row to the same batch of rows for processing.
+        currentBatchOfRacs.add(currentRow);
+        ensureMaxRowsInAWindowConstraint(currentBatchOfRacs.size());
+        if (currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized) {
+          // We don't want to materialize more than maxRowsMaterialized rows at any point in time, so process the pending batch.
+          processBatchOfRacsPendingProcessing();

Review Comment:
   I've made the change to remove `processBatchOfRacsPendingProcessingIfNeeded()` method with `shouldProcessPendingBatch() + copyAndClearCurrentBatch()` methods.
   
   > is there an approach where we can avoid this. Swapping buffers maybe
   
   Responding to this on the [other comment](https://github.com/apache/druid/pull/16823#discussion_r1729793692).
   
   



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "kgyrtkirk (via GitHub)" <gi...@apache.org>.
kgyrtkirk commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1711003916


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -56,8 +58,10 @@
 public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
 {
   private static final Logger log = new Logger(WindowOperatorQueryFrameProcessor.class);
+  private final WindowOperatorQuery query;
 
   private final List<OperatorFactory> operatorFactoryList;
+  private final ObjectMapper jsonMapper;

Review Comment:
   why add these back? they are unused



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] Simplify WindowOperatorQueryFrameProcessor to run all operators on entire partition (druid)

Posted by "kgyrtkirk (via GitHub)" <gi...@apache.org>.
kgyrtkirk commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1711023562


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -56,8 +58,10 @@
 public class WindowOperatorQueryFrameProcessor implements FrameProcessor<Object>
 {
   private static final Logger log = new Logger(WindowOperatorQueryFrameProcessor.class);
+  private final WindowOperatorQuery query;
 
   private final List<OperatorFactory> operatorFactoryList;
+  private final ObjectMapper jsonMapper;

Review Comment:
   please remove it and add back later if needed ; I think the approach in that PR should be altered...



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org


Re: [PR] MSQ WF: Batch multiple PARTITION BY keys for processing (druid)

Posted by "Akshat-Jain (via GitHub)" <gi...@apache.org>.
Akshat-Jain commented on code in PR #16823:
URL: https://github.com/apache/druid/pull/16823#discussion_r1730761433


##########
extensions-core/multi-stage-query/src/main/java/org/apache/druid/msq/querykit/WindowOperatorQueryFrameProcessor.java:
##########
@@ -153,188 +161,118 @@ public List<WritableFrameChannel> outputChannels()
   public ReturnOrAwait<Object> runIncrementally(IntSet readableInputs)
   {
     /*
-     *
-     * PARTITION BY A ORDER BY B
-     *
-     * Frame 1   -> rac1
-     * A  B
-     * 1, 2
-     * 1, 3
-     * 2, 1 --> key changed
-     * 2, 2
-     *
-     *
-     * Frame 2 -> rac2
-     * 3, 1 --> key changed
-     * 3, 2
-     * 3, 3
-     * 3, 4
-     *
-     * Frame 3 -> rac3
-     *
-     * 3, 5
-     * 3, 6
-     * 4, 1 --> key changed
-     * 4, 2
-     *
-     * In case of empty OVER clause, all these racs need to be added to a single rows and columns
-     * to be processed. The way we can do this is to use a ConcatRowsAndColumns
-     * ConcatRC [rac1, rac2, rac3]
-     * Run all ops on this
-     *
-     *
-     * The flow would look like:
-     * 1. Validate if the operator doesn't have any OVER() clause with PARTITION BY for this stage.
-     * 2. If 1 is true make a giant rows and columns (R&C) using concat as shown above
-     *    Let all operators run amok on that R&C
-     * 3. If 1 is false
-     *    Read a frame
-     *    keep the older row in a class variable
-     *    check row by row and compare current with older row to check if partition boundary is reached
-     *    when frame partition by changes
-     *    create R&C for those particular set of columns, they would have the same partition key
-     *    output will be a single R&C
-     *    write to output channel
-     *
-     *
-     *  Future thoughts: {@link https://github.com/apache/druid/issues/16126}
-     *
-     *  1. We are writing 1 partition to each frame in this way. In case of high cardinality data
-     *      we will be making a large number of small frames. We can have a check to keep size of frame to a value
-     *      say 20k rows and keep on adding to the same pending frame and not create a new frame
-     *
-     *  2. Current approach with R&C and operators materialize a single R&C for processing. In case of data
-     *     with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause
-     *     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data.
-     *     We might think to reimplement them in the MSQ way so that we do not have to materialize so much data
+     There are 2 scenarios:
+
+     *** Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY ***
+
+     In this scenario, we add all the RACs to a single RowsAndColumns to be processed. We do it via ConcatRowsAndColumns, and run all the operators on the ConcatRowsAndColumns.
+     This is done because we anyway need to run the operators on the entire set of rows when we have an OVER() clause without a PARTITION BY.
+     This scenario corresponds to partitionColumnNames.isEmpty()=true code flow.
+
+     *** Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY ***
+
+     In this scenario, we need to process rows for each PARTITION BY group together, but we can batch multiple PARTITION BY keys into the same RAC before passing it to the operators for processing.
+     Batching is fine since the operators list would have the required NaivePartitioningOperatorFactory to segregate each PARTITION BY group during the processing.
+
+     The flow for this scenario can be summarised as following:
+     1. Frame Reading and Cursor Initialization: We start by reading a frame from the inputChannel and initializing frameCursor to iterate over the rows in that frame.
+     2. Row Comparison: For each row in the frame, we decide whether it belongs to the same PARTITION BY group as the previous row.
+                        This is determined by comparePartitionKeys() method.
+                        Please refer to the Javadoc of that method for further details and an example illustration.
+        2.1. If the PARTITION BY columns of current row matches the PARTITION BY columns of the previous row,
+             they belong to the same PARTITION BY group, and gets added to currentBatchOfRacs.
+             If the number of total rows materialized exceed maxRowsMaterialized, we process the pending batch via processBatchOfRacsPendingProcessing() method.
+        2.2. If they don't match, then we have reached a partition boundary.
+             In this case, we process the rows so far *if needed* via processBatchOfRacsPendingProcessingIfNeeded() method.
+             Please refer to the Javadoc of that method for further details.
+     3. End of Input: If the input channel is finished, any remaining rows in currentBatchOfRacs are processed.
+
+     *Illustration of Row Comparison step*
+
+     Let's say we have window_function() OVER (PARTITION BY A ORDER BY B) in our query, and we get 3 frames in the input channel to process.
+
+     Frame 1
+     A, B
+     1, 2
+     1, 3
+     2, 1 --> PARTITION BY key (column A) changed from 1 to 2.
+     2, 2
+
+     Frame 2
+     A, B
+     3, 1 --> PARTITION BY key (column A) changed from 2 to 3.
+     3, 2
+     3, 3
+     3, 4
+
+     Frame 3
+     A, B
+     3, 5
+     3, 6
+     4, 1 --> PARTITION BY key (column A) changed from 3 to 4.
+     4, 2
+
+     *Why batching?*
+     We batch multiple PARTITION BY keys for processing together to avoid the overhead of creating different RACs for each PARTITION BY keys, as that would be unnecessary in scenarios where we have a large number of PARTITION BY keys, but each key having a single row.
+
+     *Future thoughts: https://github.com/apache/druid/issues/16126*
+     Current approach with R&C and operators materialize a single R&C for processing. In case of data with low cardinality a single R&C might be too big to consume. Same for the case of empty OVER() clause.
+     Most of the window operations like SUM(), RANK(), RANGE() etc. can be made with 2 passes of the data. We might think to reimplement them in the MSQ way so that we do not have to materialize so much data.
      */
 
     if (partitionColumnNames.isEmpty()) {
-      // If we do not have any OVER() clause with PARTITION BY for this stage.
-      // Bring all data to a single executor for processing.
-      // Convert each frame to RAC.
-      // Concatenate all the racs to make a giant RAC.
-      // Let all operators run on the giant RAC until channel is finished.
+      // Scenario 1: Query has atleast one window function with an OVER() clause without a PARTITION BY.
       if (inputChannel.canRead()) {
         final Frame frame = inputChannel.read();
         convertRowFrameToRowsAndColumns(frame);
+        return ReturnOrAwait.runAgain();
       } else if (inputChannel.isFinished()) {
         runAllOpsOnMultipleRac(frameRowsAndCols);
         return ReturnOrAwait.returnObject(Unit.instance());
       } else {
         return ReturnOrAwait.awaitAll(inputChannels().size());
       }
-      return ReturnOrAwait.runAgain();
-    } else {
-      // Aha, you found a PARTITION BY and maybe ORDER BY TO
-      // PARTITION BY can also be on multiple keys
-      // typically the last stage would already partition and sort for you
-      // figure out frame boundaries and convert each distinct group to a rac
-      // then run the windowing operator only on each rac
-      if (frameCursor == null || frameCursor.isDone()) {
-        if (readableInputs.isEmpty()) {
-          return ReturnOrAwait.awaitAll(1);
-        } else if (inputChannel.canRead()) {
-          final Frame frame = inputChannel.read();
-          frameCursor = FrameProcessors.makeCursor(frame, frameReader);
-          final ColumnSelectorFactory frameColumnSelectorFactory = frameCursor.getColumnSelectorFactory();
-          final Supplier<Object>[] fieldSuppliers = new Supplier[frameReader.signature().size()];
-          for (int i = 0; i < fieldSuppliers.length; i++) {
-            final ColumnValueSelector<?> selector =
-                frameColumnSelectorFactory.makeColumnValueSelector(frameReader.signature().getColumnName(i));
-            fieldSuppliers[i] = selector::getObject;
-
-          }
-          rowSupplierFromFrameCursor = () -> {
-            final ResultRow row = ResultRow.create(fieldSuppliers.length);
-            for (int i = 0; i < fieldSuppliers.length; i++) {
-              row.set(i, fieldSuppliers[i].get());
-            }
-            return row;
-          };
-        } else if (inputChannel.isFinished()) {
-          // reaached end of channel
-          // if there is data remaining
-          // write it into a rac
-          // and run operators on it
-          if (!objectsOfASingleRac.isEmpty()) {
-            if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-              throw new MSQException(new TooManyRowsInAWindowFault(objectsOfASingleRac.size(), maxRowsMaterialized));
-            }
-            RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-                objectsOfASingleRac,
-                frameReader.signature()
-            );
-            runAllOpsOnSingleRac(rac);
-            objectsOfASingleRac.clear();
-          }
-          return ReturnOrAwait.returnObject(Unit.instance());
-        } else {
-          return ReturnOrAwait.runAgain();
-        }
-      }
-      while (!frameCursor.isDone()) {
-        final ResultRow currentRow = rowSupplierFromFrameCursor.get();
-        if (outputRow == null) {
-          outputRow = currentRow;
-          objectsOfASingleRac.add(currentRow);
-        } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
-          // if they have the same partition key
-          // keep adding them after checking
-          // guardrails
-          objectsOfASingleRac.add(currentRow);
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-        } else {
-          // key change noted
-          // create rac from the rows seen before
-          // run the operators on these rows and columns
-          // clean up the object to hold the new rows only
-          if (objectsOfASingleRac.size() > maxRowsMaterialized) {
-            throw new MSQException(new TooManyRowsInAWindowFault(
-                objectsOfASingleRac.size(),
-                maxRowsMaterialized
-            ));
-          }
-          RowsAndColumns rac = MapOfColumnsRowsAndColumns.fromResultRow(
-              objectsOfASingleRac,
-              frameReader.signature()
-          );
-          runAllOpsOnSingleRac(rac);
-          objectsOfASingleRac.clear();
-          outputRow = currentRow.copy();
-          return ReturnOrAwait.runAgain();
-        }
-        frameCursor.advance();
+    }
+
+    // Scenario 2: All window functions in the query have OVER() clause with a PARTITION BY
+    if (frameCursor == null || frameCursor.isDone()) {
+      if (readableInputs.isEmpty()) {
+        return ReturnOrAwait.awaitAll(1);
+      } else if (inputChannel.canRead()) {
+        final Frame frame = inputChannel.read();
+        frameCursor = FrameProcessors.makeCursor(frame, frameReader);
+        makeRowSupplierFromFrameCursor();
+      } else if (inputChannel.isFinished()) {
+        // Handle any remaining data.
+        batchOfRacsPendingProcessing.addAll(currentBatchOfRacs);
+        processBatchOfRacsPendingProcessing();
+        return ReturnOrAwait.returnObject(Unit.instance());
+      } else {
+        return ReturnOrAwait.runAgain();
       }
     }
-    return ReturnOrAwait.runAgain();
-  }
 
-  /**
-   * @param singleRac Use this {@link RowsAndColumns} as a single input for the operators to be run
-   */
-  private void runAllOpsOnSingleRac(RowsAndColumns singleRac)
-  {
-    Operator op = new Operator()
-    {
-      @Nullable
-      @Override
-      public Closeable goOrContinue(Closeable continuationObject, Receiver receiver)
-      {
-        receiver.push(singleRac);
-        if (singleRac.numRows() > maxRowsMaterialized) {
-          throw new MSQException(new TooManyRowsInAWindowFault(singleRac.numRows(), maxRowsMaterialized));
+    while (!frameCursor.isDone()) {
+      final ResultRow currentRow = rowSupplierFromFrameCursor.get();
+      if (outputRow == null) {
+        outputRow = currentRow;
+        currentBatchOfRacs.add(currentRow);
+      } else if (comparePartitionKeys(outputRow, currentRow, partitionColumnNames)) {
+        // Add current row to the same batch of rows for processing.
+        currentBatchOfRacs.add(currentRow);
+        ensureMaxRowsInAWindowConstraint(currentBatchOfRacs.size());
+        if (currentBatchOfRacs.size() + batchOfRacsPendingProcessing.size() > maxRowsMaterialized) {
+          // We don't want to materialize more than maxRowsMaterialized rows at any point in time, so process the pending batch.
+          processBatchOfRacsPendingProcessing();

Review Comment:
   Closing this comment as it's not relevant anymore with the latest changes.



-- 
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: commits-unsubscribe@druid.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org