hive-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From <Andres.Qui...@parc.com>
Subject RE: Request for feedback on work intent for non-equijoin support
Date Thu, 02 Apr 2015 13:07:09 GMT
This is a great pointer, Szehon and Brock, thank you. I will catch up with the material on
theta joins and circle back.

Andrés

-----Original Message-----
From: Brock Noland [mailto:brock@apache.org] 
Sent: Thursday, April 02, 2015 1:31 AM
To: dev@hive.apache.org
Subject: Re: Request for feedback on work intent for non-equijoin support

Nice, it'd be great if someone finally implemented this :)

On Wed, Apr 1, 2015 at 10:10 PM, Szehon Ho <szehon@cloudera.com> wrote:
> From Hive side, there has been some thought on the subject here:
> https://cwiki.apache.org/confluence/display/Hive/Theta+Join, it has 
> some ideas but nobody has gotten around to giving it a try.  It might 
> be of interest.
>
> Thanks
> Szehon
>
>
> On Wed, Apr 1, 2015 at 10:05 PM, Lefty Leverenz 
> <leftyleverenz@gmail.com>
> wrote:
>
>> D'oh!  Thanks Chao.
>>
>> -- Lefty
>>
>> On Thu, Apr 2, 2015 at 12:59 AM, Chao Sun <chao@cloudera.com> wrote:
>>
>> > Hey Lefty,
>> >
>> > You need to use the ftp protocol, not http.
>> > After clicking the link, you'll need to remove "http://" from the
>> address
>> > bar.
>> >
>> > Best,
>> > Chao
>> >
>> > On Wed, Apr 1, 2015 at 9:41 PM, Lefty Leverenz 
>> > <leftyleverenz@gmail.com>
>> > wrote:
>> >
>> > > Andrés, I followed that link and got the dread 404 Not Found:
>> > >
>> > > "The requested URI /pub/torres/Hiperfuse/extended_hiperfuse.pdf 
>> > > was not found on this server."
>> > >
>> > > -- Lefty
>> > >
>> > > On Wed, Apr 1, 2015 at 7:23 PM, <Andres.Quiroz@parc.com> wrote:
>> > >
>> > > > Dear Lefty,
>> > > >
>> > > > Thank you very much for pointing that out and for your initial
>> > pointers.
>> > > > Here is the missing link:
>> > > >
>> > > > ftp.parc.com/pub/torres/Hiperfuse/extended_hiperfuse.pdf
>> > > >
>> > > > Regards,
>> > > >
>> > > > Andrés
>> > > >
>> > > > -----Original Message-----
>> > > > From: Lefty Leverenz [mailto:leftyleverenz@gmail.com]
>> > > > Sent: Wednesday, April 01, 2015 12:48 AM
>> > > > To: dev@hive.apache.org
>> > > > Subject: Re: Request for feedback on work intent for 
>> > > > non-equijoin
>> > support
>> > > >
>> > > > Hello Andres, the link to your paper is missing:
>> > > >
>> > > > In our preliminary work, which you can find here (pointer to 
>> > > > the
>> paper)
>> > > ...
>> > > >
>> > > >
>> > > > You can find general information about contributing to Hive in 
>> > > > the
>> > > > wiki:  Resources
>> > > > for Contributors
>> > > > <
>> > > >
>> > >
>> >
>> https://cwiki.apache.org/confluence/display/Hive/Home#Home-Resourcesf
>> orContributors
>> > > > >
>> > > > , How to Contribute
>> > > > <https://cwiki.apache.org/confluence/display/Hive/HowToContribute>.
>> > > >
>> > > > -- Lefty
>> > > >
>> > > > On Tue, Mar 31, 2015 at 10:42 PM, <Andres.Quiroz@parc.com> wrote:
>> > > >
>> > > > >  Dear Hive development community members,
>> > > > >
>> > > > >
>> > > > >
>> > > > > I am interested in learning more about the current support 
>> > > > > for non-equijoins in Hive and/or other Hadoop SQL engines, 
>> > > > > and in
>> getting
>> > > > > feedback about community interest in more extensive support 
>> > > > > for
>> such
>> > a
>> > > > > feature. I intend to work on this challenge, assuming people

>> > > > > find
>> it
>> > > > > compelling, and I intend to contribute results to the community.
>> > Where
>> > > > > possible, it would be great to receive feedback and engage in

>> > > > > collaborations along the way (for a bit more context, see the

>> > > > > postscript of this message).
>> > > > >
>> > > > >
>> > > > >
>> > > > > My initial goal is to support query conditions such as the
>> following:
>> > > > >
>> > > > >
>> > > > >
>> > > > > A.x < B.y
>> > > > >
>> > > > > A.x in_range [B.y, B.z]
>> > > > >
>> > > > > distance(A.x, B.y) < D
>> > > > >
>> > > > >
>> > > > >
>> > > > > where A and B are distinct tables/files. It is my 
>> > > > > understanding
>> that
>> > > > > current support for performing non-equijoins like those above

>> > > > > is
>> > quite
>> > > > > limited, and where some forms are supported (like in 
>> > > > > Cloudera's Impala), this support is based on doing a 
>> > > > > potentially expensive
>> cross
>> > > > product join.
>> > > > > Depending on the data types involved, I believe that joins 
>> > > > > with
>> these
>> > > > > conditions can be made to be tractable (at least on the 
>> > > > > average)
>> with
>> > > > > join algorithms that exploit properties of the data types, 
>> > > > > possibly with some pre-scanning of the data.
>> > > > >
>> > > > >
>> > > > >
>> > > > > I am asking for feedback on the interest & need in the 
>> > > > > community
>> for
>> > > > > this work, as well as any pointers to similar work. In 
>> > > > > particular,
>> I
>> > > > > would appreciate any answers people could give on the 
>> > > > > following
>> > > > questions:
>> > > > >
>> > > > >
>> > > > >
>> > > > > - Is my understanding of the state of the art in Hive and 
>> > > > > similar tools accurate? Are there groups currently working on

>> > > > > similar or related issues, or tools that already accomplish 
>> > > > > some or all of
>> what
>> > I
>> > > > have proposed?
>> > > > >
>> > > > > - Is there significant value to the community in the support

>> > > > > of
>> such
>> > a
>> > > > > feature? In other words, are the manual workarounds necessary
>> because
>> > > > > of the absence of non-equijoins such as these enough of a 
>> > > > > pain to justify the work I propose?
>> > > > >
>> > > > > - Being aware that the potential pre-scanning adds to the 
>> > > > > cost of
>> the
>> > > > > join, and that data could still blow-up in the worst case, am

>> > > > > I missing any other important considerations and tradeoffs 
>> > > > > for this
>> > > > problem?
>> > > > >
>> > > > > - What would be a good avenue to contribute this feature to 
>> > > > > the community (e.g. as a standalone tool on top of Hadoop, or

>> > > > > as a Hive extension or plugin)?
>> > > > >
>> > > > > - What is the best way to get started in working with the
>> community?
>> > > > >
>> > > > >
>> > > > >
>> > > > > Thanks for your attention and any info you can provide!
>> > > > >
>> > > > >
>> > > > >
>> > > > > Andres Quiroz
>> > > > >
>> > > > >
>> > > > >
>> > > > > P.S. If you are interested in some context, and why/how I am
>> > proposing
>> > > > > to do this work, please read on.
>> > > > >
>> > > > >
>> > > > >
>> > > > > I am part of a small project team at PARC working on the 
>> > > > > general problems of data integration and automated ETL. We 
>> > > > > have proposed a tool called HiperFuse that is designed to 
>> > > > > accept declarative, high-level queries in order to produce 
>> > > > > joined (fused) data sets
>> from
>> > > > > multiple heterogeneous raw data sources. In our preliminary 
>> > > > > work, which you can find here (pointer to the paper), we 
>> > > > > designed the architecture of the tool and obtained some 
>> > > > > results separately on
>> the
>> > > > > problems of automated data cleansing, data type inference, 
>> > > > > and
>> query
>> > > > > planning. One of the planned prototype implementations of 
>> > > > > HiperFuse relies on Hadoop MR, and because the declarative 
>> > > > > language we
>> proposed
>> > > > > was closely related to SQL, we thought that we could exploit

>> > > > > the existing work in Hive and/or other open-source tools for

>> > > > > handling
>> the
>> > > > > SQL part and layer our work on top of that. For example, the

>> > > > > query given in the paper could easily be expressed in 
>> > > > > SQL-like form with
>> a
>> > > > > non-equijoin
>> > > > > condition:
>> > > > >
>> > > > >
>> > > > >
>> > > > > SELECT web_access_log.ip, census.income
>> > > > >
>> > > > > FROM web_access_log, ip2zip, census
>> > > > >
>> > > > > WHERE web_access_log.ip in_range [ip2zip.ip_low, 
>> > > > > ip2zip.ip_high]
>> > > > >
>> > > > > AND ip2zip.zip = census.zip
>> > > > >
>> > > > >
>> > > > >
>> > > > > As you can see, the first impasse that we hit in order to 
>> > > > > bring the elements together to solve this query end-to-end 
>> > > > > was the
>> realization
>> > > > > and performance of the non-equality join in the query. The 
>> > > > > intent
>> now
>> > > > > is to tackle this problem in a general sense and provide a 
>> > > > > solution for a wide range of queries.
>> > > > >
>> > > > >
>> > > > >
>> > > > > The work I propose to do would be based on three main 
>> > > > > components within
>> > > > > HiperFuse:
>> > > > >
>> > > > >
>> > > > >
>> > > > > - Enhancements to the extensible data type framework in 
>> > > > > HiperFuse
>> > that
>> > > > > would categorize data types based on the properties needed to
>> support
>> > > > > the join algorithms, in order to write join-ready 
>> > > > > domain-specific
>> > data
>> > > > > type libraries.
>> > > > >
>> > > > > - The join algorithms themselves, based on Hive or directly 
>> > > > > on
>> Hadoop
>> > > MR.
>> > > > >
>> > > > > - A query planner, which would determine the right algorithm

>> > > > > to
>> apply
>> > > > > and automatically schedule any necessary pre-scanning of the
data.
>> > > > >
>> > > > >
>> > > > >
>> > > >
>> > >
>> >
>> >
>> >
>> > --
>> > Best,
>> > Chao
>> >
>>
Mime
View raw message