Repository: polarsignals/frostdb
Pull request #520 (2023-09-05 19:32:41)

*: filter out column chunks with some null values
Previously, if a column chunk had at least one null value, we would automatically further filter it in the execution engine. However, there are cases where we can rely on min/max values as long as they are non-null and the column chunk is not all nulls to filter out column chunks. This greatly reduces load on the execution engine.


Patch:
diff --git a/binaryscalarexpr.go b/binaryscalarexpr.go
index b438be3..0569b1b 100644
--- a/binaryscalarexpr.go
+++ b/binaryscalarexpr.go
@@ -112,25 +112,58 @@ func BinaryScalarOperation(left parquet.ColumnChunk, right parquet.Value, operat
 		return true, nil
 	}
 
-	// The following operators are not optimized. If there is at least one null
-	// in the page, return true for safety since min/max values are not
-	// guaranteed to be set correctly. We can definitely improve this in the
-	// future for better performance. This is not a correctness issue because
-	// the execution engine will take care of correctly applying the operator.
-	// This applies if the right value is null as well, since it cannot be
-	// compared.
-	if numNulls > 0 || right.IsNull() {
+	// If right is NULL automatically return that the column chunk needs further
+	// processing. According to SQL semantics we might be able to elide column
+	// chunks in these cases since NULL is not comparable to anything else, but
+	// play it safe (delegate to execution engine) for now since we shouldn't
+	// have many of these cases.
+	if right.IsNull() {
 		return true, nil
 	}
+
+	if numNulls == left.NumValues() {
+		// In this case min/max values are meaningless and not comparable to the
+		// right expression, so we can automatically discard the column chunk.
+		return false, nil
+	}
+
 	switch operator {
 	case logicalplan.OpLtEq:
-		return compare(Min(left), right) <= 0, nil
+		min := Min(left)
+		if min.IsNull() {
+			// If min is null, we don't know what the non-null min value is, so
+			// we need to let the execution engine scan this column chunk
+			// further.
+			return true, nil
+		}
+		return compare(min, right) <= 0, nil
 	case logicalplan.OpLt:
-		return compare(Min(left), right) < 0, nil
+		min := Min(left)
+		if min.IsNull() {
+			// If min is null, we don't know what the non-null min value is, so
+			// we need to let the execution engine scan this column chunk
+			// further.
+			return true, nil
+		}
+		return compare(min, right) < 0, nil
 	case logicalplan.OpGt:
-		return compare(Max(left), right) > 0, nil
+		max := Max(left)
+		if max.IsNull() {
+			// If max is null, we don't know what the non-null max value is, so
+			// we need to let the execution engine scan this column chunk
+			// further.
+			return true, nil
+		}
+		return compare(max, right) > 0, nil
 	case logicalplan.OpGtEq:
-		return compare(Max(left), right) >= 0, nil
+		max := Max(left)
+		if max.IsNull() {
+			// If max is null, we don't know what the non-null max value is, so
+			// we need to let the execution engine scan this column chunk
+			// further.
+			return true, nil
+		}
+		return compare(max, right) >= 0, nil
 	default:
 		return true, nil
 	}


Test patch:
diff --git a/binaryscalarexpr_test.go b/binaryscalarexpr_test.go
index f43f276..85309bb 100644
--- a/binaryscalarexpr_test.go
+++ b/binaryscalarexpr_test.go
@@ -139,12 +139,11 @@ func TestBinaryScalarOperation(t *testing.T) {
 			expectSatisfies: false,
 		},
 		{
-			name:      "OpGtFullNullColumn",
-			right:     1,
-			nullCount: 10,
-			op:        logicalplan.OpGt,
-			// expectSatisfies should probably be false once we optimize this.
-			expectSatisfies: true,
+			name:            "OpGtFullNullColumn",
+			right:           1,
+			nullCount:       10,
+			op:              logicalplan.OpGt,
+			expectSatisfies: false,
 		},
 		{
 			name:            "OpGtNullValueMatch",
@@ -161,6 +160,24 @@ func TestBinaryScalarOperation(t *testing.T) {
 			// expectSatisfies should probably be false once we optimize this.
 			expectSatisfies: true,
 		},
+		{
+			name:            "OpGtWithSomeNullValuesNoMatch",
+			min:             1,
+			max:             10,
+			right:           11,
+			nullCount:       1,
+			op:              logicalplan.OpGt,
+			expectSatisfies: false,
+		},
+		{
+			name:            "OpGtWithSomeNullValuesMatch",
+			min:             1,
+			max:             10,
+			right:           5,
+			nullCount:       1,
+			op:              logicalplan.OpGt,
+			expectSatisfies: true,
+		},
 	} {
 		t.Run(tc.name, func(t *testing.T) {
 			if tc.op == logicalplan.OpUnknown {