FIELD OF THE INVENTION

The present invention relates to database systems and, more specifically, to database systems in which sharded tables store semi-structured data items.

BACKGROUND

Database systems that store increasingly large amounts of data are becoming more and more prevalent. For example, online transaction processing (OLTP) systems, such as e-commerce, mobile, social, and Software-as-a-Service (SaaS) system, typically require large database storage. Example applications for OLTP systems include, but are not limited to, large billing systems, ticketing systems, online financial services, media companies, online information services, and social media companies. Given the significant amount of data stored by these database systems, storing all the data on a single database instance is not practical, as the amount of data can utilize significant computing resources, such as processors, memory, and storage.

Furthermore, non-relational databases, sometimes referred to as NoSQL databases, do not provide the fully featured benefits of a relational database. For example, NoSQL databases do not offer the same schema control, atomicity, consistency, isolation, durability, or fully-featured structured query language (SQL) of a relational database.

To more efficiently handle well-structured relational data, techniques have been developed for “horizontally partitioning” a database. Horizontal partitioning involves decomposing a single larger table into smaller, more manageable subsets of information, called “partitions.” Sharding is a data tier architecture where data is horizontally partitioned across independent database instances, where each independent database instance is referred to as a “shard.” A collection of shards, together, makes up a single logical database which is referred to as a “sharded database” (“SDB”). Logically, a sharded database can be accessible to a client application just like a traditional unsharded database. However, tables in a sharded database are horizontally partitioned across shards.

FIG. 1illustrates an example of an unsharded database100and a sharded database110. Unsharded database100is a relational database and includes table102. All of the contents of table102are stored in the same unsharded database100, and thus use the same computing resources, such as processors, memory, and disk space.

Sharded database110, however, depicts an alternative configuration using sharding techniques. Sharded database110, includes three shards112,114, and116. Each of the shards112,114, and116is its own database instance and includes its own tables113,115, and117, respectively. However, in sharded database110, table102has been horizontally partitioned across shards112,114, and116into tables113,115, and117. Horizontal partitioning in a sharded database involves splitting a database table, such as table102, across shards so that each shard contains a subset of rows of table102. In this example, tables113,115, and117each contain a subset of rows of table102. Collectively, tables113,115, and117can be referred to as a “sharded table.” The data collectively stored in tables113,115, and117is equivalent to the data stored in table102. Sharded database110is logically treated as a single database, and thus can be accessible by client applications just like unsharded database100.

FIG. 2is a block diagram of a sharded database system. Client application210is any sort of client application that requires access to data stored in a database. Sharded database250is a logical database where data is horizontally partitioned across independent database instances. Specifically, data stored in sharded database250is horizontally partitioned and stored in shards260A,260B, and260C. A sharded database may include any number of shards, and the number of shards in a sharded database may vary over time. Each of shards260A,260B, and260C may be its own database instance that does need to share physical resources, such as processors, memory, and/or storage device, with other shards in the sharded database250.

Shard catalogue230is a special database system that is used to store configuration data for the sharded database250and may include, for example: a routing table that maps which shard stores a chunk of data that corresponds to a given value, range of values, or set of values of a sharding key, shard topology data, the configuration of the shards260A,260B, and260C, the configuration of the catalog server220, information about the client application210, etc. Catalog server220coordinates various functionalities across the sharded database250, including, but not limited to: routing database requests to shards, propagating database schema changes to shards, monitoring the status of shards, receiving status updates from shards, receiving notifications from client applications, sending notifications to shards, sending notifications to client applications, and/or coordinating various operations that affect the configuration of the sharded database260, such as resharding operations.

The horizontal partitioning techniques used by a sharded database improve scalability by eliminating performance bottlenecks and making it possible to increase performance and capacity of the system by adding additional shards and distributing load across shards. However, even when conventional relational database systems employ horizontally-partitioning, the needs of all users are not adequately addressed because those systems do not provide an agile document-object storage model that allows schema-less query, indexing, and search capability. Consequently, for users who deal with semi-structured data and unstructured data, horizontally partitioning a conventional relational table is insufficient. The term “semi-structured and unstructured data” refers to data items that are not known to strictly conform to any explicitly defined schema. Users who want to enjoy horizontal partitioning with both structured and unstructured data typically have to maintain multiple sharding systems and build a home-grown middle-tier to integrate both systems. Therefore, there is a clear need for a system that provides the benefits of horizontal partitioning regardless of whether the underlying data is fully-structured, semi-structured, unstructured, or any combination thereof.

The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.

