Mailing-List: contact dev-help@calcite.incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@calcite.incubator.apache.org
MIME-Version: 1.0
In-Reply-To: 
 <CAK55V=LrrP0iXM0V5OP8ng7-CEpwzqGcav_r6h+ArgCAK3bR9A@mail.gmail.com>
References: <D562E769-A0C4-4645-98AA-6A8DD7622FA2@apache.org>
	<CALcavhvTzc-JqjqFJpszNVVE7xfP76Cc+2H64p886jNpxOpn-Q@mail.gmail.com>
	<CACwebjSifkvWaeTyUrpVDP3D2TZVVJbF7JEMsCdkGE5iJmCVPw@mail.gmail.com>
	<CAK55V=LrrP0iXM0V5OP8ng7-CEpwzqGcav_r6h+ArgCAK3bR9A@mail.gmail.com>
Date: Fri, 31 Jul 2015 09:22:41 -0700
Message-ID: 
 <CAFyDVvJFKYBxOEGsbFpGp_mcyi6Nw=QsTQ3y1Wn9mP0q0XBdZA@mail.gmail.com>
Subject: Re: Collation meets relational algebra
From: Aman Sinha <asinha@maprtech.com>
To: dev@calcite.incubator.apache.org
Cc: Maryann Xue <maryann.xue@gmail.com>, Julian Hyde <jhyde@apache.org>,
	Maryann Xue <maryannxue@apache.org>
Content-Type: multipart/alternative; boundary=f46d043d67599f9ae9051c2e3ab7

--f46d043d67599f9ae9051c2e3ab7
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Yes, in general collation is a better fit as a physical property rather
than logical property of a plan node.  With regard to places where it makes
sense to treat it as logical property, agree with the ORDER-BY comments and
these should be extended to window functions too:
   SELECT  b,  RANK() OVER (ORDER BY b) FROM table;
I would think the LogicalWindow  should have collation on b.

Jinfeng, the subquery's ORDER-BY can be dropped in some cases but not all..
for instance in the following query:
  SELECT  a1 FROM (SELECT a1 FROM t1 WHERE .... ORDER BY a1)  LIMIT 10;
The OB should not be dropped.  There are other cases, this is one example.

Aman

On Fri, Jul 31, 2015 at 9:09 AM, Jinfeng Ni <jinfengni99@gmail.com> wrote:

> I think it makes sense that LogicalAggregate does not have collation, sin=
ce
> a LogicalAggregate could be implemented with different physical operator,
> either hash-based aggregation, or sort-based aggregation. Only when
> LogicalAggregate is converted into physical aggregator,  it makes sense t=
o
> have collation, depending on the which physical operator is used.
>
> Same thing could be applied to LogicalJoin, which could be implemented
> either as hash-join, or sort-based join.
>
> At logical level, the only collation will come from the top level ORDER B=
Y
> clause.  In that sense, I feel that the ORDER BY clause in a SUBQUERY, or
> VIEW probably should be removed in logical planning, since semantically i=
t
> does not impact query result.
>
>  SELECT   S.C1, T2.C4
>  FROM  (SELECT C1, C2, C3
>                FROM T1 ORDER BY C1) AS S JOIN
>                T2
> ON S  ...
> ORDER BY T2.C4;
>
> In Drill, we separate logical planning from physical planning, where the
> collation (together with distribution trait) will matter in physical
> planing.
>
>
>
>
> On Fri, Jul 31, 2015 at 7:27 AM, Milinda Pathirage <mpathira@umail.iu.edu=
>
> wrote:
>
> > Thanks Julian for looking in to this. Thanks Maryann for detecting the
> > issue in CALCITE-783 patch.
> >
> > As I understand we only need input's (input to aggregate) order related
> > metadata at the level of aggregate. I think I was wrong saying that
> > LogicalAggregate discards collation metadata from input in CALCITE-784
> > given that input is accessible from LogicalAggregate. We will only need
> to
> > do some calculations on input's collation metadata (or something simila=
r)
> > if we need to infer something about LogicalAggregate to be use by
> operators
> > which take aggregate as an input.
> >
> > Thanks
> > Milinda
> >
> > On Thu, Jul 30, 2015 at 11:32 PM, Maryann Xue <maryann.xue@gmail.com>
> > wrote:
> >
> > > Thanks Julian for taking time to sort out all these requirements and
> > > rethink about the model!
> > > Thank you Milinda! Really appreciate your quick response to the issue=
.
> > >
> > > On Thu, Jul 30, 2015 at 4:57 PM, Julian Hyde <jhyde@apache.org> wrote=
:
> > >
> > >> There are a few issues in play regarding collations (783, 784, 793;
> see
> > >> links below) and they seem to be overlapping. Maryann and Milinda ha=
ve
> > been
> > >> at odds with each other (in the politest possible way!)
> > >>
> > >> The cause is that they are both doing very interesting new work usin=
g
> > >> collation:
> > >> * Maryann is optimizing Phoenix plans to use secondary indexes. Thes=
e
> > are
> > >> tables that are project-sort materializations of a base table, itsel=
f
> > >> sorted.
> > >> * Milinda is planning Samza streaming-aggregation queries. A plan ca=
n
> > >> only be found if you know that the stream is sorted on one of the
> > >> aggregation keys, usually a time column.
> > >>
> > >> I spoke with Maryann about this today. I think that logical plans
> should
> > >> not have a sort order:
> > >> * In 783 and 784, I think I was wrong to allow logical RelNodes
> > >> (LogicalProject and LogicalAggregate) to have collations. Because th=
ey
> > are
> > >> logical, they are inherently un-sorted. (But they may be based on a
> > table,
> > >> say an ArrayTable, that does have a sort order.)
> > >> * In 793, Maryann was right so say that we should not bake in the
> > >> collation that a plan *happens to have* when the SQL is first
> > translated,
> > >> because trying to find a physical plan with the same collation
> restricts
> > >> our options.
> > >>
> > >> But SQL ASTs should have a sort order (if the top node is an ORDER B=
Y
> > >> clause, or if a table referenced in the FROM clause is a stream) and
> > >> physical RelNodes should also have a sort order.
> > >>
> > >> And Milinda=E2=80=99s logical plans need a concept similar to sortin=
g. Maybe a
> > >> piece of metadata that this RelNode *could be sorted by X, Y if
> > desired*.
> > >> Any table can, of course, be re-sorted into any order you like, but =
a
> > >> stream, which is infinite, can only be re-sorted to an order that do=
es
> > not
> > >> conflict with the order of the incoming data.
> > >>
> > >> I still need to roll up my sleeves and help these patient developers
> > >> (especially Milinda) get something working, but I hope it helps to
> have
> > a
> > >> general direction.
> > >>
> > >> Julian
> > >>
> > >> * https://issues.apache.org/jira/browse/CALCITE-783 Infer collation
> of
> > >> Project using monotonicity
> > >> * https://issues.apache.org/jira/browse/CALCITE-784
> LogicalAggregate's
> > >> create method discards any collation traits from input
> > >> * https://issues.apache.org/jira/browse/CALCITE-793 The compiler ask=
s
> > >> for unnecessary collation trait on plan with materialized view
> > >> * https://issues.apache.org/jira/browse/CALCITE-825 Allow user to
> > >> specify sort order of an ArrayTable
> > >>
> > >
> > >
> >
> >
> > --
> > Milinda Pathirage
> >
> > PhD Student | Research Assistant
> > School of Informatics and Computing | Data to Insight Center
> > Indiana University
> >
> > twitter: milindalakmal
> > skype: milinda.pathirage
> > blog: http://milinda.pathirage.org
> >
>

--f46d043d67599f9ae9051c2e3ab7--