US 8,805,784 B2Granted

Partitioning online databases

AssigneeMicrosoft Corporation

InventorsLev Novik, Andrew Kimball, Tony Petrossian, Cihangir Biyikoglu, Santeri Olavi Voutilainen, Tomas Talius, Istvan Cseri, Joachim Hammer, Jason D. Clark, Marc T. Friedman, Ajay Kalhan

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

The present invention extends to methods, systems, and computer program products for partitioning online databases. Online database operations, such as, for example, SPLIT, MERGE, and DROP, are used to alter the arrangement of partitions in a federated database. A SPLIT operation splits rows at one partition across a plurality of other partitions. A MERGE operation merges rows at a plurality of partitions in to one partition. A DROP operation shifts responsibility for rows of data from one partition to another partition and then drops the rows from the one partition.

Claims22

Dependent claims

At a computer system including one or more processors and system memory, the computer system included in a federated database system, the federated database system configured to store a plurality of rows of data, the plurality of rows of data distributed across one or more database partitions of the federated database system, each row of data corresponding to a federation key value used to identify the row of data, the federation key value selected from among a set of federation key values for the federated database system, partition criteria defining how the rows of data are distributed across the one or more database partitions based on federation key values, the computer system including a database partition from among the one or more database partitions, the partition criteria defining that the database partition is to store rows of data corresponding to a specified subset of the set of federation key values, a method for splitting the database partition into a plurality of database partitions, the method comprising:

an act of receiving a partition splitting directive indicating how to divide the specified subset of federation key values into at least a first portion and a second portion to split the rows of data stored in the database partition;
an act of executing a split operation to split the database partition in accordance with the partition splitting directive and while the database partition remains online, including:
an act of establishing a first new database partition to store rows of data corresponding to the first portion of the specified subset of federation key values;
an act of establishing a second new database partition to store rows of data corresponding to the second portion of the specified subset of federation key values;
an act of establishing at least one copy stream from the database partition to each of the first and second new database partitions;
and
for each of one or more rows of data from the database partition, an act of filtering the row of data to identify one of the first new database partition and the second new database partition as an appropriate destination database partition for the row of data, the filtering based on the federation key value for the row of data being in the first portion or the second portion of the specified subset of federation key values;
and
an act of copying each of the one or more rows of data from the database partition to the appropriate destination database over the at least one copy stream in accordance with the results of the filtering;
an act of establishing at least one update stream from the database partition to each of the first and second new database partitions;
an act of receiving an incoming update to a row of data in the database partition prior to completing the split command;
and
an act of copying the update to the row of data from the database partition to an appropriate destination database partition for the update over the at least one update stream.

10 more elements

At a computer system including one or more processors and system memory, the computer system included in a federated database system, the federated database system configured to store a plurality of rows of data, the plurality of rows of data distributed across a plurality of database partitions of the federated database system, each row of data corresponding to a federation key value used to identify the row of data, the federation key value selected from among a set of federation key values for the federated database system, partition criteria defining how the rows of data are distributed across the one or more database partitions based on federation key values, including defining that each of the plurality of database partitions is to store rows of data corresponding to a different specified subset of the set of federation key values, a method for merging database partitions, the method comprising:

an act of receiving a partition merging directive indicating how to combine the plurality of specified subsets of federation key values to merge together rows of data stored in the plurality of database partitions;
an act of executing a merge operation to merge the plurality database partitions together in accordance with the partition merging directive and while the plurality of database partitions remain online, including:
an act of establishing a new database partition to store rows of data corresponding to the plurality of specified subsets of federation key values;
an act of establishing at least one copy stream from each of the plurality of database partitions to the new database partition;
and
an act of transferring one or more rows of data from the plurality of database partitions to the new database partition over the at least one copy stream;
an act of establishing at least one update stream from each of plurality of database partitions to the new database partition;
an act of receiving an incoming update to a row of data stored in one of the plurality of database partitions;
and
an act of transferring the update to the corresponding row of data in the new database partition over the at least one update stream.

7 more elements

A computing system included in a federated database system, the federated database system configured to store a plurality of rows of data, the plurality of rows of data distributed across one or more database partitions of the federated database system, each row of data corresponding to a federation key value used to identify the row of data, the federation key value selected from among a set of federation key values for the federated database system, partition criteria defining how the rows of data are distributed across the one or more database partitions based on federation key values, the computer system including a database partition from among the one or more database partitions, the partition criteria defining that the database partition is to store rows of data corresponding to a specified subset of the set of federation key values, the computing system comprising:

at least one processor;
and
one or more storage medium having stored computer executable instructions which, when executed by the at least one processor, implements a method for splitting the database partition into a plurality of database partitions, the method comprising:
an act of receiving a partition splitting directive indicating how to divide the specified subset of federation key values into at least a first portion and a second portion to split the rows of data stored in the database partition;
an act of executing a split operation to split the database partition in accordance with the partition splitting directive and while the database partition remains online, including:
an act of establishing a first new database partition to store rows of data corresponding to the first portion of the specified subset of federation key values;
an act of establishing a second new database partition to store rows of data corresponding to the second portion of the specified subset of federation key values;
an act of establishing at least one copy stream from the database partition to each of the first and second new database partitions;
and
for each of one or more rows of data from the database partition, an act of filtering the row of data to identify one of the first new database partition and the second new database partition as an appropriate destination database partition for the row of data, the filtering based on the federation key value for the row of data being in the first portion or the second portion of the specified subset of federation key values;
and
an act of copying each of the one or more rows of data from the database partition to the appropriate destination database over the at least one copy stream in accordance with the results of the filtering;
an act of establishing at least one update stream from the database partition to each of the first and second new database partitions;
an act of receiving an incoming update to a row of data in the database partition prior to completing the split command;
and
an act of copying the update to the row of data from the database partition to an appropriate destination database partition for the update over the at least one update stream.

13 more elements

A computing system included in a federated database system, the federated database system configured to store a plurality of rows of data, the plurality of rows of data distributed across a plurality of database partitions of the federated database system, each row of data corresponding to a federation key value used to identify the row of data, the federation key value selected from among a set of federation key values for the federated database system, partition criteria defining how the rows of data are distributed across the one or more database partitions based on federation key values, including defining that each of the plurality of database partitions is to store rows of data corresponding to a different specified subset of the set of federation key values, the computing system comprising:

at least one processor;
and
one or more storage medium having stored computer executable instructions which, when executed by the at least one processor, implements a method for merging database partitions, the method comprising:
an act of receiving a partition merging directive indicating how to combine the plurality of specified subsets of federation key values to merge together rows of data stored in the plurality of database partitions;
an act of executing a merge operation to merge the plurality database partitions together in accordance with the partition merging directive and while the plurality of database partitions remain online, including:
an act of establishing a new database partition to store rows of data corresponding to the plurality of specified subsets of federation key values;
an act of establishing at least one copy stream from each of the plurality of database partitions to the new database partition;
and
an act of transferring one or more rows of data from the plurality of database partitions to the new database partition over the at least one copy stream;
an act of establishing at least one update stream from each of plurality of database partitions to the new database partition;
an act of receiving an incoming update to a row of data stored in one of the plurality of database partitions;
and
an act of transferring the update to the corresponding row of data in the new database partition over the at least one update stream.

10 more elements

at least one processor;
and
one or more storage medium having stored computer executable instructions which, when executed by the at least one processor, implements a method for splitting the database partition into a plurality of database partitions, the method comprising:
an act of receiving a partition splitting directive indicating how to divide the specified subset of federation key values into at least a first portion and a second portion to split the rows of data stored in the database partition, wherein the act of a receiving partition splitting directive indicating how to divide the specified subset of federation key values comprises:
an act of receiving a dividing federation key value indicating where to divide a range of federation key values, the range of federation key values including federation key values between a lower federation key value and a higher federation key value,
the act of establishing a first new database partition to store rows of data corresponding to the first portion of the specified subset of federation key values comprises an act of establishing the first new database partition to store rows of data corresponding to a first sub-range of federation key values, the first sub-range of federation key values including federation key values from the lower federation key value to the dividing federation key value, and
the act of establishing a second new database partition to store rows of data corresponding to the second portion of the specified subset of federation key values comprises an act of establishing the second new database partition to store rows of data corresponding to a second sub-range of federation key values, the second sub-range of federation key values including federation key values from the dividing federation key value to the higher federation key value;
and
an act of executing a split operation to split the database partition in accordance with the partition splitting directive and while the database partition remains online, including:
an act of establishing a first new database partition to store rows of data corresponding to the first portion of the specified subset of federation key values;
an act of establishing a second new database partition to store rows of data corresponding to the second portion of the specified subset of federation key values;
an act of establishing at least one copy stream from the database partition to each of the first and second new database partitions;
for each of one or more rows of data from the database partition, an act of filtering the row of data to identify one of the first new database partition and the second new database partition as an appropriate destination database partition for the row of data, the filtering based on the federation key value for the row of data being in the first portion or the second portion of the specified subset of federation key values;
and
an act of copying each of the one or more rows of data from the database partition to the appropriate destination database over the at least one copy stream in accordance with the results of the filtering.

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/165,557Filed 21 Jun 2011 · us provisional application
Priority: 28 Oct 2010
Published: US 2012/0109892 A13 May 2012
Granted: 12 Aug 2014
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

G06F 16/2379
Updating: updates performed during online database operations; commit processing
G06F 16/256
Integrating or interfacing systems involving database management systems: in federated or virtual databases
G06F 16/27
Of structured data, e.g. relational data: replication, distribution or synchronisation of data between databases or within a distributed database…
G06F 16/278
Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system…: data…