Add index pages to the format to support efficient page skipping

[asfimport]

When a Parquet file is sorted we can define an index consisting of the boundary values for the pages of the columns sorted on as well as the offsets and length of said pages in the file.
The goal is to optimize lookup and range scan type queries, using this to read only the pages containing data matching the filter.
We'd require the pages to be aligned accross columns.

[~marcelk] will add a link to the google doc to discuss the spec

Reporter: Julien Le Dem / @julienledem
Assignee: Marcel Kinard

Related issues:

• Release Parquet format 2.4.0 (blocks)
• Don't write page level statistics in Parquet files in anticipation of page indexes (is required by)
• Write page index in Parquet files (is required by)
• Column indexes (is depended upon by)
• Write index page in parquet file (is depended upon by)

PRs and other links:

• GitHub Pull Request #63
• Impala prototype implementation results
• Format PR #72

_{Note: This issue was originally created as PARQUET-922. Please see the migration documentation for further details.}

[asfimport]

Lars Volker / @lekv:
The design doc for this feature can be found here: https://docs.google.com/document/d/1sBACp8Lbutuj1Zxdowvsrlm8ku4BFxf8U_Do5K2wSO4/edit?usp=sharing

[asfimport]

Ryan Blue / @rdblue:
Merged format PR #72. Thanks for getting this pushed through @lekv!

[asfimport]

Zoltan Ivanfi / @zivanfi:
I was looking for a JIRA for the actual implementation in parquet-mr, but couldn't find it. Does such a JIRA already exist?

[asfimport]

legend:
Hi @zivanfi

    I have same question with you. Do you working on the issue that implement in parquet-mr for Index Page?

[asfimport]

Gabor Szadovszky / @gszadovszky:
Hi [~legend],

I am working on it. Already linked the related JIRA to this one: PARQUET-1201. Please, feel free to add any questions to that JIRA if you think it is public or send an email directly to me.

[asfimport]

legend:
@gszadovszky, Great!(y)