> This implies that each canonical alternative layout would codify a > primary layout as its "fallback."
Yes, that was part of my proposal: > * A new layout, if it is semantically equivalent to another, is considered an alternative layout Or, to phrase it another way. If there is not a "fallback" then it is not an alternative layout. It's a brand new primary layout. I'd expect this to be quite rare. I can't really even hypothesize any examples. I think the only truly atomic layouts are fixed-width, list, and struct. > This seems reasonable but it opens > up some cans of worms, such as how two components communicating > through an Arrow interface would negotiate which layout is supported Most APIs that I'm aware of already do this. For example, pyarrow.parquet.read_table has a "read_dictionary" property that can be used to control whether or not a column is returned with the dictionary encoding. There is no way (that I'm aware of) to get a column in REE encoding today without explicitly requesting it. In fact, this could be as simple as a boolean "use_advanced_features" flag although I would discourage something so simplistic. The point is that arrow-compatible software should, by default, emit types that are supported by all arrow implementations. Of course, there is no way to enforce this, it's just a guideline / strong recommendation on how software should behave if it wants to state "arrow compatible" as a feature. On Tue, Jun 6, 2023 at 3:33 PM Ian Cook <ianmc...@apache.org> wrote: > Thanks Weston. That all sounds reasonable to me. > > > with the caveat that the primary layout must be emitted if the user > does not specifically request the alternative layout > > This implies that each canonical alternative layout would codify a > primary layout as its "fallback." This seems reasonable but it opens > up some cans of worms, such as how two components communicating > through an Arrow interface would negotiate which layout is supported. > I suppose such details should be discussed in a separate thread, but I > raise this here just to point out that it implies an expansion in the > scope of what Arrow interfaces can do. > > On Tue, Jun 6, 2023 at 6:17 PM Weston Pace <weston.p...@gmail.com> wrote: > > > > From Micah: > > > > > 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). > > > > I'm not sure I understand. Is the concern that an alternative layout is > > eventually > > used more and more by implementations until it is used more often than > the > > primary > > layouts? In that case I think that is ok and we can promote the > alternative > > to a primary layout. > > > > Or is the concern that some applications will only support the > alternative > > layouts and > > not the primary layout? In that case I would argue the application is > not > > "arrow compatible". > > I don't know that we prevent or enforce this today either. An author can > > always falsely > > claim they support Arrow even if they are using their own bespoke format. > > > > From Ian: > > > > > 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. > > > > I'd maybe take a slightly harsher stance. I don't think an application > > needs to > > support all types. For example, an Arrow-native string processing > library > > might > > not worry about the integer types. That would be fine. I think it would > > still > > be fair to call it an "arrow compatible string processing library". > > > > However, an application must support primary layouts in addition to > > alternative > > layouts. For example, a string processing library that expects all > strings > > to be > > delivered as a single buffer sequence of null-terminated strings would > not > > be "an > > arrow compatible string processing library" unless it also fully > supported > > the > > standard (lengths + data) variable-sized list layout for strings defined > at > > [1]. > > > > In other words: > > > > * Only receives and emits alternative layouts - not arrow compatible > > * Only receives and emits primary layouts - arrow compatible > > * Receives and emits both primary and alternative layouts - arrow > > compatible† > > > > † - with the caveat that the primary layout must be emitted if the user > > does not > > specifically request the alternative layout. > > > > [1] > > > https://arrow.apache.org/docs/format/Columnar.html#variable-size-list-layout > > > > On Tue, Jun 6, 2023 at 2:45 PM 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 > > > > > > > > >>>>>>>>>>>>>> > > > > > > > > >>>>>> > > > > > > > > >>>> > > > > > > > > >>>> > > > > > > > > >>> > > > > > > > > >> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
