HIVE-28484 SharedWorkOptimizer leaves residual unused operator tree that send DPP events to unknown operators

[ramesh0201]

What changes were proposed in this pull request?

Why are the changes needed?

Does this PR introduce any user-facing change?

Is the change a dependency upgrade?

How was this patch tested?

[deniskuzZ]

@ramesh0201, could you please add a test and update the PR description

[deniskuzZ]

hi @ngsg, would you be able to check this PR as well since you work on class refactor?

[ngsg]

@deniskuzZ , the changes seems reasonable, but we need a reproducing query to verify the patch. Let me see if I can write one.

[ramesh0201]

Thank you @deniskuzZ and @ngsg for the review and comments. This is a production query that ran into failure but we were not able to reproduce this in the upstream. This might be probably due to the missing column stats that lead to the operator tree and DPP events that were not able to be reproduced without the stats. Does it seem reasonable if I use a unit test in the TestSharedWorkOptimizer to simulate an artificial operator tree that reproduces but that would be from a real query though.

[ngsg]

I reproduced the same issue by running the following query on 10TB dataset. I'll share a better version that works on TestMiniLlapLocalCluster later.

set hive.tez.dynamic.semijoin.reduction=false;

with
a1 as (select distinct inv_date_sk from inventory, date_dim where inv_date_sk = d_date_sk and d_year = 2000 and d_dom = 1),
a2 as (select * from web_returns, a1 where inv_date_sk = wr_returned_date_sk),
a3 as (select wr_item_sk,
max(wr_refunded_customer_sk) col1, max(wr_refunded_cdemo_sk) col2, max(wr_refunded_hdemo_sk) col3, max(wr_refunded_addr_sk) col4, max(wr_returning_customer_sk) col5, max(wr_returning_cdemo_sk) col6, max(wr_returning_hdemo_sk) col7, max(wr_returning_addr_sk) col8, max(wr_web_page_sk) col9, max(wr_reason_sk) col10, max(wr_order_number) col11, max(wr_return_quantity) col12, max(wr_return_amt) col13, max(wr_return_tax) col14, max(wr_return_amt_inc_tax) col15, max(wr_fee) col16, max(wr_return_ship_cost) col17, max(wr_refunded_cash) col18, max(wr_reversed_charge) col19 from a2 group by wr_item_sk),
a4 as (select wr_item_sk,
min(wr_refunded_customer_sk) col1, min(wr_refunded_cdemo_sk) col2, min(wr_refunded_hdemo_sk) col3, min(wr_refunded_addr_sk) col4, min(wr_returning_customer_sk) col5, min(wr_returning_cdemo_sk) col6, min(wr_returning_hdemo_sk) col7, min(wr_returning_addr_sk) col8, min(wr_web_page_sk) col9, min(wr_reason_sk) col10, min(wr_order_number) col11, min(wr_return_quantity) col12, min(wr_return_amt) col13, min(wr_return_tax) col14, min(wr_return_amt_inc_tax) col15, min(wr_fee) col16, min(wr_return_ship_cost) col17, min(wr_refunded_cash) col18, min(wr_reversed_charge) col19 from a2 group by wr_item_sk)
select * from a3 join a4 on a3.wr_item_sk = a4.wr_item_sk and a3.col1 + a3.col5 < a4.col11 + a4.col8;

Caused by: java.lang.AssertionError: No work found for tablescan TS[3]
  at org.apache.hadoop.hive.ql.parse.GenTezUtils.processAppMasterEvent(GenTezUtils.java:548) ~[hive-exec-4.0.0.jar:4.0.0]
  at org.apache.hadoop.hive.ql.parse.TezCompiler.generateTaskTree(TezCompiler.java:719) ~[hive-exec-4.0.0.jar:4.0.0]
  at org.apache.hadoop.hive.ql.parse.TaskCompiler.compile(TaskCompiler.java:302) ~[hive-exec-4.0.0.jar:4.0.0]
  at org.apache.hadoop.hive.ql.parse.SemanticAnalyzer.compilePlan(SemanticAnalyzer.java:13067) ~[hive-exec-4.0.0.jar:4.0.0]

[ngsg]

@ramesh0201 , I write a qfile that verifies your patch. I tested it using TestMiniLlapLocalCliDriver and checked that your patch solves the issue. If you want, you could include the qfile in your patch.

set hive.cbo.enable=true;
set hive.auto.convert.join=true;
set hive.optimize.shared.work=true;
set hive.tez.dynamic.semijoin.reduction=false;
set hive.tez.dynamic.partition.pruning=true;

create table x_date_dim (d_date_sk bigint, d_year int);
create table x_inventory (inv_quantity_on_hand int) partitioned by (inv_date_sk bigint);
create table x_web_returns (wr_item_sk bigint, wr_refunded_customer_sk bigint) partitioned by (wr_returned_date_sk bigint);

insert into table x_date_dim values (1, 1999), (2, 2000), (3, 2001);
insert into table x_inventory (inv_quantity_on_hand, inv_date_sk) values (1, 1999), (2, 2000), (3, 2001);
insert into table x_web_returns (wr_item_sk, wr_refunded_customer_sk, wr_returned_date_sk) values (1, 1, 1999), (2, 2, 2000), (3, 3, 2001);

alter table x_date_dim update statistics set('numRows'='35', 'rawDataSize'='81449');
alter table x_inventory partition (inv_date_sk = 2000) update statistics set('numRows'='12345', 'rawDataSize'='1234567');
alter table x_web_returns partition (wr_returned_date_sk = 2000) update statistics set('numRows'='123456', 'rawDataSize'='12345678');

alter table x_date_dim update statistics for column d_date_sk set('numDVs'='35','numNulls'='0');
alter table x_inventory partition (inv_date_sk = 2000) update statistics for column inv_quantity_on_hand set('numDVs'='350','numNulls'='0');
alter table x_web_returns partition (wr_returned_date_sk = 2000) update statistics for column wr_item_sk set('numDVs'='3500','numNulls'='0');

with
a1 as (select distinct inv_date_sk, inv_quantity_on_hand from x_inventory, x_date_dim where inv_date_sk = d_date_sk and d_year = 2000),
a2 as (select * from x_web_returns, a1 where inv_date_sk = wr_returned_date_sk),
a3 as (select wr_item_sk, max(wr_refunded_customer_sk) col1 from a2 group by wr_item_sk),
a4 as (select wr_item_sk, min(wr_refunded_customer_sk) col1 from a2 group by wr_item_sk)
select * from a3 join a4 on a3.wr_item_sk = a4.wr_item_sk and a3.col1 < 2 * a4.col1;

[ramesh0201]

@ngsg Thank you very much for the test, yes I will use this test.

[ngsg]

I have investgated this issue for few days and conclude that the patch is sufficient to solve this issue.

This issues happens when a query plan contains a diamond pattern: an operator that have multiple parent operators, and those parent operators have a common ancestor operator. By default, SWO compares and merges the parent operators of a discardable operator. However, it stops gathering and only performs the comparison if it meets an operator with multiple child operators. [1] Therefore, merging 2 identical diamond patterns always leaves an unmerged common ancestor operator. As far as I know, multiple child operators can be produced by only 2 optimizers: DynamicPartitionPruningOptimization and SharedWorkOptimizer. In case of SWO, there cannot exists 2 identical diamond patterns because if they are identical, then they should be merged by SWO previously. So the only possible problem is DPPOpt, which is covered by this patch.

The following link contains some notes about this issue. For those who are interested, feel free to check it out. https://gist.github.com/ngsg/ec53cd605ee58d715b17b8449ef5a5e5

[1] https://github.com/apache/hive/blob/e0bd9eac32851b27976a78cd83584cb867b83182/ql/src/java/org/apache/hadoop/hive/ql/optimizer/SharedWorkOptimizer.java#L1695-L1698

[sonarqubecloud[bot]]

Quality Gate passed

Issues
6 New issues
0 Accepted issues

Measures
0 Security Hotspots
0.0% Coverage on New Code
0.0% Duplication on New Code

See analysis details on SonarCloud