>From Shahrzad Shirazi <[email protected]>: Shahrzad Shirazi has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21675?usp=email )
Change subject: WIP:Fix the CLUSTER BY seed draw and unseeded randomness ...................................................................... WIP:Fix the CLUSTER BY seed draw and unseeded randomness - user model changes: no - storage format changes: no - interface changes: no Details: Two defects in how CLUSTER BY chooses its starting centres. 1. A seed did not guarantee the same clustering. The draw ordered rows by random(v[0] + seed), which keys on a single vector component, so distinct vectors sharing that component received identical keys. ORDER BY key LIMIT n then had no unique winner and the choice fell to the merge, which breaks ties by partition index -- making the starting vector a function of the layout rather than of the seed. random() is also stateful: RandomHelper reseeds only when its argument changes, so a row's key depended on the rows read before it. Fixed by keying on vector-shuffle-key(vector, seed): a hash of every component mixed with the seed, reusing KMeansLoopIO.fingerprint and the mixing the oversampling rounds already draw with. Distinct vectors get distinct keys, so the draw is decided by the seed alone. Registered non-functional, as random() is, so the optimizer does not move or share the assign that computes it. 2. Omitting the seed did not produce a random clustering. The oversampling and RECLUSTER stages fell back to fixed constants (SEED_BASE, RECLUSTER_SEED_DEFAULT) and the draw key carried no seed term at all, so every execution of an unseeded query returned the same result. Fixed by compiling with the KMeansLoopIO.SEED_FROM_JOB placeholder, which the runtime resolves per job. Drawing a value at compile time would not work: plans are cached by statement text, so one draw would serve every later execution. The placeholder is constant, so the plan stays cacheable, and the value is derived at execution time, as current_datetime() derives its own. Behaviour: a seeded CLUSTER BY is now reproducible across partitionings; an unseeded one returns a different clustering on each execution. A seeded query also returns a different clustering than before this change, since the same seed now selects a different starting vector -- goldens are regenerated accordingly. kmeans-seed and kmeans-budget-sensitivity raise compiler.groupmemory: the group-by carrying the assertion caps a single group at 96KB under the test config, and one cluster of the 2000 x 128 fixture exceeds that at k=64. Co-Authored-By: Claude Opus 5 <[email protected]> Ext-ref: MB-73589 Change-Id: Ie67d51cf5d44a9503c1e01f6787b6d48223e5856 --- M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/ExpandClusterByRule.java M asterixdb/asterix-app/src/test/resources/optimizerts/queries/cluster-by/kmeans-decor-validate.sqlpp M asterixdb/asterix-app/src/test/resources/optimizerts/queries/cluster-by/kmeans-init-random-validate.sqlpp M asterixdb/asterix-app/src/test/resources/optimizerts/queries/cluster-by/kmeans-limit-input-validate.sqlpp M asterixdb/asterix-app/src/test/resources/optimizerts/queries/cluster-by/kmeans-syntax-full-validate.sqlpp M asterixdb/asterix-app/src/test/resources/optimizerts/queries/cluster-by/kmeans-syntax-validate.sqlpp M asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-budget-sensitivity/kmeans-budget-sensitivity.3.query.sqlpp M asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-budget-sensitivity/kmeans-budget-sensitivity.4.query.sqlpp M asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-budget-sensitivity/kmeans-budget-sensitivity.5.query.sqlpp M asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-seed/kmeans-seed.3.query.sqlpp M asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-seed/kmeans-seed.4.query.sqlpp M asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-seed/kmeans-seed.5.query.sqlpp M asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-budget-sensitivity/kmeans-budget-sensitivity.3.adm M asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-budget-sensitivity/kmeans-budget-sensitivity.4.adm M asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-budget-sensitivity/kmeans-budget-sensitivity.5.adm M asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-seed/kmeans-seed.3.adm M asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-seed/kmeans-seed.4.adm M asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-seed/kmeans-seed.5.adm M asterixdb/asterix-app/src/test/resources/runtimets/results_cloud/cluster-by/kmeans-budget-sensitivity/kmeans-budget-sensitivity.3.adm M asterixdb/asterix-app/src/test/resources/runtimets/results_cloud/cluster-by/kmeans-budget-sensitivity/kmeans-budget-sensitivity.4.adm M asterixdb/asterix-app/src/test/resources/runtimets/results_cloud/cluster-by/kmeans-budget-sensitivity/kmeans-budget-sensitivity.5.adm M asterixdb/asterix-app/src/test/resources/runtimets/results_cloud/cluster-by/kmeans-seed/kmeans-seed.3.adm M asterixdb/asterix-app/src/test/resources/runtimets/results_cloud/cluster-by/kmeans-seed/kmeans-seed.4.adm M asterixdb/asterix-app/src/test/resources/runtimets/results_cloud/cluster-by/kmeans-seed/kmeans-seed.5.adm M asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml M asterixdb/asterix-common/src/main/java/org/apache/asterix/common/exceptions/ErrorCode.java M asterixdb/asterix-common/src/main/resources/asx_errormsg/en.properties M asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/SqlppClusterByVisitor.java M asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/BuiltinFunctions.java A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/VectorShuffleKeyDescriptor.java A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/VectorShuffleKeyScalarEvaluator.java M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionCollection.java M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansLoopIO.java M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansReclusterOperatorDescriptor.java M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansSampleOperatorDescriptor.java M asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/operators/kmeans/KMeansReclusterOperatorTest.java 36 files changed, 1,032 insertions(+), 848 deletions(-) git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/75/21675/1 -- To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21675?usp=email To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings?usp=email Gerrit-MessageType: newchange Gerrit-Project: asterixdb Gerrit-Branch: master Gerrit-Change-Id: Ie67d51cf5d44a9503c1e01f6787b6d48223e5856 Gerrit-Change-Number: 21675 Gerrit-PatchSet: 1 Gerrit-Owner: Shahrzad Shirazi <[email protected]>
