# US 9,436,721 B2 · Optimization of mixed database workload scheduling and concurrency control by mining data dependency relationships via lock tracking > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,436,721 B2 - Document ID: US9436721B2 - Status: Granted - Kind: B2 - Application number: 14/193,221 - Filed: 2014-02-28 - Published: 2015-09-03 - Granted: 2016-09-06 - Earliest claimed: 2014-02-28 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Donna N. Dillenberger; Hubertus Franke; Hong Min; Yefim Shuf - Web page: https://patentgrep.com/patent/US9436721B2 ## CPC - G06F 16/2343: {Locking methods, e.g. distributed locking or locking implementation details} - G06F 16/217: {Database tuning (G06F16/2282 takes precedence; database performance monitoring G06F11/3409)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract The present disclosure relates generally to the field of determining data access patterns associated with different workloads. In various examples, determining data access patterns associated with different workloads may be implemented in the form of systems, methods and/or algorithms. The present disclosure also relates generally to the field of scheduling workloads (and/or recommending scheduling for workloads) based upon the determined data access patterns associated with the different workloads. In various examples, scheduling workloads (and/or recommending scheduling for workloads) may be implemented in the form of systems, methods and/or algorithms. ## Claims ### Claim 1 A method for workload scheduling, the method comprising: obtaining, by a processor, first lock trace data associated with a plurality of workloads, the first lock trace data relating to a first set of objects; replaying, by the processor, the first lock trace data associated with the workloads to identify first data access conflicts between a first one of the workloads and a second one of the workloads; determining by the processor, based upon the identified first data access conflicts associated with the first lock trace data, a subset of the first set of objects; obtaining, by the processor, second lock trace data associated with the workloads, the second lock trace data relating to the subset of objects; replaying, by the processor, the second lock trace data associated with the workloads to identify second data access conflicts between the first one of the workloads and the second one of the workloads; decomposing by the processor, based at least in part upon the identified second data access conflicts, at least the first one of the workloads into a plurality of shorter duration execution units; and scheduling, by the processor, at least one of the shorter duration execution units at a first time window that at least partially overlaps a second time window of at least the second one of the workloads. ### Claim 2 (depends on 1) The method of claim 1, wherein the first workload is a first application and the second workload is a second application that is different from the first application. ### Claim 3 (depends on 2) The method of claim 2, wherein: (a) each of the first and second applications is an OLTP application; or (b) each of the first and second applications is a Batch processing application. ### Claim 4 (depends on 1) The method of claim 1, wherein each of the first and second lock trace data is obtained from at least one of: (a) one or more application lock managers; (b) one or more subsystem lock managers; or (c) a combination thereof. ### Claim 5 (depends on 1) The method of claim 1, wherein each of the workloads has associated therewith respective first and second lock trace data. ### Claim 6 (depends on 1) The method of claim 1, wherein each of the first and second lock trace data comprises at least one of: (a) a lock target object; (b) a lock type; (c) a lock timestamp; (d) a lock duration; and (e) a combination thereof. ### Claim 7 (depends on 1) The method of claim 1, wherein the replay of the first and second lock trace data identifies at least one data access conflict at a desired granularity selected from a plurality granularities. ### Claim 8 (depends on 7) The method of claim 7, wherein the selected granularity comprises one of: (a) database table; (b) database page; (c) database record; (d) a database column; (e) a database; (f) a data set; (g) a collection thereof that has some association among them either logical or via referential integrity constraints; or (h) any combination thereof. ### Claim 9 (depends on 1) The method of claim 1, wherein: each of the objects of the first set of objects and each of the objects of the subset of objects is a table; each of the objects of the subset of objects is one of the tables of the first set of objects; and the second lock trace data relates to the tables of the subset of objects but not to the tables of the first set of objects. ### Claim 10 (depends on 1) The method of claim 1, wherein: each of the objects of the first set of objects and each of the objects of the subset of objects is a partition; and each of the objects of the subset of objects is one of the partitions of the first set of objects; and the second lock trace data relates to the partitions of the subset of objects but not to the partitions of the first set of objects. ### Claim 11 (depends on 1) The method of claim 1, wherein the objects in the subset of objects are determined based upon an amount of the first data access conflicts associated with the first set of objects. ### Claim 12 (depends on 1) The method of claim 1, wherein the objects in the first set of objects and the objects in the subset of objects are database objects. ### Claim 13 A computer readable storage medium, tangibly embodying a program of instructions executable by the computer for workload scheduling, the program of instructions, when executing, performing the following steps: obtaining first lock trace data associated with a plurality of workloads, the first lock trace data relating to a first set of objects; replaying the first lock trace data associated with the workloads to identify first data access conflicts between a first one of the workloads and a second one of the workloads; determining, based upon the identified first data access conflicts associated with the first lock trace data, a subset of the first set of objects; obtaining second lock trace data associated with the workloads, the second lock trace data relating to the subset of objects, replaying the second lock trace data associated with the workloads to identify second data access conflicts between the first one of the workloads and the second one of the workloads; decomposing, based at least in part upon the identified second data access conflicts, at least the first one of the workloads into a plurality of shorter duration execution units; and scheduling at least one of the shorter duration execution units at a first time window that at least partially overlaps a second time window of at least the second one of the workloads. ### Claim 14 (depends on 13) The computer readable storage medium of claim 13, wherein the first workload is a first application and the second workload is a second application that is different from the first application. ### Claim 15 (depends on 14) The computer readable storage medium of claim 14, wherein: (a) each of the first and second applications is an OLTP application; or (b) each of the first and second applications is a Batch processing application. ### Claim 16 (depends on 13) The computer readable storage medium of claim 13, wherein each of the first and second lock trace data is obtained from at least one of: (a) one or more application lock managers; (b) one or more subsystem lock managers; or (c) a combination thereof. ### Claim 17 A computer-implemented system for workload scheduling, the system comprising: a processor; and a memory storing computer readable instructions that, when executed by the processor, implement: obtaining first lock trace data associated with a plurality of workloads, the first lock trace data relating to a first set of objects; replaying the first lock trace data associated with the workloads to identify first data access conflicts between a first one of the workloads and a second one of the workloads; determining, based upon the identified first data access conflicts associated with the first lock trace data, a subset of the first set of objects; obtaining second lock trace data associated with the workloads, the second lock trace data relating to the subset of objects; replaying the second lock trace data associated with the workloads to identify second data access conflicts between the first one of the workloads and the second one of the workloads; decomposing, based at least in part upon the identified second data access conflicts, at least the first one of the workloads into a plurality of shorter duration execution units; and scheduling at least one of the shorter duration execution units at a first time window that at least partially overlaps a second time window of at least the second one of the workloads. ### Claim 18 (depends on 17) The system of claim 17, wherein: (a) each of the first and second applications is an OLTP application; or (b) each of the first and second applications is a Batch processing application. ### Claim 19 (depends on 17) The system of claim 17, wherein each of the first and second lock trace data is obtained from at least one of: (a) one or more application lock managers; (b) one or more subsystem lock managers; or (c) a combination thereof. ### Claim 20 (depends on 17) The system of claim 17, wherein the computer readable instructions, when executed by the processor, implement outputting the schedule of the at least one of the shorter duration execution units at the first time window that at least partially overlaps the second time window.