Skip to content

Commit c57d471

Browse files
seawindeyujun777
authored andcommitted
[improvement](fe) Use 128-bit hash for IVM row id (apache#16)
Issue Number: N/A Related PR: apache#63196 Problem Summary: IVM hash-based row_id generation used murmur_hash3_64 and then cast the result to LARGEINT, so the hidden row-id column kept only 64 bits of hash entropy. This changes the shared IVM row-id builder to use murmur_hash3_128 directly, keeping the existing null-safe key encoding and LARGEINT row-id type. Normalize plan tests are updated to assert the actual IVM paths now produce MurmurHash3128 expressions. None - Test: Unit Test - ./run-fe-ut.sh --run org.apache.doris.mtmv.ivm.IvmUtilTest - ./run-fe-ut.sh --run org.apache.doris.nereids.rules.rewrite.IvmNormalizeMtmvTest - Behavior changed: Yes. Hash-based IVM row_id generation now uses murmur_hash3_128 instead of murmur_hash3_64. - Does this need documentation: No
1 parent ad050b4 commit c57d471

3 files changed

Lines changed: 20 additions & 22 deletions

File tree

‎fe/fe-core/src/main/java/org/apache/doris/mtmv/ivm/IvmUtil.java‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -23,13 +23,12 @@
2323
import org.apache.doris.nereids.trees.expressions.Expression;
2424
import org.apache.doris.nereids.trees.expressions.IsNull;
2525
import org.apache.doris.nereids.trees.expressions.Slot;
26-
import org.apache.doris.nereids.trees.expressions.functions.scalar.MurmurHash364;
26+
import org.apache.doris.nereids.trees.expressions.functions.scalar.MurmurHash3128;
2727
import org.apache.doris.nereids.trees.expressions.functions.scalar.Nvl;
2828
import org.apache.doris.nereids.trees.expressions.literal.LargeIntLiteral;
2929
import org.apache.doris.nereids.trees.expressions.literal.VarcharLiteral;
3030
import org.apache.doris.nereids.trees.plans.commands.info.ColumnDefinition;
3131
import org.apache.doris.nereids.types.DataType;
32-
import org.apache.doris.nereids.types.LargeIntType;
3332
import org.apache.doris.nereids.types.VarcharType;
3433
import org.apache.doris.nereids.types.coercion.CharacterType;
3534

@@ -55,7 +54,7 @@ public static boolean isIvmHiddenColumn(String columnName) {
5554
* <ul>
5655
* <li>Empty list (scalar agg): returns {@code LargeIntLiteral(0)}</li>
5756
* <li>Non-empty (grouped agg): returns
58-
* {@code CAST(murmur_hash3_64(ifnull(k1,''), isnull(k1), ifnull(k2,''), isnull(k2), ...) AS LARGEINT)}</li>
57+
* {@code murmur_hash3_128(ifnull(k1,''), isnull(k1), ifnull(k2,''), isnull(k2), ...)}</li>
5958
* </ul>
6059
*
6160
* <p>Each key produces two hash arguments: {@code ifnull(cast(key AS VARCHAR), '')} to prevent
@@ -80,7 +79,7 @@ public static Expression buildRowIdHash(List<? extends Expression> keyExprs) {
8079
hashArgs.add(new Nvl(asVarchar, new VarcharLiteral("")));
8180
hashArgs.add(new Cast(new IsNull(key), VarcharType.SYSTEM_DEFAULT));
8281
}
83-
return new Cast(new MurmurHash364(hashArgs.build()), LargeIntType.INSTANCE);
82+
return new MurmurHash3128(hashArgs.build());
8483
}
8584

8685
/**

‎fe/fe-core/src/test/java/org/apache/doris/mtmv/ivm/IvmUtilTest.java‎

Lines changed: 12 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,7 @@
2121
import org.apache.doris.nereids.trees.expressions.Expression;
2222
import org.apache.doris.nereids.trees.expressions.IsNull;
2323
import org.apache.doris.nereids.trees.expressions.SlotReference;
24-
import org.apache.doris.nereids.trees.expressions.functions.scalar.MurmurHash364;
24+
import org.apache.doris.nereids.trees.expressions.functions.scalar.MurmurHash3128;
2525
import org.apache.doris.nereids.trees.expressions.functions.scalar.Nvl;
2626
import org.apache.doris.nereids.trees.expressions.literal.LargeIntLiteral;
2727
import org.apache.doris.nereids.types.IntegerType;
@@ -45,6 +45,11 @@ private SlotReference varcharSlot(String name, boolean nullable) {
4545
return new SlotReference(name, VarcharType.SYSTEM_DEFAULT, nullable);
4646
}
4747

48+
private MurmurHash3128 rowIdHash(Expression result) {
49+
Assertions.assertInstanceOf(MurmurHash3128.class, result);
50+
return (MurmurHash3128) result;
51+
}
52+
4853
@Test
4954
void testBuildRowIdHashEmptyReturnsZero() {
5055
Expression result = IvmUtil.buildRowIdHash(Collections.emptyList());
@@ -55,22 +60,16 @@ void testBuildRowIdHashEmptyReturnsZero() {
5560
@Test
5661
void testBuildRowIdHashSingleKeyStructure() {
5762
Expression result = IvmUtil.buildRowIdHash(ImmutableList.of(intSlot("k1", false)));
58-
// Outer: Cast(MurmurHash364(...), LARGEINT)
59-
Assertions.assertInstanceOf(Cast.class, result);
60-
Cast outerCast = (Cast) result;
61-
Assertions.assertEquals(LargeIntType.INSTANCE, outerCast.getDataType());
62-
// Inner: MurmurHash364 with 2 args (ifnull'd value + isnull flag)
63-
Assertions.assertInstanceOf(MurmurHash364.class, outerCast.child());
64-
MurmurHash364 hash = (MurmurHash364) outerCast.child();
63+
Assertions.assertEquals(LargeIntType.INSTANCE, result.getDataType());
64+
MurmurHash3128 hash = rowIdHash(result);
6565
Assertions.assertEquals(2, hash.arity());
6666
}
6767

6868
@Test
6969
void testBuildRowIdHashMultipleKeysStructure() {
7070
List<Expression> keys = ImmutableList.of(intSlot("k1", false), intSlot("k2", true));
7171
Expression result = IvmUtil.buildRowIdHash(keys);
72-
Cast outerCast = (Cast) result;
73-
MurmurHash364 hash = (MurmurHash364) outerCast.child();
72+
MurmurHash3128 hash = rowIdHash(result);
7473
// 2 keys * 2 args each = 4 hash arguments
7574
Assertions.assertEquals(4, hash.arity());
7675
}
@@ -79,7 +78,7 @@ void testBuildRowIdHashMultipleKeysStructure() {
7978
void testBuildRowIdHashContainsNvlAndIsNull() {
8079
List<Expression> keys = ImmutableList.of(intSlot("k1", true), intSlot("k2", true));
8180
Expression result = IvmUtil.buildRowIdHash(keys);
82-
MurmurHash364 hash = (MurmurHash364) ((Cast) result).child();
81+
MurmurHash3128 hash = rowIdHash(result);
8382
// Even-indexed args (0, 2) should be Nvl; odd-indexed (1, 3) should be Cast(IsNull)
8483
Assertions.assertInstanceOf(Nvl.class, hash.child(0));
8584
Assertions.assertInstanceOf(Cast.class, hash.child(1));
@@ -92,7 +91,7 @@ void testBuildRowIdHashContainsNvlAndIsNull() {
9291
@Test
9392
void testBuildRowIdHashVarcharKeySkipsInnerCast() {
9493
Expression result = IvmUtil.buildRowIdHash(ImmutableList.of(varcharSlot("k1", false)));
95-
MurmurHash364 hash = (MurmurHash364) ((Cast) result).child();
94+
MurmurHash3128 hash = rowIdHash(result);
9695
Nvl nvl = (Nvl) hash.child(0);
9796
// VARCHAR key should not have inner Cast — Nvl wraps the slot directly
9897
Assertions.assertInstanceOf(SlotReference.class, nvl.child(0));
@@ -101,7 +100,7 @@ void testBuildRowIdHashVarcharKeySkipsInnerCast() {
101100
@Test
102101
void testBuildRowIdHashNonVarcharKeyHasInnerCast() {
103102
Expression result = IvmUtil.buildRowIdHash(ImmutableList.of(intSlot("k1", false)));
104-
MurmurHash364 hash = (MurmurHash364) ((Cast) result).child();
103+
MurmurHash3128 hash = rowIdHash(result);
105104
Nvl nvl = (Nvl) hash.child(0);
106105
// INT key should have Cast(slot, VARCHAR) inside Nvl
107106
Assertions.assertInstanceOf(Cast.class, nvl.child(0));

‎fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/IvmNormalizeMtmvTest.java‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,7 @@
5555
import org.apache.doris.nereids.trees.expressions.functions.agg.Min;
5656
import org.apache.doris.nereids.trees.expressions.functions.agg.Sum;
5757
import org.apache.doris.nereids.trees.expressions.functions.scalar.BitmapFromString;
58+
import org.apache.doris.nereids.trees.expressions.functions.scalar.MurmurHash3128;
5859
import org.apache.doris.nereids.trees.expressions.functions.scalar.UuidNumeric;
5960
import org.apache.doris.nereids.trees.expressions.literal.BooleanLiteral;
6061
import org.apache.doris.nereids.trees.expressions.literal.LargeIntLiteral;
@@ -289,7 +290,7 @@ void testExcludedAggKeyTableUsesDeterministicRowIdHashOnAggKeys() {
289290
LogicalProject<?> project = (LogicalProject<?>) result;
290291
Assertions.assertInstanceOf(Alias.class, project.getProjects().get(0));
291292
Alias rowIdAlias = (Alias) project.getProjects().get(0);
292-
Assertions.assertInstanceOf(Cast.class, rowIdAlias.child());
293+
Assertions.assertInstanceOf(MurmurHash3128.class, rowIdAlias.child());
293294
Assertions.assertEquals(
294295
IvmUtil.buildRowIdHash(ImmutableList.of(aggScan.getOutput().get(0))).toSql(),
295296
rowIdAlias.child().toSql());
@@ -332,7 +333,7 @@ void testExcludedMowTableUsesDeterministicRowId() {
332333
LogicalProject<?> project = (LogicalProject<?>) result;
333334
Alias rowIdAlias = (Alias) project.getProjects().get(0);
334335
// Excluded MOW table should still compute deterministic row-id from unique key hash
335-
Assertions.assertInstanceOf(Cast.class, rowIdAlias.child());
336+
Assertions.assertInstanceOf(MurmurHash3128.class, rowIdAlias.child());
336337
IvmNormalizeResult normalizeResult = jobContext.getCascadesContext().getIvmNormalizeResult().get();
337338
Assertions.assertTrue(normalizeResult.getRowIdDeterminism().values().iterator().next());
338339
}
@@ -462,10 +463,9 @@ void testGroupedAggInjectsRowIdAndHiddenColumns() {
462463
Assertions.assertEquals(IvmUtil.ivmAggHiddenColumnName(0, "COUNT"), outputNames.get(4));
463464
Assertions.assertEquals(5, outputNames.size());
464465

465-
// row-id expression is hash(id) via Cast(MurmurHash364)
466+
// row-id expression is a 128-bit hash over the group key.
466467
Alias rowIdAlias = (Alias) topProject.getProjects().get(0);
467-
Assertions.assertInstanceOf(
468-
org.apache.doris.nereids.trees.expressions.Cast.class, rowIdAlias.child());
468+
Assertions.assertInstanceOf(MurmurHash3128.class, rowIdAlias.child());
469469

470470
// IvmNormalizeResult has aggMeta
471471
IvmNormalizeResult normalizeResult = jobContext.getCascadesContext().getIvmNormalizeResult().get();

0 commit comments

Comments
 (0)