================================================================================ FIXED_SIZE_LIST def-level experiment: backing code (apache/arrow-go, PR #854 tip + a ~50-line annotation-aware skip-levels reader) ================================================================================ Answers: does an OPTIONAL outer array (maxDef=2, 2-bit def levels) make the annotation-aware "C" reader decode slower than the required case (maxDef=1)? Measured: no -- C-hint is flat across maxDef=1 vs =2 (-0.56%, within 1 sigma), because it skips level decode entirely. Meanwhile "B/VECTOR" cannot even represent a nullable array (PR #854 only emits VECTOR for a REQUIRED outer field), so C is the only proposal that can encode the reviewer's optional array. -------------------------------------------------------------------------------- 1) The skip-levels fast path (parquet/file/column_reader.go, determineNumToRead) This is the whole mechanism. It is INDEPENDENT of def-level bit width: it returns `size = numBuffered - numDecoded` (= page.nvals) values without ever expanding the RLE def-level stream into int16s. SetData (at page init) has already advanced the value decoder past the level bytes, so reading `size` values is byte-identical to the full Dremel decode -- valid precisely because the FIXED_SIZE_LIST annotation guarantees fixed multiplicity + no nulls (every def level == maxDef). -------------------------------------------------------------------------------- func (c *columnChunkReader) determineNumToRead(batchLen int64, defLvls, repLvls []int16) (ndefs int, toRead int64, err error) { if !c.HasNext() { return 0, 0, c.err } size := utils.Min(batchLen, c.numBuffered-c.numDecoded) // C-with-hint skip-levels fast path: the FIXED_SIZE_LIST annotation // guarantees a fixed multiplicity with no nulls, so every definition level // equals maxDef and there are no "missing" values. The number of physical // values to read equals the number of level slots (size), and we do NOT // expand the RLE levels into int16 arrays. The level decoders' SetData // (called in initDataDecoder) already positioned the value decoder past the // level bytes, so reading `size` values directly is byte-identical to the // full-decode result -- regardless of the def-level BIT WIDTH. if c.fslSkipLevels { FSLSkipLevelsCalls++ return 0, size, nil } if c.descr.MaxDefinitionLevel() > 0 { if defLvls == nil { defLvls = c.getDefLvlBuffer(size) } ndefs, toRead = c.readDefinitionLevels(defLvls[:size]) // O(n) RLE expand FSLLevelDecodeCalls++ } else { toRead = size } if c.descr.MaxRepetitionLevel() > 0 && repLvls != nil { nreps := c.readRepetitionLevels(repLvls[:size]) FSLLevelDecodeCalls++ if defLvls != nil && ndefs != nreps { err = errors.New("parquet: number of decoded rep/def levels did not match") } } return } // EnableFSLSkipLevels turns on the fast path for a FIXED_SIZE_LIST-annotated // column. The caller asserts (via the annotation) fixed multiplicity + no nulls, // i.e. every rep/def level is the max level. Exact analog of what PR #854's // VECTOR achieves structurally (maxDef==maxRep==0), but gated on the annotation // so the on-disk file stays a standard, backward-compatible 3-level LIST. func (c *columnChunkReader) EnableFSLSkipLevels() { c.fslSkipLevels = true } -------------------------------------------------------------------------------- 2) Why "B/VECTOR" cannot be the nullable comparison (PR #854, schema.go) VECTOR is emitted ONLY for a required (non-nullable) outer FSL; a nullable FSL silently falls back to a plain LIST, and reading a nullable VECTOR is explicitly unsupported. So there is no "nullable VECTOR": B is inherently the maxDef=0 shape. Only C (and plain LIST) can represent the reviewer's optional array. -------------------------------------------------------------------------------- func isVectorEligibleFixedSizeList(fieldNullable bool, fsl *arrow.FixedSizeListType) bool { return !fieldNullable && fsl.Len() > 0 && !fsl.ElemField().Nullable && isSupportedVectorElementType(fsl.Elem()) } // elsewhere: fmt.Errorf("%w: reading nullable VECTOR columns is not supported", arrow.ErrNotImplemented) -------------------------------------------------------------------------------- 3) Harness: the nullability knob (writes an OPTIONAL outer array with ZERO nulls -> maxDef=2 on disk, same 100%-present data). VECTOR is forced non-nullable in both modes (see #2), so `Nullable` varies only the LIST-based arms C-hint / C-naive / LIST -- exactly annotation-on-optional-LIST vs VECTOR. -------------------------------------------------------------------------------- // Config.Nullable: when true, mark the OUTER embedding array OPTIONAL even // though zero nulls are written -> leaf maxDef goes 1 -> 2 (1-bit -> 2-bit def // levels), same 100%-present data. type Config struct { Dim, Rows, RowGroupSize int Zstd bool Nullable bool Seed uint64 } func writeArrowFSL(c Config, data []float32, asVector bool) ([]byte, error) { listSize := int32(c.Dim) elemField := arrow.Field{Name: "element", Type: arrow.PrimitiveTypes.Float32, Nullable: false} fslType := arrow.FixedSizeListOfField(listSize, elemField) // VECTOR is only emitted for a REQUIRED outer array (isVectorEligibleFixedSizeList // requires !fieldNullable), so keep VECTOR non-nullable in both modes. c.Nullable // widens only the LIST-based arms from maxDef=1 to maxDef=2. outerNullable := c.Nullable && !asVector arrowSchema := arrow.NewSchema([]arrow.Field{{Name: "embedding", Type: fslType, Nullable: outerNullable}}, nil) // ... write every row present (bldr.Append(true)); zero actual nulls ... } -------------------------------------------------------------------------------- 4) Assertions (all pass in BOTH nullability modes) -------------------------------------------------------------------------------- // On-disk maxDef is exactly what each mode intends. C-arms: 1 (required) / // 2 (optional-zero-null). FLBA: 0 both. VECTOR: 0 both (stays InVectorColumn). func TestMaxDefLevels(t *testing.T) { want := map[bool]map[Arm]int16{ false: {ArmFLBA: 0, ArmVector: 0, ArmCHint: 1, ArmCNaive: 1, ArmList: 1}, true: {ArmFLBA: 0, ArmVector: 0, ArmCHint: 2, ArmCNaive: 2, ArmList: 2}, } for _, nullable := range []bool{false, true} { for _, arm := range allArms { raw, _ := WriteFile(Config{Dim: 8, Rows: 100, RowGroupSize: 64, Nullable: nullable, Seed: 1}, arm, data) d := openReader(raw).MetaData().Schema.Column(0) require(d.MaxDefinitionLevel() == want[nullable][arm]) if arm == ArmVector { require(d.InVectorColumn()) } // still a real VECTOR } } } // Skip path engages + decodes ZERO levels, in nullable mode too. // nullable=false C-hint: skip taken 16x, 0 level-decode calls // nullable=true C-hint: skip taken 16x, 0 level-decode calls <-- maxDef=2 // C-naive / LIST: 32 level-decode calls (full Dremel), both modes // B/VECTOR, A/FLBA: 0 level-decode calls (structurally no levels) // C-hint == C-naive byte-for-byte (SAME on-disk bytes, different reader), and // both == the written data, in nullable/maxDef=2 mode too. (TestCrossArmCorrectness, // TestCHintEqualsCNaiveByteForByte, TestSkipPathEngaged) -------------------------------------------------------------------------------- 5) Numbers (100k rows, dim=512 f32, uncompressed; 10 runs x 40 iters; ns/row) -------------------------------------------------------------------------------- arm maxdef=1 (required) maxdef=2 (optional, 0 nulls) delta A/FLBA 1914 +/- 88 1726 +/- 18 -9.8% (no levels; thermal drift, not real) B/VECTOR 1401 +/- 6 1403 +/- 12 +0.2% (same required file; can't be nullable) C-hint 1436 +/- 8 1428 +/- 8 -0.6% (skip path; FLAT across bit-width) C-naive 2606 +/- 11 2603 +/- 10 -0.1% (full Dremel; also flat, see below) LIST 2613 +/- 11 2617 +/- 13 +0.1% C-hint vs B/VECTOR @ maxdef=1: +2.5% @ maxdef=2: +1.8% (gap NARROWS at 2-bit) C-hint maxdef=2 vs maxdef=1: -0.6% (flat, within 1 sigma) C-naive maxdef=2 vs maxdef=1: -0.1% Even the level-DECODING arms (C-naive/LIST) show no 1-bit->2-bit threshold cost, because for 100%-present data the def-level stream is a single RLE run at either bit width. C-hint skips that decode outright, so def-level width is free to it. ================================================================================