Sorted database table

Abstract

A method for updating a partially ordered database, the method includes (a) obtaining, by a merge circuit, density values of multiple sorted table chunks of the partially ordered database, wherein a density value of each sorted table chunk is indicative of a relationship between a number of populated rows of the sorted table chunk and a width of the sorted table chunk, wherein the width of the sorted table chunk is determined based on (i) values of sort keys of the sorted table chunk, and (ii) a parameter of a distribution of values of sort keys of the partially ordered database; each sort key is associated with a row of a table of the partially ordered database and represents values of multiple cells of the row; (b) merging, by the merge circuit, a set of sorted table chunks to provide a new sorted table chunk that exhibits a density value that exceeds a density value of each sorted table chunk of the set; and (c) replacing, in a storage unit of a storage system, the set of sorted table chunks by the new sorted table chunk.

Dependencies are inferred from the claim text.