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


##########
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:
   Thanks for the precise repro. Fixed in b74b1a8678.
   
   The device now sorts with the same tie-breaker as both CPU merge readers. 
Before the sort, a kernel folds the row kind into the sequence slot as `2 * 
sequence + isAdd`, so at an equal sequence number a retraction sorts before an 
addition and the addition survives. A second kernel restores the sequence 
numbers right after the survivors are marked, so the written files and their 
metadata are unchanged. Files whose sequence numbers are outside `[0, 2^62)` 
stay on the CPU.
   
   Two rows of a key with the same sequence number *and* the same kind (for 
example two concurrent inserts at sequence 0) are not resolved by this 
tie-breaker. On the CPU the reader order decides, so the device flags the tie 
and hands the whole compaction to Paimon's rewriter.
   
   New device tests in `GpuCompactionITCase`, each comparing against Paimon's 
own rewriter:
   - `testEqualSequenceNumbersKeepTheInsertBeforeADelete` and 
`...InsertAfterADelete`: both input orders of your two-writer scenario.
   - `testEqualSequenceNumbersKeepTheUpdateAfter`: the same for 
UPDATE_BEFORE/UPDATE_AFTER.
   - `testEqualSequenceNumbersAndKindsRunOnTheCpu`: the full tie falls back.
   
   On the old head, the delete-after-insert orders returned zero rows, as you 
found. With the fix, all six device tests pass on an RTX 4090.
   



##########
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:
   Agreed. Fixed in b74b1a8678: `KvLayout` now rejects 
`sequence.snapshot-ordering`, so such tables never reach the device until a 
per-file sequence override is implemented. `KvLayoutTest` covers the option.
   
   `GpuCompactionITCase#testSnapshotSequenceOrderingRunsOnTheCpu` reproduces 
your scenario. Writer A writes the key three times (physical sequence 2, value 
10), writer B once (sequence 0, value 20), A commits first. The test checks 
that the compacted table returns 20, that the result matches Paimon's rewriter, 
and that no batch ran on the device. On the old head this test returned 10.
   



-- 
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