Empty collection in array or map lead to incorrect results in parquet reader

[qqibrow]

Bug description

parquet-tools output is different than velox parquet reader output:

lniu@devrestricted-lniu:~/velox_parquet_test_triage/fail_parquet_files/testArray$ parquet-tools show native_parquet_reader_test2148048251466121645parquet
+-------------------+
| test              |
|-------------------|
| [ 1. nan  3.]     |
| [5.]              |
| [nan nan nan]     |
| []                |
| [ 7. 11.]         |      ---> difference starting here 
| [nan]             |
| [13.]             |
| [17.]             |
| [ 1. nan  3.]     |
| [5.]              |
| [nan nan nan  7.] |
| [11. nan 13.]     |
+-------------------+

lniu@devrestricted-lniu:~/velox_parquet_test_triage/fail_parquet_files/testArray$ ~/velox_scan_parquet native_parquet_reader_test2148048251466121645parquet
number of rows: 12
velox type: ROW<test:ARRAY<INTEGER>>
{3 elements starting at 0 {1, null, 3}}
{1 elements starting at 3 {5}}
{3 elements starting at 4 {null, null, null}}
{<empty>}
{2 elements starting at 7 {null, 7}} ---> difference starting here 
{1 elements starting at 9 {11}}
{1 elements starting at 10 {null}}
{1 elements starting at 11 {13}}
{3 elements starting at 12 {17, 1, null}}
{1 elements starting at 15 {3}}
{4 elements starting at 16 {5, null, null, null}}
{3 elements starting at 20 {7, 11, null}}

System information

Velox System Info v0.0.2
Commit: 1e186e548833750cdee4b95d829711ddad78aba1
CMake Version: 3.16.3
System: Linux-5.4.0-1063-aws
Arch: x86_64
C++ Compiler: /usr/bin/c++
C++ Compiler Version: 9.4.0
C Compiler: /usr/bin/cc
C Compiler Version: 9.4.0
CMake Prefix Path: /usr/local;/usr;/;/usr;/usr/local;/usr/X11R6;/usr/pkg;/opt

Relevant logs

file to reproduce: https://www.dropbox.com/scl/fi/ln4d2tnoz497w309dr2qr/native_parquet_reader_test2148048251466121645parquet?rlkey=3ke9bkml3w35ij3g6gdymmz26&dl=0

[qqibrow]

file to reproduce: https://www.dropbox.com/scl/fi/ln4d2tnoz497w309dr2qr/native_parquet_reader_test2148048251466121645parquet?rlkey=3ke9bkml3w35ij3g6gdymmz26&dl=0

[aditi-pandit]

@yingsu00 @nmahadevuni

[jaystarshot]

I am taking a look thanks! Initial inspection seems like there is some bug in the offsets and size vectors of type Array or null of type Row

[yingsu00]

@jaystarshot I'm working on the refactor of null handling. It should resolve this issue.

[Yohahaha]

We encounter same issue when reading map, will keep tracking this issue.

[qqibrow]

Hi, I realized this has already been caught in existing test. I did an analysis and found the problem is empty collection related. whenever there is a empty array or map, the final result will be incorrect.

There is already a unit test capture the issue. I use the data https://github.com/facebookincubator/velox/blob/main/velox/dwio/parquet/tests/examples/array_2.parquet . the expect output is:

A array with type ARRAY<VARCHAR> containing 3 elements:

0: 2 elements starting at 0 {a, null}
1: <empty>
2: 2 elements starting at 2 {null, b}

array vector:

offset size  value
0      2     a
2      0     null 
2      2     null
             b

the actual output:

size = 0
0: 2 elements starting at 0 {a, null}
1: <empty>
2: 2 elements starting at 2 {null, null}

array vector:

offset size  value
0      2     a
2      0     null 
2      2     null
             null

parquet meta data:

lniu@lniu-FXGFKFV Downloads % parquet meta array_2.parquet

File path:  array_2.parquet
Created by: parquet-mr version 1.12.2 (build 77e30c8093386ec52c3cfa6c34b7ef3321322c94)
Properties:
  writer.model.name: example
Schema:
message spark_schema {
  required group _1 (LIST) {
    repeated group list {
      optional binary element (STRING);
    }
  }
}

Row group 0:  count: 3  20.00 B records  start: 4  total(compressed): 60 B total(uncompressed):46 B
--------------------------------------------------------------------------------
                 type      encodings count     avg size   nulls   min / max
_1.list.element  BINARY    G   _     5         12.00 B    3       "a" / "b"

the data in parquet format is:

def rep data
2   0   a 
1   1   b 
0   0
1   0
2   1

Current findings:

1. offset and size are right. RepeatedColumnReader::setLengthsFromRepDefs is correct.
2. on leaf level. pageReader.readPageDefLevels() which calls arrow::DefLevelsToBitmap() that makes leafNulls_ is “0b10001” . this is incorrect because 3rd def is 0, which is less than max def - 1, means the value doesn’t exist at all. (value has 3 status: exist_value, exist_null, not_exist)
3. Given size info, ListColumnReader decided to read 4 elements from leafReader that becomes [’a’, null, null, null]

Possible Solutions:

1. Given we are using arrow library to get nulls and value_to_read information, is it possible we are not using it correct? if so, fix the usage can fix the problem.
2. don’t reply on arrow::DefLevelsToBitmap() when deciding leaf level data.
3. Depending on whether 1 or 2 alone can cover all cases (nested array containing empty, array over map containing empty), might need to rebuild whole readPageDefLevels and not use arrow library here.

I also realized this is so far the only issue that can lead to data incorrectness issue when (we use presto unit test testing velox parquet)[https://gist.github.com/qqibrow/689ed97b91cc0b58337be96a86291301]. If [ I remove all generating empty list in presto unit test] (https://github.com/qqibrow/presto/pull/1/files), all data incorrectness issues will go away.

[yingsu00]

@qqibrow Thanks for the findings. Yes NestedStructureDecoder::readOffsetsAndNulls() will replace Arrow's rep/def decoder and should correctly process this case. However, it has a known bug, and it requires more changes than just replacing the rep/def decoder. I have the fix to the known bug, but haven't gotten time to send PRs. Once the first Iceberg equality delete PR is out I'll start working on this, hopefully next week.

[FelixYBW]

@yingsu00 is this known issue for map only? or also impact array/struct? We noted parquet parse issue on array

[nmahadevuni]

@yingsu00 is this known issue for map only? or also impact array/struct? We noted parquet parse issue on array

@FelixYBW This issue occurs with Array too

[FelixYBW]

does it impact stringview? We hit a bug that a string should be null but it return as ""

[jaystarshot]

I tried various parquet files with different iterations of empty and null.
Through various iterations, confirmed that the result mismatch happened in these cases.

and

and

Seems to be just an issue with the empty array as @qqibrow mentioned and not related to null atm.
Maybe we are wrongly reading the define and repetition level of empty ?

[jaystarshot]

@hitarth @qqibrow and me debugged this issue.
Seems like the current root cause is us not properly using arrows' arrow::DefLevelsToBitmap() function properly as we were not updating arrow::LevelInfo's repeated_ancestor_def_level properly.
We found out how arrow populated repeated_ancestor_def_level here which it apparently uses for empty checks.
So now we are trying to give arrow the correct repeated_ancestor_def_level. I have a wip here but this still needs some work.

[FelixYBW]

does it impact stringview? We hit a bug that a string should be null but it return as ""

forgot about it. It's fixed by #9129

[jaystarshot]

Pr #9187 is ready for review