impala-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Todd Lipcon <t...@cloudera.com>
Subject Re: Min/Max runtime filtering on Impala-Kudu
Date Tue, 28 Mar 2017 23:41:14 GMT
On Tue, Mar 28, 2017 at 4:39 PM, Sailesh Mukil <sailesh@cloudera.com> wrote:

> On Tue, Mar 28, 2017 at 3:33 AM, Lars Volker <lv@cloudera.com> wrote:
>
> > Thanks for sending this around, Sailesh.
> >
> > parquet-column-stats.h is somewhat tied to parquet statistics and will
> soon
> > need more parquet-specific fields (null_count and distinct_count). It
> will
> > also need extension to copy strings and handle there memory when tracking
> > min/max values for variable length data across row batches. I'm not sure
> > how these changes will affect its suitability for your purposes, but I
> > thought I'd give a quick heads up.
> >
> > Thanks, Lars. In that case, it looks like the right path to take is to
> implement a simpler version of this for this patch. Thanks for weighing in.
>
> On Mon, Mar 27, 2017 at 11:35 PM, Todd Lipcon <todd@cloudera.com> wrote:
> >
> > > Sounds reasonable to me as well.
> > >
> > > The only thing I'd add is that, if it's easy to design the code to be
> > > extended to pushing small 'IN (...)' predicate for low-cardinality
> > filters,
> > > that would be great. eg if the filter can start as an IN(...) and then
> if
> > > it exceeds 32K (or whatever arbitrary threshold), "collapse" it to the
> > > min/max range predicate?
> > >
> > > This should have a big advantage for partition pruning in
> low-cardinality
> > > joins against hash-partitioned tables.
> > >
> > > -Todd
> > >
> >
>
> Thanks, Todd. You're right, the IN predicate filters would be a great
> addition. We can add that as a follow on patch, just to keep this patch
> simple for now.
>

Sure, just wanted to suggest that whatever path's taken now, implementation
wise, is reasonably easy to extend to the IN() case without too much
backtracking.

-Todd


>
> >
> > >
> > > On Mon, Mar 27, 2017 at 2:29 PM, Matthew Jacobs <mj@cloudera.com>
> wrote:
> > >
> > > > Thanks for writing this up, Sailesh. It sounds reasonable.
> > > >
> > > > On Mon, Mar 27, 2017 at 2:24 PM, Sailesh Mukil <sailesh@cloudera.com
> >
> > > > wrote:
> > > > > On Mon, Mar 27, 2017 at 11:49 AM, Marcel Kornacker <
> > > marcel@cloudera.com>
> > > > > wrote:
> > > > >
> > > > >> On Mon, Mar 27, 2017 at 11:42 AM, Sailesh Mukil <
> > sailesh@cloudera.com
> > > >
> > > > >> wrote:
> > > > >> > I will be working on a patch to add min/max filter support
in
> > > Impala,
> > > > and
> > > > >> > as a first step, specifically target the KuduScanNode, since
the
> > > Kudu
> > > > >> > client is already able to accept a Min and a Max that it
would
> > > > internally
> > > > >> > use to filter during its scans. Below is a brief design
> proposal.
> > > > >> >
> > > > >> > *Goal:*
> > > > >> >
> > > > >> > To leverage runtime min/max filter support in Kudu for the
> > potential
> > > > >> speed
> > > > >> > up of queries over Kudu tables. Kudu does this by taking
a min
> > and a
> > > > max
> > > > >> > that Impala will provide and only return values in the range
> > Impala
> > > is
> > > > >> > interested in.
> > > > >> >
> > > > >> > *[min <= range we're interested in >= max]*
> > > > >> >
> > > > >> > *Proposal:*
> > > > >> >
> > > > >> >
> > > > >> >    - As a first step, plumb the runtime filter code from
> > > > >> > *exec/hdfs-scan-node-base.cc/h
> > > > >> >    <http://hdfs-scan-node-base.cc/h>* to *exec/scan-node.cc/h
> > > > >> >    <http://scan-node.cc/h>*, so that it can be applied
to
> > > > *KuduScanNode*
> > > > >> >    cleanly as well, since *KuduScanNode* and *HdfsScanNodeBase*
> > both
> > > > >> >    inherit from *ScanNode.*
> > > > >>
> > > > >> Quick comment: please make sure your solution also applies to
> > > > >> KuduScanNodeMt.
> > > > >>
> > > > >
> > > > > Thanks for the input, I'll make sure to do that.
> > > > >
> > > > >
> > > > >>
> > > > >> >    - Reuse the *ColumnStats* class (exec/parquet-column-stats.h)
> > or
> > > > >> >    implement a lighter weight version of it to process and
store
> > the
> > > > Min
> > > > >> and
> > > > >> >    the Max on the build side of the join.
> > > > >> >    - Once the Min and Max values are added to the existing
> runtime
> > > > filter
> > > > >> >    structures, as a first step, we will ignore the Min and
Max
> > > values
> > > > for
> > > > >> >    non-Kudu tables. Using them for non-Kudu tables can come
in
> as
> > a
> > > > >> following
> > > > >> >    patch(es).
> > > > >> >    - Similarly, the bloom filter will be ignored for Kudu
> tables,
> > > and
> > > > >> only
> > > > >> >    the Min and Max values will be used, since Kudu does
not
> accept
> > > > bloom
> > > > >> >    filters yet. (https://issues.apache.org/
> > jira/browse/IMPALA-3741)
> > > > >> >    - Applying the bloom filter on the Impala side of the
Kudu
> scan
> > > > (i.e.
> > > > >> in
> > > > >> >    KuduScanNode) is not in the scope of this patch.
> > > > >> >
> > > > >> >
> > > > >> > *Complications:*
> > > > >> >
> > > > >> >    - We have to make sure that finding the Min and Max values
on
> > the
> > > > >> build
> > > > >> >    side doesn't regress certain workloads, since the difference
> > > > between
> > > > >> >    generating a bloom filter and generating a Min and a
Max, is
> > > that a
> > > > >> bloom
> > > > >> >    filter can be type agnostic (we just take a raw hash
over the
> > > data)
> > > > >> whereas
> > > > >> >    a Min and a Max have to be type specific.
> > > > >>
> > > >
> > >
> > >
> > >
> > > --
> > > Todd Lipcon
> > > Software Engineer, Cloudera
> > >
> >
>



-- 
Todd Lipcon
Software Engineer, Cloudera

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message