You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by GitBox <gi...@apache.org> on 2021/02/09 00:16:57 UTC
[GitHub] [incubator-pinot] Jackie-Jiang opened a new pull request #6559: Optimize group-key generator
Jackie-Jiang opened a new pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559
## Description
Optimize the `IntMapBasedHolder` in the `DictionaryBasedGroupKeyGenerator` for better group-by performance on query with group-by columns cardinality product from 10K to 2B.
The improvement (up to ~40%) is mainly from replacing the `Int2IntOpenHashMap` with the new implemented `IntGroupIdMap`. The `IntGroupIdMap` stores both keys and values within a single array so that it is more friendly to CPU cache.
The benchmark result for these 2 map implementations are as followings (with 20 threads):
```
Benchmark (_cardinality) Mode Cnt Score Error Units
BenchmarkIntOpenHashMap.intGroupIdMap 10000 avgt 5 177.478 ± 13.114 ms/op
BenchmarkIntOpenHashMap.intGroupIdMap 20000 avgt 5 192.885 ± 14.417 ms/op
BenchmarkIntOpenHashMap.intGroupIdMap 50000 avgt 5 274.969 ± 20.314 ms/op
BenchmarkIntOpenHashMap.intGroupIdMap 100000 avgt 5 568.092 ± 1.432 ms/op
BenchmarkIntOpenHashMap.intGroupIdMap 150000 avgt 5 720.392 ± 5.983 ms/op
BenchmarkIntOpenHashMap.intOpenHashMap 10000 avgt 5 170.883 ± 5.290 ms/op
BenchmarkIntOpenHashMap.intOpenHashMap 20000 avgt 5 229.085 ± 12.062 ms/op
BenchmarkIntOpenHashMap.intOpenHashMap 50000 avgt 5 377.269 ± 5.762 ms/op
BenchmarkIntOpenHashMap.intOpenHashMap 100000 avgt 5 1001.601 ± 34.179 ms/op
BenchmarkIntOpenHashMap.intOpenHashMap 150000 avgt 5 984.365 ± 17.488 ms/op
```
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] siddharthteotia commented on pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
siddharthteotia commented on pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#issuecomment-777917013
> > I don't think the following 2 changes are needed for the optimization done in this PR.
> > ```
> > private static final int INITIAL_MAP_SIZE = (int) ((1 << 9) * 0.75f);
> > private static final int MAX_CACHING_MAP_SIZE = (int) ((1 << 20) * 0.75f);
> > ```
> >
> >
> > We should be able to keep them to their original values right since the optimization done in this PR for IntGroupId map internally uses the capacity of 4K to align with the page size and is not really dependent on the above 2 changes. Just wondering if the above 2 changes can impact performance in any case. I don't think they are related to this PR.
>
> These 2 changes are just making the value calculation more obvious for readability. Because we use the map size as threshold, we should multiply it by the load factor. There is no performance impact.
Discussed offline with @Jackie-Jiang to clarify this. The difference between this and standard Java hashmap is that in the latter we provide initial capacity and the load factor as the input and then load factor is used to compute the threshold size (expected size) after which resize is triggered.
However, in case of Int2IntOpenHashMap, the expected size should be provided as the input. That's the reason to use the load factor as the multipler.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] Jackie-Jiang commented on a change in pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on a change in pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#discussion_r573381665
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -108,35 +116,35 @@ public DictionaryBasedGroupKeyGenerator(TransformOperator transformOperator, Exp
_isSingleValueColumn[i] = transformOperator.getResultMetadata(groupByExpression).isSingleValue();
}
+ // TODO: Clear the holder after processing the query instead of before
if (longOverflow) {
+ // ArrayMapBasedHolder
_globalGroupIdUpperBound = numGroupsLimit;
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(ArrayMapBasedHolder.class.getName(),
- o -> new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new ArrayMapBasedHolder(mapInternal);
- if (((Object2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
+ Object2IntOpenHashMap<IntArray> groupIdMap = THREAD_LOCAL_INT_ARRAY_MAP.get();
+ int size = groupIdMap.size();
+ groupIdMap.clear();
+ if (size > MAX_CACHING_MAP_SIZE) {
+ groupIdMap.trim();
}
+ _rawKeyHolder = new ArrayMapBasedHolder(groupIdMap);
} else {
if (cardinalityProduct > Integer.MAX_VALUE) {
+ // LongMapBasedHolder
_globalGroupIdUpperBound = numGroupsLimit;
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(LongMapBasedHolder.class.getName(),
- o -> new LongMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new LongMapBasedHolder(mapInternal);
- if (((Long2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
+ Long2IntOpenHashMap groupIdMap = THREAD_LOCAL_LONG_MAP.get();
+ int size = groupIdMap.size();
+ groupIdMap.clear();
+ if (size > MAX_CACHING_MAP_SIZE) {
+ groupIdMap.trim();
}
+ _rawKeyHolder = new LongMapBasedHolder(groupIdMap);
} else {
_globalGroupIdUpperBound = Math.min((int) cardinalityProduct, numGroupsLimit);
if (cardinalityProduct > arrayBasedThreshold) {
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(IntMapBasedHolder.class.getName(),
- o -> new IntMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new IntMapBasedHolder(mapInternal);
- if (((Int2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- }
+ // IntMapBasedHolder
+ IntGroupIdMap groupIdMap = THREAD_LOCAL_INT_MAP.get();
+ groupIdMap.clear();
Review comment:
`trim()` reduces the capacity of the map, but does not clear the map. The `clear()` here handles the logic of clear the map, then check the map capacity and trim it if it is over the caching threshold (as described in the javadoc). We don't want to split this into 2 APIs because that will be more costly. If we need to reduce the capacity, we can directly allocate a new array instead of first clearing the old array.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] Jackie-Jiang commented on a change in pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on a change in pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#discussion_r573384462
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -831,6 +777,156 @@ private String getGroupKey(IntArray rawKey) {
return groupKeyBuilder.toString();
}
+ /**
+ * Fast int-to-int hashmap with {@link #INVALID_ID} as the default return value.
+ * <p>Different from {@link it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap}, this map uses one single array to store
+ * keys and values to reduce the cache miss.
+ */
+ @VisibleForTesting
+ public static class IntGroupIdMap {
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private int[] _keyValueHolder;
+ private int _capacity;
+ private int _mask;
+ private int _maxNumEntries;
+ private int _size;
+
+ public IntGroupIdMap() {
+ _capacity = 1 << 10;
+ int holderSize = _capacity << 1;
+ _keyValueHolder = new int[holderSize];
+ _mask = holderSize - 1;
+ _maxNumEntries = (int) (_capacity * LOAD_FACTOR);
+ }
+
+ public int size() {
+ return _size;
+ }
+
+ /**
+ * Returns the group id for the given raw key. Create a new group id if the raw key does not exist and the group id
+ * upper bound is not reached.
+ */
+ public int getGroupId(int rawKey, int groupIdUpperBound) {
+ // NOTE: Key 0 is reserved as the null key. Use (rawKey + 1) as the internal key because rawKey can never be -1.
+ int internalKey = rawKey + 1;
+ int index = (HashCommon.mix(internalKey) << 1) & _mask;
+ int key = _keyValueHolder[index];
+
+ // Handle hash hit separately for better performance
+ if (key == internalKey) {
+ return _keyValueHolder[index + 1];
+ }
+ if (key == 0) {
+ return _size < groupIdUpperBound ? addNewGroup(internalKey, index) : INVALID_ID;
+ }
+
+ // Hash collision
+ while (true) {
+ index = (index + 2) & _mask;
+ key = _keyValueHolder[index];
+ if (key == internalKey) {
+ return _keyValueHolder[index + 1];
+ }
+ if (key == 0) {
+ return _size < groupIdUpperBound ? addNewGroup(internalKey, index) : INVALID_ID;
+ }
+ }
+ }
+
+ private int addNewGroup(int internalKey, int index) {
+ int groupId = _size++;
+ _keyValueHolder[index] = internalKey;
+ _keyValueHolder[index + 1] = groupId;
+ if (_size > _maxNumEntries) {
+ expand();
+ }
+ return groupId;
+ }
+
+ private void expand() {
+ _capacity <<= 1;
+ int holderSize = _capacity << 1;
+ int[] oldKeyValueHolder = _keyValueHolder;
+ _keyValueHolder = new int[holderSize];
+ _mask = holderSize - 1;
+ _maxNumEntries <<= 1;
+ int oldIndex = 0;
+ for (int i = 0; i < _size; i++) {
+ while (oldKeyValueHolder[oldIndex] == 0) {
+ oldIndex += 2;
+ }
+ int key = oldKeyValueHolder[oldIndex];
+ int value = oldKeyValueHolder[oldIndex + 1];
+ int newIndex = (HashCommon.mix(key) << 1) & _mask;
+ if (_keyValueHolder[newIndex] != 0) {
+ do {
+ newIndex = (newIndex + 2) & _mask;
+ } while (_keyValueHolder[newIndex] != 0);
+ }
+ _keyValueHolder[newIndex] = key;
+ _keyValueHolder[newIndex + 1] = value;
+ oldIndex += 2;
+ }
+ }
+
+ public Iterator<Entry> iterator() {
+ return new Iterator<Entry>() {
+ private final Entry _entry = new Entry();
+ private int _index;
+ private int _numRemainingEntries = _size;
+
+ @Override
+ public boolean hasNext() {
+ return _numRemainingEntries > 0;
+ }
+
+ @Override
+ public Entry next() {
+ int key;
+ while ((key = _keyValueHolder[_index]) == 0) {
+ _index += 2;
+ }
+ _entry._rawKey = key - 1;
+ _entry._groupId = _keyValueHolder[_index + 1];
+ _index += 2;
+ _numRemainingEntries--;
+ return _entry;
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ };
+ }
+
+ /**
Review comment:
It is basically clear + trim if the size is larger than the threshold
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] Jackie-Jiang commented on a change in pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on a change in pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#discussion_r573380233
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -61,8 +61,16 @@
* bounded by the number of groups limit (globalGroupIdUpperBound is always smaller or equal to numGroupsLimit).
*/
public class DictionaryBasedGroupKeyGenerator implements GroupKeyGenerator {
- private final static int INITIAL_MAP_SIZE = 256;
- private final static int MAX_CACHING_MAP_SIZE = 1048576;
+ // NOTE: map size = map capacity (power of 2) * load factor
+ private static final int INITIAL_MAP_SIZE = (int) ((1 << 10) * 0.75f);
+ private static final int MAX_CACHING_MAP_SIZE = (int) ((1 << 20) * 0.75f);
+
+ private static final ThreadLocal<IntGroupIdMap> THREAD_LOCAL_INT_MAP = ThreadLocal.withInitial(IntGroupIdMap::new);
+ private static final ThreadLocal<Long2IntOpenHashMap> THREAD_LOCAL_LONG_MAP =
Review comment:
Yes, but that is not the case for common queries. Also, for long2int map, using a single array will force us to store the value as long, which might consume more memory. This PR is focusing on the most common case of cardinality product between 10k to 2b.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] siddharthteotia commented on a change in pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
siddharthteotia commented on a change in pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#discussion_r573305843
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -61,8 +61,16 @@
* bounded by the number of groups limit (globalGroupIdUpperBound is always smaller or equal to numGroupsLimit).
*/
public class DictionaryBasedGroupKeyGenerator implements GroupKeyGenerator {
- private final static int INITIAL_MAP_SIZE = 256;
- private final static int MAX_CACHING_MAP_SIZE = 1048576;
+ // NOTE: map size = map capacity (power of 2) * load factor
+ private static final int INITIAL_MAP_SIZE = (int) ((1 << 10) * 0.75f);
+ private static final int MAX_CACHING_MAP_SIZE = (int) ((1 << 20) * 0.75f);
+
+ private static final ThreadLocal<IntGroupIdMap> THREAD_LOCAL_INT_MAP = ThreadLocal.withInitial(IntGroupIdMap::new);
+ private static final ThreadLocal<Long2IntOpenHashMap> THREAD_LOCAL_LONG_MAP =
Review comment:
The Long2IntOpenHashMap can also be reimplemented in a different format for better locality and cache friendliness right. Similar to how this PR implements IntGroupIdMap ?
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -108,35 +116,35 @@ public DictionaryBasedGroupKeyGenerator(TransformOperator transformOperator, Exp
_isSingleValueColumn[i] = transformOperator.getResultMetadata(groupByExpression).isSingleValue();
}
+ // TODO: Clear the holder after processing the query instead of before
if (longOverflow) {
+ // ArrayMapBasedHolder
_globalGroupIdUpperBound = numGroupsLimit;
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(ArrayMapBasedHolder.class.getName(),
- o -> new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new ArrayMapBasedHolder(mapInternal);
- if (((Object2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
+ Object2IntOpenHashMap<IntArray> groupIdMap = THREAD_LOCAL_INT_ARRAY_MAP.get();
+ int size = groupIdMap.size();
+ groupIdMap.clear();
+ if (size > MAX_CACHING_MAP_SIZE) {
+ groupIdMap.trim();
}
+ _rawKeyHolder = new ArrayMapBasedHolder(groupIdMap);
} else {
if (cardinalityProduct > Integer.MAX_VALUE) {
+ // LongMapBasedHolder
_globalGroupIdUpperBound = numGroupsLimit;
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(LongMapBasedHolder.class.getName(),
- o -> new LongMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new LongMapBasedHolder(mapInternal);
- if (((Long2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
+ Long2IntOpenHashMap groupIdMap = THREAD_LOCAL_LONG_MAP.get();
+ int size = groupIdMap.size();
+ groupIdMap.clear();
+ if (size > MAX_CACHING_MAP_SIZE) {
+ groupIdMap.trim();
}
+ _rawKeyHolder = new LongMapBasedHolder(groupIdMap);
} else {
_globalGroupIdUpperBound = Math.min((int) cardinalityProduct, numGroupsLimit);
if (cardinalityProduct > arrayBasedThreshold) {
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(IntMapBasedHolder.class.getName(),
- o -> new IntMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new IntMapBasedHolder(mapInternal);
- if (((Int2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- }
+ // IntMapBasedHolder
+ IntGroupIdMap groupIdMap = THREAD_LOCAL_INT_MAP.get();
+ groupIdMap.clear();
Review comment:
What is the difference between trim() and clear() ? Can we use the same API?
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -831,6 +777,156 @@ private String getGroupKey(IntArray rawKey) {
return groupKeyBuilder.toString();
}
+ /**
+ * Fast int-to-int hashmap with {@link #INVALID_ID} as the default return value.
+ * <p>Different from {@link it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap}, this map uses one single array to store
+ * keys and values to reduce the cache miss.
+ */
+ @VisibleForTesting
+ public static class IntGroupIdMap {
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private int[] _keyValueHolder;
+ private int _capacity;
+ private int _mask;
+ private int _maxNumEntries;
+ private int _size;
+
+ public IntGroupIdMap() {
+ _capacity = 1 << 10;
+ int holderSize = _capacity << 1;
Review comment:
So looks like there are 2048 slots in the keyValueHolder array and we are going to use the lower order 12 bits of the incoming key for hash computation to get to the index/slot. And we will resize when 750 slots are full. Right ? How did we come up with these values of 1024, 2048 etc
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -831,6 +777,156 @@ private String getGroupKey(IntArray rawKey) {
return groupKeyBuilder.toString();
}
+ /**
+ * Fast int-to-int hashmap with {@link #INVALID_ID} as the default return value.
+ * <p>Different from {@link it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap}, this map uses one single array to store
+ * keys and values to reduce the cache miss.
+ */
+ @VisibleForTesting
+ public static class IntGroupIdMap {
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private int[] _keyValueHolder;
+ private int _capacity;
+ private int _mask;
+ private int _maxNumEntries;
+ private int _size;
+
+ public IntGroupIdMap() {
+ _capacity = 1 << 10;
+ int holderSize = _capacity << 1;
+ _keyValueHolder = new int[holderSize];
+ _mask = holderSize - 1;
+ _maxNumEntries = (int) (_capacity * LOAD_FACTOR);
+ }
+
+ public int size() {
+ return _size;
+ }
+
+ /**
+ * Returns the group id for the given raw key. Create a new group id if the raw key does not exist and the group id
+ * upper bound is not reached.
+ */
+ public int getGroupId(int rawKey, int groupIdUpperBound) {
+ // NOTE: Key 0 is reserved as the null key. Use (rawKey + 1) as the internal key because rawKey can never be -1.
+ int internalKey = rawKey + 1;
+ int index = (HashCommon.mix(internalKey) << 1) & _mask;
+ int key = _keyValueHolder[index];
+
+ // Handle hash hit separately for better performance
+ if (key == internalKey) {
+ return _keyValueHolder[index + 1];
+ }
+ if (key == 0) {
+ return _size < groupIdUpperBound ? addNewGroup(internalKey, index) : INVALID_ID;
Review comment:
So `key == 0` implies we hashed to the empty array slot right ?
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -831,6 +777,156 @@ private String getGroupKey(IntArray rawKey) {
return groupKeyBuilder.toString();
}
+ /**
+ * Fast int-to-int hashmap with {@link #INVALID_ID} as the default return value.
+ * <p>Different from {@link it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap}, this map uses one single array to store
+ * keys and values to reduce the cache miss.
+ */
+ @VisibleForTesting
+ public static class IntGroupIdMap {
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private int[] _keyValueHolder;
+ private int _capacity;
+ private int _mask;
+ private int _maxNumEntries;
+ private int _size;
+
+ public IntGroupIdMap() {
+ _capacity = 1 << 10;
+ int holderSize = _capacity << 1;
+ _keyValueHolder = new int[holderSize];
+ _mask = holderSize - 1;
+ _maxNumEntries = (int) (_capacity * LOAD_FACTOR);
+ }
+
+ public int size() {
+ return _size;
+ }
+
+ /**
+ * Returns the group id for the given raw key. Create a new group id if the raw key does not exist and the group id
+ * upper bound is not reached.
+ */
+ public int getGroupId(int rawKey, int groupIdUpperBound) {
+ // NOTE: Key 0 is reserved as the null key. Use (rawKey + 1) as the internal key because rawKey can never be -1.
+ int internalKey = rawKey + 1;
+ int index = (HashCommon.mix(internalKey) << 1) & _mask;
+ int key = _keyValueHolder[index];
+
+ // Handle hash hit separately for better performance
+ if (key == internalKey) {
+ return _keyValueHolder[index + 1];
+ }
+ if (key == 0) {
+ return _size < groupIdUpperBound ? addNewGroup(internalKey, index) : INVALID_ID;
+ }
+
+ // Hash collision
+ while (true) {
+ index = (index + 2) & _mask;
+ key = _keyValueHolder[index];
+ if (key == internalKey) {
+ return _keyValueHolder[index + 1];
+ }
+ if (key == 0) {
+ return _size < groupIdUpperBound ? addNewGroup(internalKey, index) : INVALID_ID;
+ }
+ }
+ }
+
+ private int addNewGroup(int internalKey, int index) {
+ int groupId = _size++;
+ _keyValueHolder[index] = internalKey;
+ _keyValueHolder[index + 1] = groupId;
+ if (_size > _maxNumEntries) {
+ expand();
+ }
+ return groupId;
+ }
+
+ private void expand() {
+ _capacity <<= 1;
+ int holderSize = _capacity << 1;
+ int[] oldKeyValueHolder = _keyValueHolder;
+ _keyValueHolder = new int[holderSize];
+ _mask = holderSize - 1;
+ _maxNumEntries <<= 1;
+ int oldIndex = 0;
+ for (int i = 0; i < _size; i++) {
+ while (oldKeyValueHolder[oldIndex] == 0) {
+ oldIndex += 2;
+ }
+ int key = oldKeyValueHolder[oldIndex];
+ int value = oldKeyValueHolder[oldIndex + 1];
+ int newIndex = (HashCommon.mix(key) << 1) & _mask;
+ if (_keyValueHolder[newIndex] != 0) {
+ do {
+ newIndex = (newIndex + 2) & _mask;
+ } while (_keyValueHolder[newIndex] != 0);
+ }
+ _keyValueHolder[newIndex] = key;
+ _keyValueHolder[newIndex + 1] = value;
+ oldIndex += 2;
+ }
+ }
+
+ public Iterator<Entry> iterator() {
+ return new Iterator<Entry>() {
+ private final Entry _entry = new Entry();
+ private int _index;
+ private int _numRemainingEntries = _size;
+
+ @Override
+ public boolean hasNext() {
+ return _numRemainingEntries > 0;
+ }
+
+ @Override
+ public Entry next() {
+ int key;
+ while ((key = _keyValueHolder[_index]) == 0) {
+ _index += 2;
+ }
+ _entry._rawKey = key - 1;
+ _entry._groupId = _keyValueHolder[_index + 1];
+ _index += 2;
+ _numRemainingEntries--;
+ return _entry;
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ };
+ }
+
+ /**
Review comment:
There is no trimming here like the way it happens in combiner where we sort and trim for. We are just zeroing out the keyValueHolder array and allocating a new array if size > MAX_CACHING_MAP_SIZE
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -831,6 +777,156 @@ private String getGroupKey(IntArray rawKey) {
return groupKeyBuilder.toString();
}
+ /**
+ * Fast int-to-int hashmap with {@link #INVALID_ID} as the default return value.
+ * <p>Different from {@link it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap}, this map uses one single array to store
+ * keys and values to reduce the cache miss.
+ */
+ @VisibleForTesting
+ public static class IntGroupIdMap {
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private int[] _keyValueHolder;
+ private int _capacity;
+ private int _mask;
+ private int _maxNumEntries;
+ private int _size;
+
+ public IntGroupIdMap() {
+ _capacity = 1 << 10;
+ int holderSize = _capacity << 1;
+ _keyValueHolder = new int[holderSize];
+ _mask = holderSize - 1;
+ _maxNumEntries = (int) (_capacity * LOAD_FACTOR);
+ }
+
+ public int size() {
+ return _size;
+ }
+
+ /**
+ * Returns the group id for the given raw key. Create a new group id if the raw key does not exist and the group id
+ * upper bound is not reached.
+ */
+ public int getGroupId(int rawKey, int groupIdUpperBound) {
+ // NOTE: Key 0 is reserved as the null key. Use (rawKey + 1) as the internal key because rawKey can never be -1.
+ int internalKey = rawKey + 1;
+ int index = (HashCommon.mix(internalKey) << 1) & _mask;
+ int key = _keyValueHolder[index];
+
+ // Handle hash hit separately for better performance
+ if (key == internalKey) {
+ return _keyValueHolder[index + 1];
+ }
+ if (key == 0) {
+ return _size < groupIdUpperBound ? addNewGroup(internalKey, index) : INVALID_ID;
+ }
+
+ // Hash collision
+ while (true) {
+ index = (index + 2) & _mask;
+ key = _keyValueHolder[index];
+ if (key == internalKey) {
+ return _keyValueHolder[index + 1];
+ }
+ if (key == 0) {
+ return _size < groupIdUpperBound ? addNewGroup(internalKey, index) : INVALID_ID;
+ }
+ }
+ }
+
+ private int addNewGroup(int internalKey, int index) {
+ int groupId = _size++;
+ _keyValueHolder[index] = internalKey;
+ _keyValueHolder[index + 1] = groupId;
+ if (_size > _maxNumEntries) {
+ expand();
+ }
+ return groupId;
+ }
+
+ private void expand() {
+ _capacity <<= 1;
+ int holderSize = _capacity << 1;
+ int[] oldKeyValueHolder = _keyValueHolder;
+ _keyValueHolder = new int[holderSize];
+ _mask = holderSize - 1;
+ _maxNumEntries <<= 1;
+ int oldIndex = 0;
+ for (int i = 0; i < _size; i++) {
+ while (oldKeyValueHolder[oldIndex] == 0) {
+ oldIndex += 2;
+ }
+ int key = oldKeyValueHolder[oldIndex];
+ int value = oldKeyValueHolder[oldIndex + 1];
+ int newIndex = (HashCommon.mix(key) << 1) & _mask;
+ if (_keyValueHolder[newIndex] != 0) {
+ do {
+ newIndex = (newIndex + 2) & _mask;
+ } while (_keyValueHolder[newIndex] != 0);
+ }
+ _keyValueHolder[newIndex] = key;
+ _keyValueHolder[newIndex + 1] = value;
+ oldIndex += 2;
+ }
+ }
+
+ public Iterator<Entry> iterator() {
+ return new Iterator<Entry>() {
+ private final Entry _entry = new Entry();
+ private int _index;
+ private int _numRemainingEntries = _size;
+
+ @Override
+ public boolean hasNext() {
+ return _numRemainingEntries > 0;
+ }
+
+ @Override
+ public Entry next() {
+ int key;
+ while ((key = _keyValueHolder[_index]) == 0) {
+ _index += 2;
+ }
+ _entry._rawKey = key - 1;
+ _entry._groupId = _keyValueHolder[_index + 1];
+ _index += 2;
+ _numRemainingEntries--;
+ return _entry;
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ };
+ }
+
+ /**
+ * Clears the map and trims the map if the size is larger than the {@link #MAX_CACHING_MAP_SIZE}.
+ */
+ public void clear() {
+ if (_size == 0) {
+ return;
+ }
+ if (_size <= MAX_CACHING_MAP_SIZE) {
+ Arrays.fill(_keyValueHolder, 0);
+ } else {
+ _capacity = 1 << 10;
Review comment:
(nit) this is same as the initialization in the constructor. consider creating an init() function and moving this code in that function.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] Jackie-Jiang commented on a change in pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on a change in pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#discussion_r573384919
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -831,6 +777,156 @@ private String getGroupKey(IntArray rawKey) {
return groupKeyBuilder.toString();
}
+ /**
+ * Fast int-to-int hashmap with {@link #INVALID_ID} as the default return value.
+ * <p>Different from {@link it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap}, this map uses one single array to store
+ * keys and values to reduce the cache miss.
+ */
+ @VisibleForTesting
+ public static class IntGroupIdMap {
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private int[] _keyValueHolder;
+ private int _capacity;
+ private int _mask;
+ private int _maxNumEntries;
+ private int _size;
+
+ public IntGroupIdMap() {
+ _capacity = 1 << 10;
+ int holderSize = _capacity << 1;
+ _keyValueHolder = new int[holderSize];
+ _mask = holderSize - 1;
+ _maxNumEntries = (int) (_capacity * LOAD_FACTOR);
+ }
+
+ public int size() {
+ return _size;
+ }
+
+ /**
+ * Returns the group id for the given raw key. Create a new group id if the raw key does not exist and the group id
+ * upper bound is not reached.
+ */
+ public int getGroupId(int rawKey, int groupIdUpperBound) {
+ // NOTE: Key 0 is reserved as the null key. Use (rawKey + 1) as the internal key because rawKey can never be -1.
+ int internalKey = rawKey + 1;
+ int index = (HashCommon.mix(internalKey) << 1) & _mask;
+ int key = _keyValueHolder[index];
+
+ // Handle hash hit separately for better performance
+ if (key == internalKey) {
+ return _keyValueHolder[index + 1];
+ }
+ if (key == 0) {
+ return _size < groupIdUpperBound ? addNewGroup(internalKey, index) : INVALID_ID;
+ }
+
+ // Hash collision
+ while (true) {
+ index = (index + 2) & _mask;
+ key = _keyValueHolder[index];
+ if (key == internalKey) {
+ return _keyValueHolder[index + 1];
+ }
+ if (key == 0) {
+ return _size < groupIdUpperBound ? addNewGroup(internalKey, index) : INVALID_ID;
+ }
+ }
+ }
+
+ private int addNewGroup(int internalKey, int index) {
+ int groupId = _size++;
+ _keyValueHolder[index] = internalKey;
+ _keyValueHolder[index + 1] = groupId;
+ if (_size > _maxNumEntries) {
+ expand();
+ }
+ return groupId;
+ }
+
+ private void expand() {
+ _capacity <<= 1;
+ int holderSize = _capacity << 1;
+ int[] oldKeyValueHolder = _keyValueHolder;
+ _keyValueHolder = new int[holderSize];
+ _mask = holderSize - 1;
+ _maxNumEntries <<= 1;
+ int oldIndex = 0;
+ for (int i = 0; i < _size; i++) {
+ while (oldKeyValueHolder[oldIndex] == 0) {
+ oldIndex += 2;
+ }
+ int key = oldKeyValueHolder[oldIndex];
+ int value = oldKeyValueHolder[oldIndex + 1];
+ int newIndex = (HashCommon.mix(key) << 1) & _mask;
+ if (_keyValueHolder[newIndex] != 0) {
+ do {
+ newIndex = (newIndex + 2) & _mask;
+ } while (_keyValueHolder[newIndex] != 0);
+ }
+ _keyValueHolder[newIndex] = key;
+ _keyValueHolder[newIndex + 1] = value;
+ oldIndex += 2;
+ }
+ }
+
+ public Iterator<Entry> iterator() {
+ return new Iterator<Entry>() {
+ private final Entry _entry = new Entry();
+ private int _index;
+ private int _numRemainingEntries = _size;
+
+ @Override
+ public boolean hasNext() {
+ return _numRemainingEntries > 0;
+ }
+
+ @Override
+ public Entry next() {
+ int key;
+ while ((key = _keyValueHolder[_index]) == 0) {
+ _index += 2;
+ }
+ _entry._rawKey = key - 1;
+ _entry._groupId = _keyValueHolder[_index + 1];
+ _index += 2;
+ _numRemainingEntries--;
+ return _entry;
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ };
+ }
+
+ /**
+ * Clears the map and trims the map if the size is larger than the {@link #MAX_CACHING_MAP_SIZE}.
+ */
+ public void clear() {
+ if (_size == 0) {
+ return;
+ }
+ if (_size <= MAX_CACHING_MAP_SIZE) {
+ Arrays.fill(_keyValueHolder, 0);
+ } else {
+ _capacity = 1 << 10;
Review comment:
Good point, added
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] codecov-io commented on pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
codecov-io commented on pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#issuecomment-775571753
# [Codecov](https://codecov.io/gh/apache/incubator-pinot/pull/6559?src=pr&el=h1) Report
> Merging [#6559](https://codecov.io/gh/apache/incubator-pinot/pull/6559?src=pr&el=desc) (b8b0839) into [master](https://codecov.io/gh/apache/incubator-pinot/commit/1beaab59b73f26c4e35f3b9bc856b03806cddf5a?el=desc) (1beaab5) will **decrease** coverage by `1.37%`.
> The diff coverage is `59.94%`.
[](https://codecov.io/gh/apache/incubator-pinot/pull/6559?src=pr&el=tree)
```diff
@@ Coverage Diff @@
## master #6559 +/- ##
==========================================
- Coverage 66.44% 65.07% -1.38%
==========================================
Files 1075 1339 +264
Lines 54773 65902 +11129
Branches 8168 9621 +1453
==========================================
+ Hits 36396 42885 +6489
- Misses 15700 19955 +4255
- Partials 2677 3062 +385
```
| Flag | Coverage Δ | |
|---|---|---|
| unittests | `65.07% <59.94%> (?)` | |
Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags#carryforward-flags-in-the-pull-request-comment) to find out more.
| [Impacted Files](https://codecov.io/gh/apache/incubator-pinot/pull/6559?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [...e/pinot/broker/api/resources/PinotBrokerDebug.java](https://codecov.io/gh/apache/incubator-pinot/pull/6559/diff?src=pr&el=tree#diff-cGlub3QtYnJva2VyL3NyYy9tYWluL2phdmEvb3JnL2FwYWNoZS9waW5vdC9icm9rZXIvYXBpL3Jlc291cmNlcy9QaW5vdEJyb2tlckRlYnVnLmphdmE=) | `0.00% <0.00%> (-79.32%)` | :arrow_down: |
| [...ot/broker/broker/AllowAllAccessControlFactory.java](https://codecov.io/gh/apache/incubator-pinot/pull/6559/diff?src=pr&el=tree#diff-cGlub3QtYnJva2VyL3NyYy9tYWluL2phdmEvb3JnL2FwYWNoZS9waW5vdC9icm9rZXIvYnJva2VyL0FsbG93QWxsQWNjZXNzQ29udHJvbEZhY3RvcnkuamF2YQ==) | `71.42% <ø> (-28.58%)` | :arrow_down: |
| [.../helix/BrokerUserDefinedMessageHandlerFactory.java](https://codecov.io/gh/apache/incubator-pinot/pull/6559/diff?src=pr&el=tree#diff-cGlub3QtYnJva2VyL3NyYy9tYWluL2phdmEvb3JnL2FwYWNoZS9waW5vdC9icm9rZXIvYnJva2VyL2hlbGl4L0Jyb2tlclVzZXJEZWZpbmVkTWVzc2FnZUhhbmRsZXJGYWN0b3J5LmphdmE=) | `33.96% <0.00%> (-32.71%)` | :arrow_down: |
| [...ker/routing/instanceselector/InstanceSelector.java](https://codecov.io/gh/apache/incubator-pinot/pull/6559/diff?src=pr&el=tree#diff-cGlub3QtYnJva2VyL3NyYy9tYWluL2phdmEvb3JnL2FwYWNoZS9waW5vdC9icm9rZXIvcm91dGluZy9pbnN0YW5jZXNlbGVjdG9yL0luc3RhbmNlU2VsZWN0b3IuamF2YQ==) | `100.00% <ø> (ø)` | |
| [...ava/org/apache/pinot/client/AbstractResultSet.java](https://codecov.io/gh/apache/incubator-pinot/pull/6559/diff?src=pr&el=tree#diff-cGlub3QtY2xpZW50cy9waW5vdC1qYXZhLWNsaWVudC9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY2xpZW50L0Fic3RyYWN0UmVzdWx0U2V0LmphdmE=) | `66.66% <ø> (+9.52%)` | :arrow_up: |
| [...n/java/org/apache/pinot/client/BrokerResponse.java](https://codecov.io/gh/apache/incubator-pinot/pull/6559/diff?src=pr&el=tree#diff-cGlub3QtY2xpZW50cy9waW5vdC1qYXZhLWNsaWVudC9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY2xpZW50L0Jyb2tlclJlc3BvbnNlLmphdmE=) | `100.00% <ø> (ø)` | |
| [.../main/java/org/apache/pinot/client/Connection.java](https://codecov.io/gh/apache/incubator-pinot/pull/6559/diff?src=pr&el=tree#diff-cGlub3QtY2xpZW50cy9waW5vdC1qYXZhLWNsaWVudC9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY2xpZW50L0Nvbm5lY3Rpb24uamF2YQ==) | `35.55% <ø> (-13.29%)` | :arrow_down: |
| [...n/java/org/apache/pinot/client/ExecutionStats.java](https://codecov.io/gh/apache/incubator-pinot/pull/6559/diff?src=pr&el=tree#diff-cGlub3QtY2xpZW50cy9waW5vdC1qYXZhLWNsaWVudC9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY2xpZW50L0V4ZWN1dGlvblN0YXRzLmphdmE=) | `15.55% <ø> (ø)` | |
| [...inot/client/JsonAsyncHttpPinotClientTransport.java](https://codecov.io/gh/apache/incubator-pinot/pull/6559/diff?src=pr&el=tree#diff-cGlub3QtY2xpZW50cy9waW5vdC1qYXZhLWNsaWVudC9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY2xpZW50L0pzb25Bc3luY0h0dHBQaW5vdENsaWVudFRyYW5zcG9ydC5qYXZh) | `10.90% <ø> (-51.10%)` | :arrow_down: |
| [...n/java/org/apache/pinot/client/ResultSetGroup.java](https://codecov.io/gh/apache/incubator-pinot/pull/6559/diff?src=pr&el=tree#diff-cGlub3QtY2xpZW50cy9waW5vdC1qYXZhLWNsaWVudC9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY2xpZW50L1Jlc3VsdFNldEdyb3VwLmphdmE=) | `65.38% <ø> (+0.16%)` | :arrow_up: |
| ... and [1205 more](https://codecov.io/gh/apache/incubator-pinot/pull/6559/diff?src=pr&el=tree-more) | |
------
[Continue to review full report at Codecov](https://codecov.io/gh/apache/incubator-pinot/pull/6559?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/apache/incubator-pinot/pull/6559?src=pr&el=footer). Last update [e62addb...b8b0839](https://codecov.io/gh/apache/incubator-pinot/pull/6559?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] Jackie-Jiang commented on pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#issuecomment-777887324
> I don't think the following 2 changes are needed for the optimization done in this PR.
>
> ```
> private static final int INITIAL_MAP_SIZE = (int) ((1 << 9) * 0.75f);
> private static final int MAX_CACHING_MAP_SIZE = (int) ((1 << 20) * 0.75f);
> ```
>
> We should be able to keep them to their original values right since the optimization done in this PR for IntGroupId map internally uses the capacity of 4K to align with the page size and is not really dependent on the above 2 changes. Just wondering if the above 2 changes can impact performance in any case. I don't think they are related to this PR.
These 2 changes are just making the value calculation more obvious for readability. Because we use the map size as threshold, we should multiply it by the load factor. There is no performance impact.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] siddharthteotia commented on a change in pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
siddharthteotia commented on a change in pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#discussion_r573484761
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -108,35 +116,35 @@ public DictionaryBasedGroupKeyGenerator(TransformOperator transformOperator, Exp
_isSingleValueColumn[i] = transformOperator.getResultMetadata(groupByExpression).isSingleValue();
}
+ // TODO: Clear the holder after processing the query instead of before
if (longOverflow) {
+ // ArrayMapBasedHolder
_globalGroupIdUpperBound = numGroupsLimit;
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(ArrayMapBasedHolder.class.getName(),
- o -> new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new ArrayMapBasedHolder(mapInternal);
- if (((Object2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
+ Object2IntOpenHashMap<IntArray> groupIdMap = THREAD_LOCAL_INT_ARRAY_MAP.get();
+ int size = groupIdMap.size();
+ groupIdMap.clear();
+ if (size > MAX_CACHING_MAP_SIZE) {
+ groupIdMap.trim();
}
+ _rawKeyHolder = new ArrayMapBasedHolder(groupIdMap);
} else {
if (cardinalityProduct > Integer.MAX_VALUE) {
+ // LongMapBasedHolder
_globalGroupIdUpperBound = numGroupsLimit;
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(LongMapBasedHolder.class.getName(),
- o -> new LongMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new LongMapBasedHolder(mapInternal);
- if (((Long2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
+ Long2IntOpenHashMap groupIdMap = THREAD_LOCAL_LONG_MAP.get();
+ int size = groupIdMap.size();
+ groupIdMap.clear();
+ if (size > MAX_CACHING_MAP_SIZE) {
+ groupIdMap.trim();
}
+ _rawKeyHolder = new LongMapBasedHolder(groupIdMap);
} else {
_globalGroupIdUpperBound = Math.min((int) cardinalityProduct, numGroupsLimit);
if (cardinalityProduct > arrayBasedThreshold) {
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(IntMapBasedHolder.class.getName(),
- o -> new IntMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new IntMapBasedHolder(mapInternal);
- if (((Int2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- }
+ // IntMapBasedHolder
+ IntGroupIdMap groupIdMap = THREAD_LOCAL_INT_MAP.get();
+ groupIdMap.clear();
Review comment:
Thanks. We also discussed this offline that trim() here is essentially truncation. I confused it with sort based trimming that we do in combine operator for ordering
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] Jackie-Jiang commented on a change in pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on a change in pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#discussion_r573385274
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -108,35 +116,35 @@ public DictionaryBasedGroupKeyGenerator(TransformOperator transformOperator, Exp
_isSingleValueColumn[i] = transformOperator.getResultMetadata(groupByExpression).isSingleValue();
}
+ // TODO: Clear the holder after processing the query instead of before
if (longOverflow) {
+ // ArrayMapBasedHolder
_globalGroupIdUpperBound = numGroupsLimit;
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(ArrayMapBasedHolder.class.getName(),
- o -> new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new ArrayMapBasedHolder(mapInternal);
- if (((Object2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
+ Object2IntOpenHashMap<IntArray> groupIdMap = THREAD_LOCAL_INT_ARRAY_MAP.get();
+ int size = groupIdMap.size();
+ groupIdMap.clear();
+ if (size > MAX_CACHING_MAP_SIZE) {
+ groupIdMap.trim();
}
+ _rawKeyHolder = new ArrayMapBasedHolder(groupIdMap);
} else {
if (cardinalityProduct > Integer.MAX_VALUE) {
+ // LongMapBasedHolder
_globalGroupIdUpperBound = numGroupsLimit;
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(LongMapBasedHolder.class.getName(),
- o -> new LongMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new LongMapBasedHolder(mapInternal);
- if (((Long2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
+ Long2IntOpenHashMap groupIdMap = THREAD_LOCAL_LONG_MAP.get();
+ int size = groupIdMap.size();
+ groupIdMap.clear();
+ if (size > MAX_CACHING_MAP_SIZE) {
+ groupIdMap.trim();
}
+ _rawKeyHolder = new LongMapBasedHolder(groupIdMap);
} else {
_globalGroupIdUpperBound = Math.min((int) cardinalityProduct, numGroupsLimit);
if (cardinalityProduct > arrayBasedThreshold) {
- Object mapInternal = mapBasedRawKeyHolders.computeIfAbsent(IntMapBasedHolder.class.getName(),
- o -> new IntMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- _rawKeyHolder = new IntMapBasedHolder(mapInternal);
- if (((Int2IntOpenHashMap) mapInternal).size() > MAX_CACHING_MAP_SIZE) {
- mapBasedRawKeyHolders
- .put(ArrayMapBasedHolder.class.getName(), new ArrayMapBasedHolder(INITIAL_MAP_SIZE).getInternal());
- }
+ // IntMapBasedHolder
+ IntGroupIdMap groupIdMap = THREAD_LOCAL_INT_MAP.get();
+ groupIdMap.clear();
Review comment:
Rename the method to `clearAndTrim()` for clarity
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] Jackie-Jiang commented on a change in pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on a change in pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#discussion_r573384195
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -831,6 +777,156 @@ private String getGroupKey(IntArray rawKey) {
return groupKeyBuilder.toString();
}
+ /**
+ * Fast int-to-int hashmap with {@link #INVALID_ID} as the default return value.
+ * <p>Different from {@link it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap}, this map uses one single array to store
+ * keys and values to reduce the cache miss.
+ */
+ @VisibleForTesting
+ public static class IntGroupIdMap {
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private int[] _keyValueHolder;
+ private int _capacity;
+ private int _mask;
+ private int _maxNumEntries;
+ private int _size;
+
+ public IntGroupIdMap() {
+ _capacity = 1 << 10;
+ int holderSize = _capacity << 1;
+ _keyValueHolder = new int[holderSize];
+ _mask = holderSize - 1;
+ _maxNumEntries = (int) (_capacity * LOAD_FACTOR);
+ }
+
+ public int size() {
+ return _size;
+ }
+
+ /**
+ * Returns the group id for the given raw key. Create a new group id if the raw key does not exist and the group id
+ * upper bound is not reached.
+ */
+ public int getGroupId(int rawKey, int groupIdUpperBound) {
+ // NOTE: Key 0 is reserved as the null key. Use (rawKey + 1) as the internal key because rawKey can never be -1.
+ int internalKey = rawKey + 1;
+ int index = (HashCommon.mix(internalKey) << 1) & _mask;
+ int key = _keyValueHolder[index];
+
+ // Handle hash hit separately for better performance
+ if (key == internalKey) {
+ return _keyValueHolder[index + 1];
+ }
+ if (key == 0) {
+ return _size < groupIdUpperBound ? addNewGroup(internalKey, index) : INVALID_ID;
Review comment:
Yes, 0 is reserved as the null key (check the comment on line 812)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] Jackie-Jiang merged pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang merged pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] Jackie-Jiang commented on a change in pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on a change in pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#discussion_r573385797
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -831,6 +777,156 @@ private String getGroupKey(IntArray rawKey) {
return groupKeyBuilder.toString();
}
+ /**
+ * Fast int-to-int hashmap with {@link #INVALID_ID} as the default return value.
+ * <p>Different from {@link it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap}, this map uses one single array to store
+ * keys and values to reduce the cache miss.
+ */
+ @VisibleForTesting
+ public static class IntGroupIdMap {
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private int[] _keyValueHolder;
+ private int _capacity;
+ private int _mask;
+ private int _maxNumEntries;
+ private int _size;
+
+ public IntGroupIdMap() {
+ _capacity = 1 << 10;
+ int holderSize = _capacity << 1;
Review comment:
Changed the initial capacity to 512 so that the array can fit into a single memory page. Added more comments also
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] siddharthteotia commented on a change in pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
siddharthteotia commented on a change in pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#discussion_r573484428
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -61,8 +61,16 @@
* bounded by the number of groups limit (globalGroupIdUpperBound is always smaller or equal to numGroupsLimit).
*/
public class DictionaryBasedGroupKeyGenerator implements GroupKeyGenerator {
- private final static int INITIAL_MAP_SIZE = 256;
- private final static int MAX_CACHING_MAP_SIZE = 1048576;
+ // NOTE: map size = map capacity (power of 2) * load factor
+ private static final int INITIAL_MAP_SIZE = (int) ((1 << 10) * 0.75f);
+ private static final int MAX_CACHING_MAP_SIZE = (int) ((1 << 20) * 0.75f);
+
+ private static final ThreadLocal<IntGroupIdMap> THREAD_LOCAL_INT_MAP = ThreadLocal.withInitial(IntGroupIdMap::new);
+ private static final ThreadLocal<Long2IntOpenHashMap> THREAD_LOCAL_LONG_MAP =
Review comment:
Sounds good.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [incubator-pinot] Jackie-Jiang commented on a change in pull request #6559: Optimize group-key generator
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on a change in pull request #6559:
URL: https://github.com/apache/incubator-pinot/pull/6559#discussion_r573383852
##########
File path: pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/groupby/DictionaryBasedGroupKeyGenerator.java
##########
@@ -831,6 +777,156 @@ private String getGroupKey(IntArray rawKey) {
return groupKeyBuilder.toString();
}
+ /**
+ * Fast int-to-int hashmap with {@link #INVALID_ID} as the default return value.
+ * <p>Different from {@link it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap}, this map uses one single array to store
+ * keys and values to reduce the cache miss.
+ */
+ @VisibleForTesting
+ public static class IntGroupIdMap {
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private int[] _keyValueHolder;
+ private int _capacity;
+ private int _mask;
+ private int _maxNumEntries;
+ private int _size;
+
+ public IntGroupIdMap() {
+ _capacity = 1 << 10;
+ int holderSize = _capacity << 1;
Review comment:
We don't want to start with a too small map, nor a too large map. Small map will result in more hash collisions and more resizes. Large map will result in bigger memory footprint. A map of capacity 1024 is quite small, but we will expand and cache it if we need a larger map. This value does not matter that much as long as it is not too large.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org