[PR] [WIP][Spec] PFOR encoding with delta support. [parquet-format]

["prtkgaur (via GitHub)" <gi...@apache.org>]

prtkgaur opened a new pull request, #617:
URL: https://github.com/apache/parquet-format/pull/617

   <!--
   Thanks for opening a pull request!
   
   If you're new to Parquet-Format, information on how to contribute can be found here: https://parquet.apache.org/docs/contribution-guidelines/contributing
   
   Please open a GitHub issue for this pull request: https://github.com/apache/parquet-format/issues/new/choose
   and format pull request title as below:
   
       GH-${GITHUB_ISSUE_ID}: ${SUMMARY}
   
   or simply use the title below if it is a minor issue:
   
       MINOR: ${SUMMARY}
   
   -->
   
   ### Rationale for this change
   
   
   ### What changes are included in this PR?
   
   
   ### Do these changes have PoC implementations?
   
   
   <!-- Please uncomment the line below and replace ${GITHUB_ISSUE_ID} with the actual Github issue id. -->
   <!-- Closes #${GITHUB_ISSUE_ID} -->
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org

Re: [PR] [WIP][Spec] PFOR encoding with delta support. [parquet-format]

["prtkgaur (via GitHub)" <gi...@apache.org>]

prtkgaur commented on code in PR #617:
URL: https://github.com/apache/parquet-format/pull/617#discussion_r3936638490


##########
Encodings.md:
##########
@@ -420,3 +420,636 @@ enabling random access to individual values and parallel encoding/decoding.
 
 The detailed specification of the ALP encoding, including the page layout and
 the encoding and decoding procedures, is in [AlpEncoding.md](AlpEncoding.md).
+<a name="PFOR"></a>
+### Patched Frame of Reference (PFOR = 11)
+
+Supported Types: INT32, INT64
+
+PFOR (Patched Frame of Reference) compresses integer columns by subtracting the
+minimum value (Frame of Reference), then bit-packing the residuals at an optimal
+bit width selected by a cost model. Values that do not fit in the chosen bit width
+are stored as exceptions ("patches"). The cost model trades off narrower bit-packing
+against the overhead of storing exceptions, achieving better compression than plain
+FOR when a few outlier values would otherwise inflate the bit width.
+
+A writer MAY instead pack the differences between successive values. That choice
+is the **delta mode**, it is recorded per vector in bit 7 of `bit_width`, and a
+vector in that mode carries its own first value so that it still decodes without
+reading the vector before it. Everything else -- the frame of reference, the bit
+width, the exceptions -- is then chosen over the differences exactly as it would
+be over the values, and a reader runs one extra step, a prefix sum, to reverse
+the differencing.
+
+The values that reach the packed stream are called *residuals* throughout this
+section, in both modes: a residual is what remains after the frame of reference
+is subtracted, whether the frame was subtracted from a value or from a
+difference.
+
+#### Overview

Review Comment:
   Will be moved to a separate file (just like ALP)



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org