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 2022/05/24 16:02:37 UTC

[GitHub] [pinot] gortiz opened a new pull request, #8766: Optimize ColumnValueSegmentPruner by caching value hashes

gortiz opened a new pull request, #8766:
URL: https://github.com/apache/pinot/pull/8766

   ColumnValueSegmentPruner was calculating the hash of each value once per segment. This PR introduces a hash cache that is populated the first time one of each element is hashed. 
   
   The cost of this map is that it may have more entries than a normal map, but they are always going to be limited by the number of literal expressions in the where expression.
   
   The PR includes a two JMH microbenchmarks:
   - `BenchmarkBloomFilter` is a benchmark that shows the performance difference between calling several times `mightContain(String)` and `mightContain(long, long)`.
   - `BenchmarkServerSegmentPruner` is a benchmark that tests `ColumnValueSegmentPruner`. It initially create several IndexSegments and given a query, analyses how much time is spent in pruning it
   
   `BenchmarkServerSegmentPruner` has been executed with the previous `ColumnValueSegmentPruner` version and with the optimized one. The results on my laptop are the following:
   
   ```
   Without optimization
   Benchmark                           (_numRows)  (_numSegments)  Mode  Cnt   Score   Error  Units
   BenchmarkServerSegmentPruner.query          10              10  avgt    5   1.426 ± 0.003  us/op
   BenchmarkServerSegmentPruner.query          10             100  avgt    5  14.719 ± 1.342  us/op
   BenchmarkServerSegmentPruner.query          10            1000  avgt    5  174.879 ± 5.115  us/op
   BenchmarkServerSegmentPruner.query         100              10  avgt    5   1.459 ± 0.009  us/op
   BenchmarkServerSegmentPruner.query         100             100  avgt    5  13.966 ± 0.520  us/op
   BenchmarkServerSegmentPruner.query        1000              10  avgt    5   1.445 ± 0.004  us/op
   BenchmarkServerSegmentPruner.query        1000             100  avgt    5  15.349 ± 0.071  us/op
   
   With optimization
   Benchmark                           (_numRows)  (_numSegments)  Mode  Cnt   Score   Error  Units
   BenchmarkServerSegmentPruner.query          10              10  avgt    5   0.972 ± 0.003  us/op
   BenchmarkServerSegmentPruner.query          10             100  avgt    5  10.149 ± 0.046  us/op
   BenchmarkServerSegmentPruner.query          10            1000  avgt    5  135.063 ± 14.670  us/op
   BenchmarkServerSegmentPruner.query         100              10  avgt    5   0.960 ± 0.006  us/op
   BenchmarkServerSegmentPruner.query         100             100  avgt    5  10.512 ± 0.054  us/op
   BenchmarkServerSegmentPruner.query        1000              10  avgt    5   0.796 ± 0.003  us/op
   BenchmarkServerSegmentPruner.query        1000             100  avgt    5  10.636 ± 0.021  us/op
   ```
   
   As expected, the cost seems to be linear on the number of segments and it doesn't seem that the number of rows affects the results in a significant way. Given that the tests with 1000 segments takes a while to build, I've decided to do not test it with different number of rows. In this benchmark the time spent pruning has been reduced 23% and 30%.


-- 
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@pinot.apache.org

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] [pinot] gortiz commented on pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on PR #8766:
URL: https://github.com/apache/pinot/pull/8766#issuecomment-1136857476

   > I feel a better way to optimize this segment pruner would be to first pre-process the predicates (convert the value, compute the hash etc.), then use the pre-processed values to prune each segment. This can avoid the overhead of processing the predicate for each segment. Since the `FilterContext` won't be changed, we should be able to use the identity map to store the mapping from `Predicate` to the pre-computed values
   
   That sounds like a good idea that would be interesting for future improvements. Although I'm not sure about the priority of these changes. JFR metrics taken with the benchmarks show that most of the time is spent in `DataSource dataSource = dataSourceCache.computeIfAbsent(column, segment::getDataSource);`.
   
   In case we still want to focus on improve the performance of this class, I think we should focus on how to make getDataSource faster. Specifically, `ImmutableSegmentImpl` should be able to cache these values. I don't know the codebase that well, but it seems that these datasources are going to be immutable, are relative expensive to be created, and are used several times during the lifecycle of a `ImmutableSegmentImpl`.


-- 
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@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r882423798


##########
pinot-core/src/test/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPrunerTest.java:
##########
@@ -148,17 +158,18 @@ public void testBloomFilterInPredicatePruning() {
     when(indexSegment.getDataSource("column")).thenReturn(dataSource);
     // Add support for bloom filter
     DataSourceMetadata dataSourceMetadata = mock(DataSourceMetadata.class);
-    BloomFilterReader bloomFilterReader = mock(BloomFilterReader.class);
+    BloomFilterReader bloomFilterReader = new BloomFilterReaderBuilder()
+        .put("1")

Review Comment:
   Would you prefer
   
   ```java
   BloomFilterReader bloomFilterReader = new BloomFilterReaderBuilder().put("1").put("2").put("3").put("5").put("7").put("21")
           .build();
   ```
   
   instead? If that's the case I think that it is significantly more difficult to read.



-- 
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@pinot.apache.org

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] [pinot] Jackie-Jiang merged pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
Jackie-Jiang merged PR #8766:
URL: https://github.com/apache/pinot/pull/8766


-- 
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@pinot.apache.org

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] [pinot] richardstartin commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
richardstartin commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r882766409


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -483,26 +476,97 @@ private static Comparable convertValue(String stringValue, DataType dataType) {
     }
   }
 
-  private static class CachedValue {
-    private final String _strValue;
-    private final long _hash1;
-    private final long _hash2;
-    private DataType _dt;
-    private Comparable _comparableValue;
-
-    private CachedValue(Object value) {
-      _strValue = value.toString();
-      byte[] hash = GuavaBloomFilterReaderUtils.hash(_strValue);
-      _hash1 = Longs.fromBytes(hash[7], hash[6], hash[5], hash[4], hash[3], hash[2], hash[1], hash[0]);
-      _hash2 = Longs.fromBytes(hash[15], hash[14], hash[13], hash[12], hash[11], hash[10], hash[9], hash[8]);
+  private static class ValueCache {
+    // As Predicates are recursive structures, their hashCode is quite expensive.
+    // By using an IdentityHashMap here we don't need to iterate over the recursive
+    // structure. This is specially useful in the IN expression.
+    private final Map<Predicate, Object> _cache = new IdentityHashMap<>();
+
+    public void add(EqPredicate pred) {
+      _cache.put(pred, new CachedValue(pred.getValue()));
+    }
+
+    public void add(InPredicate pred) {
+      List<CachedValue> list = new ArrayList<>(pred.getValues().size());
+      for (String value : pred.getValues()) {
+        list.add(new CachedValue(value));
+      }
+      _cache.put(pred, list);
+    }
+
+    public CachedValue get(EqPredicate pred, DataType dt) {
+      CachedValue cachedValue = (CachedValue) _cache.get(pred);
+      cachedValue.ensureDataType(dt);
+      return cachedValue;
+    }
+
+    public List<CachedValue> get(InPredicate pred, DataType dt) {
+      List<CachedValue> cachedValues = (List<CachedValue>) _cache.get(pred);
+      for (CachedValue cachedValue : cachedValues) {
+        cachedValue.ensureDataType(dt);
+      }
+      return cachedValues;
     }
 
-    private Comparable getComparableValue(DataType dt) {
-      if (!dt.equals(_dt)) {
-        _dt = dt;
-        _comparableValue = convertValue(_strValue, dt);
+    public static class CachedValue {
+      private final Object _value;
+      private boolean _hashed = false;
+      private long _hash1;
+      private long _hash2;
+      private DataType _dt;
+      private Comparable _comparableValue;
+
+      private CachedValue(Object value) {
+        _value = value;
+      }
+
+      private Comparable getComparableValue() {
+        assert _dt != null;
+        return _comparableValue;
+      }
+
+      static final LongExtractor EXTRACTOR;
+
+      interface LongExtractor {
+        long extract(byte[] bytes, int index);
+      }
+
+      static {
+        LongExtractor extractor;
+        try {
+          MethodType mt = MethodType.methodType(VarHandle.class, Class.class, ByteOrder.class);
+          MethodHandle mh = MethodHandles.lookup().findStatic(MethodHandles.class, "byteArrayViewVarHandle", mt);
+
+          VarHandle varHandle = (VarHandle) mh.invokeExact(long[].class, ByteOrder.LITTLE_ENDIAN);
+          extractor = (bytes, index) -> (long) varHandle.get(bytes, index * 8);
+        } catch (Throwable e) {
+          extractor = (bytes, index) -> {
+            int i = index * 8;
+            return Longs.fromBytes(bytes[i + 7], bytes[i + 6], bytes[i + 5],
+                bytes[i + 4], bytes[i + 3], bytes[i + 2], bytes[i + 1], bytes[i]);
+          };

Review Comment:
   You will need a little more indirection here to make this compile to JDK8 :(



-- 
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@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r884466651


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -435,4 +469,74 @@ private static Comparable convertValue(String stringValue, DataType dataType) {
       throw new BadQueryRequestException(e);
     }
   }
+
+  private static class ValueCache {
+    // As Predicates are recursive structures, their hashCode is quite expensive.
+    // By using an IdentityHashMap here we don't need to iterate over the recursive
+    // structure. This is specially useful in the IN expression.
+    private final Map<Predicate, Object> _cache = new IdentityHashMap<>();
+
+    public void add(EqPredicate pred) {
+      _cache.put(pred, new CachedValue(pred.getValue()));
+    }
+
+    public void add(InPredicate pred) {
+      List<CachedValue> list = new ArrayList<>(pred.getValues().size());
+      for (String value : pred.getValues()) {
+        list.add(new CachedValue(value));
+      }
+      _cache.put(pred, list);
+    }
+
+    public CachedValue get(EqPredicate pred, DataType dt) {
+      CachedValue cachedValue = (CachedValue) _cache.get(pred);
+      cachedValue.ensureDataType(dt);
+      return cachedValue;
+    }
+
+    public List<CachedValue> get(InPredicate pred, DataType dt) {
+      List<CachedValue> cachedValues = (List<CachedValue>) _cache.get(pred);
+      for (CachedValue cachedValue : cachedValues) {
+        cachedValue.ensureDataType(dt);
+      }
+      return cachedValues;
+    }
+
+    public static class CachedValue {
+      private final Object _value;
+      private boolean _hashed = false;
+      private long _hash1;
+      private long _hash2;
+      private DataType _dt;
+      private Comparable _comparableValue;
+
+      private CachedValue(Object value) {
+        _value = value;
+      }
+
+      private Comparable getComparableValue() {
+        assert _dt != null;
+        return _comparableValue;
+      }
+
+      private void ensureDataType(DataType dt) {
+        if (!dt.equals(_dt)) {

Review Comment:
   Are you used to compare enums by reference? In my experience, it is quite dangerous. It should happen that there is only one instance for each literal... but sometimes deserialize some enum using reflection and creates more than one instance and the equality by reference start to fail.



-- 
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@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r880702682


##########
pinot-core/src/test/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPrunerTest.java:
##########
@@ -148,17 +158,18 @@ public void testBloomFilterInPredicatePruning() {
     when(indexSegment.getDataSource("column")).thenReturn(dataSource);
     // Add support for bloom filter
     DataSourceMetadata dataSourceMetadata = mock(DataSourceMetadata.class);
-    BloomFilterReader bloomFilterReader = mock(BloomFilterReader.class);
+    BloomFilterReader bloomFilterReader = new BloomFilterReaderBuilder()

Review Comment:
   I have to remove the mock and use an actual object because the new implementation doesn't call `mightContain(String)` and instead calls `mightContain(long, long)`, which would make mocks quite more difficult to read.
   
   This new implementation has the problem that false positives may affect the tests, but the bloom filter created is larger than required, so the possibility is very small. Even more, this false positives are deterministic. So even if one false positive is found in future, we can just change the examples to use a set of values that doesn't produce a collision.



-- 
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@pinot.apache.org

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] [pinot] richardstartin commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
richardstartin commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r884633136


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -435,4 +469,74 @@ private static Comparable convertValue(String stringValue, DataType dataType) {
       throw new BadQueryRequestException(e);
     }
   }
+
+  private static class ValueCache {
+    // As Predicates are recursive structures, their hashCode is quite expensive.
+    // By using an IdentityHashMap here we don't need to iterate over the recursive
+    // structure. This is specially useful in the IN expression.
+    private final Map<Predicate, Object> _cache = new IdentityHashMap<>();
+
+    public void add(EqPredicate pred) {
+      _cache.put(pred, new CachedValue(pred.getValue()));
+    }
+
+    public void add(InPredicate pred) {
+      List<CachedValue> list = new ArrayList<>(pred.getValues().size());
+      for (String value : pred.getValues()) {
+        list.add(new CachedValue(value));
+      }
+      _cache.put(pred, list);
+    }
+
+    public CachedValue get(EqPredicate pred, DataType dt) {
+      CachedValue cachedValue = (CachedValue) _cache.get(pred);
+      cachedValue.ensureDataType(dt);
+      return cachedValue;
+    }
+
+    public List<CachedValue> get(InPredicate pred, DataType dt) {
+      List<CachedValue> cachedValues = (List<CachedValue>) _cache.get(pred);
+      for (CachedValue cachedValue : cachedValues) {
+        cachedValue.ensureDataType(dt);
+      }
+      return cachedValues;
+    }
+
+    public static class CachedValue {
+      private final Object _value;
+      private boolean _hashed = false;
+      private long _hash1;
+      private long _hash2;
+      private DataType _dt;
+      private Comparable _comparableValue;
+
+      private CachedValue(Object value) {
+        _value = value;
+      }
+
+      private Comparable getComparableValue() {
+        assert _dt != null;
+        return _comparableValue;
+      }
+
+      private void ensureDataType(DataType dt) {
+        if (!dt.equals(_dt)) {

Review Comment:
   The behaviour you describe violates the [JLS](https://docs.oracle.com/javase/specs/jls/se9/html/jls-8.html#jls-8.9) so doesn’t seem like a real concern.
   
   > **An enum type has no instances other than those defined by its enum constants. It is a compile-time error to attempt to explicitly instantiate an enum type ([§15.9.1](https://docs.oracle.com/javase/specs/jls/se9/html/jls-15.html#jls-15.9.1))**.
   >
   > In addition to the compile-time error, three further mechanisms ensure that no instances of an enum type exist beyond those defined by its enum constants:
   >
   > The final clone method in Enum ensures that enum constants can never be cloned.
   >
   > Reflective instantiation of enum types is prohibited.
   >
   > Special treatment by the serialization mechanism ensures that duplicate instances are never created as a result of deserialization.



-- 
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@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r884676766


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -435,4 +469,74 @@ private static Comparable convertValue(String stringValue, DataType dataType) {
       throw new BadQueryRequestException(e);
     }
   }
+
+  private static class ValueCache {
+    // As Predicates are recursive structures, their hashCode is quite expensive.
+    // By using an IdentityHashMap here we don't need to iterate over the recursive
+    // structure. This is specially useful in the IN expression.
+    private final Map<Predicate, Object> _cache = new IdentityHashMap<>();
+
+    public void add(EqPredicate pred) {
+      _cache.put(pred, new CachedValue(pred.getValue()));
+    }
+
+    public void add(InPredicate pred) {
+      List<CachedValue> list = new ArrayList<>(pred.getValues().size());
+      for (String value : pred.getValues()) {
+        list.add(new CachedValue(value));
+      }
+      _cache.put(pred, list);
+    }
+
+    public CachedValue get(EqPredicate pred, DataType dt) {
+      CachedValue cachedValue = (CachedValue) _cache.get(pred);
+      cachedValue.ensureDataType(dt);
+      return cachedValue;
+    }
+
+    public List<CachedValue> get(InPredicate pred, DataType dt) {
+      List<CachedValue> cachedValues = (List<CachedValue>) _cache.get(pred);
+      for (CachedValue cachedValue : cachedValues) {
+        cachedValue.ensureDataType(dt);
+      }
+      return cachedValues;
+    }
+
+    public static class CachedValue {
+      private final Object _value;
+      private boolean _hashed = false;
+      private long _hash1;
+      private long _hash2;
+      private DataType _dt;
+      private Comparable _comparableValue;
+
+      private CachedValue(Object value) {
+        _value = value;
+      }
+
+      private Comparable getComparableValue() {
+        assert _dt != null;
+        return _comparableValue;
+      }
+
+      private void ensureDataType(DataType dt) {
+        if (!dt.equals(_dt)) {

Review Comment:
   I'm sure I found more than one instance of a enum literal in the past when deserializing them from json. May it be that the reflective instanciation was permited in Java 6? That or my memory is not what it was!
   
   Anyway, it seems clear that I should not be worried about that, so I'm gonna change it.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r882777594


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -483,26 +476,97 @@ private static Comparable convertValue(String stringValue, DataType dataType) {
     }
   }
 
-  private static class CachedValue {
-    private final String _strValue;
-    private final long _hash1;
-    private final long _hash2;
-    private DataType _dt;
-    private Comparable _comparableValue;
-
-    private CachedValue(Object value) {
-      _strValue = value.toString();
-      byte[] hash = GuavaBloomFilterReaderUtils.hash(_strValue);
-      _hash1 = Longs.fromBytes(hash[7], hash[6], hash[5], hash[4], hash[3], hash[2], hash[1], hash[0]);
-      _hash2 = Longs.fromBytes(hash[15], hash[14], hash[13], hash[12], hash[11], hash[10], hash[9], hash[8]);
+  private static class ValueCache {
+    // As Predicates are recursive structures, their hashCode is quite expensive.
+    // By using an IdentityHashMap here we don't need to iterate over the recursive
+    // structure. This is specially useful in the IN expression.
+    private final Map<Predicate, Object> _cache = new IdentityHashMap<>();
+
+    public void add(EqPredicate pred) {
+      _cache.put(pred, new CachedValue(pred.getValue()));
+    }
+
+    public void add(InPredicate pred) {
+      List<CachedValue> list = new ArrayList<>(pred.getValues().size());
+      for (String value : pred.getValues()) {
+        list.add(new CachedValue(value));
+      }
+      _cache.put(pred, list);
+    }
+
+    public CachedValue get(EqPredicate pred, DataType dt) {
+      CachedValue cachedValue = (CachedValue) _cache.get(pred);
+      cachedValue.ensureDataType(dt);
+      return cachedValue;
+    }
+
+    public List<CachedValue> get(InPredicate pred, DataType dt) {
+      List<CachedValue> cachedValues = (List<CachedValue>) _cache.get(pred);
+      for (CachedValue cachedValue : cachedValues) {
+        cachedValue.ensureDataType(dt);
+      }
+      return cachedValues;
     }
 
-    private Comparable getComparableValue(DataType dt) {
-      if (!dt.equals(_dt)) {
-        _dt = dt;
-        _comparableValue = convertValue(_strValue, dt);
+    public static class CachedValue {
+      private final Object _value;
+      private boolean _hashed = false;
+      private long _hash1;
+      private long _hash2;
+      private DataType _dt;
+      private Comparable _comparableValue;
+
+      private CachedValue(Object value) {
+        _value = value;
+      }
+
+      private Comparable getComparableValue() {
+        assert _dt != null;
+        return _comparableValue;
+      }
+
+      static final LongExtractor EXTRACTOR;
+
+      interface LongExtractor {
+        long extract(byte[] bytes, int index);
+      }
+
+      static {
+        LongExtractor extractor;
+        try {
+          MethodType mt = MethodType.methodType(VarHandle.class, Class.class, ByteOrder.class);
+          MethodHandle mh = MethodHandles.lookup().findStatic(MethodHandles.class, "byteArrayViewVarHandle", mt);
+
+          VarHandle varHandle = (VarHandle) mh.invokeExact(long[].class, ByteOrder.LITTLE_ENDIAN);
+          extractor = (bytes, index) -> (long) varHandle.get(bytes, index * 8);
+        } catch (Throwable e) {
+          extractor = (bytes, index) -> {
+            int i = index * 8;
+            return Longs.fromBytes(bytes[i + 7], bytes[i + 6], bytes[i + 5],
+                bytes[i + 4], bytes[i + 3], bytes[i + 2], bytes[i + 1], bytes[i]);
+          };

Review Comment:
   I see, `VarHandle` is Java 9, right?



-- 
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@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r882417186


##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/indexsegment/immutable/ImmutableSegmentImpl.java:
##########
@@ -65,6 +67,7 @@ public ImmutableSegmentImpl(SegmentDirectory segmentDirectory, SegmentMetadataIm
     _segmentMetadata = segmentMetadata;
     _indexContainerMap = columnIndexContainerMap;
     _starTreeIndexContainer = starTreeIndexContainer;
+    _lazyDataSource = new HashMap<>(segmentMetadata.getColumnMetadataMap().size());

Review Comment:
   You are right. I didn't think about concurrency.



-- 
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@pinot.apache.org

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] [pinot] gortiz commented on pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on PR #8766:
URL: https://github.com/apache/pinot/pull/8766#issuecomment-1138661638

   With the new changes, the performance is a bit worse:
   
   ```
   Benchmark                                (_numRows)  (_numSegments)  Mode  Cnt   Score   Error  Units
   BenchmarkColumnValueSegmentPruner.query          10              10  avgt    5   0.756 ± 0.001  us/op
   BenchmarkColumnValueSegmentPruner.query          10             100  avgt    5   6.893 ± 0.031  us/op
   BenchmarkColumnValueSegmentPruner.query          10            1000  avgt    5  78.610 ± 1.915  us/op
   ```
   
   All problems detected in the discussions should been already fixed. 
   
   > Great findings on the overhead of creating data source per column! Suggest making a separate PR for the optimization of data source. That one can benefit a lot of use cases and should not be under the scope of this PR
   
   I tried to change that file in different commits just in case we need to cherry pick them, but don't you think we would be able to merge this soon?


-- 
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@pinot.apache.org

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] [pinot] Jackie-Jiang commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r880970866


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -277,7 +286,8 @@ private boolean pruneEqPredicate(IndexSegment segment, EqPredicate eqPredicate,
     // Check bloom filter
     BloomFilterReader bloomFilter = dataSource.getBloomFilter();
     if (bloomFilter != null) {
-      if (!bloomFilter.mightContain(value.toString())) {
+      Hash128 hash = hashes.computeIfAbsent(value, Hash128::new);

Review Comment:
   I don't think we can use identity map here. Notice that the value might go through some conversion, so each time we are getting the same reference. We should probably just use a hash map from `String` to `Hash128`.



-- 
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@pinot.apache.org

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] [pinot] Jackie-Jiang commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r883172026


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -190,6 +201,33 @@ private void extractPredicateColumns(FilterContext filter, Set<String> eqInColum
         String column = lhs.getIdentifier();
 
         Predicate.Type predicateType = predicate.getType();
+        switch (predicateType) {
+          case EQ: {
+            eqInColumns.add(column);
+            cachedValues.put(predicate, new CachedValue(((EqPredicate) predicate).getValue()));

Review Comment:
   In most of the cases, all the segments should have the same schema, so IMO we should try to optimize on the happy path, but still support the unhappy path (not cause false positive and prune segments that should not be pruned).
   I like your approach of comparing the data type, and re-calculate the cached value if the data type does not match. It will have the same behavior as the current code, but perform good for happy path



-- 
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@pinot.apache.org

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] [pinot] gortiz commented on pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on PR #8766:
URL: https://github.com/apache/pinot/pull/8766#issuecomment-1138721759

   I've just removed the usage of VarHandle as it was quite messy to make it work with Java 8 and 11.
   
   The performance difference is not significant, so we may try to use VarHandle in future, but doesn't seem to have high priority.
   
   ```
   Benchmark                                (_numRows)  (_numSegments)  Mode  Cnt   Score   Error  Units
   BenchmarkColumnValueSegmentPruner.query          10              10  avgt    5   0.800 ± 0.016  us/op
   BenchmarkColumnValueSegmentPruner.query          10             100  avgt    5   5.974 ± 0.047  us/op
   BenchmarkColumnValueSegmentPruner.query          10            1000  avgt    5  80.062 ± 3.744  us/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.

To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r882409290


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -91,23 +95,28 @@ public List<IndexSegment> prune(List<IndexSegment> segments, QueryContext query)
     // Extract EQ/IN/RANGE predicate columns
     Set<String> eqInColumns = new HashSet<>();
     Set<String> rangeColumns = new HashSet<>();
-    extractPredicateColumns(filter, eqInColumns, rangeColumns);
+    // As Predicates are recursive structures, their hashCode is quite expensive.
+    // By using an IdentityHashMap here we don't need to iterate over the recursive
+    // structure. This is specially useful in the IN expression.
+    Map<Predicate, Object> cachedValues = new IdentityHashMap<>();
+    extractPredicateColumns(filter, eqInColumns, rangeColumns, cachedValues);
 
     if (eqInColumns.isEmpty() && rangeColumns.isEmpty()) {
       return segments;
     }
 
     int numSegments = segments.size();
     List<IndexSegment> selectedSegments = new ArrayList<>(numSegments);
+
     if (!eqInColumns.isEmpty() && query.isEnablePrefetch()) {
       Map[] dataSourceCaches = new Map[numSegments];
       FetchContext[] fetchContexts = new FetchContext[numSegments];
       try {
         // Prefetch bloom filter for columns within the EQ/IN predicate if exists
         for (int i = 0; i < numSegments; i++) {
           IndexSegment segment = segments.get(i);
-          Map<String, DataSource> dataSourceCache = new HashMap<>();
-          Map<String, List<ColumnIndexType>> columnToIndexList = new HashMap<>();
+          Map<String, DataSource> dataSourceCache = new HashMap<>(eqInColumns.size());

Review Comment:
   The reason I added the size is because I saw some resizes in the flamegraph. Anyway, the new implementation doesn't use `dataSourceCache` when immutableSegments are used, so it isn't going to be as remarkable as before.
   
   IMHO if the map is very small doesn't really matter if there are too many collisions, as a linear probe will be fast. In fact, if the map is very small, probably an ArrayList that filters by hashcode before equals would be than a map.
   
   



-- 
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@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r882753919


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -435,4 +446,17 @@ private static Comparable convertValue(String stringValue, DataType dataType) {
       throw new BadQueryRequestException(e);
     }
   }
+
+  private static class Hash128 {
+    private final long _hash1;
+    private final long _hash2;
+
+    private Hash128(Object value) {
+      String strValue = value.toString();
+
+      byte[] hash = GuavaBloomFilterReaderUtils.hash(strValue);
+      _hash1 = Longs.fromBytes(hash[7], hash[6], hash[5], hash[4], hash[3], hash[2], hash[1], hash[0]);
+      _hash2 = Longs.fromBytes(hash[15], hash[14], hash[13], hash[12], hash[11], hash[10], hash[9], hash[8]);

Review Comment:
   I've never try to do something like that. I hope I did it in a way that can work in any JVM >= 7, but I'm not sure, can you @richardstartin review this carefully?



-- 
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@pinot.apache.org

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] [pinot] Jackie-Jiang commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r883161749


##########
pinot-core/src/test/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPrunerTest.java:
##########
@@ -148,17 +158,18 @@ public void testBloomFilterInPredicatePruning() {
     when(indexSegment.getDataSource("column")).thenReturn(dataSource);
     // Add support for bloom filter
     DataSourceMetadata dataSourceMetadata = mock(DataSourceMetadata.class);
-    BloomFilterReader bloomFilterReader = mock(BloomFilterReader.class);
+    BloomFilterReader bloomFilterReader = new BloomFilterReaderBuilder()
+        .put("1")

Review Comment:
   I usually put minor/nit for optional comment, and you may ignore them. I'm good with both format, and I put one comment here because I remember Richard likes the compact way so that we can get more content when reading the code on a small screen :-P



-- 
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@pinot.apache.org

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] [pinot] richardstartin commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
richardstartin commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r882426219


##########
pinot-core/src/test/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPrunerTest.java:
##########
@@ -148,17 +158,18 @@ public void testBloomFilterInPredicatePruning() {
     when(indexSegment.getDataSource("column")).thenReturn(dataSource);
     // Add support for bloom filter
     DataSourceMetadata dataSourceMetadata = mock(DataSourceMetadata.class);
-    BloomFilterReader bloomFilterReader = mock(BloomFilterReader.class);
+    BloomFilterReader bloomFilterReader = new BloomFilterReaderBuilder()
+        .put("1")

Review Comment:
   We actually relaxed the formatter on builders because there was consensus that a line per method was easier to read. It's only a nit so you don't have to do this, it's just a suggestion.



-- 
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@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r880699775


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -99,6 +102,11 @@ public List<IndexSegment> prune(List<IndexSegment> segments, QueryContext query)
 
     int numSegments = segments.size();
     List<IndexSegment> selectedSegments = new ArrayList<>(numSegments);
+
+    // By using an IdentityHashMap, we may be creating more entries, but each lookup will be faster
+    // which should compensate in cases where there are hundreds of segments
+    Map<Object, Hash128> hashCache = new IdentityHashMap<>();

Review Comment:
   IdentityMap removes the call to equals, which can be relatively expensive when the keys (specially strings) are not the same reference but has the same hash code. This is can happen when an expression contains the same literal several times. For example, in the following query, the literal "someString" may be the same instance or a different one:
   
   ```sql
   select * from Table where col1 = "someString" and col2 = "someString"
   ```



-- 
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@pinot.apache.org

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] [pinot] richardstartin commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
richardstartin commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r880814967


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -435,4 +446,17 @@ private static Comparable convertValue(String stringValue, DataType dataType) {
       throw new BadQueryRequestException(e);
     }
   }
+
+  private static class Hash128 {
+    private final long _hash1;
+    private final long _hash2;
+
+    private Hash128(Object value) {
+      String strValue = value.toString();
+
+      byte[] hash = GuavaBloomFilterReaderUtils.hash(strValue);
+      _hash1 = Longs.fromBytes(hash[7], hash[6], hash[5], hash[4], hash[3], hash[2], hash[1], hash[0]);
+      _hash2 = Longs.fromBytes(hash[15], hash[14], hash[13], hash[12], hash[11], hash[10], hash[9], hash[8]);

Review Comment:
   let's improve this code on JDK11+ with `MethodHandles.byteArrayViewVarHandle()` (which will itself need to be dealt with via `MethodHandle` :() so we can read two longs directly from the array. This can use `Unsafe` on JDK8, or just do it the slow way like 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@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r881295029


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -99,6 +102,11 @@ public List<IndexSegment> prune(List<IndexSegment> segments, QueryContext query)
 
     int numSegments = segments.size();
     List<IndexSegment> selectedSegments = new ArrayList<>(numSegments);
+
+    // By using an IdentityHashMap, we may be creating more entries, but each lookup will be faster
+    // which should compensate in cases where there are hundreds of segments
+    Map<Object, Hash128> hashCache = new IdentityHashMap<>();

Review Comment:
   As shown by @Jackie-Jiang, in the equals case it is not correct to use the identity, so I'm going to use a normal map here.



-- 
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@pinot.apache.org

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] [pinot] gortiz commented on pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on PR #8766:
URL: https://github.com/apache/pinot/pull/8766#issuecomment-1137183022

   I've added two new commits, creating what I called V2 and V3. I ran the benchmark in both phases. Taking into consideration what @richardstartin said about IdentityHashMap, I ran these tests twice: One using the IdentityHashMap and another one using a normal HashMap.
   
   The first commit, V2, tries to apply what @Jackie-Jiang suggested about not only cache the hashes but also the converted values and instead of doing that lazily, just eagerly do that while the expression is visited during the prepare phase. This implies that the key used in the cache is a `Predicate`, not the `literals`. I also had to break the safe compatibility, because the value of the EQ operators is a single `CachedValue` but the value of the IN operator is a list of them. I could create two maps instead, but I didn't like that solution either. Which one would you prefer? Do you have another solution in mind?
   
   The second commit, V3, has a bigger impact (it cuts the cost by a half!). The idea here is to add a cache of DataSource in ImmutableSegment. It is clear in the flamegraphs created from the benchmark that a lot of time was spent trying to calculate this value. It makes a lot of sense, as there are a lot of segments and we need to create a new instance for each one. In fact the instance creation is quite expensive not because it has to generate memory, but due to the fact that the columns used as keys are different strings that has the same content. This force HashMap to calculate compare them by equals, which is relative expensive when the operation itself is in the order of microseconds.
   
   In the benchmark each segment is read tons of times, so having the DataSource cached on all executions but the first is a huge advantage. In a Pinot Server that condition should also be true and the improvement should applicable to other methods that heavily use `getDataSource()`. As I said in another comment, I'm not sure about the correctness of this change. It seems correct but I would like the confirmation from someone else that knows the codebase.  
   
   The results of the benchmark are the following:
   
   Before any change:
   ```
   Benchmark                           (_numRows)  (_numSegments)  Mode  Cnt   Score   Error  Units
   BenchmarkServerSegmentPruner.query          10              10  avgt    5   1.426 ± 0.003  us/op
   BenchmarkServerSegmentPruner.query          10             100  avgt    5  14.719 ± 1.342  us/op
   BenchmarkServerSegmentPruner.query          10            1000  avgt    5  174.879 ± 5.115  us/op
   ```
   V1 (yesterday):
   ```
   Benchmark                           (_numRows)  (_numSegments)  Mode  Cnt   Score   Error  Units
   BenchmarkServerSegmentPruner.query          10              10  avgt    5   0.972 ± 0.003  us/op
   BenchmarkServerSegmentPruner.query          10             100  avgt    5  10.149 ± 0.046  us/op
   BenchmarkServerSegmentPruner.query          10            1000  avgt    5  135.063 ± 14.670  us/op
   ```
   V2
   ```
   V2 with HashMap
   Benchmark                                (_numRows)  (_numSegments)  Mode  Cnt    Score   Error  Units
   BenchmarkColumnValueSegmentPruner.query          10              10  avgt    5    1.325 ± 0.029  us/op
   BenchmarkColumnValueSegmentPruner.query          10             100  avgt    5   12.851 ± 0.171  us/op
   BenchmarkColumnValueSegmentPruner.query          10            1000  avgt    5  138.314 ± 2.238  us/op
   
   V2 with IdentityHashMap
   Benchmark                                (_numRows)  (_numSegments)  Mode  Cnt    Score   Error  Units
   BenchmarkColumnValueSegmentPruner.query          10              10  avgt    5    1.110 ± 0.001  us/op
   BenchmarkColumnValueSegmentPruner.query          10             100  avgt    5   10.659 ± 0.139  us/op
   BenchmarkColumnValueSegmentPruner.query          10            1000  avgt    5  120.608 ± 0.159  us/op
   ```
   
   V3
   ```
   V3 with HashMap
   Benchmark                                (_numRows)  (_numSegments)  Mode  Cnt   Score   Error  Units
   BenchmarkColumnValueSegmentPruner.query          10              10  avgt    5   0.971 ± 0.003  us/op
   BenchmarkColumnValueSegmentPruner.query          10             100  avgt    5   4.843 ± 0.045  us/op
   BenchmarkColumnValueSegmentPruner.query          10            1000  avgt    5  72.658 ± 0.735  us/op
   
   V3 with IdentityHashMap
   Benchmark                                (_numRows)  (_numSegments)  Mode  Cnt   Score   Error  Units
   BenchmarkColumnValueSegmentPruner.query          10              10  avgt    5   0.556 ± 0.001  us/op
   BenchmarkColumnValueSegmentPruner.query          10             100  avgt    5   4.964 ± 0.268  us/op
   BenchmarkColumnValueSegmentPruner.query          10            1000  avgt    5  58.304 ± 0.382  us/op
   ```
   
   I cannot print them all in a single JMH execution because each one requires to do some modifications in the code. I will try to edit this message to create a table to make the difference clear, but the TL;DR: is that by merging these changes we should get an almost 57% improvement when pruning 1000 segments


-- 
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@pinot.apache.org

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] [pinot] richardstartin commented on pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
richardstartin commented on PR #8766:
URL: https://github.com/apache/pinot/pull/8766#issuecomment-1137731904

   Thanks for the thorough review @Jackie-Jiang , I missed some of the issues


-- 
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@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r882436535


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -190,6 +201,33 @@ private void extractPredicateColumns(FilterContext filter, Set<String> eqInColum
         String column = lhs.getIdentifier();
 
         Predicate.Type predicateType = predicate.getType();
+        switch (predicateType) {
+          case EQ: {
+            eqInColumns.add(column);
+            cachedValues.put(predicate, new CachedValue(((EqPredicate) predicate).getValue()));

Review Comment:
   Nice catch! I was so focused on the IN case that didn't see that problem int he EQ case. 
   
   This can be a big problem. As we need to use the hash of the converted value and the converted value depends on each column, we will need to either pick one type as the _main_ one and then not prune segments whose column type doesn't match with it or we would need to have a map from datatype to Pair<Long, Long> (or equivalent) to do not evaluate the hash every time. Both solutions are bad in terms of performance.
   
   The first option seems cheap to implement (we don't need to lookup for the data type every time) and we always think that there should be a very small proportion of segments with a different column type, but given that we don't know the actual type of the column in the schema, we need to either pick the _main_ type with some heuristic (randomly, the first we find, etc) or iterate over all the segments to look for the most used datatype for each column, which may be expensive.
   
   I'm going to think about that and try some implementations. Also, I'm going to change `ColumnValueSegmentPrunerTest` to use doubles instead if ints. This should automatically tests errors like this without the invaluable review of Jackie.



-- 
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@pinot.apache.org

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] [pinot] richardstartin commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
richardstartin commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r880815921


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -99,6 +102,11 @@ public List<IndexSegment> prune(List<IndexSegment> segments, QueryContext query)
 
     int numSegments = segments.size();
     List<IndexSegment> selectedSegments = new ArrayList<>(numSegments);
+
+    // By using an IdentityHashMap, we may be creating more entries, but each lookup will be faster
+    // which should compensate in cases where there are hundreds of segments
+    Map<Object, Hash128> hashCache = new IdentityHashMap<>();

Review Comment:
   Do you have some data to justify this? Computing identity hash codes have various side effects and it's not always a win.



-- 
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@pinot.apache.org

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] [pinot] codecov-commenter commented on pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
codecov-commenter commented on PR #8766:
URL: https://github.com/apache/pinot/pull/8766#issuecomment-1137208380

   # [Codecov](https://codecov.io/gh/apache/pinot/pull/8766?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) Report
   > Merging [#8766](https://codecov.io/gh/apache/pinot/pull/8766?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (20a4832) into [master](https://codecov.io/gh/apache/pinot/commit/15416e5e8ada7e8ab546017f048a011862d65ec2?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (15416e5) will **decrease** coverage by `1.30%`.
   > The diff coverage is `91.80%`.
   
   ```diff
   @@             Coverage Diff              @@
   ##             master    #8766      +/-   ##
   ============================================
   - Coverage     69.73%   68.42%   -1.31%     
   + Complexity     4617     4604      -13     
   ============================================
     Files          1732     1736       +4     
     Lines         90741    91217     +476     
     Branches      13508    13639     +131     
   ============================================
   - Hits          63279    62419     -860     
   - Misses        23055    24409    +1354     
   + Partials       4407     4389      -18     
   ```
   
   | Flag | Coverage Δ | |
   |---|---|---|
   | integration1 | `26.92% <77.04%> (-0.22%)` | :arrow_down: |
   | integration2 | `?` | |
   | unittests1 | `66.18% <91.80%> (-0.11%)` | :arrow_down: |
   | unittests2 | `14.17% <0.00%> (-0.02%)` | :arrow_down: |
   
   Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#carryforward-flags-in-the-pull-request-comment) to find out more.
   
   | [Impacted Files](https://codecov.io/gh/apache/pinot/pull/8766?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) | Coverage Δ | |
   |---|---|---|
   | [...ot/core/query/pruner/ColumnValueSegmentPruner.java](https://codecov.io/gh/apache/pinot/pull/8766/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9xdWVyeS9wcnVuZXIvQ29sdW1uVmFsdWVTZWdtZW50UHJ1bmVyLmphdmE=) | `79.03% <91.07%> (+3.26%)` | :arrow_up: |
   | [...l/indexsegment/immutable/ImmutableSegmentImpl.java](https://codecov.io/gh/apache/pinot/pull/8766/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3Qtc2VnbWVudC1sb2NhbC9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3Qvc2VnbWVudC9sb2NhbC9pbmRleHNlZ21lbnQvaW1tdXRhYmxlL0ltbXV0YWJsZVNlZ21lbnRJbXBsLmphdmE=) | `66.66% <100.00%> (+1.04%)` | :arrow_up: |
   | [...apache/pinot/common/helix/ExtraInstanceConfig.java](https://codecov.io/gh/apache/pinot/pull/8766/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29tbW9uL3NyYy9tYWluL2phdmEvb3JnL2FwYWNoZS9waW5vdC9jb21tb24vaGVsaXgvRXh0cmFJbnN0YW5jZUNvbmZpZy5qYXZh) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
   | [...t/core/plan/StreamingInstanceResponsePlanNode.java](https://codecov.io/gh/apache/pinot/pull/8766/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9wbGFuL1N0cmVhbWluZ0luc3RhbmNlUmVzcG9uc2VQbGFuTm9kZS5qYXZh) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
   | [...ore/operator/streaming/StreamingResponseUtils.java](https://codecov.io/gh/apache/pinot/pull/8766/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9vcGVyYXRvci9zdHJlYW1pbmcvU3RyZWFtaW5nUmVzcG9uc2VVdGlscy5qYXZh) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
   | [...ager/realtime/PeerSchemeSplitSegmentCommitter.java](https://codecov.io/gh/apache/pinot/pull/8766/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9kYXRhL21hbmFnZXIvcmVhbHRpbWUvUGVlclNjaGVtZVNwbGl0U2VnbWVudENvbW1pdHRlci5qYXZh) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
   | [...ator/streaming/StreamingSelectionOnlyOperator.java](https://codecov.io/gh/apache/pinot/pull/8766/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9vcGVyYXRvci9zdHJlYW1pbmcvU3RyZWFtaW5nU2VsZWN0aW9uT25seU9wZXJhdG9yLmphdmE=) | `0.00% <0.00%> (-90.00%)` | :arrow_down: |
   | [...he/pinot/core/plan/StreamingSelectionPlanNode.java](https://codecov.io/gh/apache/pinot/pull/8766/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9wbGFuL1N0cmVhbWluZ1NlbGVjdGlvblBsYW5Ob2RlLmphdmE=) | `0.00% <0.00%> (-88.89%)` | :arrow_down: |
   | [...che/pinot/common/auth/StaticTokenAuthProvider.java](https://codecov.io/gh/apache/pinot/pull/8766/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29tbW9uL3NyYy9tYWluL2phdmEvb3JnL2FwYWNoZS9waW5vdC9jb21tb24vYXV0aC9TdGF0aWNUb2tlbkF1dGhQcm92aWRlci5qYXZh) | `0.00% <0.00%> (-87.50%)` | :arrow_down: |
   | [...re/query/reduce/SelectionOnlyStreamingReducer.java](https://codecov.io/gh/apache/pinot/pull/8766/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9xdWVyeS9yZWR1Y2UvU2VsZWN0aW9uT25seVN0cmVhbWluZ1JlZHVjZXIuamF2YQ==) | `0.00% <0.00%> (-80.96%)` | :arrow_down: |
   | ... and [162 more](https://codecov.io/gh/apache/pinot/pull/8766/diff?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) | |
   
   ------
   
   [Continue to review full report at Codecov](https://codecov.io/gh/apache/pinot/pull/8766?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation).
   > **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation)
   > `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
   > Powered by [Codecov](https://codecov.io/gh/apache/pinot/pull/8766?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation). Last update [15416e5...20a4832](https://codecov.io/gh/apache/pinot/pull/8766?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation).
   


-- 
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@pinot.apache.org

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] [pinot] Jackie-Jiang commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r881937489


##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/indexsegment/immutable/ImmutableSegmentImpl.java:
##########
@@ -65,6 +67,7 @@ public ImmutableSegmentImpl(SegmentDirectory segmentDirectory, SegmentMetadataIm
     _segmentMetadata = segmentMetadata;
     _indexContainerMap = columnIndexContainerMap;
     _starTreeIndexContainer = starTreeIndexContainer;
+    _lazyDataSource = new HashMap<>(segmentMetadata.getColumnMetadataMap().size());

Review Comment:
   We can create all the data sources up-front in the constructor instead of creating them lazily. If we create them lazily, we need to use a concurrent map here, which might impact performance; also, the first query hitting the column could be slower than other queries.



-- 
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@pinot.apache.org

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] [pinot] gortiz commented on pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on PR #8766:
URL: https://github.com/apache/pinot/pull/8766#issuecomment-1137309522

   The same content as before, but all together, sorted by number of segments:
   
   ```
   Benchmark  (hash/iden)  (_numSegments)    Score    Error  Units
   V1               iden         10          0.972  ± 0.003  us/op
   V0               iden         10          1.426  ± 0.003  us/op
   V2          hash              10          1.325  ± 0.029  us/op
   V2               iden         10          1.110  ± 0.001  us/op
   V3          hash              10          0.971  ± 0.003  us/op
   V3               iden         10          0.556  ± 0.001  us/op
   
   V0               iden        100         14.719  ± 1.342  us/op
   V1               iden        100         10.149  ± 0.046  us/op
   V2          hash             100         12.851  ± 0.171  us/op
   V2               iden        100         10.659  ± 0.139  us/op
   V3          hash             100          4.843  ± 0.045  us/op
   V3               iden        100          4.964  ± 0.268  us/op
   
   V0               iden       1000        174.879  ± 5.115  us/op
   V1               iden       1000        135.063  ±14.670  us/op
   V2          hash            1000        138.314  ± 2.238  us/op
   V2               iden       1000        120.608  ± 0.159  us/op
   V3          hash            1000         72.658  ± 0.735  us/op
   V3               iden       1000         58.304  ± 0.382  us/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.

To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org

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] [pinot] Jackie-Jiang commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r881989071


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -190,6 +201,33 @@ private void extractPredicateColumns(FilterContext filter, Set<String> eqInColum
         String column = lhs.getIdentifier();
 
         Predicate.Type predicateType = predicate.getType();
+        switch (predicateType) {
+          case EQ: {
+            eqInColumns.add(column);
+            cachedValues.put(predicate, new CachedValue(((EqPredicate) predicate).getValue()));
+            break;
+          }
+          case IN: {
+            InPredicate inPredicate = (InPredicate) predicate;
+            if (inPredicate.getValues().size() > _inPredicateThreshold) {
+              break;
+            }
+            eqInColumns.add(column);
+            List<CachedValue> list = new ArrayList<>(inPredicate.getValues().size());
+            for (String value : inPredicate.getValues()) {
+              list.add(new CachedValue(value));
+            }
+            cachedValues.put(predicate, list);
+            break;
+          }
+          case RANGE: {
+            rangeColumns.add(column);
+            break;
+          }
+          default: {
+            break;
+          }
+        }
         if (predicateType == Predicate.Type.EQ || (predicateType == Predicate.Type.IN

Review Comment:
   (MAJOR) We are adding the columns twice



##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -190,6 +201,33 @@ private void extractPredicateColumns(FilterContext filter, Set<String> eqInColum
         String column = lhs.getIdentifier();
 
         Predicate.Type predicateType = predicate.getType();
+        switch (predicateType) {
+          case EQ: {
+            eqInColumns.add(column);
+            cachedValues.put(predicate, new CachedValue(((EqPredicate) predicate).getValue()));

Review Comment:
   (MAJOR) There is also correctness issue. We need to calculate hash on the converted value instead of the value in the predicate. For example, when the column is of data type `DOUBLE`, and the predicate is `col = 1`, we need to calculate hash on `"1.0"` instead of `"1"`.



##########
pinot-core/src/test/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPrunerTest.java:
##########
@@ -148,17 +158,18 @@ public void testBloomFilterInPredicatePruning() {
     when(indexSegment.getDataSource("column")).thenReturn(dataSource);
     // Add support for bloom filter
     DataSourceMetadata dataSourceMetadata = mock(DataSourceMetadata.class);
-    BloomFilterReader bloomFilterReader = mock(BloomFilterReader.class);
+    BloomFilterReader bloomFilterReader = new BloomFilterReaderBuilder()
+        .put("1")

Review Comment:
   (nit) Make it one line



##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -190,6 +201,33 @@ private void extractPredicateColumns(FilterContext filter, Set<String> eqInColum
         String column = lhs.getIdentifier();
 
         Predicate.Type predicateType = predicate.getType();
+        switch (predicateType) {
+          case EQ: {
+            eqInColumns.add(column);
+            cachedValues.put(predicate, new CachedValue(((EqPredicate) predicate).getValue()));

Review Comment:
   This can cause unnecessary overhead when bloom filter is not available for the column. We should still update the map lazily when applying the bloom filter



##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -91,23 +95,28 @@ public List<IndexSegment> prune(List<IndexSegment> segments, QueryContext query)
     // Extract EQ/IN/RANGE predicate columns
     Set<String> eqInColumns = new HashSet<>();
     Set<String> rangeColumns = new HashSet<>();
-    extractPredicateColumns(filter, eqInColumns, rangeColumns);
+    // As Predicates are recursive structures, their hashCode is quite expensive.
+    // By using an IdentityHashMap here we don't need to iterate over the recursive
+    // structure. This is specially useful in the IN expression.
+    Map<Predicate, Object> cachedValues = new IdentityHashMap<>();
+    extractPredicateColumns(filter, eqInColumns, rangeColumns, cachedValues);
 
     if (eqInColumns.isEmpty() && rangeColumns.isEmpty()) {
       return segments;
     }
 
     int numSegments = segments.size();
     List<IndexSegment> selectedSegments = new ArrayList<>(numSegments);
+
     if (!eqInColumns.isEmpty() && query.isEnablePrefetch()) {
       Map[] dataSourceCaches = new Map[numSegments];
       FetchContext[] fetchContexts = new FetchContext[numSegments];
       try {
         // Prefetch bloom filter for columns within the EQ/IN predicate if exists
         for (int i = 0; i < numSegments; i++) {
           IndexSegment segment = segments.get(i);
-          Map<String, DataSource> dataSourceCache = new HashMap<>();
-          Map<String, List<ColumnIndexType>> columnToIndexList = new HashMap<>();
+          Map<String, DataSource> dataSourceCache = new HashMap<>(eqInColumns.size());

Review Comment:
   The parameter here is the initial capacity without regards to the load factor. So if we insert this number of entries to the map, very likely it needs to do a resize which is undesired. Also, if there are very few columns, initializing a very small map can increase the chance of hash collision, and cause worse performance.
   I'd suggest just using the empty constructor, or we do have util methods `HashUtil.getHashMapCapacity()` and `HashUtil.getMinHashSetSize()` to create the capacity with regard to the load factor (IMO that is not necessary, the default initial capacity of 16 should be good for most scenarios)



##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -435,4 +482,27 @@ private static Comparable convertValue(String stringValue, DataType dataType) {
       throw new BadQueryRequestException(e);
     }
   }
+
+  private static class CachedValue {
+    private final String _strValue;
+    private final long _hash1;
+    private final long _hash2;
+    private DataType _dt;
+    private Comparable _comparableValue;
+
+    private CachedValue(Object value) {
+      _strValue = value.toString();
+      byte[] hash = GuavaBloomFilterReaderUtils.hash(_strValue);
+      _hash1 = Longs.fromBytes(hash[7], hash[6], hash[5], hash[4], hash[3], hash[2], hash[1], hash[0]);
+      _hash2 = Longs.fromBytes(hash[15], hash[14], hash[13], hash[12], hash[11], hash[10], hash[9], hash[8]);
+    }
+
+    private Comparable getComparableValue(DataType dt) {

Review Comment:
   Here we made an assumption that all the segments follow the same schema (the same column always have the same data type across all segments), which might not always be the case. In some corner cases, different segment might be generated with different schema.
   We may cache a data type here, and check if the data type matches before pruning the segment. If the data type does not match, skip pruning the segment. This could cause false negative for the pruning, but should be very rare



-- 
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@pinot.apache.org

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] [pinot] Jackie-Jiang commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r883923117


##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/indexsegment/immutable/ImmutableSegmentImpl.java:
##########
@@ -65,6 +68,15 @@ public ImmutableSegmentImpl(SegmentDirectory segmentDirectory, SegmentMetadataIm
     _segmentMetadata = segmentMetadata;
     _indexContainerMap = columnIndexContainerMap;
     _starTreeIndexContainer = starTreeIndexContainer;
+    _dataSources = new HashMap<>(HashUtil.getHashMapCapacity(segmentMetadata.getColumnMetadataMap().size()));
+
+    for (String colName : segmentMetadata.getColumnMetadataMap().keySet()) {

Review Comment:
   We can reduce the map lookups by using `entrySet()`



##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -435,4 +469,74 @@ private static Comparable convertValue(String stringValue, DataType dataType) {
       throw new BadQueryRequestException(e);
     }
   }
+
+  private static class ValueCache {
+    // As Predicates are recursive structures, their hashCode is quite expensive.
+    // By using an IdentityHashMap here we don't need to iterate over the recursive
+    // structure. This is specially useful in the IN expression.
+    private final Map<Predicate, Object> _cache = new IdentityHashMap<>();
+
+    public void add(EqPredicate pred) {
+      _cache.put(pred, new CachedValue(pred.getValue()));
+    }
+
+    public void add(InPredicate pred) {
+      List<CachedValue> list = new ArrayList<>(pred.getValues().size());
+      for (String value : pred.getValues()) {
+        list.add(new CachedValue(value));
+      }
+      _cache.put(pred, list);
+    }
+
+    public CachedValue get(EqPredicate pred, DataType dt) {
+      CachedValue cachedValue = (CachedValue) _cache.get(pred);
+      cachedValue.ensureDataType(dt);
+      return cachedValue;
+    }
+
+    public List<CachedValue> get(InPredicate pred, DataType dt) {
+      List<CachedValue> cachedValues = (List<CachedValue>) _cache.get(pred);
+      for (CachedValue cachedValue : cachedValues) {
+        cachedValue.ensureDataType(dt);
+      }
+      return cachedValues;
+    }
+
+    public static class CachedValue {
+      private final Object _value;
+      private boolean _hashed = false;
+      private long _hash1;
+      private long _hash2;
+      private DataType _dt;
+      private Comparable _comparableValue;
+
+      private CachedValue(Object value) {
+        _value = value;
+      }
+
+      private Comparable getComparableValue() {
+        assert _dt != null;
+        return _comparableValue;
+      }
+
+      private void ensureDataType(DataType dt) {
+        if (!dt.equals(_dt)) {
+          String strValue = _value.toString();
+          _dt = dt;
+          _comparableValue = convertValue(strValue, dt);
+          _hashed = false;
+        }
+      }
+
+      private boolean mightBeContained(BloomFilterReader bloomFilter) {
+        if (!_hashed) {
+          byte[] hash = GuavaBloomFilterReaderUtils.hash(_comparableValue.toString());
+          _hash1 = Longs.fromBytes(hash[7], hash[6], hash[5], hash[4], hash[3], hash[2], hash[1], hash[0]);

Review Comment:
   (minor) Suggest moving the calculation of `hash1` and `hash2` to `GuavaBloomFilterReaderUtils` for better logic isolation. We might also want to have an `assert bloomFilter instanceof BaseGuavaBloomFilterReader` since this calculation logic only applies to the guava bloom filter



##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -435,4 +469,74 @@ private static Comparable convertValue(String stringValue, DataType dataType) {
       throw new BadQueryRequestException(e);
     }
   }
+
+  private static class ValueCache {
+    // As Predicates are recursive structures, their hashCode is quite expensive.
+    // By using an IdentityHashMap here we don't need to iterate over the recursive
+    // structure. This is specially useful in the IN expression.
+    private final Map<Predicate, Object> _cache = new IdentityHashMap<>();
+
+    public void add(EqPredicate pred) {
+      _cache.put(pred, new CachedValue(pred.getValue()));
+    }
+
+    public void add(InPredicate pred) {
+      List<CachedValue> list = new ArrayList<>(pred.getValues().size());
+      for (String value : pred.getValues()) {
+        list.add(new CachedValue(value));
+      }
+      _cache.put(pred, list);
+    }
+
+    public CachedValue get(EqPredicate pred, DataType dt) {
+      CachedValue cachedValue = (CachedValue) _cache.get(pred);
+      cachedValue.ensureDataType(dt);
+      return cachedValue;
+    }
+
+    public List<CachedValue> get(InPredicate pred, DataType dt) {
+      List<CachedValue> cachedValues = (List<CachedValue>) _cache.get(pred);
+      for (CachedValue cachedValue : cachedValues) {
+        cachedValue.ensureDataType(dt);
+      }
+      return cachedValues;
+    }
+
+    public static class CachedValue {
+      private final Object _value;
+      private boolean _hashed = false;
+      private long _hash1;
+      private long _hash2;
+      private DataType _dt;
+      private Comparable _comparableValue;
+
+      private CachedValue(Object value) {
+        _value = value;
+      }
+
+      private Comparable getComparableValue() {
+        assert _dt != null;
+        return _comparableValue;
+      }
+
+      private void ensureDataType(DataType dt) {
+        if (!dt.equals(_dt)) {

Review Comment:
   (nit) 
   ```suggestion
           if (dt != _dt) {
   ```



##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/indexsegment/immutable/ImmutableSegmentImpl.java:
##########
@@ -65,6 +68,15 @@ public ImmutableSegmentImpl(SegmentDirectory segmentDirectory, SegmentMetadataIm
     _segmentMetadata = segmentMetadata;
     _indexContainerMap = columnIndexContainerMap;
     _starTreeIndexContainer = starTreeIndexContainer;
+    _dataSources = new HashMap<>(HashUtil.getHashMapCapacity(segmentMetadata.getColumnMetadataMap().size()));
+
+    for (String colName : segmentMetadata.getColumnMetadataMap().keySet()) {
+      ColumnMetadata columnMetadata = _segmentMetadata.getColumnMetadataFor(colName);
+      Preconditions.checkNotNull(columnMetadata,

Review Comment:
   This check is redundant because we actually looped over the metadata map



-- 
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@pinot.apache.org

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] [pinot] gortiz commented on a diff in pull request #8766: Optimize ColumnValueSegmentPruner by caching value hashes

Posted by GitBox <gi...@apache.org>.
gortiz commented on code in PR #8766:
URL: https://github.com/apache/pinot/pull/8766#discussion_r882415004


##########
pinot-core/src/main/java/org/apache/pinot/core/query/pruner/ColumnValueSegmentPruner.java:
##########
@@ -435,4 +482,27 @@ private static Comparable convertValue(String stringValue, DataType dataType) {
       throw new BadQueryRequestException(e);
     }
   }
+
+  private static class CachedValue {
+    private final String _strValue;
+    private final long _hash1;
+    private final long _hash2;
+    private DataType _dt;
+    private Comparable _comparableValue;
+
+    private CachedValue(Object value) {
+      _strValue = value.toString();
+      byte[] hash = GuavaBloomFilterReaderUtils.hash(_strValue);
+      _hash1 = Longs.fromBytes(hash[7], hash[6], hash[5], hash[4], hash[3], hash[2], hash[1], hash[0]);
+      _hash2 = Longs.fromBytes(hash[15], hash[14], hash[13], hash[12], hash[11], hash[10], hash[9], hash[8]);
+    }
+
+    private Comparable getComparableValue(DataType dt) {

Review Comment:
   Something like that is what I wanted to do, but I don't know what I was thinking when I added the if predicate. Now it should be correct. The idea is to store the datatype used to convert the value. If the datatype is the same, the cached value is used. If the datatype is different, the cached value is reevaluated. This shouldn't change the semantic we already have and it should be more efficient except in very bizarre cases like having interleaved segments where columns datatypes are different.



-- 
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@pinot.apache.org

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