Dear all, I have added the draft for the fourth part of the document. This part contains discussion of more algorithms, some of which are already in progress.
Please pay special attention to Section 4.2.1, as it contains a general discussion about the representation of integer vectors. Please take a look, and give your valuable feedback: https://docs.google.com/document/d/17nqHWS7gs0vARfeDAcUEbhKMOYHnCtA46TOY_Nls69s/edit?usp=sharing Thanks a lot for your attention. Best, Liya Fan On Sat, Oct 5, 2019 at 2:59 PM fan_li_ya <fan_li...@aliyun.com> wrote: > Hi Micah and Praveen, > > Thanks a lot for your valuable feedback. > > My thoughts on the problems: > > 1. About audiance of the algorithms: > > I think the algorithms should be better termed "micro-algorithms". They > are termed "micro" in the sense that they do not directly compose a query > engine, because they only provide primitive functionalities (e.g. vector > sort). > Instead, they can be used as building blocks for query engines. The major > benefit of the micro-algorithms is their generality: they can be used in > wide ranges of common scenarios. They can be used in more than one query > engine. In addition, there are other common scenarios, like vector data > compression/decompression (e.g. dictionary encoding and RLE encoding, as we > have already supported/discussed), IPC communication, data analysis, data > mining, etc. > > 2. About performance improvments: > > Code generation and template types are powerful tools. In addition, JIT is > also a powerful tool, as it can inline megamorphic virtual functions for > many scenarios, if the algorithm is implemented appropriately. > IMO, code generation is applicable to almost all scenarios to achieve good > performance, if we are willing to pay the price of code readability. > I will try to detail the principles for choosing these tools for > performance improvements later. > > Best, > Liya Fan > > ------------------------------------------------------------------ > 发件人：Praveen Kumar <prav...@dremio.com> > 发送时间：2019年10月4日(星期五) 19:20 > 收件人：Micah Kornfield <emkornfi...@gmail.com> > 抄 送：Fan Liya <liya.fa...@gmail.com>; dev <dev@arrow.apache.org> > 主 题：Re: [DISCUSS][Java] Design of the algorithm module > > Hi Micah, > > I agree with 1., i think as an end user, what they would really want is a > query/data processing engine. I am not sure how easy/relevant the > algorithms will be in the absence of the engine. For e.g. most of these > operators would need to pipelined, handle memory, distribution etc. So > bundling this along with engine makes a lot more sense, the interfaces > required might be a bit different too for that. > > Thx. > > > > On Thu, Oct 3, 2019 at 10:27 AM Micah Kornfield <emkornfi...@gmail.com> > wrote: > > > Hi Liya Fan, > > Thanks again for writing this up. I think it provides a road-map for > > > intended features. I commented on the document but I wanted to raise a few > > high-level concerns here as well to get more feedback from the community. > > > > > 1. It isn't clear to me who the users will of this will be. My perception > > is that in the Java ecosystem there aren't use-cases for the algorithms > > > outside of specific compute engines. I'm not super involved in open-source > > > Java these days so I would love to hear others opinions. For instance, I'm > > not sure if Dremio would switch to using these algorithms instead of the > > ones they've already open-sourced [1] and Apache Spark I believe is only > > using Arrow for interfacing with Python (they similarly have there own > > > compute pipeline). I think you mentioned in the past that these are being > > used internally on an engine that your company is working on, but if that > > > is the only consumer it makes me wonder if the algorithm development might > > be better served as part of that engine. > > > > 2. If we do move forward with this, we also need a plan for how to > > optimize the algorithms to avoid virtual calls. There are two high-level > > approaches template-based and (byte)code generation based. Both aren't > > > applicable in all situations but it would be good to come consensus on when > > (and when not to) use each. > > > > Thanks, > > Micah > > > > [1] > > > > > https://github.com/dremio/dremio-oss/tree/master/sabot/kernel/src/main/java/com/dremio/sabot/op/sort/external > > > > On Tue, Sep 24, 2019 at 6:48 AM Fan Liya <liya.fa...@gmail.com> wrote: > > > > > Hi Micah, > > > > > > Thanks for your effort and precious time. > > > Looking forward to receiving more valuable feedback from you. > > > > > > Best, > > > Liya Fan > > > > > > On Tue, Sep 24, 2019 at 2:12 PM Micah Kornfield <emkornfi...@gmail.com > > > > > wrote: > > > > > >> Hi Liya Fan, > > >> I started reviewing but haven't gotten all the way through it. I will > > try > > >> to leave more comments over the next few days. > > >> > > >> Thanks again for the write-up I think it will help frame a productive > > >> conversation. > > >> > > >> -Micah > > >> > > >> On Tue, Sep 17, 2019 at 1:47 AM Fan Liya <liya.fa...@gmail.com > > wrote: > > >> > > >>> Hi Micah, > > >>> > > >>> Thanks for your kind reminder. Comments are enabled now. > > >>> > > >>> Best, > > >>> Liya Fan > > >>> > > >>> On Tue, Sep 17, 2019 at 12:45 PM Micah Kornfield < > > emkornfi...@gmail.com> > > >>> wrote: > > >>> > > >>>> Hi Liya Fan, > > > >>>> Thank you for this writeup, it doesn't look like comments are enabled > > on > > >>>> the document. Could you allow for them? > > >>>> > > >>>> Thanks, > > >>>> Micah > > >>>> > > >>>> On Sat, Sep 14, 2019 at 6:57 AM Fan Liya <liya.fa...@gmail.com> > > wrote: > > >>>> > > >>>> > Dear all, > > >>>> > > > > >>>> > We have prepared a document for discussing the requirements, design > > >>>> and > > >>>> > implementation issues for the algorithm module of Java: > > >>>> > > > >>>> > > > >>>> > > > >>>> > > > https://docs.google.com/document/d/17nqHWS7gs0vARfeDAcUEbhKMOYHnCtA46TOY_Nls69s/edit?usp=sharing > > >>>> > > > >>>> > So far, we have finished the initial draft for sort, search and > > >>>> dictionary > > > >>>> > encoding algorithms. Discussions for more algorithms may be added in > > >>>> the > > >>>> > future. This document will keep evolving to reflect the latest > > >>>> discussion > > >>>> > results in the community and the latest code changes. > > >>>> > > > >>>> > Please give your valuable feedback. > > >>>> > > > >>>> > Best, > > >>>> > Liya Fan > > >>>> > > > >>>> > > >>> > > > > >
