Consider range partitioning

[purplefox]

Prana currently uses hash partitioning to partition data into shards.

Hash partitioning has an advantage when ingesting sequential data (e.g. for Kafka topics where the key is ascending) as data is balanced evenly over partitions, whereas for range partitioning it will end up in the highest range thus creating a hotspot.

Range partitioning has an advantage for range scans as they might only need to get data from a subset of partitions whereas with hash partitioning range scans need to contact all partitions.

Range partitioning also has an advantage in that redistributing data when adding a new partition is simpler.

With range partitioning, each partition owns a range of keys. Initially a table might have a single partition, and as more rows are written to it, it gets to a certain size and can be split into two partitions each owning half the previous range.

This process continues and we end up with a binary search tree structure which maps keys to partitions. The partitions are the leaves of the tree.

We should consider whether it makes sense to support range partitioning too.