[Format] Make requirement around dense union offsets less ambiguous

[asfimport]

Currently, the spec states that dense union offsets for each child array must be "in order / increasing". There is an ambiguity: should they be strictly increasing, or are equal values supported?

The C++ implementation currently considers that equal offsets are acceptable.

 

Reporter: Antoine Pitrou / @pitrou

_{Note: This issue was originally created as ARROW-13479. Please see the migration documentation for further details.}

[asfimport]

Antoine Pitrou / @pitrou:
cc @bkietz @wesm  @emkornfield

[asfimport]

Micah Kornfield / @emkornfield:
Hmm, I would have thought strictly, but I don't know the implications of changing it at this point.

[asfimport]

Antoine Pitrou / @pitrou:
Same opinion. We should probably be conservative. @wesm What do you say?

[Jefffrey]

Stumbled upon this whilst refreshing my knowledge of union arrays. Some reference reading too:

• https://lists.apache.org/thread/8pgv7tsko4mlxjzptor0ool98j6m578c
• https://lists.apache.org/thread/cj5dh060kdrz2vdhgrwzmmkyw986nyc7

Did some quick research on how the implementations are handling validation of this (with some help from chatgpt to identify relevant code locations; I'm not as familiar with implementations other than Rust so feel free to correct me if anything is incorrect here)

• Not accounting for how they may build the union arrays

Rust/Java/nanoarrow

These implementations only check offsets are within bounds, not enforcing them to be increasing:

• https://github.com/apache/arrow-rs/blob/7e4432e997e5b0be31a5641e078a889d82b6f61b/arrow-array/src/array/union_array.rs#L230
• https://github.com/apache/arrow-java/blob/06170242bde2f492e068235efdd2183a3cbd87d7/vector/src/main/java/org/apache/arrow/vector/validate/ValidateVectorDataVisitor.java#L185
• https://github.com/apache/arrow-nanoarrow/blob/a59c5a0e18d607a6a43d3c05bda192c6480d3a62/src/nanoarrow/common/array.c#L1604

C++/Go

Validates according to the spec that offsets are monotonic, though doesn't enforce them to be strictly increasing.

• arrow/cpp/src/arrow/array/validate.cc

  Lines 390 to 408 in 906bc0a

  	for (int64_t i = 0; i < data.length; ++i) {
  	const int32_t code = type_codes[i];
  	const int32_t offset = offsets[i];
  	if (offset < 0) {
  	return Status::Invalid("Union value at position ", i, " has negative offset ",
  	offset);
  	}
  	if (offset >= child_lengths[code]) {
  	return Status::Invalid("Union value at position ", i,
  	" has offset larger "
  	"than child length (",
  	offset, " >= ", child_lengths[code], ")");
  	}
  	if (offset < last_child_offsets[code]) {
  	return Status::Invalid("Union value at position ", i,
  	" has non-monotonic offset ", offset);
  	}
  	last_child_offsets[code] = offset;
  	}

• https://github.com/apache/arrow-go/blob/666f8dc2ea470d69fc294ba1f850d04050fb5047/arrow/array/union.go#L209

.NET/JavaScript/Julia/Swift

Couldn't find/not present