GGraziadei commented on issue #17758: URL: https://github.com/apache/iceberg/issues/17758#issuecomment-5375860646
Hi @RussellSpitzer, I found your PR and the reference to the interleaving discussion: https://github.com/apache/iceberg/pull/3983 Thanks! This is a good starting point. As an additional reference, I’d also like to point to the work done in other lakehouse projects, particularly Delta Lake. The approach I’m proposing is similar and is based on a lookup table: * https://github.com/delta-io/delta/commit/22a0be1c81e9f43fab1550ada9dab586f5e7203e * https://github.com/delta-io/delta/commit/56e1b9b417e8815cd7003eaf1796988c670b8b0d The source of this issue actually came from a profiler comparison between the Delta and Iceberg interleaving implementations :-). I also investigated the theoretical background. I don’t want to cite Morton directly, since that reference is fairly generic. I believe the first paper that proposes a specific fast bit-interleaving implementation is: > R. Raman and D. S. Wise, “Converting to and from Dilated Integers,” *IEEE Transactions on Computers*, vol. 57, no. 4, pp. 567–573, April 2008. doi: 10.1109/TC.2007.70814. There seems to be a direct correspondence between the algorithm described in the paper and the proposed implementation. For example, the paper uses: ``` inline unsigned int dilate_2(unsigned short x){ return dilate_tab2[0xFF & x] | (dilate_tab2[(0xFFFF & x) >> 8] << 16); } ``` while the proposed code uses (because we have to generalize for k dimensions) ``` long chunk = 0L; for (int c = 0; c < numColumns; c++) { chunk |= spread[columnsBinary[c][j] & 0xFF] >>> c; } for (int k = numColumns - 1; k >= 0; k--) { interleavedBytes[out++] = (byte) (chunk >>> (8 * k)); } ``` The common idea is to use a precomputed lookup table to expand/spread the bits and then combine the resulting chunks with the appropriate offset. I think this is the relevant connection between the proposed algorithm and the paper. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
