[jira] [Commented] (IMPALA-10325) Parquet scan should use min/max statistics to skip pages based on equi-join predicate

["ASF subversion and git services (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/IMPALA-10325?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17287464#comment-17287464 ] 

ASF subversion and git services commented on IMPALA-10325:
----------------------------------------------------------

Commit ebb2e0663988d4fb597aeecb4defebbda1669f12 in impala's branch refs/heads/master from Qifan Chen
[ https://gitbox.apache.org/repos/asf?p=impala.git;h=ebb2e06 ]

IMPALA-10325: Parquet scan should use min/max statistics to skip pages based on equi-join predicate

This patch adds a new class of predicates called overlap predicates
to aid in the acceptance or rejection of a row group, a page, or a
row in a Parquet table, utilizing the minimal and the maximal values
gathered from an equi hash join and the Parquet column index stats.
When a row group or page is rejected, all contained rows within are
rejected all together.

For example in the following query, the min and max in the overlap
predicate are computed from the join column from table 'b', and
are compared against the min/max of each row group or page at the
scan node for 'a'.

  select straight_join count(*)
  from lineitem a join [SHUFFLE] lineitem b
  where a.l_shipdate = b.l_receiptdate
  and b.l_commitdate = "1992-01-31";

An overlap predicate associated with the column type B in hash
table and scan column type A will be formed when both A and B are
of or can be converted to as:
  1. booleans;
  2. integers (tinyint, smallint, int, or bigint);
  3. approximate numeric (float or double);
  4. decimals with the same precision and scale;
  5. strings;
  6. date; or
  7. timestamps.

The overlap predicate is implemented as a min/max filter and can be
observed in the explain output of a query.

A new query option 'minmax_filter_threshold' is provided to control
the new feature. Setting it to 0.0 disables the feature. Setting it
to a value > 0.0 but less than 1.0 provides a threshold. An overlap
predicate will be evaluated against a row group and possibly the
containing pages/rows, as long as its overlap ratio is less than the
threshold. The overlap ratio is the common area of the row group
and the filter, divided by the area of the row group.

A second query option, minmax_filtering_level, is provided to
specify the filtering scope:
  1. ROW_GROUP: the overlap is only tested for row groups;
  2. PAGE: the overlap is tested for both row groups and pages;
  3. ROW: the overlap is for row groups, pages and rows.

Two new run-time profile counters are added to report the number of
row groups or pages filtered out via the overlap predicates
respectively:
  1. NumRuntimeFilteredRowGroups
  2. NumRuntimeFilteredPages

Two new column "Min value" and "Max value" are added to the
"Filter routing table" and "Final filter table" in profile to
display the min and the max values for a min/max filter.

Testing:
1. Unit tested on various column types with TPCH and TPCDS tables.
   Benefits were significant when the join column on the outer table
   is sorted and there exist many row groups or pages no overlapping
   with the min/max filters;
2. Added following new tests:
    a) In overlap_min_max_filters.test to demonstrate the number of
       filtered out pages and row groups with the two new profile
       counters;
    b) In runtime-filter-propagation.test to demonstrate that the
       overlap predicates work with different column types;
3. Core testing;
4. Performance measurement: the overal improvement with 3TB scale
   TPCDS is at 1.45% with the filter threshold at 0.5 and filtering
   level at ROW_GROUP. Good improvement (over 10%) are seen with
   query 16, 25, 62, 83, 94 and 99, due to the join column
   ship_date_sk being strongly correlated to the partition column
   sold_date_sk.

To do in follow-up JIRAs:
1. Improve filtering efficiency;
2. Apply the overlap predicate on partition columns;
3. IR code-gen for various MinMaxFilter::EvalOverlap methods.
4. Address the current limitation that the "Min value" and
   "Max value" columns may be empty for LOCAL filters.

Change-Id: I379405ee75b14929df7d6b5d20dabc6f51375691
Reviewed-on: http://gerrit.cloudera.org:8080/16720
Reviewed-by: Impala Public Jenkins <im...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>


> Parquet scan should use min/max statistics to skip pages based on equi-join predicate
> -------------------------------------------------------------------------------------
>
>                 Key: IMPALA-10325
>                 URL: https://issues.apache.org/jira/browse/IMPALA-10325
>             Project: IMPALA
>          Issue Type: Bug
>          Components: Backend
>            Reporter: Qifan Chen
>            Assignee: Qifan Chen
>            Priority: Major
>
> Parquet stores min/max stats for pages which can be used to skip certain pages if they don't qualify an equi-join predicate. 
> The query below ends up scanning all rows for table a, which may not be needed if the min/max of b.ss_addr_sk can be detected and used during the scan of a. 
> {code:java}
> select a.ss_sold_time_sk from
> store_sales a join [SHUFFLE] store_sales b
> where a.ss_addr_sk = b.ss_addr_sk and
> b.ss_customer_sk < 10
> ;
> {code}



--
This message was sent by Atlassian Jira
(v8.3.4#803005)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-all-unsubscribe@impala.apache.org
For additional commands, e-mail: issues-all-help@impala.apache.org