>From Shahrzad Shirazi <[email protected]>: Shahrzad Shirazi has submitted this change. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21626?usp=email )
Change subject: [ASTERIXDB-3785][COMP] Fix CENTROID rejecting non-double vector elements ...................................................................... [ASTERIXDB-3785][COMP] Fix CENTROID rejecting non-double vector elements Change-Id: I23197c638c039bd19237b00761f5924f29405d68 Reviewed-on: https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21626 Reviewed-by: Hongyu Shi <[email protected]> Reviewed-by: Ian Maxon <[email protected]> Integration-Tests: Jenkins <[email protected]> Reviewed-by: Shahrzad Shirazi <[email protected]> Tested-by: Jenkins <[email protected]> --- M asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.1.ddl.sqlpp M asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.2.update.sqlpp A asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.7.query.sqlpp A asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.8.query.sqlpp A asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.7.adm A asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.8.adm M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/aggregates/std/AbstractCentroidAggregateFunction.java M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/VectorListDecoder.java M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansCostControllerOperatorDescriptor.java 9 files changed, 108 insertions(+), 4 deletions(-) Approvals: Anon. E. Moose #1000171: Hongyu Shi: Looks good to me, but someone else must approve Jenkins: Verified; Verified Ian Maxon: Looks good to me, approved Shahrzad Shirazi: Looks good to me, but someone else must approve diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.1.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.1.ddl.sqlpp index 481477a..fdfa676 100644 --- a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.1.ddl.sqlpp +++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.1.ddl.sqlpp @@ -28,3 +28,4 @@ create type PointType as open { id : integer }; create dataset Points(PointType) primary key id; +create dataset IntPoints(PointType) primary key id; diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.2.update.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.2.update.sqlpp index 58306cf..789675b 100644 --- a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.2.update.sqlpp +++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.2.update.sqlpp @@ -31,3 +31,11 @@ {"id":12,"vec":"nope"}, {"id":13,"vec":2.0} ]); + +insert into IntPoints ([ + {"id":1,"vec":[0,0]}, + {"id":2,"vec":[2.0,0]}, + {"id":3,"vec":[100,0.0]}, + {"id":4,"vec":[102,0]}, + {"id":5,"vec":[1,"x"]} +]); diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.7.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.7.query.sqlpp new file mode 100644 index 0000000..19e93e1 --- /dev/null +++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.7.query.sqlpp @@ -0,0 +1,28 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +-- Integer-written and mixed-tag vectors must produce a real centroid, not NULL. The CENTROID aggregate once +-- accepted DOUBLE elements alone while every other reader of a vector took the whole numeric family, so +-- these rows clustered and then had no centroid to show for it. +use test; + +from IntPoints as p +cluster by p.vec as sc +with {"clustering_algorithm": "K-Means","dimension": [2], "num_clusters": 2 } +select sc.cluster_id as cid, sc.centroid as centroid +order by cid; diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.8.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.8.query.sqlpp new file mode 100644 index 0000000..005b1f6 --- /dev/null +++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.8.query.sqlpp @@ -0,0 +1,30 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +-- The same rows by membership: the four usable vectors are placed two and two, and the row carrying a +-- non-numeric element is in no cluster at all -- rejected by the labeling, so it never reaches a centroid. +use test; + +from IntPoints as p +cluster by p.vec as sc +cluster as members +with {"clustering_algorithm": "K-Means","dimension": [2], "num_clusters": 2 } +select sc.cluster_id as cid, + array_count(members) as cnt, + (select value m.p.id from members as m order by m.p.id) as ids +order by cid; diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.7.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.7.adm new file mode 100644 index 0000000..ca40512 --- /dev/null +++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.7.adm @@ -0,0 +1,2 @@ +{ "cid": 0, "centroid": [ 1.0, 0.0 ] } +{ "cid": 1, "centroid": [ 101.0, 0.0 ] } diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.8.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.8.adm new file mode 100644 index 0000000..4674af3 --- /dev/null +++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/kmeans-mixed-dimensions/kmeans-mixed-dimensions.8.adm @@ -0,0 +1,2 @@ +{ "cid": 0, "cnt": 2, "ids": [ 1, 2 ] } +{ "cid": 1, "cnt": 2, "ids": [ 3, 4 ] } diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/aggregates/std/AbstractCentroidAggregateFunction.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/aggregates/std/AbstractCentroidAggregateFunction.java index f335571..969fb94 100644 --- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/aggregates/std/AbstractCentroidAggregateFunction.java +++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/aggregates/std/AbstractCentroidAggregateFunction.java @@ -43,6 +43,7 @@ import org.apache.asterix.runtime.evaluators.common.AccessibleByteArrayEval; import org.apache.asterix.runtime.evaluators.common.ClosedRecordConstructorEvalFactory.ClosedRecordConstructorEval; import org.apache.asterix.runtime.evaluators.common.ListAccessor; +import org.apache.asterix.runtime.evaluators.functions.vector.VectorListDecoder; import org.apache.asterix.runtime.exceptions.UnsupportedItemTypeException; import org.apache.hyracks.algebricks.core.algebra.functions.FunctionIdentifier; import org.apache.hyracks.algebricks.runtime.base.IScalarEvaluator; @@ -181,13 +182,15 @@ listAccessor.getOrWriteItem(i, itemVal, itemStorage); byte[] ib = itemVal.getByteArray(); int io = itemVal.getStartOffset(); - if (EnumDeserializer.ATYPETAGDESERIALIZER.deserialize(ib[io]) != ATypeTag.DOUBLE) { + ATypeTag itemTag = EnumDeserializer.ATYPETAGDESERIALIZER.deserialize(ib[io]); + double item = VectorListDecoder.getValueFromTag(itemTag, ib, io); + if (Double.isNaN(item)) { // Nothing of this row has reached sum: a rejected row leaves the running sum untouched. - warnOnce(ATypeTag.DOUBLE); + warnOnce(itemTag); processNull(); return; } - scratch[i] = ADoubleSerializerDeserializer.getDouble(ib, io + 1); + scratch[i] = item; } } catch (IOException e) { throw HyracksDataException.create(e); diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/VectorListDecoder.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/VectorListDecoder.java index 8baf171..c9f58d3 100644 --- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/VectorListDecoder.java +++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/VectorListDecoder.java @@ -64,7 +64,7 @@ return getValueFromTag(typeTag, data, offset); } - private double getValueFromTag(ATypeTag typeTag, byte[] data, int offset) { + public static double getValueFromTag(ATypeTag typeTag, byte[] data, int offset) { return switch (typeTag) { case TINYINT -> AInt8SerializerDeserializer.getByte(data, offset + 1); case SMALLINT -> AInt16SerializerDeserializer.getShort(data, offset + 1); diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansCostControllerOperatorDescriptor.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansCostControllerOperatorDescriptor.java index dfc781d..660843b 100644 --- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansCostControllerOperatorDescriptor.java +++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansCostControllerOperatorDescriptor.java @@ -311,6 +311,17 @@ FrameTupleAppender sigmaAppender = new FrameTupleAppender(new VSizeFrame(ctx)); ArrayTupleBuilder tb = new ArrayTupleBuilder(3); MaterializerTaskState scoreState = null; + // An empty pool[0] means the drawn seed did not decode: the draw filters on shape alone, and + // its ORDER BY <key> LIMIT 1 has already discarded the rows that would have decoded. Scoring + // then leaves every vector at +INF, so phi = 0, nothing is drawn, and a usable input answers + // nothing. Identical on every partition: the seed is broadcast, later pools are Release's. + boolean poolEmpty = isEmpty(poolState); + if (poolEmpty && ctx.getWarningCollector().shouldWarn()) { + ctx.getWarningCollector() + .warn(Warning.of(null, ErrorCode.CLUSTER_BY_INVALID_INPUT, + "the CLUSTER BY seed was not a numeric array of the declared dimension; the " + + "initial candidates were sampled uniformly from the input instead")); + } try { for (int r = 0; r < loopRounds; r++) { // A fresh column per round; the previous one is dead once Op3 consumed it, which the @@ -325,12 +336,21 @@ final KMeansLoopIO.ScoreColumnWriter column = new KMeansLoopIO.ScoreColumnWriter(scoreState, ctx); final double[] localSum = { 0.0d }; + // Nothing to measure against: score every vector 1 rather than +INF, so phi is the + // vector count and Op3's l * 1 / phi draws l of them uniformly -- from vectors the + // decoder already accepted, so this draw cannot fail the way the seed did. Re-tested + // every round, not just the first: a uniform round can draw nothing (about e^-l). + final boolean bootstrapRound = poolEmpty; // Blocked against pool[r] rather than holding it: the pool is 2*k per round, so the // resident form grew with the requested cluster count. Vectors still reach the sink in // run-file order, so localSum adds its terms in the same order as before. KMeansLoopIO.streamScoredAgainstPool(vectorState, poolState, ctx, framesLimit, (vecs, n, nearest, nearestIdx) -> { for (int i = 0; i < n; i++) { + if (bootstrapRound) { + // The column is built from this array: Op3 reads the same 1. + nearest[i] = 1.0d; + } double best = nearest[i]; if (!Double.isNaN(best) && best != Double.POSITIVE_INFINITY) { localSum[0] += best; @@ -351,6 +371,9 @@ sigmaWriter.flush(); // push this round's localSigma so PhiMerge can proceed // Wait for Release to append round r's global draws (pool[r] -> pool[r+1]) and release. control.awaitTurn("kmeans systolic loop"); + if (poolEmpty) { + poolEmpty = isEmpty(poolState); // this round's draws may have ended the bootstrap + } } } finally { if (scoreState != null) { @@ -360,6 +383,13 @@ } } + /** Whether a run file holds no vector. One pass, and pool[0] is a single vector. */ + private boolean isEmpty(MaterializerTaskState state) throws HyracksDataException { + final boolean[] any = { false }; + KMeansLoopIO.streamRawVectors(state, ctx, vec -> any[0] = true); + return !any[0]; + } + /** * The terminal weighing pass: once the rounds are done, weigh every resident vector against the * final candidate pool -- this partition's pool run file already holds the complete, -- To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21626?usp=email To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings?usp=email Gerrit-MessageType: merged Gerrit-Project: asterixdb Gerrit-Branch: master Gerrit-Change-Id: I23197c638c039bd19237b00761f5924f29405d68 Gerrit-Change-Number: 21626 Gerrit-PatchSet: 7 Gerrit-Owner: Shahrzad Shirazi <[email protected]> Gerrit-Reviewer: Anon. E. Moose #1000171 Gerrit-Reviewer: Hongyu Shi <[email protected]> Gerrit-Reviewer: Ian Maxon <[email protected]> Gerrit-Reviewer: Jenkins <[email protected]> Gerrit-Reviewer: Shahrzad Shirazi <[email protected]>
