[FEA] Nulls pushdowns for LIST columns

[devavret]

There are places in libcudf that expect a LIST column that has nulls in parent properly applied to the child.[1] i.e. if a list is null then it should also be empty and thus the offsets describing it should be same.

Similar to the superimpose_parent_nulls function for STRUCT columns, we need a function that can pushdown the nulls in a list column and compact a child when it had non-empty nulls.

This is also a blocker for #10289

[1] Parquet writer depends on the nulls properly applied to leaf child. When writing leaf child columns of lists, the range to write in a particular page is determined using the offsets. e.g. if row 0 to 5 are to be written to page 1, then the selected children are offsets[0] to offset[5]. If row 2 is null but offset[2] < offset[2+1] then those extraneous children also end up in the page.

[jrhemstad]

For posterity, can you summarize how a non-empty null list breaks things?

I liked your naming of "sanitize" as opposed to "superimpose" or "pushdown" in this scenario.

So something like sanitize_null_lists.

Or maybe "normalize"? normalize_null_lists?

[jrhemstad]

I think the easiest way to implement this is to simply perform an identity gather (i.e., gather map [0,n)).

Unfortunately, I spoke with @nvdbaranec and gather won't filter out non-empty lists currently. But it should be easier to modify gather than to create a whole new function just for stripping out non-empty null lists.

In addition, I'd like to see two additional APIs for determining if sanitization is necessary:

1. An approximate/fast one that only checks the null counts of all the nested list columns
2. An exact/slower one that launches a kernel to inspect the offsets/null masks to determine if non-empty null lists exist.

[jrhemstad]

We also have a decision to make about who is responsible for list sanitization.

As I see it, we only have two options:

1. User's responsibility

• A caller must ensure that any list column does not have non-empty null lists when passing to any libcudf API. libcudf would perform zero error checking to detect if this requirement is violated. If a caller violates this pre-condition, behavior is undefined (though most likely will result in silently incorrect answers as opposed to segfault).

2. libcudf responsibility

• All libcudf functions assume list columns must always be sanitized, and thus effectively create a deep copy of every list column before performing any operation. (Edit: The obvious exception here would be gather, but I think we'd keep the fact that gather works on dirty columns as an internal detail and just expose sanitization through a public sanitize API that internally calls gather)

(1.) is obviously running with scissors, but it is also far more performant and less memory intensive. This is especially relevant when using the same list column in multiple operations where you can sanitize it once and reuse it multiple times.

(2.) is safer, more convenient, but very expensive. In the case of reusing the same list column many times, we'd have to sanitize it every time, incurring a deep copy and the compute overhead of the sanitization.

Personally, in the spirit of "not making decisions" I would opt for (1.). First and foremost, libcudf is a performance oriented library and there are higher level layers to add convenience. To ease the burden, we would provide APIs for checking if sanitization is needed (described above):

a.) An approximate/fast one that only checks the null counts of all the nested list columns
b.) An exact/slower one that launches a kernel to inspect the offsets/null masks to determine if non-empty null lists exist.

Additionally, I think we can guarantee that libcudf will never return a list column that needs sanitization (including file readers) so long as we are never given a dirty list column as input. (I assume if a file contains a dirty list column, we would sanitize it as part of reading it and returning it. @devavret @vuule correct me if I'm wrong). So the only time a list column would need sanitization is if it's coming from somewhere other than libcudf.

Conceivably, we could put sanitization logic in interop APIs like from_arrow as well to further reduce the burden.

That way, the only way to get a dirty column is to manually construct a column/column_view yourself.

[nvdbaranec]

Additionally, I think we can guarantee that libcudf will never return a list column that needs sanitization

I think this is a pretty safe assumption (though we'd certainly have to retrofit some old stuff). It's pretty common for list-based functions to rely on gather() for final assembly so if we fix that, we're 80% of the way there.

[devavret]

if a file contains a dirty list column, we would sanitize it as part of reading it and returning it

This is always true for parquet, because parquet has a different representation which we convert from and i don't think we can create a dirty list from it, ever. @nvdbaranec, right?

[vuule]

I'm pretty sure ORC by definition cannot have elements in a null list. Content of null elements is never encoded in the file (which is
a pain for other reasons). @rgsl888prabhu, can you confirm?

[nvdbaranec]

This is always true for parquet, because parquet has a different representation which we convert from and i don't think we can >create a dirty list from it, ever.

Correct. I don't believe it's possible to have dirty lists in parquet.

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[sameerz]

Still needed.