On Wed, Jun 14, 2023 at 5:07 PM Raphael Taylor-Davies <r.taylordav...@googlemail.com.invalid> wrote:
> Even something relatively straightforward becomes a huge implementation > effort when multiplied by a large number of codebases, users and > datasets. Parquet is a great source of historical examples of the > challenges of incremental changes that don't meaningfully unlock new > use-cases. To take just one, Int96 was deprecated almost a decade ago, > in favour of some additional metadata over an existing physical layout, > and yet Int96 is still to the best of my knowledge used by Spark by > default. > > That's not to say that I think the arrow specification should ossify and > we should never change it, but I'm not hugely enthusiastic about adding > encodings that are only incremental improvements over existing encodings. > > I therefore wonder if there are some new use-cases I am missing that > would be unlocked by this change, and that wouldn't be supported by the > dictionary proposal? Perhaps you could elaborate here? The dict-encoded ListArray would add a memory indirection: the slot in the dictionary has to be resolved before the offset can be. With ListView, the CPU can access offset and size without waiting on that memory access. Both need two buffer accesses after the validity check, but ListView doesn't have that dependency. > Whilst I do agree > using dictionaries as proposed is perhaps a less elegant solution, I > don't see anything inherently wrong with it, and if it ain't broke we > really shouldn't be trying to fix it. > > Kind Regards, > > Raphael Taylor-Davies > > On 14 June 2023 17:52:52 BST, Felipe Oliveira Carvalho > <felipe...@gmail.com> wrote: > > General approach to alternative formats aside, in the specific case > of ListView, I think the implementation complexity is being > overestimated in these discussions. The C++ Arrow implementation > shares a lot of code between List and LargeList. And with some > tweaks, I'm able to share that common infrastructure for ListView as > well. [1] ListView is similar to list: it doesn't require offsets to > be sorted and adds an extra buffer containing sizes. For symmetry > with the List and LargeList types (FixedSizeList not included), I'm > going to propose we add a LargeListView. That is not part of the > draft implementation yet, but seems like an obvious thing to have > now that I implemented the `if_else` specialization. [2] David Li > asked about this above and I can confirm now that 64-bit version of > ListView (LargeListView) is in the plans. Trying to avoid > re-implementing some kernels is not a good goal to chase, IMO, > because kernels need tweaks to take advantage of the format. [1] > https://github.com/apache/arrow/pull/35345 [2] > https://github.com/felipecrv/arrow/commits/list_view_backup -- > Felipe On Wed, Jun 14, 2023 at 12:08 PM Weston Pace > <weston.p...@gmail.com> wrote: > > perhaps we could support this use-case as a canonical > extension type over dictionary encoded, variable-sized arrays > > I believe this suggestion is valid and could be used to solve > the if-else case. The algorithm, if I understand it, would be > roughly: ``` // Note: Simple pseudocode, vectorization left as > exercise for the reader auto indices_builder = ... auto > list_builder = ... indices_builder.resize(batch.length); Array > condition_mask = condition.EvaluateBatch(batch); for row_index > in selected_rows(condition_mask): indices_builder[row_index] = > list_builder.CurrentLength(); > list_builder.Append(if_expr.EvaluateRow(batch, row_index)) for > row_index in unselected_rows(condition_mask): > indices_builder[row_index] = list_builder.CurrentLength(); > list_builder.Append(else_expr.EvaluateRow(batch, row_index)) > return DictionaryArray(indices_builder.Finish(), > list_builder.Finish()) ``` I also agree this is a slightly > awkward use of dictionaries (e.g. the dictionary would have the > same size as the # of indices) and perhaps not the most > intuitive way to solve the problem. My gut reaction is simply > "an improved if/else kernel is not, alone, enough justification > for a new layout" and yet... I think we are seeing the start (I > hope) of a trend where Arrow is not just used "between systems" > (e.g. to shuttle data from one place to another, or between a > query engine and a visualization tool) but also "within systems" > (e.g. UDFs, bespoke file formats and temporary tables, between > workers in a distributed query engine). When arrow is used > "within systems" I think both the number of bespoke formats and > the significance of conversion cost increases. For example, it's > easy to say that Velox should convert at the boundary as data > leaves Velox. But what if Velox (or datafusion or ...) were to > define an interface for UDFs. Would we want to use Arrow there > (e.g. the C data interface is a good fit)? If so, wouldn't the > conversion cost be more significant? > > Also, I'm very lukewarm towards the concept of "alternative > layouts" suggested somewhere else in this thread. It does > not seem a good choice to complexify the Arrow format that > much. > > I think, in my opinion, this depends on how many of these > alternative layouts exist. If there are just a few, then I > agree, we should just adopt them as formal first-class layouts. > If there are many, then I think it will be too much complexity > in Arrow to have all the different choices. Or, we could say > there are many, but the alternatives don't belong in Arrow at > all. In that case I think it's the same question as the above > paragraph, "do we want Arrow to be used within systems? Or just > between systems?" On Wed, Jun 14, 2023 at 2:07 AM Antoine Pitrou > <anto...@python.org> wrote: > > I agree that ListView cannot be an extension type, given > that it features a new layout, and therefore cannot > reasonably be backed by an existing storage type (AFAICT). > Also, I'm very lukewarm towards the concept of "alternative > layouts" suggested somewhere else in this thread. It does > not seem a good choice to complexify the Arrow format that > much. Regards Antoine. Le 07/06/2023 à 00:21, Felipe > Oliveira Carvalho a écrit : > > +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 > > <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 > <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: <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 > <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 > > <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 > >
