System and method for positioning records in a database

A method for positioning data in a database, comprising:

• constructing a base graph in which a plurality of data blocks in the database each correspond to one of a plurality of vertices, wherein the base graph is a weighted graph having weights of edges corresponding to affinities of data blocks of data;
• and
• constructing a simpler graph, comprising:
• a plurality of final vertices, each corresponding to at least two of the vertices from the base graph;
• and
• at least one final edge corresponding to at least one of the edges in the base graph;
• and
• wherein the simpler graph is a weighted graph having edges with weights corresponding to weights of edges in the base graph;
• selecting a simple partition for the simpler graph;
• and
• determining a penultimate partition for the base graph wherein each group comprises every parent vertex to any daughter vertex in the simpler graph if the group comprises at least one parent vertex to that daughter vertex;
• and
• determining a rough distribution of the data blocks in which a given data block is positioned on the a page with each data block with which the given data block shares an adjacent edge, unless that edge is cut in the penultimate partition;
• and
• refining the rough distribution by moving at least one data block from the page on which it was positioned during the determining a rough distribution of the data blocks.

A method of positioning a first new data block of data on a page, comprising:

• buffering the first new data block in server memory;
• and
• selecting a page containing data blocks having a high collective affinity for the first new data block;
• and
• determining whether the collective affinity of the data blocks on the selected page for the first new data block exceeds a preselected value;
• and
• positioning the first new data block on the selected page if the collective affinity of the data blocks on the selected page exceed the preselected value;
• and
• positioning the first new data block on a new page if the collective affinity of the data blocks on the selected page do not exceed the preselected value.

A method for assigning at least one weight to at least one edge of a weighted graph corresponding to data blocks in a database, the method comprising:

• providing a schema of the database defining at least one collection;
• and
• selecting at least one derived access type from a predefined set for the at least one collection of the schema of the database;
• and
• assigning at least one weight to at least one edge corresponding to at least one relationship between data blocks comprising the collection, the at least one relationship being defined by the derived access type.

A method for positioning data in a database, comprising:

• constructing a weighted base graph in which a plurality of data blocks in the database each correspond to one of a plurality of vertices, and in which at least one affinity between objects corresponds to at least one edge;
• and
• constructing a weighted simpler graph, comprising:
• a plurality of final vertices, each corresponding to at least two of the vertices from the base graph;
• and
• at least one final edge corresponding to at least one of the edges in the base graph;
• and
• selecting a simple partition for the simpler graph;
• and
• determining a final partition for the data in the database from the simple partition of the simpler graph;
• and
• wherein at least one weight of at least one edge is assigned using information from the database about explicit connections between at least one pair of data blocks, the at least one pair of data blocks corresponding to at least one pair of vertices of the weighted base graph.

A method for positioning data in a database, comprising:

• constructing a weighted base graph in which a plurality of data blocks in the database each correspond to one of a plurality of vertices, and in which at least one affinity between objects corresponds to at least one edge;
• and
• constructing a weighted simpler graph, comprising:
• a plurality of final vertices, each corresponding to at least two of the vertices from the base graph;
• and
• at least one final edge corresponding to at least one of the edges in the base graph;
• and
• selecting a simple partition for the simpler graph;
• and
• determining a final partition for the data in the database from the simple partition of the simpler graph;
• and
• wherein at least one weight of at least one edge is assigned using statistical information regarding the patterns of past accesses of data blocks.

A method for positioning data in a database, comprising:

• constructing a weighted base graph in which a plurality of data blocks in the database each correspond to one of a plurality of vertices, and in which at least one affinity between objects corresponds to at least one edge;
• and
• constructing a weighted simpler graph, comprising:
• a plurality of final vertices, each corresponding to at least two of the vertices from the base graph;
• and
• at least one final edge corresponding to at least one of the edges in the base graph;
• and
• selecting a simple partition for the simpler graph;
• and
• determining a final partition for the data in the database from the simple partition of the simpler graph;
• and
• wherein at least one weight of at least one edge is assigned using information provided by an application developer.

A method for positioning data in a database, comprising:

• providing a schema of the database defining at least one collection and at least one predefined set of derived access types;
• and
• constructing a weighted base graph in which a plurality of data blocks in the database each correspond to one of a plurality of vertices, and in which at least one affinity between objects corresponds to at least one edge, the constructing comprising:
• selecting at least one derived access type from the predefined set for the at least one collection of the schema of the database;
• and
• assigning at least one weight to at least one edge corresponding to at least one relationship between data blocks comprising the collection, the at least one relationship being defined by the derived access type;
• and
• constructing a weighted simpler graph, comprising:
• a plurality of final vertices, each corresponding to at least two of the vertices from the base graph;
• and
• at least one final edge corresponding to at least one of the edges in the base graph;
• and
• selecting a simple partition for the simpler graph;
• and
• determining a final partition for the data in the database from the simple partition of the simpler graph.

A method for positioning data in a database, comprising:

• providing a schema of the database defining a first and second collection and at least one predefined set of derived access types;
• and
• constructing a weighted base graph in which a plurality of data blocks in the database each correspond to one of a plurality of vertices, and in which at least one affinity between objects corresponds to at least one edge, the constructing comprising:
• collecting statistical data on access patterns of a plurality of data blocks associated with the first collection;
• and
• selecting from the predefined set the derived access type most closely matching the statistical data;
• and
• assigning at least one weight to at least one edge corresponding to at least one relationship between data blocks associated with the second collection, the at least one relationship being defined by the derived access type;
• and
• constructing one or more intermediate graphs, each intermediate graph being a subsequent graph to one from which it is constructed and being a prior graph to a graph constructed from it, each intermediate graph comprising:
• a plurality of new vertices corresponding to pairs of vertices from the previous graph;
• and
• at least one new edge corresponding to at least one edge adjacent to one of the vertices in the pair of vertices corresponding to the new vertex adjacent to the at least one new edge;
• and
• constructing a weighted simpler graph from one of the intermediate graphs, the simpler graph comprising:
• a plurality of final vertices, each corresponding to at least one of the vertices from the base graph;
• and
• at least one final edge corresponding to at least one of the edges in the base graph;
• and
• selecting a simple partition for the simpler graph;
• and
• determining a penultimate partition for the base graph wherein each group comprises every parent vertex to any daughter vertex in the simpler graph if the group comprises at least one parent vertex to that daughter vertex;
• and
• determining a rough distribution of the data blocks in which a given data block is positioned on the a page with each data block with which the given data block shares an adjacent edge, unless that edge is cut in the penultimate partition;
• and
• refining the rough distribution by moving at least one data block from the page on which it was positioned during the determining a rough distribution of the data blocks.

A method of positioning a first new data block of data on a page, comprising:

• buffering the first new data block in server memory;
• selecting a page containing data blocks having a high collective affinity for the first new data block;
• and
• positioning the first new data block the page containing data blocks having a high collective affinity for the first new data block.