Re: Impala Sorter just sort small partition?

[Tim Armstrong]

No problems at all, thanks for your interest.

On Fri, Aug 4, 2017 at 9:07 PM, cjjnj...@gmail.com 
wrote:

> oh, there is an assignment to low.  thanks for patience:)
>
> ---Original---
> *From:* "Tim Armstrong "
> *Date:* 2017/8/5 11:27:21
> *To:* "dev@impala";
> *Subject:* Re: Impala Sorter just sort small partition?
>
> It does sort both left and right partitions - it just recurses on the small
> partition and the next iteration of the loop processes the large partition.
>
> This is a pretty common optimisation. This page has a nice 
> explanation:http://www.geeksforgeeks.org/quicksort-tail-call-optimization-reducing-worst-case-space-log-n/
>
> On Fri, Aug 4, 2017 at 6:12 PM, 俊杰陈  wrote:
>
> > Thanks for your detail description.
> >
> > My question should be more specific to quicksort part. This line
> >  > be/src/runtime/sorter.cc#L1258>
> > say
> > recurse on the small partition due to stack consideration, while as my
> > understanding quicksort should recurse on both left partition and right
> > partition, so I'm curious how it keep one run sorted, does it sort in later
> > merge sort or somewhere else?   But the merge process should take sorted
> > runs as input.
> >
> > 2017-08-05 0:18 GMT+08:00 Tim Armstrong :
> >
> > > The Sorter does a 3-level hybrid sort with merge sort, quicksort and
> > > insertion sort.
> > >
> > > SortHelper implements a 2-level hybrid in-memory sort. It fully sorts an
> > > arbitrarily sized in-memory input. E.g. if 'begin' and 'end' point to the
> > > begin and end of the sorted run, it will sort the full run. It does
> > > quicksort recursively then switches to insertion sort once the partitions
> > > are less than INSERTION_THRESHOLD = 16.
> > >
> > > Sorter also supports an external merge sort - if the full input doesn't
> > fit
> > > in memory, it sorts in-memory runs with SortHelper() then does merge sort
> > > with the sorted runs.
> > >
> > > On Thu, Aug 3, 2017 at 11:13 PM, 俊杰陈  > wrote:
> > >
> > > > Hi
> > > > I'm looking Sorter.cc and found that Sorter::SortHelper just sort
> > smaller
> > > > partition. Is there anything I missed?
> > > >
> > > > --
> > > > Thanks & Best Regards
> > > >
> > >
> >
> >
> >
> > --
> > Thanks & Best Regards
> >
>
>

Podling Report Reminder - August 2017

[johndament]

Dear podling,

This email was sent by an automated system on behalf of the Apache
Incubator PMC. It is an initial reminder to give you plenty of time to
prepare your quarterly board report.

The board meeting is scheduled for Wed, 16 August 2017, 10:30 am PDT.
The report for your podling will form a part of the Incubator PMC
report. The Incubator PMC requires your report to be submitted 2 weeks
before the board meeting, to allow sufficient time for review and
submission (Wed, August 02).

Please submit your report with sufficient time to allow the Incubator
PMC, and subsequently board members to review and digest. Again, the
very latest you should submit your report is 2 weeks prior to the board
meeting.

Thanks,

The Apache Incubator PMC

Submitting your Report

--

Your report should contain the following:

*   Your project name
*   A brief description of your project, which assumes no knowledge of
the project or necessarily of its field
*   A list of the three most important issues to address in the move
towards graduation.
*   Any issues that the Incubator PMC or ASF Board might wish/need to be
aware of
*   How has the community developed since the last report
*   How has the project developed since the last report.
*   How does the podling rate their own maturity.

This should be appended to the Incubator Wiki page at:

https://wiki.apache.org/incubator/August2017

Note: This is manually populated. You may need to wait a little before
this page is created from a template.

Mentors
---

Mentors should review reports for their project(s) and sign them off on
the Incubator wiki page. Signing off reports shows that you are
following the project - projects that are not signed may raise alarms
for the Incubator PMC.

Incubator PMC