On Wed, Dec 15, 2021 at 3:56 PM Micah Kornfield <emkornfi...@gmail.com> wrote: > > > > > Big +1 in replacing our current representation of variable-sized arrays by > > the "sequence view". atm I am -0.5 in adding it without removing the > > [Large]Utf8Array / Binary / List, as I see the advantages as sufficiently > > large to break compatibility and deprecate the previous representations > > (and do not enjoy maintaining multiple similar representations that solve > > very similar problems). > > > I don't think we should be deprecating anything in favor of these at a > format level. There are many production systems built on the current > encodings, and we've publicly documented such changes as a rare occurrence > [1]. If we do adopt the new encodings I think it is fine if most systems > only want to deal with them on system boundaries and convert to one of the > new encodings.
I agree with Micah's perspective here. We don't want to disrupt any production systems that have been built in the last 6 years. There are many of them at this point. There might be systems that would choose not to use these new encodings at all, and if they encounter them at the C ABI, they could choose to convert to one of the existing representations. For example, in the C ABI, one might choose: * UTF8 StringView -> convert to existing Arrow string layout * List/Map SequenceView -> convert to existing Arrow list layout * RLE / Constant View of anything -> unroll to non-RLE / Constant Arrow layout In a sense, giving systems the freedom to elect which representation makes sense for them but not requiring them to *emit* these new representations at the C ABI boundaries (beyond potentially implementing the conversion functions if they choose not to implement them at all). Converting from this StringView or SequenceView representation to one of the existing memory layouts is not complicated so I do not think this is too burdensome. In any case, having memory layouts that support O(# records) selections on strings and nested data will greatly benefit some data processing systems built on Arrow. If we don't have something like this "natively" in Arrow, then you are forcing such systems to serialize when pushing or pulling data from other Arrow-based systems. Rather than have every system implement some solution for this problem in a slightly different way, by establishing a standard in Arrow we can increase the likelihood that more systems will use a common representation that can be zero-copied (if that's what one wants) through the C ABI. > [1] https://arrow.apache.org/docs/format/Versioning.html#long-term-stability > > On Wed, Dec 15, 2021 at 1:35 PM Weston Pace <weston.p...@gmail.com> wrote: > > > > I am -0.5 in adding it without removing the > > > [Large]Utf8Array / Binary / List > > > > I'm not sure about dropping List. > > > > Is SequenceView semantically equivalent to List / FixedSizeList? In > > other words, is SequenceView a nested type? The document seems to > > suggest it is but the use case you described does not. For example, > > in the C++ compute today you cannot add List<INT32> + List<INT32> but > > I think you would want to be able to add SequenceView<INT32> + > > SequenceView<INT32>. Also, the size of a List<INT32> is the # of > > lists and not the # of items. For a SequenceView I think the size of > > the array would be the number of items. I would also consider it a > > semantic change to go from Struct{"x": INT32} to Struct{"X": > > List<INT32>}. > > > > From the use case it sounds more like SequenceView would be similar to > > dictionary and RLE, a different encoding for existing arrays. > > However, it is possible I am misreading things. > > > > On Wed, Dec 15, 2021 at 10:49 AM Jorge Cardoso Leitão > > <jorgecarlei...@gmail.com> wrote: > > > > > > Hi, > > > > > > Thanks a lot for this initiative and the write up. > > > > > > I did a small bench for the sequence view and added a graph to the > > document > > > for evidence of what Wes is writing wrt to performance of "selection / > > take > > > / filter". > > > > > > Big +1 in replacing our current representation of variable-sized arrays > > by > > > the "sequence view". atm I am -0.5 in adding it without removing the > > > [Large]Utf8Array / Binary / List, as I see the advantages as sufficiently > > > large to break compatibility and deprecate the previous representations > > > (and do not enjoy maintaining multiple similar representations that solve > > > very similar problems). > > > > > > Likewise, +1 for the RLE and -0.5 for the constant array, as the latter > > > seems redundant to me (it is an RLE). > > > > > > Wrt to the string view: would like to run some benches on that too. Could > > > someone clarify what are the "good cases" for that one? > > > > > > More generally, I second the point made by Antoine: there is already some > > > fragmentation over the types in the official implementations (see [1]), > > and > > > we do not even have a common integration test suite for the c data > > > interface. One approach to this dimension is to *deprecate* > > > representations, which goes into the direction mentioned above. > > > > > > Wrt to design, we could consider a separate enum for the RLE vs plain > > > encoding, as they are not really semantic types (the dictionary is also > > not > > > a semantic type but it is represented as one in at least the Rust > > > implementation, unfortunately). > > > > > > Wrt to Rust impl in particular, I do not think that the String View > > poses a > > > problem - Rust can layout according to the C representation. Here [2] is > > > the corresponding Rust code of the struct in the doc (generated via > > Rust's > > > bindgen [3]). > > > > > > Thanks again for this, looking very much forward to it! > > > > > > [1] > > > > > https://github.com/apache/arrow/blob/master/dev/archery/archery/integration/datagen.py#L1546 > > > [2] > > > > > https://github.com/DataEngineeringLabs/arrow-string-view/blob/main/src/string_view.rs > > > [3] https://rust-lang.github.io/rust-bindgen/command-line-usage.html > > > > > > > > > On Wed, Dec 15, 2021 at 3:15 AM Wes McKinney <wesmck...@gmail.com> > > wrote: > > > > > > > Ultimately, the problem comes down to providing a means of O(# > > > > records) selection (take, filter) performance and memory use for > > > > non-numeric data (strings, arrays, maps, etc.). > > > > > > > > DuckDB and Velox are two projects which have designed themselves to be > > > > very nearly Arrow-compatible but have implemented alternative memory > > > > layouts to achieve O(# records) selections on all data types. I am > > > > proposing to adopt these innovations as additional memory layouts in > > > > Arrow with a target of zero-copy across the C ABI — how exactly they > > > > are translated to the IPC format seems less of an immediate benefit > > > > than enabling the in-memory performance/memory use optimization since > > > > query engines can accelerate performance with faster selections. If > > > > there are some alternative proposals to achieve O(# records) time and > > > > space complexity for selection operations, let's definitely look at > > > > them. > > > > > > > > > > > > On Tue, Dec 14, 2021 at 8:02 PM Weston Pace <weston.p...@gmail.com> > > wrote: > > > > > > > > > > Would it be simpler to change the spec so that child arrays can be > > > > > chunked? This might reduce the data type growth and make the intent > > > > > more clear. > > > > > > > > > > This will add another dimension to performance analysis. We pretty > > > > > regularly get issues/tickets from users that have unknowingly created > > > > > parquet files with poor row group resolution (e.g. 50 rows per row > > > > > group) and experience rotten performance as a result. I suspect > > > > > something similar could happen here. It sounds like arrays will > > > > > naturally subdivide over time. Users might start seeing poor > > > > > performance without realizing the root cause is because their 1 > > > > > million element array has been split into 10,000 allocations of 100 > > > > > elements. However, I suspect this is something that could be managed > > > > > with visibility and recompaction utilities. > > > > > > > > > > > > > > > On Tue, Dec 14, 2021 at 1:22 PM Wes McKinney <wesmck...@gmail.com> > > > > wrote: > > > > > > > > > > > > hi folks, > > > > > > > > > > > > A few things in the general discussion, before certain things will > > > > > > have to be split off into their own dedicated discussions. > > > > > > > > > > > > It seems that I didn't do a very good job of motivating the > > "sequence > > > > > > view" type. Let me take a step back and discuss one of the problems > > > > > > these new memory layouts are solving. > > > > > > > > > > > > In Arrow currently, selection operations ("take", "filter", or > > > > > > indirect sort — the equivalent of > > arr.take(argsort(something_else)) if > > > > > > you're coming from NumPy) have time complexity proportional to the > > > > > > number of records for primitive types and complexity proportional > > to > > > > > > the greater of max(# records, memory size) for nested types. > > > > > > > > > > > > So, for example: > > > > > > > > > > > > * Take(arr, indices) has O(# records) complexity for primitive > > types > > > > > > and does O(# records) memory allocation > > > > > > * Take(arr, indices) has O(max(# records, size of memory buffers / > > > > > > child arrays)) complexity for strings and nested types and does > > O(size > > > > > > of memory buffers) memory allocation > > > > > > > > > > > > This means that columnar query engines that leverage selections can > > > > > > experience heavy costs both in time complexity and memory use when > > > > > > doing selections on non-primitive array data. Selections may arise > > > > > > from filtering or sorting or other operations. > > > > > > > > > > > > The "String view" and "Sequence view" memory layouts in this > > document > > > > > > do not have this problem. When using these for strings and nested > > > > > > data, they have the same time complexity and memory allocation > > > > > > behavior for selections as primitive types, and the "child" memory > > > > > > buffers do not have to be manipulated or rebuilt at all. This has > > > > > > significant performance benefits and reduced memory use. > > > > > > > > > > > > Additionally, the string view and sequence view layouts solve the > > > > > > problem of out-of-order construction. As has been pointed out, one > > way > > > > > > to work around this issue at present is to use "chunked arrays". > > > > > > However, this means that you cannot ever use thread parallelism in > > the > > > > > > construction of non-chunked outputs with nested data (for example, > > in > > > > > > expression evaluation) — if a nested array forms part of a record > > > > > > batch, then either you must stick to single-threaded execution or > > use > > > > > > thread parallelism to subdivide even the other fields of the record > > > > > > batch that are non-nested to obtain equal-sized arrays across all > > > > > > fields. For example, if you had a record batch with 32K rows and > > > > > > wanted to parallelize execution of a projection using 4 threads — > > you > > > > > > would need to divide all fields into chunks of 8K each prior to > > > > > > beginning to produce outputs. This is fairly inflexible. > > > > > > > > > > > > As another motivating example, consider a parallel selection > > operation > > > > > > (e.g. "take" or "filter") on a nested array. Currently it is not > > > > > > possible to parallelize at all because of the in-order construction > > > > > > requirement. > > > > > > > > > > > > I don't expect you to just trust me — here is an example: > > > > > > > > > > > > https://gist.github.com/wesm/25fc7b877f913c7e4449117178302646 > > > > > > > > > > > > In this example, I use Take to permute 1M doubles and 1M strings > > with > > > > > > 50 bytes each > > > > > > > > > > > > * Doubles: 2.45ms (new memory allocated: 8000000) > > > > > > * Strings: 39.6ms (new memory allocated: 54000000) > > > > > > > > > > > > The performance ratio is 16x even though the memory ratio is only > > ~7x. > > > > > > With the "StringView" data type, only 16000000 bytes of new memory > > > > > > would need to be allocated, and the performance should be only 2-4x > > > > > > slower than the doubles case (because we only need to relocate a > > bunch > > > > > > of 16-byte structs) instead of 16x slower. > > > > > > > > > > > > I hope you can see now that this can be a rather serious resource > > > > > > utilization issue, both in processing time and memory use. I will > > > > > > update the document to explain this better and work on responding > > to > > > > > > some of the other comments. > > > > > > > > > > > > Wes > > > > > > > > > > > > On Tue, Dec 14, 2021 at 5:08 AM Antoine Pitrou <anto...@python.org > > > > > > > wrote: > > > > > > > > > > > > > > > > > > > > > Hello, > > > > > > > > > > > > > > I think my main concern is how we can prevent the community from > > > > > > > fragmenting too much over supported encodings. The more complex > > the > > > > > > > encodings, the less likely they are to be supported by all main > > > > > > > implementations. We see this in Parquet where the efficient > > "delta" > > > > > > > encodings have just received support in Parquet C++, and even, > > only > > > > on > > > > > > > the read side. > > > > > > > > > > > > > > There is an additional subtlety in that Arrow is not a storage > > > > mechanism > > > > > > > but it represents data in memory, so pieces doing computation > > have > > > > to be > > > > > > > adapted to the new encodings, for example the entire library of > > > > > > > computation kernels in Arrow C++ (of course, an easy but > > inefficient > > > > > > > adaptation is to always unpack to an already supported layout). > > > > > > > > > > > > > > As an anecdote, the Arrow C++ kernels are supposed to accept a > > > > selection > > > > > > > vector to filter their physical inputs, but none actually > > supports > > > > it. > > > > > > > I think we should be wary of adding ambitious new features that > > might > > > > > > > never get an actual implementation. > > > > > > > > > > > > > > > > > > > > > On the detail of the proposed encodings: > > > > > > > > > > > > > > - I hope we can avoid storing raw pointers instead of offsets > > into a > > > > > > > separate buffer; I understand the flexibility argument for > > pointers > > > > but > > > > > > > it will also make data transfer more complicated > > > > > > > > > > > > > > - Constant arrays are a special case of RLE arrays and I'm not > > sure > > > > > > > doing both is really useful > > > > > > > > > > > > > > - I don't really understand the concrete use case for the weird > > > > > > > "sequence view" layout; I'll note that non-monotonic offsets can > > make > > > > > > > linear traversal less efficient, since the CPU won't > > automatically > > > > > > > prefetch data for you > > > > > > > > > > > > > > - The proposed RLE encoding seems inefficient; usually, RLE > > encodings > > > > > > > try hard to minimize the size overhead of RLE sequences, such > > that > > > > they > > > > > > > become beneficial even for very short repeated runs > > > > > > > > > > > > > > Regards > > > > > > > > > > > > > > Antoine. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Le 10/12/2021 à 20:28, Wes McKinney a écrit : > > > > > > > > > > > > > > > > This topic may provoke , but, given that Arrow is approaching > > its > > > > > > > > 6-year anniversary, I think this is an important discussion > > about > > > > how > > > > > > > > we can thoughtfully expand the Arrow specifications to support > > > > > > > > next-generation columnar data processing. In recent times, I > > have > > > > been > > > > > > > > motivated by recent interactions with CWI's DuckDB and Meta's > > Velox > > > > > > > > open source projects and the innovations they've made around > > data > > > > > > > > representation providing beneficial features above and beyond > > what > > > > we > > > > > > > > have already in Arrow. For example, they have a 16-byte "string > > > > view" > > > > > > > > data type that enables buffer memory reuse, faster "false" > > > > comparisons > > > > > > > > on strings unequal in the first 4 bytes, and inline small > > strings. > > > > > > > > Both the Rust and C++ query engine efforts could potentially > > > > benefit > > > > > > > > from this (not sure about the memory safety implications in > > Rust, > > > > > > > > comments around this would be helpful). > > > > > > > > > > > > > > > > I wrote a document to start a discussion about a few new ways > > to > > > > > > > > represent data that may help with building > > > > > > > > Arrow-native/Arrow-compatible query engines: > > > > > > > > > > > > > > > > > > > > > > https://docs.google.com/document/d/12aZi8Inez9L_JCtZ6gi2XDbQpCsHICNy9_EUxj4ILeE/edit# > > > > > > > > > > > > > > > > Each of these potential additions would need to be eventually > > split > > > > > > > > off into independent efforts with associated additions to the > > > > columnar > > > > > > > > specification, IPC format, C ABI, integration tests, and so on. > > > > > > > > > > > > > > > > The document is open to anyone to comment but if anyone would > > like > > > > > > > > edit access please feel free to request and I look forward to > > the > > > > > > > > discussion. > > > > > > > > > > > > > > > > Thanks, > > > > > > > > Wes > > > > > > > > > > > > > >
