3 ms·

Something I always wonder about is figuring out the optimal page size. The author seems to use 64KB. This is neither the size of a CPU cache line (often 64 by

Something I always wonder about is figuring out the optimal page size. The author seems to use 64KB. This is neither the size of a CPU cache line (often 64 bytes) nor the size of a block on an SSD (often 512KB). So why 64KB?

harrison_clarke 2y ago
a u16 can address it, which is nice. it's also the minimum virtual address allocation on windows. not sure if either of those are the reason, in this case
magnat 2y ago
If your data/leaf/heap pages hold indexed cells PostgreSQL-style [1], 16-bit in-page offset limits your page size to 64KB. On the other hand, physical memory frame size usually is 4KB or larger, so going below that is not really productive. Having said that, both PostgreSQL and Microsoft SQL has 8KB page size, while original SQLite had 1KB pages, before switching to 4KB, while still supporting 64KB pages. On top of that, Microsoft SQL operates internally on extents of 8 pages (64 KB) instead of a single page, but still pretends to use 4 KB pages [2]. In other words - no idea. [1] https://www.postgresql.org/docs/current/storage-page-layout.html https://www.postgresql.org/docs/current/storage-page-layout.... [2] https://learn.microsoft.com/en-us/sql/relational-databases/pages-and-extents-architecture-guide https://learn.microsoft.com/en-us/sql/relational-databases/p...
- msanlop 2y ago
  I tried looking for papers on the subject but couldn't find much. There recent research about in-memory B-tree, and there is has been shown that smaller pages (sizes as low as 256/512B) are more performant due to better cache behavior[0]. The general wisdom seems to be that disk-based databases' IO performance is the main bottleneck—but again I couldn't find any concrete data/benchmarks about why those higher sizes were chosen. [0] There's even some cool research about B-trees that have the layout depend on the probabilistic distribution of the lookups: https://dl.acm.org/doi/10.1145/3592980.3595316 https://dl.acm.org/doi/10.1145/3592980.3595316
- sroussey 2y ago
  The default macOS page size is currently 16KB, and various (Apple) stuff is optimized for it, and I think SQLite is among them (not 100%). I think their server optimized builds for internal use are 64.
- o11c 2y ago
  16-bit offsets doesn't limit you to 64K unless you require byte-alignment. 128K or 256K is usually trivial and even 512K or 1M is often viable.
tomnipotent 2y ago
Cedar uses a PAX storage layout (hybrid row/column) so I imagine 64KB optimizes well for OLAP workloads while keeping excess disk I/O for point look-ups manageable. Depending on your OLAP load that "excess" I/O could either be a rounding error or a bottleneck.
shinycode 2y ago
From the article : « The 64KB root node of our B-Tree fits nicely into the L1/L2 cache of a modern CPU » Maybe that’s why ?
- jrockway 2y ago
  I'm just looking for more depth. Like, is that all loaded in 1 load operation when the page is touched and is therefore optimal? Does disk access / writing dirty pages not matter?
  - menaerus 2y ago
    No, 64K is definitely not loaded in 1 load operation. Maximum amount of load operations modern CPUs can do is 2x512-bit or 128 bytes per cycle or around ~600 GB of L1 bandwidth. That said, there is no universal page size one can choose from. Some workloads will benefit from smaller page size while others will benefit from larger page size but 512K is not the size you will want to choose. Read-, write-, space-amplification, CPU cache thrashing etc.
remexre 2y ago
64KiB also happens to be the largest minimum page size you can configure reasonably common hardware to have (not that this is a common configuration).

harrison_clarke 2y ago

a u16 can address it, which is nice. it's also the minimum virtual address allocation on windows. not sure if either of those are the reason, in this case

magnat 2y ago

If your data/leaf/heap pages hold indexed cells PostgreSQL-style [1], 16-bit in-page offset limits your page size to 64KB. On the other hand, physical memory frame size usually is 4KB or larger, so going below that is not really productive. Having said that, both PostgreSQL and Microsoft SQL has 8KB page size, while original SQLite had 1KB pages, before switching to 4KB, while still supporting 64KB pages. On top of that, Microsoft SQL operates internally on extents of 8 pages (64 KB) instead of a single page, but still pretends to use 4 KB pages [2]. In other words - no idea. [1] https://www.postgresql.org/docs/current/storage-page-layout.html https://www.postgresql.org/docs/current/storage-page-layout.... [2] https://learn.microsoft.com/en-us/sql/relational-databases/pages-and-extents-architecture-guide https://learn.microsoft.com/en-us/sql/relational-databases/p...

msanlop 2y ago
I tried looking for papers on the subject but couldn't find much. There recent research about in-memory B-tree, and there is has been shown that smaller pages (sizes as low as 256/512B) are more performant due to better cache behavior[0]. The general wisdom seems to be that disk-based databases' IO performance is the main bottleneck—but again I couldn't find any concrete data/benchmarks about why those higher sizes were chosen. [0] There's even some cool research about B-trees that have the layout depend on the probabilistic distribution of the lookups: https://dl.acm.org/doi/10.1145/3592980.3595316 https://dl.acm.org/doi/10.1145/3592980.3595316
sroussey 2y ago
The default macOS page size is currently 16KB, and various (Apple) stuff is optimized for it, and I think SQLite is among them (not 100%). I think their server optimized builds for internal use are 64.
o11c 2y ago
16-bit offsets doesn't limit you to 64K unless you require byte-alignment. 128K or 256K is usually trivial and even 512K or 1M is often viable.

tomnipotent 2y ago

Cedar uses a PAX storage layout (hybrid row/column) so I imagine 64KB optimizes well for OLAP workloads while keeping excess disk I/O for point look-ups manageable. Depending on your OLAP load that "excess" I/O could either be a rounding error or a bottleneck.

shinycode 2y ago

From the article : « The 64KB root node of our B-Tree fits nicely into the L1/L2 cache of a modern CPU » Maybe that’s why ?

jrockway 2y ago
I'm just looking for more depth. Like, is that all loaded in 1 load operation when the page is touched and is therefore optimal? Does disk access / writing dirty pages not matter?
- menaerus 2y ago
  No, 64K is definitely not loaded in 1 load operation. Maximum amount of load operations modern CPUs can do is 2x512-bit or 128 bytes per cycle or around ~600 GB of L1 bandwidth. That said, there is no universal page size one can choose from. Some workloads will benefit from smaller page size while others will benefit from larger page size but 512K is not the size you will want to choose. Read-, write-, space-amplification, CPU cache thrashing etc.

remexre 2y ago

64KiB also happens to be the largest minimum page size you can configure reasonably common hardware to have (not that this is a common configuration).