[IMPALA-7737] Evaluate repeated subexpressions only once

• Type: Improvement
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Affects Version/s: Impala 3.0
• Component/s: Backend, Frontend
• Labels: performance
• Epic Color: ghx-label-5
• Assignee: Unassigned
• Reporter: Paul Rogers
• Created: 22/Oct/18 18:54
• Updated: 22/Dec/20 21:08

Description

IMPALA-7655 suggests rewriting several conditional functions which can result in repeated evaluation of the same sub-expression. For example:

ISNULL(expr, ifNull)

Might become:

CASE WHEN expr IS NULL THEN ifNull ELSE expr END

In the original (interpreted) form, expr is evaluated once but used twice. In the code generated form for CASE, expr will be evaluated twice, removing some of the benefit of the rewrite.

This ticket requests to modify the FE and BE to handle common subexpressions.

In the most general case, the FE would search for such common subexpressions. For our purposes, a more narrow approach is possible: the rewrite rule would simply label such expressions during the rewrite.

Note that the label must survive subsequent rewrites (or such rewrites must be done before the rewrite into CASE.) For example:

ISNULL(1 + 2 + 3 + col, 5)

Will be rewritten to:

ISULL(6 + col, 6)

Ideally, the above rewrite would be done before the ISNULL rewrite so we'd not lose our tag. Then, we can tag the rewritten case EXPR (making something up):

CASE WHEN 6 + col {tag: $1} IS NULL THEN ifNull ELSE $1 END

Or:

TAGS $1: 6 + col CASE WHEN $1 IS NULL THEN ifNull ELSE $1 END

The code generation for CASE in the BE would be aware of these tags and would:

• In the same block where the CASE expr ... is evaluated, evaluate and store any tagged expressions.
• When performing the WHEN, THEN and ELSE clauses, modify code gen to refer back to prior saved values.

Issue Links

• is part of: IMPALA-7747 Clean up the Expression Rewriter