Delta Frame of Reference Compression
Presented by:
Evgeny Voropaev
I am a C++/C software developer with a PhD in experimental physics. Having worked across a wide range of modern IT realms including embedded systems, SDKs, server backends, IoT, and GUIs for desktop as well as for embedded systems, I am currently focused on PostgreSQL development. My specific engineering focus within PG lies in the transaction system (especially in the upcoming 64-bit XID), heap layout, and highly efficient data compression, particularly differential compression methods.
The Delta Frame of Reference algorithm (DFOR) is a widely used solution for the lossless compression of integer sequences. DFOR, which is classified as differential compression method, provides a high compression ratio even for short data sequences, where statistical and dictionary-based compression methods can be ineffective. While nowadays the plenty of DFOR implementations are available, custom tailoring and further development of the algorithm are often required when we are eager to achieve a greater compression ratio, especially when dealing with data specificity, original use cases, or the unique environment of an idiosyncratic system like PostgreSQL. This presentation presents the core concepts of DFOR alongside the author’s original enhancements to the standard algorithm. The current implementation already supports both sorted and unsorted sequences, provides positive and negative deltas, utilizes exceptions to store long deltas separately, thereby increasing ‘pack density’. However, a few features that could improve the algorithm further are still awaiting implementation. The paper also describes both completed and planned applications of DFOR within PostgreSQL. Regarding accomplished milestones, DFOR has already been integrated into WAL prune/freeze records to compress offset sequences, resulting in a practical compression ratio of more than 5. The next integration step is applying DFOR to GIN-index, where compression of tuple identifier sequences looks promising and could theoretically achieve compression ratio of 16. The code architecture of the DFOR unit provides header templates comprising macros and function patterns. This allows developers to easily create an instantiation of the DFOR supporting an integer item of any size that is a multiple of 8 bits. The bit-packing utility, heavily utilised by DFOR as a workhorse, is implemented as a distinct unit and can be used by PostgreSQL independently. In conclusion, the presented DFOR solution is now largely implemented, and its application within PostgreSQL already demonstrates significant compression levels. Future work in this realm will focus on improving the algorithm’s compression ratio and expanding coverage to other areas of the PostgreSQL codebase where the compression of integer sequences is profitable.
- Date:
- 2026 October 30 13:20 +11
- Duration:
- 40 min
- Room:
- Taylor
- Conference:
- PG Down Under 2026
- Language:
- Track:
- Development
- Difficulty:
- Hard