[DISCUSS][C++] Refactoring of Expression simplification passes

[Benjamin Kietzman <be...@gmail.com>]

Currently, Expressions (used to specify dataset filters and projections)
are simplified by direct rewriting: a filter such as `alpha == 2 and beta >
3`
on a partition where we are guaranteed that `beta == 5` will be rewritten
to `alpha == 2` before evaluation against scanned batches. This can
potentially occur for each scanned batch: for example, Parquet's row group
statistics are used in the same way to simplify filters.

Rewriting is not extremely expensive (a microbenchmark estimate on
my machine shows that a simple case such as the above takes 4ms).
However it does complicate an execution of a logical plan wherein
expressions being evaluated are not identical to the expression with
which the plan was constructed.

It seems it might be preferable to avoid mutating expressions and instead
build a mapping from sub expressions to known values which can be used
by subsequent simplification passes and during execution. I'd have to
benchmark it, but it also seems like we might speed up expression
simplification this way. Any thoughts?

Re: [DISCUSS][C++] Refactoring of Expression simplification passes

[Wes McKinney <we...@gmail.com>]

This seems like it could be a premature optimization, do we know what
fraction of important workloads are taken up by this operation?

On Wed, May 5, 2021 at 12:35 PM Benjamin Kietzman <be...@gmail.com> wrote:
>
> Sorry, yes: I meant 4 microseconds and not 4 milliseconds.
>
> On Wed, May 5, 2021 at 1:27 PM Antoine Pitrou <an...@python.org> wrote:
>
> > On Wed, 5 May 2021 13:23:36 -0400
> > Benjamin Kietzman <be...@gmail.com> wrote:
> > > Currently, Expressions (used to specify dataset filters and projections)
> > > are simplified by direct rewriting: a filter such as `alpha == 2 and
> > beta >
> > > 3`
> > > on a partition where we are guaranteed that `beta == 5` will be rewritten
> > > to `alpha == 2` before evaluation against scanned batches. This can
> > > potentially occur for each scanned batch: for example, Parquet's row
> > group
> > > statistics are used in the same way to simplify filters.
> > >
> > > Rewriting is not extremely expensive (a microbenchmark estimate on
> > > my machine shows that a simple case such as the above takes 4ms).
> >
> > 4ms for a single rewriting actually sounds quite large to me.
> > (or did you mean 4µs?)
> >
> >
> >
> >

Re: [DISCUSS][C++] Refactoring of Expression simplification passes

[Benjamin Kietzman <be...@gmail.com>]

Sorry, yes: I meant 4 microseconds and not 4 milliseconds.

On Wed, May 5, 2021 at 1:27 PM Antoine Pitrou <an...@python.org> wrote:

> On Wed, 5 May 2021 13:23:36 -0400
> Benjamin Kietzman <be...@gmail.com> wrote:
> > Currently, Expressions (used to specify dataset filters and projections)
> > are simplified by direct rewriting: a filter such as `alpha == 2 and
> beta >
> > 3`
> > on a partition where we are guaranteed that `beta == 5` will be rewritten
> > to `alpha == 2` before evaluation against scanned batches. This can
> > potentially occur for each scanned batch: for example, Parquet's row
> group
> > statistics are used in the same way to simplify filters.
> >
> > Rewriting is not extremely expensive (a microbenchmark estimate on
> > my machine shows that a simple case such as the above takes 4ms).
>
> 4ms for a single rewriting actually sounds quite large to me.
> (or did you mean 4µs?)
>
>
>
>

Re: [DISCUSS][C++] Refactoring of Expression simplification passes

[Antoine Pitrou <an...@python.org>]

On Wed, 5 May 2021 13:23:36 -0400
Benjamin Kietzman <be...@gmail.com> wrote:
> Currently, Expressions (used to specify dataset filters and projections)
> are simplified by direct rewriting: a filter such as `alpha == 2 and beta >
> 3`
> on a partition where we are guaranteed that `beta == 5` will be rewritten
> to `alpha == 2` before evaluation against scanned batches. This can
> potentially occur for each scanned batch: for example, Parquet's row group
> statistics are used in the same way to simplify filters.
> 
> Rewriting is not extremely expensive (a microbenchmark estimate on
> my machine shows that a simple case such as the above takes 4ms).

4ms for a single rewriting actually sounds quite large to me.
(or did you mean 4µs?)