> 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
I have probably missed this, and if so I apologize What is the usecase for sharing data to/from DuckDB and Velox to the C/C++ implementation of Arrow via the C ABI? 1. Is it so those projects could use the arrow compute kernels instead of their own? 2. Enable high speed parquet writing directly from output produced by those engines ? 3. Some other reason? I think a key part of Arrow's strength is its interoperability between languages and its serializability. For more specialized needs in query engines, perhaps using specialized implementations such as StringView with raw pointers and converting to/from Arrow at the boundaries could be reasonable. Andrew On Wed, Dec 15, 2021 at 7:40 PM Wes McKinney <wesmck...@gmail.com> wrote: > On Wed, Dec 15, 2021 at 6:22 PM Micah Kornfield <emkornfi...@gmail.com> > wrote: > >> > >> 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. > > > > > > Wes, something that still isn't clear to me, are we proposing these new > encoding for ONLY the C-ABI or do we want to plumb them or their analogues > through the IPC/File layout as well? > > > > In my mind, I think plumbing RLE though the IPC would definitely make > sense. The other ones might or might not make sense given the overhead > needed to sanitize them properly. > > > > Regarding the IPC wire format: > > * String view: not necessary, but an IPC serialization format where > only the non-inline data is written out to a data buffer (and > swizzling pointers to offsets) could be created. The unused "inline" > portions for short strings would need to be zeroed out to not leak > bytes > * Sequence view: would be simple to write to IPC without serialization > (just two buffers: one with offsets and another with sizes, and a > normal child) > * RLE / constant / all-null: yes > > So it seems the string views are where there is uncertainty around > whether having some degree of IPC support is useful. We might need to > do some experiments to quantify the performance benefits (for example, > when transmitting such data over Flight). > > > Thanks, > > Micah > > > > On Wed, Dec 15, 2021 at 2:43 PM Wes McKinney <wesmck...@gmail.com> > wrote: > >> > >> 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 > >> > > > > > > > > > >> > > > > > >> > > >
