You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by GitBox <gi...@apache.org> on 2022/03/01 02:31:58 UTC

[GitHub] [druid] clintropolis opened a new pull request #12291: add topn heap optimization when string is dictionary encoded, but not uniquely

clintropolis opened a new pull request #12291:
URL: https://github.com/apache/druid/pull/12291


   ### Description
   This PR adds an additional optimization to `StringTopNColumnAggregatesProcessor`, the string processor used for heap based topN, for the case where a column is dictionary encoded, but not uniquely, and adds a cache of dictionaryId to `Aggregate[]` so avoid duplicate decoding of `utf8` bytes from the segment or recomputing expression virtual columns that occur on lookupName in some types of expression selectors.
   
   The existing topn tests should provide adequate coverage for this change, but will confirm this with the coverage bot once it runs in travis.
   
   This PR has:
   - [x] been self-reviewed.
   - [x] added Javadocs for most classes and all non-trivial methods. Linked related entities via Javadoc links.
   


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


[GitHub] [druid] clintropolis commented on pull request #12291: add topn heap optimization when string is dictionary encoded, but not uniquely

Posted by GitBox <gi...@apache.org>.
clintropolis commented on pull request #12291:
URL: https://github.com/apache/druid/pull/12291#issuecomment-1054990097


   >The existing topn tests should provide adequate coverage for this change, but will confirm this with the coverage bot once it runs in travis.
   
   [It looks like I was right:](https://app.travis-ci.com/github/apache/druid/jobs/561537298#L2110)
   
   ```
   Total diff coverage:
    - lines: 100% (24/24)
    - branches: 100% (16/16)
    - functions: 100% (2/2)
   ```


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


[GitHub] [druid] gianm commented on pull request #12291: adjust topn heap operation when string is dictionary encoded, but not uniquely

Posted by GitBox <gi...@apache.org>.
gianm commented on pull request #12291:
URL: https://github.com/apache/druid/pull/12291#issuecomment-1062035054


   I'm trying to understand where we'd be after this patch. What algorithm will be used in each of the following cases?
   
   - string dimension, no dictionary <-- i.e., what we get from an expression that isn't backed by a single dictionary-coded string column
   - string dimension, dictionary coded, unique (1-1 mapping from keys -> values) <-- i.e., what we get from a regular column in a segment, or a dictionary-coded string column plus an ExtractionFn that is `ONE_TO_ONE`
   - string dimension, dictionary coded, nonunique <-- i.e., what we get from an expression backed by a single dictionary-coded string column, or a dictionary-coded string column plus an ExtractionFn that is `MANY_TO_ONE`


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


[GitHub] [druid] gianm edited a comment on pull request #12291: adjust topn heap operation when string is dictionary encoded, but not uniquely

Posted by GitBox <gi...@apache.org>.
gianm edited a comment on pull request #12291:
URL: https://github.com/apache/druid/pull/12291#issuecomment-1062035054






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


[GitHub] [druid] clintropolis commented on pull request #12291: adjust topn heap operation when string is dictionary encoded, but not uniquely

Posted by GitBox <gi...@apache.org>.
clintropolis commented on pull request #12291:
URL: https://github.com/apache/druid/pull/12291#issuecomment-1062142843


   > * string dimension, no dictionary <-- i.e., what we get from an expression that isn't backed by a single dictionary-coded string column
   
   this one uses scanAndAggregateWithCardinalityUnknown because those columns which are  `1:*` or `*:*` should not report themselves as dictionary encoded/name lookup possible in advance
   
   > * string dimension, dictionary coded, unique (1-1 mapping from keys -> values) <-- i.e., what we get from a regular column in a segment, or a dictionary-coded string column plus an ExtractionFn that is ONE_TO_ONE
   > * string dimension, dictionary coded, nonunique <-- i.e., what we get from an expression backed by a single dictionary-coded string column, or a dictionary-coded string column plus an ExtractionFn that is MANY_TO_ONE, or an IndexedTable
   
   these two cases use `scanAndAggregateWithCardinalityKnown`, prior to this patch the latter case used `scanAndAggregateWithCardinalityUnknown`, which is better for `IndexedTable` (since the dictionaryIds never repeat so always has to still perform the value lookupName and hash table lookup), but far worse for expressions and lookups, which never report their dictionaries as unique currently and potentially have many repeated dictionary ids.
   
   Should I do something to clear up the javadocs?


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


[GitHub] [druid] gianm commented on pull request #12291: adjust topn heap operation when string is dictionary encoded, but not uniquely

Posted by GitBox <gi...@apache.org>.
gianm commented on pull request #12291:
URL: https://github.com/apache/druid/pull/12291#issuecomment-1062287227


   > Which cases use HeapBasedTopNAlgorithm and which use PooledTopNAlgorithm?
   
   I realized this code is all in the context of HeapBasedTopNAlgorithm. It looks good to me.


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


[GitHub] [druid] clintropolis commented on a change in pull request #12291: add topn heap optimization when string is dictionary encoded, but not uniquely

Posted by GitBox <gi...@apache.org>.
clintropolis commented on a change in pull request #12291:
URL: https://github.com/apache/druid/pull/12291#discussion_r816448406



##########
File path: processing/src/main/java/org/apache/druid/query/topn/types/StringTopNColumnAggregatesProcessor.java
##########
@@ -172,6 +180,54 @@ private long scanAndAggregateWithCardinalityKnown(
     return processedRows;
   }
 
+  /**
+   * this method uses hash table to store aggregate values ({@link #aggregatesStore}) and is geared towards selectors
+   * which have a dictionary, but those dictionary ids do not necessarily uniquely map to the value of
+   * {@link DimensionSelector#lookupName(int)}. This method keeps a cache of dictionary id to aggregators, which it uses
+   * to skip name lookup if that id has already been encountered, avoiding decoding utf8 bytes, or worse, recomputing
+   * an expression virtual column or some lookup value.
+   *
+   */
+  private long scanAndAggregateWithDictionary(
+      TopNQuery query,
+      Cursor cursor,
+      DimensionSelector selector
+  )
+  {
+    Int2ObjectOpenHashMap<Aggregator[]> aggsCache = new Int2ObjectOpenHashMap<>();

Review comment:
       yeah, that should work :+1:




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


[GitHub] [druid] gianm edited a comment on pull request #12291: adjust topn heap operation when string is dictionary encoded, but not uniquely

Posted by GitBox <gi...@apache.org>.
gianm edited a comment on pull request #12291:
URL: https://github.com/apache/druid/pull/12291#issuecomment-1062035054


   I'm trying to understand where we'd be after this patch. What algorithm will be used in each of the following cases?
   
   - string dimension, no dictionary <-- i.e., what we get from an expression that isn't backed by a single dictionary-coded string column
   - string dimension, dictionary coded, unique (1-1 mapping from keys -> values) <-- i.e., what we get from a regular column in a segment, or a dictionary-coded string column plus an ExtractionFn that is `ONE_TO_ONE`
   - string dimension, dictionary coded, nonunique <-- i.e., what we get from an expression backed by a single dictionary-coded string column, or a dictionary-coded string column plus an ExtractionFn that is `MANY_TO_ONE`, or an IndexedTable


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


[GitHub] [druid] clintropolis commented on pull request #12291: add topn heap optimization when string is dictionary encoded, but not uniquely

Posted by GitBox <gi...@apache.org>.
clintropolis commented on pull request #12291:
URL: https://github.com/apache/druid/pull/12291#issuecomment-1056079563


   heh, this is basically reverting #11186, will try to find a way to better handle `IndexedTable` in future work


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


[GitHub] [druid] imply-cheddar commented on a change in pull request #12291: add topn heap optimization when string is dictionary encoded, but not uniquely

Posted by GitBox <gi...@apache.org>.
imply-cheddar commented on a change in pull request #12291:
URL: https://github.com/apache/druid/pull/12291#discussion_r816443116



##########
File path: processing/src/main/java/org/apache/druid/query/topn/types/StringTopNColumnAggregatesProcessor.java
##########
@@ -172,6 +180,54 @@ private long scanAndAggregateWithCardinalityKnown(
     return processedRows;
   }
 
+  /**
+   * this method uses hash table to store aggregate values ({@link #aggregatesStore}) and is geared towards selectors
+   * which have a dictionary, but those dictionary ids do not necessarily uniquely map to the value of
+   * {@link DimensionSelector#lookupName(int)}. This method keeps a cache of dictionary id to aggregators, which it uses
+   * to skip name lookup if that id has already been encountered, avoiding decoding utf8 bytes, or worse, recomputing
+   * an expression virtual column or some lookup value.
+   *
+   */
+  private long scanAndAggregateWithDictionary(
+      TopNQuery query,
+      Cursor cursor,
+      DimensionSelector selector
+  )
+  {
+    Int2ObjectOpenHashMap<Aggregator[]> aggsCache = new Int2ObjectOpenHashMap<>();

Review comment:
       With the test for `hasDictionary` we could perhaps make this
   
   ```
   Aggregator[][] aggsCache = new Aggregator[selector.getValueCardinality()][];
   ```
   
   ?




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


[GitHub] [druid] gianm merged pull request #12291: adjust topn heap operation when string is dictionary encoded, but not uniquely

Posted by GitBox <gi...@apache.org>.
gianm merged pull request #12291:
URL: https://github.com/apache/druid/pull/12291


   


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


[GitHub] [druid] gianm commented on pull request #12291: adjust topn heap operation when string is dictionary encoded, but not uniquely

Posted by GitBox <gi...@apache.org>.
gianm commented on pull request #12291:
URL: https://github.com/apache/druid/pull/12291#issuecomment-1062228794


   Which cases use HeapBasedTopNAlgorithm and which use PooledTopNAlgorithm?
   
   > Should I do something to clear up the javadocs?
   
   Certainly wouldn't hurt to include a comment in the code that selects the algorithm that describes the rationale for the selection.


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