Systems and methods for redistributing data in a relational database
Systems and methods for redistributing data in a relational database are disclosed. In one embodiment, the database includes a plurality of rows of data distributed across a plurality of slices of a table in the database. The database system is configured to distribute the rows of data across the slices according to a first function based on one or more columns of the database. The database system monitors at least one database statistic indicative of variation in a distribution of the rows of data across the slices and detects a redistribution condition based on the at least one monitored database statistic. The database system is further configured to respond to the detected redistribution condition by redistributing the rows of data across the slices according to a second function based on a different number of columns than the first function.
1. A method of redistributing data in a distributed database comprising a plurality of rows of data distributed across a plurality of slices of a table in the database, the method comprising:
hashing one or more column values in a row into a column value hash;
determining one hash range, out of a plurality of hash ranges, into which the column value hash falls;
assigning the row to one of the slices based on the determined hash range;
distributing the rows of data across the slices according to a first function based on one or more columns of the database, the first function comprising a hash function;
monitoring at least one database statistic indicative of variation in a distribution of the rows of data across the slices, the at least one database statistic comprising a plurality of occupancy ratios, one for each hash range of the plurality of hash ranges, each occupancy ratio comprising a ratio of a total number of rows falling into a hash range to a size of the hash range;
detecting a redistribution condition based on the at least one monitored database statistic; and
responding to the detected redistribution condition by redistributing the rows of data across the slices according to a second function based on a different number of columns than the first function,
wherein the method is performed by one or more computing devices.
2. The method of claim 1 , wherein the first function is based on a set of one or more columns, and the second function is based on the set of one or more columns of the first function, plus at least one additional column.
3. The method of claim 1 , wherein the first function is based on a set of one or more columns, and the second function is based on the set of one or more columns of the first function, minus at least one column.
4. The method of claim 1 , wherein said monitoring comprises periodically evaluating the at least one database statistic, wherein detecting the redistribution condition comprises detecting that the at least one database statistic exceeds a threshold value.
5. The method of claim 1 , wherein detecting the redistribution condition comprises detecting that a largest occupancy ratio of the plurality of occupancy ratios, divided by a smallest occupancy ratio of the plurality of occupancy ratios, is greater than a threshold value.
6. The method of claim 1 , wherein the at least one database statistic comprises a total number of rows containing each value in a set of most common values for at least one column of the database.
7. The method of claim 1 , wherein the at least one database statistic comprises a number of rows falling into each of a plurality of quantiles of potential values for a column.
8. A method of redistributing data in a distributed database comprising a plurality of rows of data distributed across a plurality of slices of a table in the database, the method comprising:
distributing the rows of data across the slices according to a first function based on one or more columns of the database;
monitoring at least one database statistic indicative of variation in a distribution of the rows of data across the slices;
detecting a redistribution condition based on the at least one monitored database statistic; and
responding to the detected redistribution condition by redistributing the rows of data across the slices according to a second function based on a different number of columns than the first function,
wherein:
a number of rows of a largest one of the slices is greater than or equal to a number of rows of each of the remaining slices;
a number of rows of a smallest one of the slices is less than or equal to a number of rows of each of the remaining slices;
the at least one database statistic comprises a ratio of the number of rows of the largest slice to the number of rows of the smallest slice;
detecting the redistribution condition comprises detecting that the ratio exceeds a threshold value; and
the method is performed by one or more computing devices.
9. The method of claim 1 , further comprising splitting one of the slices into a plurality of new slices, wherein detecting the redistribution condition further comprises detecting the splitting of the slice into the plurality of new slices.
10. A method of redistributing data in a distributed database comprising a plurality of rows of data distributed across a plurality of slices of a table in the database, the method comprising:
distributing the rows of data across the slices according to a first function based on one or more columns of the database;
monitoring at least one database statistic indicative of variation in a distribution of the rows of data across the slices, the at least one database statistic comprising a first standard deviation of the slices' numbers of rows divided by a mean value of the slices' numbers of rows;
detecting a redistribution condition based on the at least one monitored database statistic; and
responding to the detected redistribution condition by redistributing the rows of data across the slices according to a second function based on a different number of columns than the first function,
wherein the method is performed by one or more computing devices.
11. The method of claim 10 , wherein detecting the redistribution condition comprises detecting that the first standard deviation is greater than a threshold.
12. A method of redistributing data in a distributed database comprising a plurality of rows of data distributed across a plurality of slices of a table in the database, the method comprising:
distributing the rows of data across the slices according to a first function based on one or more columns of the database;
monitoring at least one database statistic indicative of variation in a distribution of the rows of data across the slices;
detecting a redistribution condition based on the at least one monitored database statistic; and
responding to the detected redistribution condition by redistributing the rows of data across the slices according to a second function based on a different number of columns than the first function,
wherein redistributing comprises:
creating a plurality of new slices;
creating a plurality of write queues, each write queue associated with a new slice;
redistributing the rows of data across the new slices according to the second function;
queuing writes to the database into the write queues while redistributing the rows of data across the new slices;
replaying the queued writes to the new slices; and
activating the new slices,
wherein the database slices continue to be available for database transactions while the data in the first slice is redistributed to the new slices, and
wherein the method is performed by one or more computing devices.
13. A distributed database system comprising a plurality of rows of data distributed across a plurality of slices of a table in the database, and one or more processors configured to:
hash one or more column values in a row into a column value hash;
determine one hash range, out of a plurality of hash ranges, into which the column value hash falls;
assign the row to one of the slices based on the determined hash range;
distribute the rows of data across the slices according to a first function based on one or more columns of the database, the first function comprising a hash function;
monitor at least one database statistic indicative of variation in a distribution of the rows of data across the slices, the at least one database statistic comprising a plurality of occupancy ratios, one for each hash range of the plurality of hash ranges, each occupancy ratio comprising a ratio of a total number of rows falling into a hash range to a size of the hash range;
detect a redistribution condition based on the at least one monitored database statistic; and
respond to the detected redistribution condition by redistributing the rows of data across the slices according to a second function based on a different number of columns than the first function.
14. The distributed database system of claim 13 , wherein the one or more processors are further configured to detect that a largest occupancy ratio of the plurality of occupancy ratios, divided by a smallest occupancy ratio of the plurality of occupancy ratios, is greater than a threshold value.
15. A computer-readable non-transitory storage medium comprising code capable of causing one or more processors to:
hash one or more column values in a row into a column value hash;
determine one hash range, out of a plurality of hash ranges, into which the column value hash falls;
assign the row to one of the slices based on the determined hash range;
distribute a plurality rows of data across a plurality of slices of a table in a database according to a first function based on one or more columns of the database, the first function comprising a hash function;
monitor at least one database statistic indicative of variation in a distribution of the rows of data across the slices, the at least one database statistic comprising a plurality of occupancy ratios, one for each hash range of the plurality of hash ranges, each occupancy ratio comprising a ratio of a total number of rows falling into a hash range to a size of the hash range;
detect a redistribution condition based on the at least one monitored database statistic; and
respond to the detected redistribution condition by redistributing the rows of data across the slices according to a second function based on a different number of columns than the first function.
16. The medium of claim 15 , wherein the first function is based on a set of one or more columns, and the second function is based on the set of one or more columns of the first function, plus at least one additional column.
17. The medium of claim 15 , wherein said monitoring comprises periodically evaluating the at least one database statistic, wherein detecting the redistribution condition comprises detecting that the at least one database statistic exceeds a threshold value.
18. The medium of claim 15 , wherein detecting the redistribution condition comprises detecting that a largest occupancy ratio of the plurality of occupancy ratios, divided by a smallest occupancy ratio of the plurality of occupancy ratios, is greater than a threshold value.
19. The medium of claim 15 , wherein the at least one database statistic comprises a total number of rows containing each value in a set of most common values for at least one column of the database.
20. The medium of claim 15 , wherein the at least one database statistic comprises a number of rows falling into each of a plurality of quantiles of potential values for a column.