Re: [HACKERS] [PROPOSAL] Temporal query processing with range types

On 01/26/2018 07:55 AM, Peter Moser wrote:
> We have now a new approach to plan and execute NORMALIZE as a special
> join node of type NORMALIZE, an append-plan on the inner join path,
> and a merge-join executor. For the latter, we would need to
> extend nodeMergejoin.c with an point-in-range-containment join.

We are ready with a new prototype for the temporal NORMALIZE operation.
In this prototype we do not rewrite queries as in the previous patch,
but have one executor node, that solves the normalize operation. This
executor is based on a merge-join.

Our new patch is based on top of
75f7855369ec56d4a8e7d6eae98aff1182b85cac from September 6, 2018.

The syntax is
SELECT * FROM (r NORMALIZE s USING() WITH(period_r, period_s)) c;

It currently is only implemented for empty USING clauses, and solely
int4range as range attributes.

Example:

A=# table r;

a | b | period_r

---+---+----------

a | B | [1,7)

b | B | [3,9)

c | G | [8,10)

(3 rows)

A=# table s;

c | d | period_s

---+---+----------

1 | B | [2,5)

2 | B | [3,4)

3 | B | [7,9)

(3 rows)

A=# SELECT * FROM (r NORMALIZE s USING() WITH(period_r, period_s)) c;

period_r | a | b

----------+---+---

[1,2) | a | B

[2,3) | a | B

[3,4) | a | B

[4,5) | a | B

[5,7) | a | B

[3,4) | b | B

[4,5) | b | B

[5,7) | b | B

[7,9) | b | B

(9 rows)

A=# EXPLAIN SELECT * FROM (r NORMALIZE s USING() WITH(period_r,
period_s)) c;
QUERY PLAN

--------------------------------------------------------------------------

Result (cost=2.15..2.22 rows=3 width=18)

-> Merge ??? Join (cost=2.15..2.23 rows=3 width=22)

Merge Cond: (r.period_r @> (range_split(s.period_s)))

-> Sort (cost=1.05..1.06 rows=3 width=18)

Sort Key: r.period_r

-> Seq Scan on r (cost=0.00..1.03 rows=3 width=18)

-> Sort (cost=1.09..1.10 rows=3 width=4)

Sort Key: (range_split(s.period_s)) USING <

-> ProjectSet (cost=0.00..1.07 rows=3 width=4)

-> Seq Scan on s (cost=0.00..1.03 rows=3
width=14)
(10 rows)

> That is, we create a new join path within sort_inner_and_outer
> (joinpath.c). First two projection nodes to extract the start- and
> end-timepoints of the range type used as interval, and above an
> append-plan to merge both subplans. In detail, outer_path is just sort,
> whereas inner_path is append of (B, ts) projection with (B, te)
> projection.

We changed this implementation and use a set-returning function called
"range_split", that extracts the upper and lower bound of a range and
returns two tuples. For instance, a tuple '[4,10),a' becomes two tuples
of the form '4,a' and '10,a'.

> Hereby, B is a set of non-temporal attributes used in join equality
> predicates, and [ts,te) forms the valid-time interval. Non-equality
> predicates must be handled separately as a filter step.

The current prototype supports only an integer range-type without any
additional non-temporal attributes (empty USING clause).

> Do you think, it is a good idea to extend the sort_inner_and_outer()
> with a new branch, where jointype == NORMALIZE and add the projection
> and append sub-paths there?

We actually extended sort_inner_and_outer now. It is an early solution,
to support discussions. Please see the two sections starting with "if
(jointype == JOIN_TEMPORAL_NORMALIZE)" inside sort_inner_and_outer:

The purpose of these sections is to change the inner path's range type
into its single bounds.

We accomplish this with a new function called range_split. We take the
inner clause and extract the second operator of an RANGE_EQ expression
out of it. We assume *for this prototype*, that their is only one such
operator and that it is solely used for NORMALIZE. Then, we replace it
with range_split. A range split returns a set of tuples, hence we add a
new "set projection path" above the inner path, and another sort path
above that.

What we like to discuss now is:
- Is sort_inner_and_outer the correct place to perform this split?
- How could we support OID_RANGE_ELEM_CONTAINED_OP for a NORMALIZE
mergejoin executor? If we use RANGE_ELEM_CONTAINED as operator, it is
not an equality operator, but if we use RANGE_EQ it assumes that the
right-hand-side of the operator must be a range as well.
- Should we better change our mergeclause to a RANGE_ELEM_CONTAINED
comparison, or keep RANGE_EQ and fix pathkeys later?
- How do we update equivalence classes, pathkeys, and any other struct,
when changing the inner relation's data type from "int4range" to "int"
in the query tree inside "sort_inner_and_outer" to get the correct
ordering and data types

Best regards,
Anton, Johann, Michael, Peter