# US 12,007,881 B2 · Method for populating spanner databases in test environments > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,007,881 B2 - Document ID: US12007881B2 - Status: Granted - Kind: B2 - Application number: 17/555,659 - Filed: 2021-12-20 - Published: 2023-06-22 - Granted: 2024-06-11 - Earliest claimed: 2021-12-20 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Srinath Badrinath; Everett Maus; Danhao Guo; Carlos Arguelles - Web page: https://patentgrep.com/patent/US12007881B2 ## CPC - G06F 11/3688: {for test execution, e.g. scheduling of test suites} - G06F 11/3684: {for test design, e.g. generating new test cases} - G06F 11/3696: {Methods or tools to render software testable} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method of populating a test environment for integration testing of a production database. The production database includes a plurality of tables, and may be represented by a directed acyclic graph (DAG), in which each of the plurality of tables is represented by a respective node of the DAG and schema-level constraints of the plurality of tables are represented by edges of the DAG. The method may involve constructing the DAG, topologically ordering the plurality of tables of the production database according to the DAG, randomly generating test data in accordance with the schema-level constraints of the plurality of tables, and populating the randomly generated test data to the test environment according to the topological ordering of the plurality of tables. ## Claims ### Claim 1 A method of populating a test environment for testing of a production database comprising a plurality of tables, the method comprising: constructing, by one or more processors, a directed acyclic graph (DAG), wherein each of the plurality of tables is represented by a respective node of the DAG and schema-level constraints of the plurality of tables are represented by edges of the DAG; topologically ordering, by the one or more processors, the plurality of tables of the production database into a sorted table according to the DAG; dividing, by the one or more processors, the sorted table into a plurality of portions based on table size information about the plurality of tables; assigning, by the one or more processors, each of the portions of the sorted table to a respective one of a plurality of data generators; instructing, by the one or more processors, the plurality of data generators to randomly generate test data in parallel; and populating, by the one or more processors, the randomly generated test data when it satisfies the schema-level constraints of the plurality of tables to the test environment according to the topological ordering of the plurality of tables. ### Claim 2 (depends on 1) The method of claim 1, wherein the schema-level constraints of the plurality of tables include both foreign keys and interleaving, and wherein the topological ordering is based on both the foreign keys and the interleaving. ### Claim 3 (depends on 1) The method of claim 1, wherein the test data is generated by one or more data generators, each including a satisfiability modulo theories (SMT) solver for determining, for a given table of the plurality of tables, whether the randomly generated data satisfies a data type and the schema-level constraints of the given table. ### Claim 4 (depends on 3) The method of claim 3, wherein the plurality of data generators are a plurality of independent platform agnostic data generators. ### Claim 5 (depends on 4) The method of claim 4, further comprising: for each table of the plurality of tables, splitting, by the one or more processors, the table into a plurality of key ranges according to a plurality of key values, wherein each key value is a split point; generating, by the one or more processors, a work pool comprising a plurality of work units, each work unit associated with a respective table of the plurality of tables and a respective key range of the plurality of key ranges; and assigning, by the one or more processors, the plurality of work units to the plurality of data generators. ### Claim 6 (depends on 5) The method of claim 5, wherein splitting the table into a plurality of key ranges comprises: for each table of the plurality of tables, estimating, by the one or more processors, a number of bytes-per-row of the table; and determining, by the one or more processors, a balanced distribution of data across the plurality of key ranges based on a number of rows to generate and the estimated number of bytes-per-row of each table. ### Claim 7 (depends on 5) The method of claim 5, further comprising: determining, by the one or more processors, an amount of data to populate each table of the test environment with; and determining, by the one or more processors, a number of the plurality of key values based at least in part on the determined amount of data. ### Claim 8 (depends on 1) The method of claim 1, further comprising: for a given table of the plurality of tables, determining, by the one or more processors, one or more data constraints based on data contained in the given table; and constraining, by the one or more processors, the randomly generated test data for a corresponding table of the test environment based on the one or more data constraints. ### Claim 9 (depends on 8) The method of claim 8, wherein the one or more data constraints includes at least one of: a dataset range; a dataset distribution; and a number of unique dataset elements. ### Claim 10 (depends on 1) The method of claim 1, further comprising: writing the randomly generated test data to a mutation pool associated with a given table of the test environment; and in response to a size of a transaction of the mutation pool's contents to the given table of the test environment meeting or exceeding a threshold transaction value, flushing the mutation pool. ### Claim 11 (depends on 1) The method of claim 1, wherein the plurality of portions have sizes generated according to an approximation function. ### Claim 12 A system for populating a test environment for testing a production database comprising a plurality of tables, the system comprising: memory storing a representation of a directed acyclic graph (DAG), wherein each of the plurality of tables is represented by a respective node of the DAG and schema-level constraints of the plurality of tables are represented by edges of the DAG; and one or more processors configured to: topologically order the plurality of tables of the production database into a sorted table according to the DAG; divide the sorted table into a plurality of portions based on table size information about the plurality of tables; assign each of the portions of the sorted table to a respective one of a plurality of data generators instruct the plurality of data generators to randomly generate test data in parallel in accordance with the schema-level constraints of the plurality of tables; and populate the randomly generated test data to the test environment according to the topological ordering of the plurality of tables. ### Claim 13 (depends on 12) The system of claim 12, wherein the schema-level constraints of the plurality of tables include both foreign keys and interleaving, and wherein the one or more processors are configured to topologically order the plurality of tables based on both the foreign keys and the interleaving. ### Claim 14 (depends on 13) The system of claim 13, wherein the one or more processors are configured to randomly generate the test data using a plurality of SMT solvers operating in parallel. ### Claim 15 (depends on 14) The system of claim 14, wherein the one or more processors are configured to: for each table of the plurality of tables, split the table into a plurality of key ranges according to a plurality of key values, wherein each key value is a split point; generate a work pool comprising a plurality of work units, each work unit associated with a respective table of the plurality of tables and a respective key range of the plurality of key ranges; and assign the plurality of work units to the plurality of data generators. ### Claim 16 (depends on 15) The system of claim 15, wherein the one or more processors are configured to: for each table of the plurality of tables, estimate a number of bytes-per-row of the table; and determine a balanced distribution of data across the plurality of key ranges based on a number of rows to generate and the estimated number of bytes-per-row of each table. ### Claim 17 (depends on 15) The system of claim 15, wherein the one or more processors are configured to: determine an amount of data to populate each table of the test environment with; and determine a number of the plurality of key values based at least in part on the determined amount of data. ### Claim 18 (depends on 12) The system of claim 12, wherein the one or more processors are configured to generate the test data using a satisfiability modulo theories (SMT) solver for determining, for a given table of the plurality of tables, whether the randomly generated data satisfies a data type and the schema-level constraints of the given table. ### Claim 19 (depends on 12) The system of claim 12, wherein the one or more processors are configured to: for a given table of the plurality of tables, determine one or more data constraints based on data contained in the given table; and constrain the randomly generated test data for a corresponding table of the test environment based on the one or more data constraints. ### Claim 20 (depends on 12) The system of claim 12, wherein the one or more processors are configured to: write the randomly generated test data to a mutation pool associated with a given table of the test environment; and in response to a size of a transaction of the mutation pool's contents to the given table of the test environment meeting or exceeding a threshold transaction value, flush the mutation pool. ### Claim 21 (depends on 12) The system of claim 12, wherein the production database is a Spanner database. ### Claim 22 (depends on 12) The system of claim 12, wherein the plurality of portions have sizes generated according to an approximation function.