parquet: BYTE_STREAM_SPLIT FIXED_LEN_BYTE_ARRAY with nulls across multiple data pages decodes values shifted by one

[zeroshade]

Describe the bug, including details regarding any error messages, version, and platform.

A FIXED_LEN_BYTE_ARRAY column encoded with BYTE_STREAM_SPLIT decodes values shifted by one position when the column chunk contains both nulls and more than one data page. The data is silently wrong — no error is returned.

Found on main (f85b0b25 / 477eb633), linux/amd64, Go 1.24. This is not a recent regression; it reproduces on older commits as well. Surfaced while reviewing #1172, which is unrelated and does not cause it.

Isolation, already narrowed:

• Encoding-specific — PLAIN passes on byte-identical data and writer configuration; only BYTE_STREAM_SPLIT fails.
• Requires both conditions:
  • a single large data page (1 MiB) with nulls passes
  • multiple data pages without nulls passes
  • multiple data pages with nulls fails
• Reproduced at widths 2, 3, 4, 7, 8, 16, 17, and 32 — not width-specific.
• First mismatch appears partway through, not at the start (e.g. around index 259 for width 4).

Example failure at width 4:

mismatch at idx 259
expected: []byte{0x0c, 0x0d, 0x0e, 0x0f}
actual  : []byte{0x10, 0x11, 0x12, 0x13}

0x10 0x11 0x12 0x13 is the value belonging to index 260, i.e. the stream is off by exactly one value from that point on.

Not root-caused. ByteStreamSplitFixedLenByteArrayDecoder.SetData recomputing nvals = len(data)/typeLen and setting stride looks correct on inspection, so the fault is likely elsewhere — either per-page decoder reset in the column reader or the encoder's per-page flush. I have not determined whether the file is written incorrectly or read incorrectly.

Note on existing coverage: the spaced-decoding unit tests use a single SetData followed by one DecodeSpaced, so they exercise only the single-page case and pass. A fix should come with a multi-page + nulls integration test.

Reproducer

Drop into parquet/pqarrow/ as bss_flba_repro_test.go and run
go test ./parquet/pqarrow/ -run TestBSSFLBANullsMultiPage -v.

package pqarrow_test

import (
	"bytes"
	"context"
	"fmt"
	"testing"

	"github.com/apache/arrow-go/v18/arrow"
	"github.com/apache/arrow-go/v18/arrow/array"
	"github.com/apache/arrow-go/v18/arrow/memory"
	"github.com/apache/arrow-go/v18/parquet"
	"github.com/apache/arrow-go/v18/parquet/file"
	"github.com/apache/arrow-go/v18/parquet/pqarrow"
	"github.com/stretchr/testify/require"
)

func TestBSSFLBANullsMultiPage(t *testing.T) {
	encs := map[string]parquet.Encoding{
		"BSS":   parquet.Encodings.ByteStreamSplit,
		"PLAIN": parquet.Encodings.Plain,
	}
	for encName, enc := range encs {
		for _, pageSize := range []int64{512, 1 << 20} { // small pages vs one big page
			for _, width := range []int{4, 32} {
				for _, nulls := range []bool{false, true} {
					t.Run(fmt.Sprintf("%s/page%d/w%d/nulls=%v", encName, pageSize, width, nulls), func(t *testing.T) {
						mem := memory.DefaultAllocator
						const n = 5000

						dt := &arrow.FixedSizeBinaryType{ByteWidth: width}
						sc := arrow.NewSchema([]arrow.Field{{Name: "v", Type: dt, Nullable: nulls}}, nil)

						bldr := array.NewFixedSizeBinaryBuilder(mem, dt)
						defer bldr.Release()
						want := make([][]byte, 0, n)
						for i := 0; i < n; i++ {
							if nulls && i%7 == 3 {
								bldr.AppendNull()
								want = append(want, nil)
								continue
							}
							v := make([]byte, width)
							for j := range v {
								v[j] = byte(i*width + j)
							}
							bldr.Append(v)
							want = append(want, v)
						}
						arr := bldr.NewArray()
						defer arr.Release()
						rec := array.NewRecord(sc, []arrow.Array{arr}, int64(n))
						defer rec.Release()

						var buf bytes.Buffer
						props := parquet.NewWriterProperties(
							parquet.WithEncoding(enc),
							parquet.WithDictionaryDefault(false),
							parquet.WithDataPageSize(pageSize),
							parquet.WithBatchSize(128),
						)
						w, err := pqarrow.NewFileWriter(sc, &buf, props, pqarrow.DefaultWriterProps())
						require.NoError(t, err)
						require.NoError(t, w.Write(rec))
						require.NoError(t, w.Close())

						rdr, err := file.NewParquetReader(bytes.NewReader(buf.Bytes()))
						require.NoError(t, err)
						defer rdr.Close()

						fr, err := pqarrow.NewFileReader(rdr, pqarrow.ArrowReadProperties{BatchSize: 137}, mem)
						require.NoError(t, err)
						tbl, err := fr.ReadTable(context.Background())
						require.NoError(t, err)
						defer tbl.Release()

						require.EqualValues(t, n, tbl.NumRows())
						idx := 0
						for _, c := range tbl.Column(0).Data().Chunks() {
							fsb := c.(*array.FixedSizeBinary)
							for i := 0; i < fsb.Len(); i++ {
								if want[idx] == nil {
									require.True(t, fsb.IsNull(i), "idx %d should be null", idx)
								} else {
									require.False(t, fsb.IsNull(i), "idx %d should be valid", idx)
									require.Equal(t, want[idx], fsb.Value(i), "mismatch at idx %d", idx)
								}
								idx++
							}
						}
						require.Equal(t, n, idx)
					})
				}
			}
		}
	}
}

Observed result — only the BSS multi-page-with-nulls combinations fail:

--- PASS: TestBSSFLBANullsMultiPage/BSS/page512/w4/nulls=false
--- FAIL: TestBSSFLBANullsMultiPage/BSS/page512/w4/nulls=true
--- PASS: TestBSSFLBANullsMultiPage/BSS/page512/w32/nulls=false
--- FAIL: TestBSSFLBANullsMultiPage/BSS/page512/w32/nulls=true
--- PASS: TestBSSFLBANullsMultiPage/BSS/page1048576/w4/nulls=true
--- PASS: TestBSSFLBANullsMultiPage/BSS/page1048576/w32/nulls=true
--- PASS: TestBSSFLBANullsMultiPage/PLAIN/... (all)

Component(s)

Parquet

[zeroshade]

Root-caused. The file on disk is fine — this is purely a read-side bug, and the encoder is not involved.

Bisect

Reading the same written file through the low-level ReadBatch API returns correct data for all 5000 rows, multi-page and nulls included. Only the record-reader / DecodeSpaced path is wrong. That rules out the writer and the on-disk bytes.

Root cause

spacedExpand moves values into their spaced positions with copy, and deliberately does not clean up afterwards:

// because we technically don't care what is in the null slots we don't actually have to clean
// up after ourselves ... Any data that happens to be left in the null
// slots is fine since it shouldn't matter and saves us work.
n := copy(buffer[run.Pos:], buffer[idxDecode:int64(idxDecode)+run.Length])

For scalar column types that reasoning holds — the buffer holds values, and a stale value in a null slot is harmless.

For ByteArray / FixedLenByteArray the buffer holds slice headers, so copy leaves duplicate headers behind: after expansion, a null slot and a valid slot can reference the same backing array.

That is still harmless as long as the decoder replaces the header. PlainFixedLenByteArrayDecoder.Decode does exactly that:

out[idx] = pflba.data[:pflba.typeLen]   // replaces the header

But ByteStreamSplitFixedLenByteArrayDecoder writes through the caller's existing slice:

out[idx] = out[idx][:dec.typeLen]       // reuses the caller's storage
...
out[element][stream] = data[encLoc]     // writes through it

So when the record reader reuses flbaRecordReader.valueBuf for the next page, two output slots share one backing array, and the second value written clobbers the first.

Minimal demonstration

Two successive DecodeSpaced calls on one reused 5-slot buffer, 2 nulls, valid bits 0b00010101:

BSS:    alias after page1: slots [1 2] share backing 0x...
        page2 slot 2: got "lmno" want "hijk"      <-- value from slot 3 appears in slot 2
PLAIN:  alias after page1: slots [1 2] share backing 0x...
        page2: OK                                  <-- same aliasing, but harmless

Slots 1 and 2 alias after page 1. On page 2, Decode writes values 1 and 2 through those two headers into the same 4 bytes; the later write wins, and spacedExpand then shifts that slot's header into place — producing exactly the observed off-by-one. It also explains every part of the isolation: BSS-only (PLAIN replaces headers), nulls required (no nulls means no duplicate headers), and multiple pages required (the first page creates the aliases, the second decodes into them).

Fix

The general fix — making spacedExpand swap rather than copy, so the buffer stays a permutation with no duplicates — works, but is far too expensive. Replacing memmove with element-wise swaps costs +1250% to +4280% on sparse-null runs:

SpacedExpandInt64/n65536/nullEvery0     4.457µ -> 81.265µ   +1723%
SpacedExpandFLBA/n65536/nullEvery0      3.969µ -> 173.959µ  +4283%

The targeted fix is one line in the only decoder that writes through caller storage, and leaves spacedExpand (and every other type) untouched:

func (dec *ByteStreamSplitFixedLenByteArrayDecoder) DecodeSpaced(out []parquet.FixedLenByteArray, nullCount int, validBits []byte, validBitsOffset int64) (int, error) {
	toRead := len(out) - nullCount
	// spacedExpand scatters slice headers by copying, leaving duplicate headers in the
	// null slots. This decoder writes *through* the caller's slices rather than
	// replacing them, so reusing a buffer that still holds those duplicates would make
	// two output slots share one backing array and clobber each other.
	clear(out[:toRead])
	valuesRead, err := dec.Decode(out[:toRead])
	...

Verified: the reproducer above passes, and parquet/internal/encoding, parquet/file, and parquet/pqarrow all pass with PARQUET_TEST_DATA supplied.

Interaction with #1172

clear forces every spaced decode down the cold path, so the cost depends on whether #1172 has landed. Measured on 4096 slots / 3511 values / width 16:

base	allocs/op for DecodeSpaced
main today (buggy, reuses headers)	0
main + this fix	3511
#1172 + this fix	1

#1172's contiguous cold-output allocation collapses the cost of the fix to a single allocation, so it is worth landing #1172 first and this fix on top of it.

I have not opened a PR for the fix yet — flagging the analysis first in case there is a preferred approach (for example fixing this at the flbaRecordReader level instead, or making the "decoders must not write through caller storage after spacedExpand" contract explicit somewhere).