JingsongLi commented on code in PR #11211:
URL: https://github.com/apache/paimon/pull/11211#discussion_r4600489340


##########
paimon-gpu/src/main/java/org/apache/paimon/gpu/KvLayout.java:
##########
@@ -0,0 +1,331 @@
+/*
+ * 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.
+ */
+
+package org.apache.paimon.gpu;
+
+import org.apache.paimon.CoreOptions;
+import org.apache.paimon.KeyValue;
+import org.apache.paimon.types.DataField;
+import org.apache.paimon.types.DataTypeRoot;
+import org.apache.paimon.types.RowType;
+
+import uk.ac.manchester.tornado.cudf.enums.CudfType;
+import uk.ac.manchester.tornado.cudf.enums.ParquetColumnType;
+
+import javax.annotation.Nullable;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.EnumSet;
+import java.util.List;
+import java.util.Locale;
+import java.util.Set;
+
+/**
+ * Where each column of a primary-key data file lives on the device, for the 
read, the merge and the
+ * write.
+ *
+ * <p>A file holds the key columns, {@code _SEQUENCE_NUMBER}, {@code 
_VALUE_KIND}, then the value
+ * columns. Every key column and the sequence number are read as INT64 into 
long slots {@code
+ * 0..keys}, so the sort runs over them in place. {@code _VALUE_KIND} is int 
slot 0.
+ */
+final class KvLayout {
+
+    static final int INTS = 0;
+    static final int LONGS = 1;
+    static final int DOUBLES = 2;
+
+    /** Values per output column in {@link #gatherSpec}. */
+    static final int SPEC_WIDTH = 6;
+
+    /**
+     * How a TINYINT is written: INT8 where the device writer has it, else 
plain INT32, which Paimon
+     * reads but whose schema differs from the one Paimon writes.
+     */
+    static final ParquetColumnType TINYINT_WRITE = tinyintWrite();
+
+    private static final Set<DataTypeRoot> KEY_TYPES =
+            EnumSet.of(DataTypeRoot.INTEGER, DataTypeRoot.BIGINT);
+
+    private static final Set<DataTypeRoot> VALUE_TYPES =
+            EnumSet.of(
+                    DataTypeRoot.INTEGER,
+                    DataTypeRoot.BIGINT,
+                    DataTypeRoot.DOUBLE,
+                    DataTypeRoot.DATE,
+                    DataTypeRoot.VARCHAR,
+                    DataTypeRoot.CHAR);
+
+    final RowType keyType;
+    final RowType valueType;
+    final RowType writeRowType;
+    final int keyCount;
+
+    final int[] readColumns;
+    final CudfType[] readTypes;
+    final int[] stringColumns;
+    final int intSlots;
+    final int longSlots;
+    final int doubleSlots;
+
+    final String names;
+    final int[] fieldIds;
+    final ParquetColumnType[] writeTypes;
+    final boolean[] optional;
+    final int[] details;
+    final int outIntSlots;
+    final int outLongSlots;
+    final int outDoubleSlots;
+
+    /**
+     * Per numeric output column: source buffer, source slot, target buffer, 
target slot, read
+     * validity column (-1 for a required column), written column index.
+     */
+    final int[] gatherSpec;
+
+    final int numericOutputs;
+
+    private KvLayout(RowType keyType, RowType valueType) {
+        this.keyType = keyType;
+        this.valueType = valueType;
+        this.writeRowType = KeyValue.schema(keyType, valueType);
+        this.keyCount = keyType.getFieldCount();
+
+        List<DataField> fields = writeRowType.getFields();
+        List<Integer> reads = new ArrayList<>();
+        List<CudfType> readTypeList = new ArrayList<>();
+        List<Integer> strings = new ArrayList<>();
+        // Per file column: where the read put it (buffer, slot, read index); 
null for a string.
+        int[][] placed = new int[fields.size()][];
+        int ints = 0;
+        int longs = 0;
+        int doubles = 0;
+        for (int c = 0; c <= keyCount; c++) {
+            placed[c] = new int[] {LONGS, longs++, reads.size()};
+            reads.add(c);
+            readTypeList.add(CudfType.INT64);
+        }
+        placed[keyCount + 1] = new int[] {INTS, ints++, reads.size()};
+        reads.add(keyCount + 1);
+        readTypeList.add(CudfType.INT32);
+        for (int c = keyCount + 2; c < fields.size(); c++) {
+            switch (fields.get(c).type().getTypeRoot()) {
+                case INTEGER:
+                case DATE:
+                    placed[c] = new int[] {INTS, ints++, reads.size()};
+                    reads.add(c);
+                    readTypeList.add(CudfType.INT32);
+                    break;
+                case BIGINT:
+                    placed[c] = new int[] {LONGS, longs++, reads.size()};
+                    reads.add(c);
+                    readTypeList.add(CudfType.INT64);
+                    break;
+                case DOUBLE:
+                    placed[c] = new int[] {DOUBLES, doubles++, reads.size()};
+                    reads.add(c);
+                    readTypeList.add(CudfType.FLOAT64);
+                    break;
+                case VARCHAR:
+                case CHAR:
+                    strings.add(c);
+                    break;
+                default:
+                    throw new IllegalArgumentException("Unsupported column " + 
fields.get(c));
+            }
+        }
+        this.readColumns = toArray(reads);
+        this.readTypes = readTypeList.toArray(new CudfType[0]);
+        this.stringColumns = toArray(strings);
+        this.intSlots = ints;
+        this.longSlots = longs;
+        this.doubleSlots = doubles;
+
+        int numericReads = readColumns.length;
+        this.fieldIds = new int[fields.size()];
+        this.writeTypes = new ParquetColumnType[fields.size()];
+        this.optional = new boolean[fields.size()];
+        this.details = new int[fields.size()];
+        StringBuilder joined = new StringBuilder();
+        List<int[]> spec = new ArrayList<>();
+        int outInts = 0;
+        int outLongs = 0;
+        int outDoubles = 0;
+        int stringIndex = 0;
+        for (int c = 0; c < fields.size(); c++) {
+            DataField field = fields.get(c);
+            fieldIds[c] = field.id();
+            optional[c] = field.type().isNullable();
+            if (c > 0) {
+                joined.append('\n');
+            }
+            joined.append(field.name());
+            if (placed[c] == null) {
+                writeTypes[c] = ParquetColumnType.STRING;
+                // Its validity as the string read wrote it, after the numeric 
columns'.
+                details[c] = numericReads + stringIndex++;
+                continue;
+            }
+            int target;
+            int targetSlot;
+            switch (field.type().getTypeRoot()) {
+                case INTEGER:
+                    writeTypes[c] = ParquetColumnType.INT32;
+                    target = INTS;
+                    targetSlot = outInts++;
+                    break;
+                case TINYINT:
+                    writeTypes[c] = TINYINT_WRITE;
+                    target = INTS;
+                    targetSlot = outInts++;
+                    break;
+                case DATE:
+                    writeTypes[c] = ParquetColumnType.DATE;
+                    target = INTS;
+                    targetSlot = outInts++;
+                    break;
+                case BIGINT:
+                    writeTypes[c] = ParquetColumnType.INT64;
+                    target = LONGS;
+                    targetSlot = outLongs++;
+                    break;
+                case DOUBLE:
+                    writeTypes[c] = ParquetColumnType.FLOAT64;
+                    target = DOUBLES;
+                    targetSlot = outDoubles++;
+                    break;
+                default:
+                    throw new IllegalArgumentException("Unsupported column " + 
field);
+            }
+            spec.add(
+                    new int[] {
+                        placed[c][0],
+                        placed[c][1],
+                        target,
+                        targetSlot,
+                        optional[c] ? placed[c][2] : -1,
+                        c
+                    });
+        }
+        this.names = joined.toString();
+        this.outIntSlots = outInts;
+        this.outLongSlots = outLongs;
+        this.outDoubleSlots = outDoubles;
+        this.numericOutputs = spec.size();
+        this.gatherSpec = new int[spec.size() * SPEC_WIDTH];
+        for (int o = 0; o < spec.size(); o++) {
+            System.arraycopy(spec.get(o), 0, gatherSpec, o * SPEC_WIDTH, 
SPEC_WIDTH);
+        }
+    }
+
+    int validColumns() {
+        return readColumns.length + stringColumns.length;
+    }
+
+    /**
+     * The layout for a table whose compactions the device can run exactly as 
Paimon's merge-tree
+     * rewriter does, or null with the reason appended to {@code why}.
+     */
+    @Nullable
+    static KvLayout of(RowType keyType, RowType valueType, CoreOptions 
options, StringBuilder why) {
+        String reason = unsupported(keyType, valueType, options);
+        if (reason != null) {
+            why.append(reason);
+            return null;
+        }
+        return new KvLayout(keyType, valueType);
+    }
+
+    @Nullable
+    private static String unsupported(RowType keyType, RowType valueType, 
CoreOptions options) {
+        if (options.mergeEngine() != CoreOptions.MergeEngine.DEDUPLICATE) {
+            return "merge-engine " + options.mergeEngine();
+        }
+        if (!options.sequenceField().isEmpty()) {

Review Comment:
   [P1] Fall back for snapshot sequence ordering
   
   This accepts `sequence.snapshot-ordering=true`, but CPU readers replace 
APPEND files' physical sequence numbers with the committing snapshot ID. GPU 
reads and sorts the physical Parquet numbers instead. I verified a real table 
with two writers started before either commits: A writes the same key three 
times (its emitted row has physical sequence 2, value 10), B writes it once 
(physical sequence 0, value 20); commit A at snapshot 1, then B at snapshot 2. 
The normal reader and CPU full compaction return 20; reading those identical 
files without the snapshot override returns 10. GPU likewise selects A's 
physical sequence 2, and `check` accepts it within the manifest sequence bounds 
[1,2], so fallback does not protect the result. Please reject 
`options.snapshotSequenceOrdering()` here until the per-input-file override is 
implemented, and add a compaction regression for this scenario.



##########
paimon-gpu/src/main/java/org/apache/paimon/gpu/DeviceCompactor.java:
##########
@@ -0,0 +1,411 @@
+/*
+ * 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.
+ */
+
+package org.apache.paimon.gpu;
+
+import uk.ac.manchester.tornado.api.GridScheduler;
+import uk.ac.manchester.tornado.api.KernelContext;
+import uk.ac.manchester.tornado.api.TaskGraph;
+import uk.ac.manchester.tornado.api.TornadoExecutionPlan;
+import uk.ac.manchester.tornado.api.WorkerGrid1D;
+import uk.ac.manchester.tornado.api.enums.DataTransferMode;
+import uk.ac.manchester.tornado.api.types.arrays.ByteArray;
+import uk.ac.manchester.tornado.api.types.arrays.DoubleArray;
+import uk.ac.manchester.tornado.api.types.arrays.IntArray;
+import uk.ac.manchester.tornado.api.types.arrays.LongArray;
+import uk.ac.manchester.tornado.cudf.Cudf;
+
+import java.util.List;
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
+
+/**
+ * Runs one batch of a compaction on the device: reads the batch's files, 
orders the rows by key and
+ * sequence number, keeps the last row of each key, and writes the survivors 
to one Parquet file.
+ *
+ * <p>One plan a capacity; a batch with more rows, or more string bytes, than 
the plan holds builds
+ * a larger one. Batches run one at a time.
+ */
+final class DeviceCompactor implements AutoCloseable {
+
+    /** What a batch wrote. */
+    static final class Summary {
+        private final int rows;
+        private final long minSequence;
+        private final long maxSequence;
+        private final long retractions;
+        private final long[] minKey;
+        private final long[] maxKey;
+
+        Summary(
+                int rows,
+                long minSequence,
+                long maxSequence,
+                long retractions,
+                long[] minKey,
+                long[] maxKey) {
+            this.rows = rows;
+            this.minSequence = minSequence;
+            this.maxSequence = maxSequence;
+            this.retractions = retractions;
+            this.minKey = minKey;
+            this.maxKey = maxKey;
+        }
+
+        int rows() {
+            return rows;
+        }
+
+        long minSequence() {
+            return minSequence;
+        }
+
+        long maxSequence() {
+            return maxSequence;
+        }
+
+        long retractions() {
+            return retractions;
+        }
+
+        long[] minKey() {
+            return minKey;
+        }
+
+        long[] maxKey() {
+            return maxKey;
+        }
+    }
+
+    private static final int MIN_CAPACITY = 1 << 20;
+
+    private final KvLayout layout;
+    private Plan plan;
+
+    DeviceCompactor(KvLayout layout) {
+        this.layout = layout;
+    }
+
+    /**
+     * The capacity a batch of {@code rows} needs: a power of two, at least 
{@code MIN_CAPACITY}.
+     */
+    static int capacityFor(long rows) {
+        long capacity = MIN_CAPACITY;
+        while (capacity < rows) {
+            capacity <<= 1;
+        }
+        if (capacity > (1 << 30)) {
+            throw new IllegalArgumentException("A batch of " + rows + " rows 
is too large");
+        }
+        return (int) capacity;
+    }
+
+    synchronized Summary compact(
+            List<String> inputs,
+            long rows,
+            long charsPerColumn,
+            String output,
+            boolean dropDelete,
+            int codec) {
+        int capacity = capacityFor(rows);
+        long chars = Math.max(1024, Long.highestOneBit(Math.max(1, 
charsPerColumn - 1)) << 1);
+        if (plan == null || plan.capacity < capacity || plan.charsStride < 
chars) {
+            if (plan != null) {
+                plan.close();
+            }
+            plan =
+                    new Plan(
+                            layout,
+                            Math.max(capacity, plan == null ? 0 : 
plan.capacity),
+                            Math.max(chars, plan == null ? 0 : 
plan.charsStride));
+        }
+        try {
+            return plan.run(inputs, rows, output, dropDelete, codec);
+        } catch (RuntimeException | Error failure) {
+            long needed = charsNeeded(failure);
+            // A plan whose execution failed part-way is not run again: the 
next batch builds anew.
+            try {
+                plan.close();
+            } catch (RuntimeException closing) {
+                failure.addSuppressed(closing);
+            }
+            plan = null;
+            if (needed > charsPerColumn) {
+                // A string column decoded to more bytes than the guess: read 
the batch again,
+                // sized.
+                return compact(inputs, rows, needed, output, dropDelete, 
codec);
+            }
+            throw failure;
+        }
+    }
+
+    private static final Pattern CHARS_NEEDED = Pattern.compile("decodes to 
(\\d+) bytes, beyond");
+
+    /** The bytes a string column needed, when that is why the read failed, 
else -1. */
+    private static long charsNeeded(Throwable failure) {
+        for (Throwable t = failure; t != null; t = t.getCause()) {
+            Matcher m = CHARS_NEEDED.matcher(String.valueOf(t.getMessage()));
+            if (m.find()) {
+                return Long.parseLong(m.group(1));
+            }
+        }
+        return -1;
+    }
+
+    @Override
+    public synchronized void close() {
+        if (plan != null) {
+            plan.close();
+            plan = null;
+        }
+    }
+
+    private static final class Plan implements AutoCloseable {
+        final int capacity;
+        final long charsStride;
+        final KvLayout layout;
+        final StringBuilder inputPath = new StringBuilder(1 << 16);
+        final StringBuilder outputPath = new StringBuilder(4096);
+        final long[] rowsHolder = new long[1];
+        final int[] sortSize = new int[2];
+        final long[] settings = new long[4];
+        final IntArray params = new IntArray(CompactKernels.P_SIZE);
+        final IntArray count = new IntArray(1);
+        final LongArray groupMin;
+        final LongArray groupMax;
+        final IntArray groupRetract;
+        final LongArray edges;
+        final TornadoExecutionPlan execution;
+
+        Plan(KvLayout layout, int capacity, long charsStride) {
+            this.layout = layout;
+            this.capacity = capacity;
+            this.charsStride = charsStride;
+            int strings = layout.stringColumns.length;
+            IntArray ints = new IntArray(Math.max(1, layout.intSlots) * 
capacity);
+            LongArray longs = new LongArray((long) layout.longSlots * 
capacity);
+            DoubleArray doubles = new DoubleArray(Math.max(1, 
layout.doubleSlots * capacity));
+            ByteArray valid = new ByteArray((long) layout.validColumns() * 
capacity);
+            IntArray order = new IntArray(capacity);
+            ByteArray mask = new ByteArray(capacity);
+            IntArray selected = new IntArray(capacity);
+            IntArray gatherMap = new IntArray(capacity);
+            IntArray outInts = new IntArray(Math.max(1, layout.outIntSlots) * 
capacity);
+            LongArray outLongs = new LongArray((long) Math.max(1, 
layout.outLongSlots) * capacity);
+            DoubleArray outDoubles = new DoubleArray(Math.max(1, 
layout.outDoubleSlots * capacity));
+            ByteArray outValid = new ByteArray((long) layout.fieldIds.length * 
capacity);
+            IntArray stringOffsets = new IntArray(Math.max(1, strings * 
(capacity + 1)));
+            ByteArray stringChars = new ByteArray(Math.max(1, strings * 
charsStride));
+            IntArray spec = IntArray.fromArray(layout.gatherSpec);
+            int groups = capacity / CompactKernels.GROUP;
+            this.groupMin = new LongArray(groups);
+            this.groupMax = new LongArray(groups);
+            this.groupRetract = new IntArray(groups);
+            this.edges = new LongArray(2L * layout.keyCount);
+            KernelContext context = new KernelContext();
+
+            TaskGraph graph =
+                    new TaskGraph("paimon")
+                            
.transferToDevice(DataTransferMode.EVERY_EXECUTION, params)
+                            .transferToDevice(
+                                    DataTransferMode.FIRST_EXECUTION,
+                                    spec,
+                                    ints,
+                                    longs,
+                                    doubles,
+                                    valid,
+                                    order,
+                                    mask,
+                                    selected,
+                                    count,
+                                    gatherMap,
+                                    outInts,
+                                    outLongs,
+                                    outDoubles,
+                                    outValid,
+                                    stringOffsets,
+                                    stringChars,
+                                    groupMin,
+                                    groupMax,
+                                    groupRetract,
+                                    edges)
+                            .libraryTask(
+                                    "read",
+                                    Cudf::readParquetColumns,
+                                    inputPath,
+                                    0,
+                                    0,
+                                    layout.readColumns,
+                                    layout.readTypes,
+                                    rowsHolder,
+                                    capacity,
+                                    ints,
+                                    longs,
+                                    doubles,
+                                    valid,
+                                    true);
+            if (strings > 0) {
+                graph.libraryTask(
+                        "readStrings",
+                        Cudf::readParquetStringColumns,
+                        inputPath,
+                        layout.stringColumns,
+                        rowsHolder,
+                        capacity,
+                        stringOffsets,
+                        stringChars,
+                        charsStride,
+                        valid,
+                        layout.readColumns.length);
+            }
+            graph.libraryTask("sort", Cudf::sortedOrderLongs, sortSize, longs, 
capacity, order)
+                    .task(
+                            "mark",
+                            CompactKernels::markSurvivors,
+                            context,
+                            params,
+                            order,
+                            longs,
+                            ints,
+                            mask)
+                    .libraryTask(
+                            "select",
+                            Cudf::selectedIndices,
+                            capacity,
+                            capacity,
+                            mask,
+                            selected,
+                            count)
+                    .task(
+                            "gather",
+                            CompactKernels::gatherRows,
+                            context,
+                            params,
+                            count,
+                            order,
+                            selected,
+                            spec,
+                            ints,
+                            longs,
+                            doubles,
+                            valid,
+                            gatherMap,
+                            outInts,
+                            outLongs,
+                            outDoubles,
+                            outValid)
+                    .libraryTask(
+                            "write",
+                            Cudf::writeParquetColumnsWithStrings,
+                            outputPath,
+                            layout.names,
+                            layout.fieldIds,
+                            layout.writeTypes,
+                            layout.optional,
+                            layout.details,
+                            new long[] {-1},
+                            count,
+                            capacity,
+                            outInts,
+                            outLongs,
+                            outDoubles,
+                            outValid,
+                            stringOffsets,
+                            stringChars,
+                            valid,
+                            gatherMap,
+                            settings)
+                    .task(
+                            "summarize",
+                            CompactKernels::summarize,
+                            context,
+                            params,
+                            count,
+                            gatherMap,
+                            longs,
+                            ints,
+                            groupMin,
+                            groupMax,
+                            groupRetract,
+                            edges)
+                    .transferToHost(
+                            DataTransferMode.EVERY_EXECUTION,
+                            count,
+                            groupMin,
+                            groupMax,
+                            groupRetract,
+                            edges);
+
+            GridScheduler grids = new GridScheduler();
+            for (String task : new String[] {"mark", "gather", "summarize"}) {
+                WorkerGrid1D grid = new WorkerGrid1D(capacity);
+                grid.setLocalWork(CompactKernels.GROUP, 1, 1);
+                grids.addWorkerGrid("paimon." + task, grid);
+            }
+            this.execution = new 
TornadoExecutionPlan(graph.snapshot()).withGridScheduler(grids);
+        }
+
+        Summary run(List<String> inputs, long rows, String output, boolean 
dropDelete, int codec) {
+            inputPath.setLength(0);
+            inputPath.append(String.join("\n", inputs));
+            outputPath.setLength(0);
+            outputPath.append(output);
+            rowsHolder[0] = rows;
+            sortSize[0] = (int) rows;
+            sortSize[1] = layout.keyCount + 1;

Review Comment:
   [P1] Preserve the CPU add/retract tie-breaker
   
   Sorting only the keys and internal sequence omits the final `isAdd()` 
comparison used by both CPU merge readers. Equal internal sequences are 
possible without `sequence.field`: open two writers on the same empty bucket, 
write `INSERT(k=1,v=10)` in one and `DELETE(k=1,v=10)` in the other before 
either commits, then commit both. I verified that both real Parquet files have 
sequence 0 and CPU reads/full compaction retain the insert. The recommended 
TornadoVM implementation uses [stable 
sorting](https://github.com/beehive-lab/TornadoVM/blob/f22ca8536e1e8056bdbdfa1ce93e2753e65a8d0a/tornado-native-libs/cudf-jni/src/main/cpp/source/tornado_cudf.cpp#L1608);
 with the insert file before the delete file, equal sort keys preserve that 
order. `markSurvivors` keeps the final delete and full compaction drops it, 
losing the row. Host execution of the unchanged kernel confirms zero survivors; 
the current row-count/sequence checks accept this result. Please include the 
same add/retract ordering as 
 CPU merging, or fall back for unresolved ties, with both input orders covered.



-- 
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: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]

Reply via email to