Entity database

• US 10,474,655 B1
• Filed: 07/23/2018
• Issued: 11/12/2019
• Est. Priority Date: 07/23/2018
• Status: Active Grant

• Current Assignee: Improbable Worlds Ltd.
• Original Assignee: Improbable Worlds Ltd.
• Inventors: Lewis, Matthew John Reveley
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US16/042,068
• Time in Patent Office: 477 Days
• Field of Search: 707E17014, 707769, 707999005, 707E1711, 707743
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

Database schemas, systems, and methods are described herein which enhance database operations when responding to streaming (subscribed) queries regarding records stored in the database. A database schema may include a data table storing a plurality of records each having a plurality of data fields. The schema may also include a query table, and a query index table or tree, or other data structure. The data table stores the current state of each record as defined by its associated data fields. The query table stores all queries mapped to the one or more clients that have subscribed to each query. The query index table, tree, or other data structure indexes the subscribed queries based on a data field common to or associated with the indexed queries. Subsequently, when records and data fields are updated (mutated) in the database, the query index data structure can be used to quickly assess which subscribed clients need to be sent updates with mutated data, so that only the clients who have subscribed to receive updates based on a particular data field do so and the cost of identifying those clients is greatly reduced.

Claims

1. A method comprising:

receiving, from a client, a request to subscribe to a query on a database storing a plurality of records, wherein each record has a plurality of data fields;

storing a client ID, the query, and a corresponding unique query ID as a new record in a query data structure storing a plurality of query records;

storing in a new record of a query index data structure the query ID and a second data field defining a location within a multidimensional space, wherein the query index data structure is indexed based on the second data field, wherein the second data field is related to one of the plurality of data fields, and wherein the query index data structure maps each query to a region of the multidimensional space;

establishing a persistent connection with the client; and

until the persistent connection is terminated;

determining, responsive to any update to one or more records, and based on the query index data structure, one or more queries of interest whose corresponding region of the multidimensional space encompasses at least one updated record; and

when the one or more queries of interest comprises the query, sending information to the client about each updated record satisfying the query.

2. The method of claim 1, wherein each record of the plurality of records defines an entity being simulated in a multidimensional spatial environment, and wherein each data field of the plurality of data fields represents a different component of that entity.

3. The method of claim 1, wherein the query index data structure comprises an R-tree.

4. The method of claim 1, wherein the computer readable instructions, when executed, further cause the device to configure a record position data structure to index each record based on its associated location within the multidimensional space, wherein the record position data structure indexes the current location of each record based on the unique entity ID of each record.

5. The method of claim 1, wherein the region of multidimensional space is defined by one of a sphere, cylinder, polyhedron, or rectangle.

6. The method of claim 1, wherein the database is sharded based on record ID.

7. One or more non-transitory computer readable storage media comprising computer readable instructions that, when executed, cause a device to perform:

receiving, from a client, a request to subscribe to a query on a database storing a plurality of records, wherein each record has a plurality of data fields;

storing a client ID, the query, and a corresponding unique query ID as a record in a query data structure;

storing in a new record of a query index data structure the query ID and a second data field defining a location within a multidimensional space, wherein the query index data structure is indexed based on the second data field, wherein the second data field is related to one of the plurality of data fields, and wherein the query index data structure maps each query to a region of the multidimensional space;

establishing a persistent connection with the client; and

until the persistent connection is terminated;

determining, responsive to any update to one or more records of the plurality of records in the database, and based on the query index data structure, one or more queries of interest whose corresponding region of the multidimensional space encompasses at least one updated record; and

when the one or more queries of interest comprises the query, sending information to the client about each updated record satisfying the query.

8. The computer readable storage media of claim 7, wherein the query data structure stores the client ID in a list, wherein each client ID stored in the list corresponds to a different client subscribed to the query.

9. The computer readable storage media of claim 7, wherein the location is multidimensional.

10. The computer readable storage media of claim 7, wherein each record of the plurality of records defines an entity being simulated in a multidimensional spatial environment, and wherein each data field of the plurality of data fields represents a different component of that entity.

11. The computer readable storage media of claim 7, wherein the query index data structure comprises an R-tree.

12. The computer readable storage media of claim 7, wherein the computer readable instructions, when executed, further cause the device to perform:

configuring a record position data structure to index each record based on its associated location within the multidimensional space, wherein the record position data structure indexes the current location of each record based on the unique record ID of each record; and

responsive to a record changing location, updating the record position data structure to reflect the current location of the record.

13. The computer readable storage media of claim 7, wherein the region of multidimensional space is defined by one of a sphere, cylinder, polyhedron, or rectangle.

14. The computer readable storage media of claim 7, wherein the database is sharded based on record ID.

15. A method comprising:

receiving, from a client, a request to subscribe to a query on a database storing a plurality of records, wherein each record represents an entity being simulated in a multidimensional spatial environment, and wherein each data field of a plurality of data fields within each record represents a different component of that entity, and wherein the plurality of data fields comprises a first data field storing a geographic location of the entity within the multidimensional spatial environment;

storing a client ID, the query, and a corresponding unique query ID in a record of a query data structure;

storing the query ID and a second data field in a record of a query index data structure indexed based on the second data field, wherein the second data field, for each query ID, defines an associated spatial region of interest within the multidimensional spatial environment;

establishing a persistent connection with the client; and

until the persistent connection is terminated;

determining, responsive to an update to one or more records of the plurality of records in the database, a list of one or more queries for which the update is within the associated region of interest;

determining one or more clients subscribed to each query in the list of one or more queries; and

sending, to each subscribed client, updated records within the associated region of interest for each query to which the client is subscribed.