+1 on what Ian said. And as I write kernels for this new format, I’m learning that it’s possible to re-use the common infrastructure used by List and LargeList to implement the ListView related features with some adjustments.
IMO having this format as a second-class citizen would more likely complicate things because it would make this unification harder. — Felipe On Tue, 6 Jun 2023 at 18:45 Ian Cook <ianmc...@apache.org> wrote: > To clarify why we cannot simply propose adding ListView as a new > “canonical extension type”: The extension type mechanism in Arrow > depends on the underlying data being organized in an existing Arrow > layout—that way an implementation that does not support the extension > type can still handle the underlying data. But ListView is a wholly > new layout. > > I strongly agree with Weston’s idea that it is a good time for Arrow > to introduce the notion of “canonical alternative layouts.” > > Taken together, I think that canonical extension types and canonical > alternative layouts could serve as an “incubator” for proposed new > representations. For example, if a proposed canonical alternative > layout ends up being broadly adopted, then that will serve as a signal > that we should consider adding it as a primary layout in the core > spec. > > It seems to me that most projects that are implementing Arrow today > are not aiming to provide complete coverage of Arrow; rather they are > adopting Arrow because of its role as a standard and they are > implementing only as much of the Arrow standard as they require to > achieve some goal. I believe that such projects are important Arrow > stakeholders, and I believe that this proposed notion of canonical > alternative layouts will serve them well and will create efficiencies > by standardizing implementations around a shared set of alternatives. > > However I think that the documentation for canonical alternative > layouts should strongly encourage implementers to default to using the > primary layouts defined in the core spec and only use alternative > layouts in cases where the primary layouts do not meet their needs. > > > On Sat, May 27, 2023 at 7:44 PM Micah Kornfield <emkornfi...@gmail.com> > wrote: > > > > This sounds reasonable to me but my main concern is, I'm not sure there > is > > a great mechanism to enforce canonical layouts don't somehow become > default > > (or the only implementation). > > > > Even for these new layouts, I think it might be worth rethinking binding > a > > layout into the schema versus having a different concept of encoding (and > > changing some of the corresponding data structures). > > > > > > On Mon, May 22, 2023 at 10:37 AM Weston Pace <weston.p...@gmail.com> > wrote: > > > > > Trying to settle on one option is a fruitless endeavor. Each type has > pros > > > and cons. I would also predict that the largest existing usage of > Arrow is > > > shuttling data from one system to another. The newly proposed format > > > doesn't appear to have any significant advantage for that use case (if > > > anything, the existing format is arguably better as it is more > compact). > > > > > > I am very biased towards historical precedent and avoiding breaking > > > changes. > > > > > > We have "canonical extension types", perhaps it is time for "canonical > > > alternative layouts". We could define it as such: > > > > > > * There are one or more primary layouts > > > * Existing layouts are automatically considered primary layouts, > even if > > > they wouldn't > > > have been primary layouts initially (e.g. large list) > > > * A new layout, if it is semantically equivalent to another, is > considered > > > an alternative layout > > > * An alternative layout still has the same requirements for adoption > (two > > > implementations and a vote) > > > * An implementation should not feel pressured to rush and implement > the > > > new layout. > > > It would be good if they contribute in the discussion and > consider the > > > layout and vote > > > if they feel it would be an acceptable design. > > > * We can define and vote and approve as many canonical alternative > layouts > > > as we want: > > > * A canonical alternative layout should, at a minimum, have some > > > reasonable justification, such as improved performance for > algorithm X > > > * Arrow implementations MUST support the primary layouts > > > * An Arrow implementation MAY support a canonical alternative, > however: > > > * An Arrow implementation MUST first support the primary layout > > > * An Arrow implementation MUST support conversion to/from the > primary > > > and canonical layout > > > * An Arrow implementation's APIs MUST only provide data in the > > > alternative > > > layout if it is explicitly asked for (e.g. schema inference should > > > prefer the primary layout). > > > * We can still vote for new primary layouts (e.g. promoting a > canonical > > > alternative) but, in these > > > votes we don't only consider the value (e.g. performance) of the > layout > > > but also the interoperability. > > > In other words, a layout can only become a primary layout if there > is > > > significant evidence that most > > > implementations plan to adopt it. > > > > > > This lets us evolve support for new layouts more naturally. We can > > > generally assume that users will not, initially, be aware of these > > > alternative layouts. However, everything will just work. They may > start > > > to see a performance penalty stemming from a lack of support for these > > > layouts. If this performance penalty becomes significant then they > will > > > discover it and become aware of the problem. They can then ask > whatever > > > library they are using to add support for the alternative layout. As > > > enough users find a need for it then libraries will add support. > > > Eventually, enough libraries will support it that we can adopt it as a > > > primary layout. > > > > > > Also, it allows libraries to adopt alternative layouts more > aggressively if > > > they would like while still hopefully ensuring that we eventually all > > > converge on the same implementation of the alternative layout. > > > > > > On Mon, May 22, 2023 at 9:35 AM Will Jones <will.jones...@gmail.com> > > > wrote: > > > > > > > Hello Arrow devs, > > > > > > > > I don't understand why we would start deprecating features in the > Arrow > > > > > format. Even starting this talk might already be a bad idea > PR-wise. > > > > > > > > > > > > > I agree we don't want to make breaking changes to the Arrow format. > But > > > > several maintainers have already stated they have no interest in > > > > maintaining both list types with full compute functionality [1][2], > so I > > > > think it's very likely one list type or the other will be > > > > implicitly preferred in the ecosystem if this data type was added. > If > > > > that's the case, I'd prefer that we agreed as a community which one > > > should > > > > be preferred. Maybe that's not the best path; it's just one way for > us to > > > > balance stability, maintenance burden, and relevance. > > > > > > > > Can someone help distill down the primary rationale and usecase for > > > > > adding ArrayView to the Arrow Spec? > > > > > > > > > > > > > Looking back at that old thread, I think one of the main motivations > is > > > to > > > > try to prevent query engine implementers from feeling there is a > tradeoff > > > > between having state-of-the-art performance and being Arrow-native. > For > > > > some of the new array types, we had both Velox and DuckDB use them, > so it > > > > was reasonable to expect they were innovations that might > proliferate. > > > I'm > > > > not sure if the ArrayView is part of that. From Wes earlier [3]: > > > > > > > > The idea is that in a world of data and query federation (for > example, > > > > > consider [1] where Arrow is being used as a data federation layer > with > > > > many > > > > > query engines), we want to increase the amount of data in-flight > and > > > > > in-memory that is in Arrow format. So if query engines are having > to > > > > depart > > > > > substantially from the Arrow format to get performance, then this > > > > creates a > > > > > potential lose-lose situation: * Depart from Arrow: get better > > > > performance > > > > > but pay serialization costs to read and write Arrow (the > performance > > > and > > > > > resource utilization benefits outweigh the serialization costs). > This > > > > puts > > > > > additional pressure on query engines to build specialized > components > > > for > > > > > solving problems rather than making use of off-the-shelf components > > > that > > > > > use Arrow. This has knock-on effects on ecosystem fragmentation. * > Or > > > use > > > > > Arrow, and accept suboptimal query processing performance > > > > > > > > > > > > > > > > > Will mentions one usecase is Velox consuming python UDF output, which > > > seems > > > > > to be mostly about how fast Velox can consume this format, not how > fast > > > > it > > > > > can be written. Are there other usecases? > > > > > > > > > > > > > To be clear, I don't know if that's the use case they want. That's > just > > > me > > > > speculating. > > > > > > > > I still have some questions myself: > > > > > > > > 1. Is this array type currently only used in Velox? (not DuckDB like > some > > > > of the other new types?) What evidence do we have that it will become > > > used > > > > outside of Velox? > > > > 2. We already have three list types: list, large list (64-bit > offsets), > > > and > > > > fixed size list. Do we think we will only want a view version of the > > > 32-bit > > > > offset variable length list? Or are we potentially talking about view > > > > variants for all three? > > > > > > > > Best, > > > > > > > > Will Jones > > > > > > > > [1] https://lists.apache.org/thread/smn13j1rnt23mb3fwx75sw3f877k3nwx > > > > [2] https://lists.apache.org/thread/cc4w3vs3foj1fmpq9x888k51so60ftr3 > > > > [3] https://lists.apache.org/thread/mk2yn62y6l8qtngcs1vg2qtwlxzbrt8t > > > > > > > > On Mon, May 22, 2023 at 3:48 AM Andrew Lamb <al...@influxdata.com> > > > wrote: > > > > > > > > > Can someone help distill down the primary rationale and usecase for > > > > > adding ArrayView to the Arrow Spec? > > > > > > > > > > From the above discussions, the stated rationale seems to be fast > > > > > (zero-copy) interchange with Velox. > > > > > > > > > > This thread has qualitatively enumerated the benefits of > (offset+len) > > > > > encoding over the existing Arrow ListArray (offets) approach, but I > > > > haven't > > > > > seen any performance measurements that might help us to gauge the > > > > tradeoff > > > > > in additional complexity vs runtime overhead. > > > > > > > > > > Will mentions one usecase is Velox consuming python UDF output, > which > > > > seems > > > > > to be mostly about how fast Velox can consume this format, not how > fast > > > > it > > > > > can be written. Are there other usecases? > > > > > > > > > > Do we have numbers showing how much overhead converting to /from > > > Velox's > > > > > internal representation and the existing ListArray adds? Has > anyone in > > > > > Velox land considered adding faster support for Arrow style > ListArray > > > > > encoding? > > > > > > > > > > > > > > > Andrew > > > > > > > > > > On Mon, May 22, 2023 at 4:38 AM Antoine Pitrou <anto...@python.org > > > > > > wrote: > > > > > > > > > > > > > > > > > Hi, > > > > > > > > > > > > I don't understand why we would start deprecating features in the > > > Arrow > > > > > > format. Even starting this talk might already be a bad idea > PR-wise. > > > > > > > > > > > > As for implementing conversions at the I/O boundary, it's a > > > reasonably > > > > > > policy, but it still requires work by implementors and it's not > > > granted > > > > > > that all consumers of the Arrow format will grow such conversions > > > > > > if/when we add non-trivial types such as ListView or StringView. > > > > > > > > > > > > Regards > > > > > > > > > > > > Antoine. > > > > > > > > > > > > > > > > > > Le 22/05/2023 à 00:39, Will Jones a écrit : > > > > > > > One more thing: Looking back on the previous discussion[1] > (which > > > > > Weston > > > > > > > pointed out in his earlier message), Jorge suggested that the > old > > > > list > > > > > > > types might be deprecated in favor of view variants [2]. Others > > > were > > > > > > > worried that it might undermine the perception that the Arrow > > > format > > > > is > > > > > > > stable. I think it might be worth thinking about "soft > deprecating" > > > > the > > > > > > old > > > > > > > list type: suggesting new implementations prefer the list > view, but > > > > > > > reassuring that implementations should support the old format, > even > > > > if > > > > > > they > > > > > > > just convert to the new format. To be clear, this wouldn't > mean we > > > > plan > > > > > > to > > > > > > > create breaking changes in the format; but if we ever did for > other > > > > > > > reasons, the old list type might go. > > > > > > > > > > > > > > Arrow compute libraries could choose either format for compute > > > > support, > > > > > > and > > > > > > > plan to do conversion at the boundaries. Libraries that use > the new > > > > > type > > > > > > > will have cheap conversion when reading the old type. Meanwhile > > > those > > > > > > that > > > > > > > are still on the old type will have some incentive to move > towards > > > > the > > > > > > new > > > > > > > one, since that conversion will not be as efficient. > > > > > > > > > > > > > > [1] > > > https://lists.apache.org/thread/49qzofswg1r5z7zh39pjvd1m2ggz2kdq > > > > > > > [2] > > > https://lists.apache.org/thread/smn13j1rnt23mb3fwx75sw3f877k3nwx > > > > > > > > > > > > > > On Sun, May 21, 2023 at 3:07 PM Will Jones < > > > will.jones...@gmail.com> > > > > > > wrote: > > > > > > > > > > > > > >> Hello, > > > > > > >> > > > > > > >> I think Sasha brings up a good point, that the advantages of > this > > > > > format > > > > > > >> seem to be primarily about query processing. Other encodings > like > > > > REE > > > > > > and > > > > > > >> dictionary have space-saving advantages that justify them > simply > > > in > > > > > > terms > > > > > > >> of space efficiency (although they have query processing > > > advantages > > > > as > > > > > > >> well). As discussed, most use cases are already well served by > > > > > existing > > > > > > >> list types and dictionary encoding. > > > > > > >> > > > > > > >> I agree that there are cases where transferring this type > without > > > > > > >> conversion would be ideal. One use case I can think of is if > Velox > > > > > > wants to > > > > > > >> be able to take Arrow-based UDFs (possibly written with > PyArrow, > > > for > > > > > > >> example) that operate on this column type and therefore wants > > > > > zero-copy > > > > > > >> exchange over the C Data Interface. > > > > > > >> > > > > > > >> One big question I have: we already have three list types: > list, > > > > large > > > > > > >> list (64-bit offsets), and fixed size list. Do we think we > will > > > only > > > > > > want a > > > > > > >> view version of the 32-bit offset variable length list? Or > are we > > > > > > >> potentially talking about view variants for all three? > > > > > > >> > > > > > > >> Best, > > > > > > >> > > > > > > >> Will Jones > > > > > > >> > > > > > > >> > > > > > > >> On Sun, May 21, 2023 at 2:19 PM Felipe Oliveira Carvalho < > > > > > > >> felipe...@gmail.com> wrote: > > > > > > >> > > > > > > >>> The benefit of having a memory format that’s friendly to > > > > > > non-deterministic > > > > > > >>> order writes is unlocked by the transport and processing of > the > > > > data > > > > > > being > > > > > > >>> agnostic to the physical order as much as possible. > > > > > > >>> > > > > > > >>> Requiring a conversion could cancel out that benefit. But it > can > > > > be a > > > > > > >>> provisory step for compatibility between systems that don’t > > > > > understand > > > > > > the > > > > > > >>> format yet. This is similar to the situation with compression > > > > schemes > > > > > > like > > > > > > >>> run-end encoding — the goal is processing the compressed data > > > > > directly > > > > > > >>> without an expansion step whenever possible. > > > > > > >>> > > > > > > >>> This is why having it as part of the open Arrow format is so > > > > > important: > > > > > > >>> everyone can agree on a format that’s friendly to parallel > and/or > > > > > > >>> vectorized compute kernels without introducing multiple > > > > incompatible > > > > > > >>> formats to the ecosystem and without imposing a conversion > step > > > > > between > > > > > > >>> the > > > > > > >>> different systems. > > > > > > >>> > > > > > > >>> — > > > > > > >>> Felipe > > > > > > >>> > > > > > > >>> On Sat, 20 May 2023 at 20:04 Aldrin > <octalene....@pm.me.invalid> > > > > > > wrote: > > > > > > >>> > > > > > > >>>> I don't feel like this representation is necessarily a > detail of > > > > the > > > > > > >>> query > > > > > > >>>> engine, but I am also not sure why this representation would > > > have > > > > to > > > > > > be > > > > > > >>>> converted to a non-view format when serializing. Could you > > > clarify > > > > > > >>> that? My > > > > > > >>>> impression is that this representation could be used for > > > > persistence > > > > > > or > > > > > > >>>> data transfer, though it can be more complex to guarantee > the > > > > > portion > > > > > > of > > > > > > >>>> the buffer that an index points to is also present in > memory. > > > > > > >>>> > > > > > > >>>> Sent from Proton Mail for iOS > > > > > > >>>> > > > > > > >>>> > > > > > > >>>> On Sat, May 20, 2023 at 15:00, Sasha Krassovsky < > > > > > > >>> krassovskysa...@gmail.com > > > > > > >>>> > <On+Sat,+May+20,+2023+at+15:00,+Sasha+Krassovsky+%3C%3Ca+href=>> > > > > > > wrote: > > > > > > >>>> > > > > > > >>>> Hi everyone, > > > > > > >>>> I understand that there are numerous benefits to this > > > > representation > > > > > > >>>> during query processing, but would it be fair to say that > this > > > is > > > > an > > > > > > >>>> implementation detail of the query engine? Query engines > don’t > > > > > > >>> necessarily > > > > > > >>>> need to conform to the Arrow format internally, only at > > > > > ingest/egress > > > > > > >>>> points, and performing a conversion from the non-view to > view > > > > format > > > > > > >>> seems > > > > > > >>>> like it would be very cheap (though I understand not > necessarily > > > > the > > > > > > >>> other > > > > > > >>>> way around, but you’d need to do that anyway if you’re > > > > serializing). > > > > > > >>>> > > > > > > >>>> Sasha Krassovsky > > > > > > >>>> > > > > > > >>>>> 20 мая 2023 г., в 13:00, Will Jones < > will.jones...@gmail.com> > > > > > > >>>> написал(а): > > > > > > >>>>> > > > > > > >>>>> Thanks for sharing these details, Pedro. The conditional > > > > branches > > > > > > >>>> argument > > > > > > >>>>> makes a lot of sense to me. > > > > > > >>>>> > > > > > > >>>>> The tensors point brings up some interesting issues. For > now, > > > > we've > > > > > > >>>> defined > > > > > > >>>>> our only tensor extension type to be built on a fixed size > > > list. > > > > > If a > > > > > > >>> use > > > > > > >>>>> case of this might be manipulating tensors with zero copy, > > > > perhaps > > > > > > >>> that > > > > > > >>>>> suggests that we want a fixed size list variant? In > addition, > > > > would > > > > > > we > > > > > > >>>> have > > > > > > >>>>> to define another extension type to be a ListView variant? > Or > > > > would > > > > > > we > > > > > > >>>> want > > > > > > >>>>> to think about making extension types somehow valid across > > > > various > > > > > > >>>>> encodings of the same "logical type"? > > > > > > >>>>> > > > > > > >>>>>> On Fri, May 19, 2023 at 1:59 PM Pedro Eugenio Rocha > Pedreira > > > > > > >>>>>> <pedro...@meta.com.invalid> wrote: > > > > > > >>>>>> > > > > > > >>>>>> Hi all, > > > > > > >>>>>> > > > > > > >>>>>> This is Pedro from the Velox team at Meta. This is my > first > > > time > > > > > > >>> here, > > > > > > >>>> so > > > > > > >>>>>> nice to e-meet you! > > > > > > >>>>>> > > > > > > >>>>>> Adding to what Felipe said, the main reason we created > > > > “ListView” > > > > > > >>>> (though > > > > > > >>>>>> we just call them ArrayVector/MapVector in Velox) is that, > > > along > > > > > > with > > > > > > >>>>>> StringViews for strings, they allow us to write any > columnar > > > > > buffer > > > > > > >>>>>> out-or-order, regardless of their types or encodings. > This is > > > > > > >>> naturally > > > > > > >>>>>> doable for all primitive types (fixed-size), but not for > types > > > > > that > > > > > > >>>> don’t > > > > > > >>>>>> have fixed size and are required to be contiguous. The > > > > StringView > > > > > > and > > > > > > >>>>>> ListView formats allow us to keep this invariant in Velox. > > > > > > >>>>>> > > > > > > >>>>>> Being able to write vectors out-of-order is useful when > > > > executing > > > > > > >>>>>> conditionals like IF/SWITCH statements, which are > pervasive > > > > among > > > > > > our > > > > > > >>>>>> workloads. To fully vectorize it, one first evaluates the > > > > > > expression, > > > > > > >>>> then > > > > > > >>>>>> generate a bitmap containing which rows take the THEN and > > > which > > > > > take > > > > > > >>> the > > > > > > >>>>>> ELSE branch. Then you populate all rows that match the > first > > > > > branch > > > > > > >>> by > > > > > > >>>>>> evaluating the THEN expression in a vectorized > (branch-less > > > and > > > > > > cache > > > > > > >>>>>> friendly) way, and subsequently the ELSE branch. If you > can’t > > > > > write > > > > > > >>> them > > > > > > >>>>>> out-of-order, you would either have a big branch per row > > > > > dispatching > > > > > > >>> to > > > > > > >>>> the > > > > > > >>>>>> right expression (slow), or populate two distinct vectors > then > > > > > > >>> merging > > > > > > >>>> them > > > > > > >>>>>> at the end (potentially even slower). How much faster our > > > > approach > > > > > > is > > > > > > >>>>>> highly depends on the buffer sizes and expressions, but we > > > found > > > > > it > > > > > > >>> to > > > > > > >>>> be > > > > > > >>>>>> faster enough on average to justify us extending the > > > underlying > > > > > > >>> layout. > > > > > > >>>>>> > > > > > > >>>>>> With that said, this is all within a single thread of > > > execution. > > > > > > >>>>>> Parallelization is done by feeding each thread its own > > > > > vector/data. > > > > > > >>> As > > > > > > >>>>>> pointed out in a previous message, this also gives you the > > > > > > >>> flexibility > > > > > > >>>> to > > > > > > >>>>>> implement cardinality increasing/reducing operations, but > we > > > > don’t > > > > > > >>> use > > > > > > >>>> it > > > > > > >>>>>> for that purpose. Operations like filtering, joining, > > > unnesting > > > > > and > > > > > > >>>> similar > > > > > > >>>>>> are done by wrapping the internal vector in a dictionary, > as > > > > these > > > > > > >>> need > > > > > > >>>> to > > > > > > >>>>>> work not only on “ListViews” but on any data types with > any > > > > > > encoding. > > > > > > >>>> There > > > > > > >>>>>> are more details on Section 4.2.1 in [1] > > > > > > >>>>>> > > > > > > >>>>>> Beyond this, it also gives function/kernel developers more > > > > > > >>> flexibility > > > > > > >>>> to > > > > > > >>>>>> implement operations that manipulate Arrays/Maps. For > example, > > > > > > >>>> operations > > > > > > >>>>>> that slice these containers can be implemented in a > zero-copy > > > > > manner > > > > > > >>> by > > > > > > >>>>>> just rearranging the lengths/offsets indices, without ever > > > > > touching > > > > > > >>> the > > > > > > >>>>>> larger internal buffers. This is a similar motivation as > for > > > > > > >>> StringView > > > > > > >>>>>> (think of substr(), trim(), and similar). One nice last > > > property > > > > > is > > > > > > >>> that > > > > > > >>>>>> this layout allows for overlapping ranges. This is > something > > > > > > >>> discussed > > > > > > >>>> with > > > > > > >>>>>> our ML people to allow deduping feature values in a tensor > > > > (which > > > > > is > > > > > > >>>> fairly > > > > > > >>>>>> common), but not something we have leveraged just yet. > > > > > > >>>>>> > > > > > > >>>>>> [1] - https://vldb.org/pvldb/vol15/p3372-pedreira.pdf > > > > > > >>>>>> > > > > > > >>>>>> Best, > > > > > > >>>>>> -- > > > > > > >>>>>> Pedro Pedreira > > > > > > >>>>>> ________________________________ > > > > > > >>>>>> From: Felipe Oliveira Carvalho <felipe...@gmail.com> > > > > > > >>>>>> Sent: Friday, May 19, 2023 10:01 AM > > > > > > >>>>>> To: dev@arrow.apache.org <dev@arrow.apache.org> > > > > > > >>>>>> Cc: Pedro Eugenio Rocha Pedreira <pedro...@meta.com> > > > > > > >>>>>> Subject: Re: [DISCUSS][Format] Starting the draft > > > implementation > > > > > of > > > > > > >>> the > > > > > > >>>>>> ArrayView array format > > > > > > >>>>>> > > > > > > >>>>>> +pedroerp On Thu, 11 May 2023 at 17: 51 Raphael > Taylor-Davies > > > > <r. > > > > > > >>>>>> taylordavies@ googlemail. com. invalid> wrote: Hi All, > > if > > > we > > > > > > added > > > > > > >>>>>> this, do we think many Arrow and query > engine > > > implementations > > > > > (for > > > > > > >>>>>> example, DataFusion) will be > > > > > > >>>>>> ZjQcmQRYFpfptBannerStart > > > > > > >>>>>> This Message Is From an External Sender > > > > > > >>>>>> > > > > > > >>>>>> ZjQcmQRYFpfptBannerEnd > > > > > > >>>>>> +pedroerp > > > > > > >>>>>> > > > > > > >>>>>> On Thu, 11 May 2023 at 17:51 Raphael Taylor-Davies > > > > > > >>>>>> <r.taylordav...@googlemail.com.invalid> wrote: > > > > > > >>>>>> Hi All, > > > > > > >>>>>> > > > > > > >>>>>>> if we added this, do we think many Arrow and query > > > > > > >>>>>>> engine implementations (for example, DataFusion) will be > > > eager > > > > to > > > > > > >>> add > > > > > > >>>>>> full > > > > > > >>>>>>> support for the type, including compute kernels? Or are > they > > > > > likely > > > > > > >>> to > > > > > > >>>>>> just > > > > > > >>>>>>> convert this type to ListArray at import boundaries? > > > > > > >>>>>> I can't speak for query engines in general, but at least > for > > > > > > arrow-rs > > > > > > >>>>>> and by extension DataFusion, and based on my current > > > > understanding > > > > > > of > > > > > > >>>>>> the use-cases I would be rather hesitant to add support > to the > > > > > > >>> kernels > > > > > > >>>>>> for this array type, definitely instead favouring > conversion > > > at > > > > > the > > > > > > >>>>>> edges. We already have issues with the amount of code > > > generation > > > > > > >>>>>> resulting in binary bloat and long compile times, and I > worry > > > > this > > > > > > >>> would > > > > > > >>>>>> worsen this situation whilst not really providing > compelling > > > > > > >>> advantages > > > > > > >>>>>> for the vast majority of workloads that don't interact > with > > > > Velox. > > > > > > >>>>>> Whilst I can definitely see that the ListView > representation > > > is > > > > > > >>> probably > > > > > > >>>>>> a better way to represent variable length lists than what > > > arrow > > > > > > >>> settled > > > > > > >>>>>> upon, I'm not yet convinced it is sufficiently better to > > > > > incentivise > > > > > > >>>>>> broad ecosystem adoption. > > > > > > >>>>>> > > > > > > >>>>>> Kind Regards, > > > > > > >>>>>> > > > > > > >>>>>> Raphael Taylor-Davies > > > > > > >>>>>> > > > > > > >>>>>>> On 11/05/2023 21:20, Will Jones wrote: > > > > > > >>>>>>> Hi Felipe, > > > > > > >>>>>>> > > > > > > >>>>>>> Thanks for the additional details. > > > > > > >>>>>>> > > > > > > >>>>>>> > > > > > > >>>>>>>> Velox kernels benefit from being able to append data to > the > > > > > array > > > > > > >>> from > > > > > > >>>>>>>> different threads without care for strict ordering. > Only the > > > > > > >>> offsets > > > > > > >>>>>> array > > > > > > >>>>>>>> has to be written according to logical order but that is > > > > > > >>> potentially a > > > > > > >>>>>> much > > > > > > >>>>>>>> smaller buffer than the values buffer. > > > > > > >>>>>>>> > > > > > > >>>>>>> It still seems to me like applications are still pretty > > > niche, > > > > > as I > > > > > > >>>>>> suspect > > > > > > >>>>>>> in most cases the benefits are outweighed by the costs. > The > > > > > benefit > > > > > > >>>> here > > > > > > >>>>>>> seems pretty limited: if you are trying to split work > between > > > > > > >>> threads, > > > > > > >>>>>>> usually you will have other levels such as array chunks > to > > > > > > >>> parallelize. > > > > > > >>>>>> And > > > > > > >>>>>>> if you have an incoming stream of row data, you'll want > to > > > > append > > > > > > in > > > > > > >>>>>>> predictable order to match the order of the other > arrays. Am > > > I > > > > > > >>> missing > > > > > > >>>>>>> something? > > > > > > >>>>>>> > > > > > > >>>>>>> And, IIUC, the cost of using ListView with out-of-order > > > values > > > > > over > > > > > > >>>>>>> ListArray is you lose memory locality; the values of > element > > > 2 > > > > > are > > > > > > >>> no > > > > > > >>>>>>> longer adjacent to the values of element 1. What do you > think > > > > > about > > > > > > >>>> that > > > > > > >>>>>>> tradeoff? > > > > > > >>>>>>> > > > > > > >>>>>>> I don't mean to be difficult about this. I'm excited for > both > > > > the > > > > > > >>> REE > > > > > > >>>> and > > > > > > >>>>>>> StringView arrays, but this one I'm not so sure about > yet. I > > > > > > suppose > > > > > > >>>>>> what I > > > > > > >>>>>>> am trying to ask is, if we added this, do we think many > Arrow > > > > and > > > > > > >>> query > > > > > > >>>>>>> engine implementations (for example, DataFusion) will be > > > eager > > > > to > > > > > > >>> add > > > > > > >>>>>> full > > > > > > >>>>>>> support for the type, including compute kernels? Or are > they > > > > > likely > > > > > > >>> to > > > > > > >>>>>> just > > > > > > >>>>>>> convert this type to ListArray at import boundaries? > > > > > > >>>>>>> > > > > > > >>>>>>> Because if it turns out to be the latter, then we might > as > > > well > > > > > ask > > > > > > >>>> Velox > > > > > > >>>>>>> to export this type as ListArray and save the rest of the > > > > > ecosystem > > > > > > >>>> some > > > > > > >>>>>>> work. > > > > > > >>>>>>> > > > > > > >>>>>>> Best, > > > > > > >>>>>>> > > > > > > >>>>>>> Will Jones > > > > > > >>>>>>> > > > > > > >>>>>>> On Thu, May 11, 2023 at 12:32 PM Felipe Oliveira > Carvalho < > > > > > > >>>>>>> felipe...@gmail.com<mailto:felipe...@gmail.com>> wrote: > > > > > > >>>>>>> > > > > > > >>>>>>>> Initial reason for ListView arrays in Arrow is zero-copy > > > > > > >>> compatibility > > > > > > >>>>>> with > > > > > > >>>>>>>> Velox which uses this format. > > > > > > >>>>>>>> > > > > > > >>>>>>>> Velox kernels benefit from being able to append data to > the > > > > > array > > > > > > >>> from > > > > > > >>>>>>>> different threads without care for strict ordering. > Only the > > > > > > >>> offsets > > > > > > >>>>>> array > > > > > > >>>>>>>> has to be written according to logical order but that is > > > > > > >>> potentially a > > > > > > >>>>>> much > > > > > > >>>>>>>> smaller buffer than the values buffer. > > > > > > >>>>>>>> > > > > > > >>>>>>>> Acero kernels could take advantage of that in the > future. > > > > > > >>>>>>>> > > > > > > >>>>>>>> In implementing ListViewArray/Type I was able to reuse > some > > > > C++ > > > > > > >>>>>> templates > > > > > > >>>>>>>> used for ListArray which can reduce some of the burden > on > > > > kernel > > > > > > >>>>>>>> implementations that aim to work with all the types. > > > > > > >>>>>>>> > > > > > > >>>>>>>> I’m can fix Acero kernels for working with ListView. > This is > > > > > > >>> similar > > > > > > >>>> to > > > > > > >>>>>> the > > > > > > >>>>>>>> work I’ve doing in kernels dealing with run-end encoded > > > > arrays. > > > > > > >>>>>>>> > > > > > > >>>>>>>> — > > > > > > >>>>>>>> Felipe > > > > > > >>>>>>>> > > > > > > >>>>>>>> > > > > > > >>>>>>>> On Wed, 26 Apr 2023 at 01:03 Will Jones < > > > > > will.jones...@gmail.com > > > > > > >>>>>> <mailto:will.jones...@gmail.com>> wrote: > > > > > > >>>>>>>> > > > > > > >>>>>>>>> I suppose one common use case is materializing list > columns > > > > > after > > > > > > >>>> some > > > > > > >>>>>>>>> expanding operation like a join or unnest. That's a > case > > > > where > > > > > I > > > > > > >>>> could > > > > > > >>>>>>>>> imagine a lot of repetition of values. Haven't yet > thought > > > of > > > > > > >>> common > > > > > > >>>>>>>> cases > > > > > > >>>>>>>>> where there is overlap but not full duplication, but am > > > eager > > > > > to > > > > > > >>> hear > > > > > > >>>>>>>> any. > > > > > > >>>>>>>>> The dictionary encoding point Raphael makes is > interesting, > > > > > > >>>> especially > > > > > > >>>>>>>>> given the existence of LargeList and FixedSizeList. For > > > many > > > > > > >>>>>> operations, > > > > > > >>>>>>>> it > > > > > > >>>>>>>>> might make more sense to just compose those existing > types. > > > > > > >>>>>>>>> > > > > > > >>>>>>>>> IIUC the operations that would be unique to the > ArrayView > > > are > > > > > > ones > > > > > > >>>>>>>> altering > > > > > > >>>>>>>>> the shape. One could truncate each array to a certain > > > length > > > > > > >>> cheaply > > > > > > >>>>>>>> simply > > > > > > >>>>>>>>> by replacing the sizes buffer. Or perhaps there are > > > > interesting > > > > > > >>>>>>>> operations > > > > > > >>>>>>>>> on tensors that would benefit. > > > > > > >>>>>>>>> > > > > > > >>>>>>>>> On Tue, Apr 25, 2023 at 7:47 PM Raphael Taylor-Davies > > > > > > >>>>>>>>> <r.taylordav...@googlemail.com.invalid> wrote: > > > > > > >>>>>>>>> > > > > > > >>>>>>>>>> Unless I am missing something, I think the selection > > > > use-case > > > > > > >>> could > > > > > > >>>> be > > > > > > >>>>>>>>>> equally well served by a dictionary-encoded > > > > > > BinarArray/ListArray, > > > > > > >>>> and > > > > > > >>>>>>>>> would > > > > > > >>>>>>>>>> have the benefit of not requiring any modifications > to the > > > > > > >>> existing > > > > > > >>>>>>>>> format > > > > > > >>>>>>>>>> or kernels. > > > > > > >>>>>>>>>> > > > > > > >>>>>>>>>> The major additional flexibility of the proposed > encoding > > > > > would > > > > > > >>> be > > > > > > >>>>>>>>>> permitting disjoint or overlapping ranges, are these > > > common > > > > > > >>> enough > > > > > > >>>> in > > > > > > >>>>>>>>>> practice to represent a meaningful bottleneck? > > > > > > >>>>>>>>>> > > > > > > >>>>>>>>>> > > > > > > >>>>>>>>>> On 26 April 2023 01:40:14 BST, David Li < > > > > lidav...@apache.org > > > > > > >>>> <mailto: > > > > > > >>>>>> lidav...@apache.org>> wrote: > > > > > > >>>>>>>>>>> Is there a need for a 64-bit offsets version the > same way > > > > we > > > > > > >>> have > > > > > > >>>>>> List > > > > > > >>>>>>>>>> and LargeList? > > > > > > >>>>>>>>>>> And just to be clear, the difference with List is > that > > > the > > > > > > lists > > > > > > >>>>>> don't > > > > > > >>>>>>>>>> have to be stored in their logical order (or in other > > > words, > > > > > > >>> offsets > > > > > > >>>>>> do > > > > > > >>>>>>>>> not > > > > > > >>>>>>>>>> have to be nondecreasing and so we also need sizes)? > > > > > > >>>>>>>>>>> On Wed, Apr 26, 2023, at 09:37, Weston Pace wrote: > > > > > > >>>>>>>>>>>> For context, there was some discussion on this back > in > > > > [1]. > > > > > At > > > > > > >>>> that > > > > > > >>>>>>>>>> time > > > > > > >>>>>>>>>>>> this was called "sequence view" but I do not like > that > > > > name. > > > > > > >>>>>>>> However, > > > > > > >>>>>>>>>>>> array-view array is a little confusing. Given this > is > > > > > similar > > > > > > >>> to > > > > > > >>>>>>>> list > > > > > > >>>>>>>>>> can > > > > > > >>>>>>>>>>>> we go with list-view array? > > > > > > >>>>>>>>>>>> > > > > > > >>>>>>>>>>>>> Thanks for the introduction. I'd be interested to > hear > > > > > about > > > > > > >>> the > > > > > > >>>>>>>>>>>>> applications Velox has found for these vectors, > and in > > > > what > > > > > > >>>>>>>>> situations > > > > > > >>>>>>>>>>>> they > > > > > > >>>>>>>>>>>>> are useful. This could be contrasted with the > current > > > > > > >>> ListArray > > > > > > >>>>>>>>>>>>> implementations. > > > > > > >>>>>>>>>>>> I believe one significant benefit is that take (and > by > > > > > proxy, > > > > > > >>>>>>>> filter) > > > > > > >>>>>>>>>> and > > > > > > >>>>>>>>>>>> sort are O(# of items) with the proposed format and > O(# > > > of > > > > > > >>> bytes) > > > > > > >>>>>>>> with > > > > > > >>>>>>>>>> the > > > > > > >>>>>>>>>>>> current format. Jorge did some profiling to this > effect > > > in > > > > > > [1]. > > > > > > >>>>>>>>>>>> > > > > > > >>>>>>>>>>>> [1] > > > > > > >>>>>>>> > > > > > https://lists.apache.org/thread/49qzofswg1r5z7zh39pjvd1m2ggz2kdq< > > > > > > >>>>>> > > > > https://lists.apache.org/thread/49qzofswg1r5z7zh39pjvd1m2ggz2kdq> > > > > > > >>>>>>>>>>>> On Tue, Apr 25, 2023 at 3:13 PM Will Jones < > > > > > > >>>> will.jones...@gmail.com > > > > > > >>>>>> <mailto:will.jones...@gmail.com> > > > > > > >>>>>>>>>> wrote: > > > > > > >>>>>>>>>>>>> Hi Felipe, > > > > > > >>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>> Thanks for the introduction. I'd be interested to > hear > > > > > about > > > > > > >>> the > > > > > > >>>>>>>>>>>>> applications Velox has found for these vectors, > and in > > > > what > > > > > > >>>>>>>>> situations > > > > > > >>>>>>>>>> they > > > > > > >>>>>>>>>>>>> are useful. This could be contrasted with the > current > > > > > > >>> ListArray > > > > > > >>>>>>>>>>>>> implementations. > > > > > > >>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>> IIUC it would be fairly cheap to transform a > ListArray > > > to > > > > > an > > > > > > >>>>>>>>>> ArrayView, but > > > > > > >>>>>>>>>>>>> expensive to go the other way. > > > > > > >>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>> Best, > > > > > > >>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>> Will Jones > > > > > > >>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>> On Tue, Apr 25, 2023 at 3:00 PM Felipe Oliveira > > > Carvalho > > > > < > > > > > > >>>>>>>>>>>>> felipe...@gmail.com<mailto:felipe...@gmail.com>> > > > wrote: > > > > > > >>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>>> Hi folks, > > > > > > >>>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>>> I would like to start a public discussion on the > > > > inclusion > > > > > > >>> of a > > > > > > >>>>>>>> new > > > > > > >>>>>>>>>> array > > > > > > >>>>>>>>>>>>>> format to Arrow — array-view array. The name is > also > > > up > > > > > for > > > > > > >>>>>>>> debate. > > > > > > >>>>>>>>>>>>>> This format is inspired by Velox's ArrayVector > format > > > > [1]. > > > > > > >>>>>>>>> Logically, > > > > > > >>>>>>>>>>>>> this > > > > > > >>>>>>>>>>>>>> array represents an array of arrays. Each element > is > > > an > > > > > > >>>>>>>> array-view > > > > > > >>>>>>>>>>>>> (offset > > > > > > >>>>>>>>>>>>>> and size pair) that points to a range within a > nested > > > > > > >>> "values" > > > > > > >>>>>>>>> array > > > > > > >>>>>>>>>>>>>> (called "elements" in Velox docs). The nested > array > > > can > > > > be > > > > > > of > > > > > > >>>> any > > > > > > >>>>>>>>>> type, > > > > > > >>>>>>>>>>>>>> which makes this format very flexible and > powerful. > > > > > > >>>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>>> [image: ../_images/array-vector.png] > > > > > > >>>>>>>>>>>>>> < > > > > > > >>>>>>>>> > > > > > > >>> > > > https://facebookincubator.github.io/velox/_images/array-vector.png > > > > < > > > > > > >>>>>> > > > > > https://facebookincubator.github.io/velox/_images/array-vector.png > > > > > > >> > > > > > > >>>>>>>>>>>>>> I'm currently working on a C++ implementation and > plan > > > > to > > > > > > >>> work > > > > > > >>>>>>>> on a > > > > > > >>>>>>>>>> Go > > > > > > >>>>>>>>>>>>>> implementation to fulfill the two-implementations > > > > > > requirement > > > > > > >>>> for > > > > > > >>>>>>>>>> format > > > > > > >>>>>>>>>>>>>> changes. > > > > > > >>>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>>> The draft design: > > > > > > >>>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>>> - 3 buffers: [validity_bitmap, int32 offsets > buffer, > > > > int32 > > > > > > >>> sizes > > > > > > >>>>>>>>>> buffer] > > > > > > >>>>>>>>>>>>>> - 1 child array: "values" as an array of the type > > > > > parameter > > > > > > >>>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>>> validity_bitmap is used to differentiate between > empty > > > > > array > > > > > > >>>>>>>> views > > > > > > >>>>>>>>>>>>>> (sizes[i] == 0) and NULL array views > > > (validity_bitmap[i] > > > > > == > > > > > > >>> 0). > > > > > > >>>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>>> When the validity_bitmap[i] is 0, both sizes and > > > offsets > > > > > are > > > > > > >>>>>>>>>> undefined > > > > > > >>>>>>>>>>>>> (as > > > > > > >>>>>>>>>>>>>> usual), and when sizes[i] == 0, offsets[i] is > > > > undefined. 0 > > > > > > is > > > > > > >>>>>>>>>> recommended > > > > > > >>>>>>>>>>>>>> if setting a value is not an issue to the system > > > > producing > > > > > > >>> the > > > > > > >>>>>>>>>> arrays. > > > > > > >>>>>>>>>>>>>> offsets buffer is not required to be ordered and > views > > > > > don't > > > > > > >>>> have > > > > > > >>>>>>>>> to > > > > > > >>>>>>>>>> be > > > > > > >>>>>>>>>>>>>> disjoint. > > > > > > >>>>>>>>>>>>>> > > > > > > >>>>>>>>>>>>>> [1] > > > > > > >>>>>>>>>>>>>> > > > > > > >>>>>>>> > > > > > > >>>>>> > > > > > > >>>> > > > > > > >>> > > > > > > > > > > > > > > > > > > > https://facebookincubator.github.io/velox/develop/vectors.html#arrayvector > > > > > > >>>>>> < > > > > > > >>>>>> > > > > > > >>>> > > > > > > >>> > > > > > > > > > > > > > > > > > > > https://facebookincubator.github.io/velox/develop/vectors.html#arrayvector > > > > > > >>>>>>> > > > > > > >>>>>>>>>>>>>> Thanks, > > > > > > >>>>>>>>>>>>>> Felipe O. Carvalho > > > > > > >>>>>>>>>>>>>> > > > > > > >>>>>> > > > > > > >>>> > > > > > > >>>> > > > > > > >>> > > > > > > >> > > > > > > > > > > > > > > > > > > > > > > > > > >
