DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-20 are pending in this application.
Double Patenting
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the conflicting claims are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, e.g., In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998); In re Goodman, 11 F.3d 1046, 29 USPQ2d 2010 (Fed. Cir. 1993); In re Longi, 759 F.2d 887, 225 USPQ 645 (Fed. Cir. 1985); In re Van Ornum, 686 F.2d 937, 214 USPQ 761 (CCPA 1982); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); In re Thorington, 418 F.2d 528, 163 USPQ 644 (CCPA 1969).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on nonstatutory double patenting provided the reference application or patent either is shown to be commonly owned with the examined application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. See MPEP § 717.02 for applications subject to examination under the first inventor to file provisions of the AIA as explained in MPEP § 2159. See MPEP § 2146 et seq. for applications not subject to examination under the first inventor to file provisions of the AIA . A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The filing of a terminal disclaimer by itself is not a complete reply to a nonstatutory double patenting (NSDP) rejection. A complete reply requires that the terminal disclaimer be accompanied by a reply requesting reconsideration of the prior Office action. Even where the NSDP rejection is provisional the reply must be complete. See MPEP § 804, subsection I.B.1. For a reply to a non-final Office action, see 37 CFR 1.111(a). For a reply to final Office action, see 37 CFR 1.113(c). A request for reconsideration while not provided for in 37 CFR 1.113(c) may be filed after final for consideration. See MPEP §§ 706.07(e) and 714.13.
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The actual filing date of the application in which the form is filed determines what form (e.g., PTO/SB/25, PTO/SB/26, PTO/AIA /25, or PTO/AIA /26) should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to www.uspto.gov/patents/apply/applying-online/eterminal-disclaimer.
Claims 1-20 are rejected on the ground of nonstatutory double patenting as being unpatentable over claims 1-20 of U.S. Patent No. 12,530,336. Although the claims at issue are not identical, they are not patentably distinct from each other because the claims of US Pat No 12,530,336 anticipate the claims of the instant application as set forth in the table below.
Instant Application
US Pat No. 12,530,336
1. A method for training an index selection agent for iteratively determining an index set I to be used when running queries against a database, the method being implemented in a computer system with a physical processing unit and a physical storage device, the computer system storing the database with K attributes in the physical storage device, the method comprising the following phases:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries; and
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set,
(c) determining a reward based on the action taken, and
(d) repeating steps (a) to (c) until an end condition is met, wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, and wherein the index selection agent comprises an artificial neural network, wherein an input of the artificial neural network is the numerical representation of the one or more operators.
1. A method for training an index selection agent for iteratively determining an index set I to be used when running queries against a database, the method being implemented in a computer system with a physical processing unit and a physical storage device, the computer system storing the database with K attributes in the physical storage device, the method comprising the following phases:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries; and
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set,
(c) determining a reward based on the action taken, and
(d) repeating steps (a) to (c) until an end condition is met, wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, wherein the index selection agent comprises an artificial neural network, wherein an input of the artificial neural network is the numerical representation of the one or more operators, wherein determining the at least one episodic workload further comprises:
generating, by the computer system, a representative plan using a set of index candidates and the set of representative queries, and wherein generating the episodic workload includes generating the episodic workload using the representative plan.
2. The method of claim 1, wherein the phase of training the index selection agent further comprises the step of updating, by the computer system, the index selection agent based on at least one of the current states determined, the actions taken, and a set of rewards determined during training.
2. The method of claim 1, wherein the phase of training the index selection agent further comprises the step of updating, by the computer system, the index selection agent based on at least one of the current states determined, the actions taken, and a set of rewards determined during training.
3. The method of claim 1, wherein the step of determining the current state of the environment is based on costs for at least one of the queries contained in the episodic workload given the current index set, wherein said costs are estimated using a what-if optimizer.
3. The method of claim 1 wherein the step of determining the current state of the environment is based on costs for at least one of the queries contained in the episodic workload given the current index set, wherein said costs are estimated using a what-if optimizer.
4. The method of claim 1, wherein the action space, from which the action is taken, is a restricted action space.
4. The method of claim 1 wherein the action space, from which the action is taken, is a restricted action space.
5. The method of claim 4, wherein the step of taking an action includes determining the restricted action space based on at least one of the current episodic workload, a storage budget, and at least one previous action taken by the index selection agent.
5. The method of claim 4 wherein the step of taking an action includes determining the restricted action space based on at least one of the current episodic workload, a storage budget, and at least one previous action taken by the index selection agent.
6. The method of claim 1, wherein the state of the environment is represented by features, the features including at least one of:
a representation of the episodic workload, a representation of costs per query for at least one class of queries contained in the episodic workload with the current index configuration, a representation of a current storage budget and consumption with the current index configuration, and a representation of the current index configuration.
6. The method of claim 1 wherein the state of the environment is represented by features, the features including at least one of:
a representation of the episodic workload, a representation of costs per query for at least one class of queries contained in the episodic workload with the current index configuration, a representation of a current storage budget and consumption with the current index configuration, and a representation of the current index configuration.
7. The method of claim 1, wherein the state of the environment is represented by features relating to at least three aspects:
the episodic workload, meta information, and the current index configuration.
7. The method of claim 1 wherein the state of the environment is represented by features relating to at least three aspects:
the episodic workload, meta information, and the current index configuration.
8. The method of claim 7, characterized in that the meta information relates to one or more of a current storage consumption, a storage budget, an initial cost for executing the episodic workload, and a current cost for executing the episodic workload.
8. The method of claim 7 characterized in that the meta information relates to one or more of a current storage consumption, a storage budget, an initial cost for executing the episodic workload, and a current cost for executing the episodic workload.
9. The method of claim 1, wherein the reward is determined based on an additional relative reduction of workload costs of an index selection per additional utilized storage.
9. The method of claim 1 wherein the reward is determined based on an additional relative reduction of workload costs of an index selection per additional utilized storage.
10. The method of claim 1, wherein the end condition is at least one of:
an index storage consumption exceeding a storage budget, a predefined maximum number of construction steps being reached, a predefined maximum number of indexes being reached, and no or no significant further improvement being achieved by adding an index candidate to the current index set.
10. The method of claim 1 wherein the end condition is at least one of:
an index storage consumption exceeding a storage budget, a predefined maximum number of construction steps being reached, a predefined maximum number of indexes being reached, and no or no significant further improvement being achieved by adding an index candidate to the current index set.
11. The method of claim 1, wherein preprocessing includes the step of determining a set of index candidates.
11. The method of claim 1 wherein preprocessing includes the step of determining a set of index candidates.
12. The method of claim 1, wherein the index selection agent takes the action based on a computation of the artificial neural network, wherein a second input of the artificial neural network is the state determined in step (a) of claim 1.
12. The method of claim 1 wherein the index selection agent takes the action based on a computation of the artificial neural network, wherein a second input of the artificial neural network is the state determined in step (a) of claim 1.
13. The method of claim 1, further comprising:
determining, by the computer system, the index set I using the index selection agent that results from the end condition having been met; and
storing, by the computer system, the index set I determined by the computer system.
13. The method of claim 1, further comprising:
determining, by the computer system, the index set I using the index selection agent that results from the end condition having been met; and
storing, by the computer system, the index set I determined by the computer system.
14. The method of claim 13, further comprising:
executing, by the computer system, a new query against the database using the index set I determined by the computer system using the index selection agent; and
outputting, by the computer system, a result of executing the new query.
14. The method of claim 13, further comprising:
executing, by the computer system, a new query against the database using the index set I determined by the computer system using the index selection agent; and
outputting, by the computer system, a result of executing the new query.
15. The method of claim 1, wherein the queries in the episodic workload correspond to one or more representative query classes.
15. The method of claim 1, wherein the queries in the episodic workload correspond to one or more representative query classes.
16. The method of claim 15, wherein each of the one or more representative query classes has a corresponding frequency of occurrence, wherein each frequency of occurrence is generated such that the index selection agent handles different query-frequency pairs.
16. The method of claim 15, wherein each of the one or more representative query classes has a corresponding frequency of occurrence, wherein each frequency of occurrence is generated such that the index selection agent handles different query-frequency pairs.
17. The method of claim 1, wherein the episodic workload includes a first set of workloads and a second set of workloads, wherein each workload in the first set of workloads has a same set of query classes with a first set of different frequencies, and wherein each workload in the second set of workloads has a different set of query classes with a second set of different frequencies.
17. The method of claim 1, wherein the episodic workload includes a first set of workloads and a second set of workloads, wherein each workload in the first set of workloads has a same set of query classes with a first set of different frequencies, and wherein each workload in the second set of workloads has a different set of query classes with a second set of different frequencies.
18. The method of claim 1, wherein constructing the numerical representation of the one or more operators includes performing dimensionality reduction on the numerical representation of the one or more operators.
18. The method of claim 1 wherein constructing the numerical representation of the one or more operators includes performing dimensionality reduction on the numerical representation of the one or more operators.
19. A computer system for training an index selection agent for iteratively determining an index set I to be used when running queries against a database, the computer system comprising:
a memory, wherein the memory is configured to store the database with K attributes in a physical storage device; and
a processor, wherein the processor is configured to control the computer system to execute a method comprising:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries; and
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set,
(c) determining a reward based on the action taken, and
(d) repeating steps (a) to (c) until an end condition is met, wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, and wherein the index selection agent comprises an artificial neural network, wherein an input of the artificial neural network is the numerical representation of the one or more operators.
19. A computer system for training an index selection agent for iteratively determining an index set I to be used when running queries against a database, the computer system comprising:
a memory, wherein the memory is configured to store the database with K attributes in a physical storage device; and
a processor, wherein the processor is configured to control the computer system to execute a method comprising:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries; and
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set,
(c) determining a reward based on the action taken, and
(d) repeating steps (a) to (c) until an end condition is met, wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, wherein the index selection agent comprises an artificial neural network, wherein an input of the artificial neural network is the numerical representation of the one or more operators, wherein determining the at least one episodic workload further comprises:
generating, by the computer system, a representative plan using a set of index candidates and the set of representative queries, and wherein generating the episodic workload includes generating the episodic workload using the representative plan.
20. A non-transitory computer-readable medium, comprising instructions which, when executed by a computer system, cause the computer system to carry out a method comprising:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries; and
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set,
(c) determining a reward based on the action taken, and
(d) repeating steps (a) to (c) until an end condition is met, wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, and wherein the index selection agent comprises an artificial neural network, wherein an input of the artificial neural network is the numerical representation of the one or more operators.
20. A non-transitory computer-readable medium, comprising instructions which, when executed by a computer system having a physical processing unit and a physical storage device, the computer system storing a database with K attributes in the physical storage device, cause the computer system to carry out a method of training an index selection agent for iteratively determining an index set I to be used when running queries against the database, the method comprising:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries; and
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set,
(c) determining a reward based on the action taken, and
(d) repeating steps (a) to (c) until an end condition is met, wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, wherein the index selection agent comprises an artificial neural network, wherein an input of the artificial neural network is the numerical representation of the one or more operators, wherein determining the at least one episodic workload further comprises:
generating, by the computer system, a representative plan using a set of index candidates and the set of representative queries, and wherein generating the episodic workload includes generating the episodic workload using the representative plan.
Claims 1-20 are rejected on the ground of nonstatutory double patenting as being unpatentable over claims 1-20 of U.S. Patent No. 12,141,117. Although the claims at issue are not identical, they are not patentably distinct from each other because claims 1-20 of US Pat. No. 12,141,117 anticipate each of claims 1-20 of the instant application as set forth in the table below.
Instant Application
US Pat. No. 12,141,117
1. A method for training an index selection agent for iteratively determining an index set I to be used when running queries against a database, the method being implemented in a computer system with a physical processing unit and a physical storage device, the computer system storing the database with K attributes in the physical storage device, the method comprising the following phases:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries; and
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set,
(c) determining a reward based on the action taken, and
(d) repeating steps (a) to (c) until an end condition is met, wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, and
wherein the index selection agent comprises an artificial neural network, wherein an input of the artificial neural network is the numerical representation of the one or more operators.
1. A method for training an index selection agent for iteratively determining an index set I to be used when running queries against a database, the method being implemented in a computer system with a physical processing unit and a physical storage device, the computer system storing the database with K attributes in the physical storage device, the method comprising the following phases:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries;
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action is adding an index candidate to the current index set,
(c) determining a reward based on the action taken,
(d) repeating steps (a) to (c) until an end condition is met,
wherein the phase of training the index selection agent further comprises the step of updating, by the computer system, the index selection agent based on at least one of the current states determined, the actions taken, and a set of rewards determined during training, wherein determining the at least one episodic workload comprises:
generating, by the computer system, a representative plan using a set of index candidates and a set of representative queries; and
generating, by the computer system, the episodic workload using the representative plan, wherein generating the episodic workload includes constructing a numerical representation of one or more operators in the set of representative queries used to generate the representative plan, and
wherein the index selection agent comprises an artificial neural network, wherein an input of the artificial neural network is the numerical representation of the one or more operators.
2. The method of claim 1, wherein the phase of training the index selection agent further comprises the step of updating, by the computer system, the index selection agent based on at least one of the current states determined, the actions taken, and a set of rewards determined during training.
1. A method…
wherein the phase of training the index selection agent further comprises the step of updating, by the computer system, the index selection agent based on at least one of the current states determined, the actions taken, and a set of rewards determined during training,…
3. The method of claim 1, wherein the step of determining the current state of the environment is based on costs for at least one of the queries contained in the episodic workload given the current index set, wherein said costs are estimated using a what-if optimizer.
2. The method of claim 1 wherein the step of determining of the current state of the environment is based on costs for at least one of the queries contained in the episodic workload given the current index set, wherein said costs are estimated using a what-if optimizer.
4. The method of claim 1, wherein the action space, from which the action is taken, is a restricted action space.
3. The method of claim 1 wherein the action space, from which the action is taken, is a restricted action space.
5. The method of claim 4, wherein the step of taking an action includes determining the restricted action space based on at least one of the current episodic workload, a storage budget, and at least one previous action taken by the index selection agent.
4. The method of claim 3 wherein the step of taking an action includes determining the restricted action space based on at least one of the current episodic workload, a storage budget, and at least one previous action taken by the index selection agent.
6. The method of claim 1, wherein the state of the environment is represented by features, the features including at least one of:
a representation of the episodic workload, a representation of costs per query for at least one class of queries contained in the episodic workload with the current index configuration, a representation of a current storage budget and consumption with the current index configuration, and a representation of the current index configuration.
5. The method of claim 1 wherein the state of the environment is represented by features, the features including at least one of:
a representation of the episodic workload, a representation of costs per query for at least one class of queries contained in the episodic workload with the current index configuration, a representation of a current storage budget and consumption with the current index configuration, and a representation of the current index configuration.
7. The method of claim 1, wherein the state of the environment is represented by features relating to at least three aspects:
the episodic workload, meta information, and the current index configuration.
6. The method of claim 1 wherein the state of the environment is represented by features relating to three aspects:
the episodic workload, meta information, and the current index configuration.
8. The method of claim 7, characterized in that the meta information relates to one or more of a current storage consumption, a storage budget, an initial cost for executing the episodic workload, and a current cost for executing the episodic workload.
7. The method of claim 6 characterized in that the meta information relates to a current storage consumption, a storage budget, an initial cost for executing the episodic workload, and a current cost for executing the episodic workload.
9. The method of claim 1, wherein the reward is determined based on an additional relative reduction of workload costs of an index selection per additional utilized storage.
8. The method of claim 1 wherein the reward is determined based on an additional relative reduction of workload costs of an index selection per additional utilized storage.
10. The method of claim 1, wherein the end condition is at least one of:
an index storage consumption exceeding a storage budget, a predefined maximum number of construction steps being reached, a predefined maximum number of indexes being reached, and no or no significant further improvement being achieved by adding an index candidate to the current index set.
9. The method of claim 1 wherein the end condition is at least one of:
an index storage consumption exceeding a storage budget, a predefined maximum number of construction steps being reached, a predefined maximum number of indexes being reached, and no or no significant further improvement being achieved by adding an index candidate to the current index set.
11. The method of claim 1, wherein preprocessing includes the step of determining a set of index candidates.
10. The method of claim 1 wherein preprocessing includes the step of determining a set of index candidates.
12. The method of claim 1, wherein the index selection agent takes the action based on a computation of the artificial neural network, wherein a second input of the artificial neural network is the state determined in step (a) of claim 1.
11. The method of claim 1 wherein the index selection agent takes the action based on a computation of the artificial neural network, wherein a second input of the artificial neural network is the state determined in step (a) of claim 1.
13. The method of claim 1, further comprising:
determining, by the computer system, the index set I using the index selection agent that results from the end condition having been met; and
storing, by the computer system, the index set I determined by the computer system.
12. The method of claim 1, further comprising:
determining, by the computer system, the index set I using the index selection agent that results from the end condition having been met; and
storing, by the computer system, the index set I determined by the computer system.
14. The method of claim 13, further comprising:
executing, by the computer system, a new query against the database using the index set I determined by the computer system using the index selection agent; and
outputting, by the computer system, a result of executing the new query.
13. The method of claim 12, further comprising:
executing, by the computer system, a new query against the database using the index set I determined by the computer system using the index selection agent; and
outputting, by the computer system, a result of executing the new query.
15. The method of claim 1, wherein the queries in the episodic workload correspond to one or more representative query classes.
14. The method of claim 1, wherein the queries in the episodic workload correspond to one or more representative query classes
16. The method of claim 15, wherein each of the one or more representative query classes has a corresponding frequency of occurrence, wherein each frequency of occurrence is generated such that the index selection agent handles different query-frequency pairs.
15. The method of claim 14, wherein each of the one or more representative classes has a corresponding frequency of occurrence, wherein each frequency of occurrence is generated such that the index selection agent handles different query-frequency pairs.
17. The method of claim 1, wherein the episodic workload includes a first set of workloads and a second set of workloads, wherein each workload in the first set of workloads has a same set of query classes with a first set of different frequencies, and wherein each workload in the second set of workloads has a different set of query classes with a second set of different frequencies.
16. The method of claim 1, wherein the episodic workload includes a first set of workloads and a second set of workloads, wherein each workload in the first set of workloads has a same set of query classes with a first set of different frequencies, and wherein each workload in the second set of workloads has a different set of query classes with a second set of different frequencies.
18. The method of claim 1, wherein constructing the numerical representation of the one or more operators includes performing dimensionality reduction on the numerical representation of the one or more operators.
18. The method of claim 1 wherein constructing the numerical representation of the one or more operators includes performing dimensionality reduction on the numerical representation of the one or more operators.
19. A computer system for training an index selection agent for iteratively determining an index set I to be used when running queries against a database, the computer system comprising:
a memory, wherein the memory is configured to store the database with K attributes in a physical storage device; and
a processor, wherein the processor is configured to control the computer system to execute a method comprising:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries; and
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set,
(c) determining a reward based on the action taken, and
(d) repeating steps (a) to (c) until an end condition is met, wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, and wherein the index selection agent comprises an artificial neural network,
wherein an input of the artificial neural network is the numerical representation of the one or more operators.
19. A computer system for training an index selection agent for iteratively determining an index set I to be used when running queries against a database, the computer system comprising:
a memory, wherein the memory is configured to store the database with K attributes in a physical storage device; and
a processor, wherein the processor is configured to control the computer system to execute a method comprising:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries;
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action is adding an index candidate to the current index set,
(c) determining a reward based on the action taken,
(d) repeating steps (a) to (c) until an end condition is met,
wherein the phase of training the index selection agent further comprises the step of updating, by the computer system, the index selection agent based on at least one of the current states determined, the actions taken, and a set of rewards determined during training, wherein determining the at least one episodic workload comprises:
generating, by the computer system, a representative plan using a set of index candidates and a set of representative queries; and
generating, by the computer system, the episodic workload using the representative plan, wherein generating the episodic workload includes constructing a numerical representation of one or more operators in the set of representative queries used to generate the representative plan, and
wherein the index selection agent comprises an artificial neural network, wherein an input of the artificial neural network is the numerical representation of the one or more operators.
20. A non-transitory computer-readable medium, comprising instructions which, when executed by a computer system, cause the computer system to carry out a method comprising:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries; and
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set,
(c) determining a reward based on the action taken, and
(d) repeating steps (a) to (c) until an end condition is met, wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, and wherein the index selection agent comprises an artificial neural network,
wherein an input of the artificial neural network is the numerical representation of the one or more operators.
20. A non-transitory computer-readable medium, comprising instructions which, when executed by a computer system, cause the computer system to carry out a method comprising:
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries;
(2) training, by the computer system, the index selection agent in at least one episode, wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set,
(b) taking an action from an action space based on the determined current state, wherein the action is adding an index candidate to the current index set,
(c) determining a reward based on the action taken,
(d) repeating steps (a) to (c) until an end condition is met,
wherein the phase of training the index selection agent further comprises the step of updating, by the computer system, the index selection agent based on at least one of the current states determined, the actions taken, and a set of rewards determined during training, wherein determining the at least one episodic workload comprises:
generating, by the computer system, a representative plan using a set of index candidates and a set of representative queries; and
generating, by the computer system, the episodic workload using the representative plan, wherein generating the episodic workload includes constructing a numerical representation of one or more operators in the set of representative queries used to generate the representative plan, and
wherein the index selection agent comprises an artificial neural network, wherein an input of the artificial neural network is the numerical representation of the one or more operators.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-4, 6, 7, 9-13, 15-17, 19, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Lai et al. (“Learning an Index Advisor with Deep Reinforcement Learning” 19 August 2021, Computer Vision – ECCV 2020, pages 178-185), hereinafter Lai, in view of Burger et al. (US 2021/0034588 A1), hereinafter Burger.
As to claim 1, Lai discloses a method for training an index selection agent for iteratively determining an index set I to be used when running queries against a database, the method being implemented in a computer system with a physical processing unit and a physical storage device, the computer system storing the database with K attributes in the physical storage device, the method comprising the following phases (Pg. 178, §1, ¶1; Pg. 179-180, §1, Regarding index selection problem, ISP, with a database D containing tables with a set of attributes (columns).; Pg. 182, §4.1, regarding implementing on a computer system):
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries (Pg. 180, §3.1, E.g. “We formulated the ISP as an episodic reinforcement learning task, i.e. broke the agent environment interaction naturally into subsequences (called episodes).”); and
(2) training, by the computer system, the index selection agent in at least one episode (Pg. 180, §3.1, E.g. “We formulated the ISP as an episodic reinforcement learning task, i.e. broke the agent environment interaction naturally into subsequences (called episodes).”), wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set (Pg. 180, §3.1, “the agent will take one action (recommend one index) according to current state and policy”, §3.2 ¶1, “Since the state observed by the agent determines the action of the agent, we include two parts of information in our state representation: 1) the current index configuration of the database. The current index configuration indicates the indexes that already existed in the database… 2) the selectivity of indexes.”; Pg. 181, ¶2-3, Selectivity is based on the workload. “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in I conf will be set to 1”. Thus, the current state is based on workload via selectivity, and also the current index configuration (index set).),
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set (Pg. 180, §3.1, “In each round of interaction between the agent (index tuner) and the environment (DBMS), the agent will take one action (recommend one index) according to current state and policy, and the environment (DBMS) will assign a reward to the agent as an evaluation of that action.”; §3.2 ¶1, “the state observed by the agent determines the action of the agent”; Pg. 181, ¶3 “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in I conf will be set to 1. Then the agent will be assigned a reward for this index and finish a round of interaction”. An action such as selecting an index from an action space of available beneficial indexes.),
(c) determining a reward based on the action taken (Pg. 180, §3.1, “In each round of interaction between the agent (index tuner) and the environment (DBMS), the agent will take one action (recommend one index) according to current state and policy, and the environment (DBMS) will assign a reward to the agent as an evaluation of that action.”; Pg. 181, ¶3, “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in Iconf will be set to 1. Then the agent will be assigned a reward for this index and finish a round of interaction.”),
(d) repeating steps (a) to (c) until an end condition is met (Pg. 180, §Definition 1, §3.1, “This training process continues until the stop criterion is met, e.g., the policy (a mapping from states to probabilities of selecting each possible action [10], which tells the agent to select an index) stabilizes, and the expected return converges.”),
wherein the index selection agent comprises an artificial neural network (Pg. 181, ¶3, “To handle the huge space of state and action, we use a neural network to represent the policy of the agent, where the input to the neural network is the representation of the state and the output is the representation of the recommended index.”).
Lai does not specifically disclose wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, and
wherein an input of the artificial neural network is the numerical representation of the one or more operators.
However, Burger discloses wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries (Figs. 2, 4, and 5; [0079], [0083], Query workloads are vectorized, i.e. constructed into a numerical operations of the operators comprising the queries therein, to form an episodic workload format fed to a neural network.), and
wherein the index selection agent comprises an artificial neural network ([0007], [0063]), wherein an input of the artificial neural network is the numerical representation of the one or more operators (Figs. 2 and 4; [0079], Query workloads are vectorized, i.e. constructed into a numerical operations of the operators comprising the queries therein, to form an episodic workload format fed to a neural network.).
Before the effective filing date of the claimed invention, it would have been obvious to a person having ordinary skill in the art to combine the teachings of Lai with the teachings of Burger by modifying Lai such that the episodic workloads provided to the neural network used in index selection of Lai (Lai, §3.2) are vectorized and provided as input to the neural network like in Burger. Said artisan would have been motivated to do so in order to more efficiently input data into the neural network by using standardized formats obtained by vectorizing the workloads into standard vectors for the system like in Burger.
As to claim 2, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, discloses wherein the phase of training the index selection agent further comprises the step of updating, by the computer system, the index selection agent based on at least one of the current states determined, the actions taken, and a set of rewards determined during training (Lai, §3.2, ¶5, “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in Iconf will be set to 1. Then the agent will be assigned a reward for this index and finish a round of interaction.” I.e. the index selection agent is updated based at least on current states and a set of rewards determined during training.).
As to claim 3, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, discloses wherein the step of determining the current state of the environment is based on costs for at least one of the queries contained in the episodic workload given the current index set, wherein said costs are estimated using a what-if optimizer (Lai, Pg. 181-182, §3.3; Pg. 182 §4.1; Indexes are selected to reduce cost of workload execution. This is done using “the HypoPG1 extension of PostgreSQL to provide a similar what-if index mechanism [15] of AutoAdmin (i.e. we use cost estimation of the optimizer to compute rewards in the training process, and avoid the overhead of actual query execution and index creation).”; Burger, [0060], [0068]).
As to claim 4, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, discloses wherein the action space, from which the action is taken, is a restricted action space (Lai, Pg. 180, §3.2, ¶1, “the action space of the index selection agent is consistent with the search space of all possible beneficial indexes in the database.” The action space is restricted all possible beneficial indexes.).
As to claim 6, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, discloses wherein the state of the environment is represented by features (Lai, Pg. 180, §3.2, ¶1, “Since the state observed by the agent determines the action of the agent we include two parts of information in our state representation: 1) the current index configuration of the database…2) the selectivity of indexes. The selectivity, or the filter factor of an index, is a good indicator of possible future benefits”), the features including at least one of:
a representation of the episodic workload, a representation of costs per query for at least one class of queries contained in the episodic workload with the current index configuration, a representation of a current storage budget and consumption with the current index configuration, and a representation of the current index configuration (Lai, Pg. 180, §3.2, ¶1, “Since the state observed by the agent determines the action of the agent we include two parts of information in our state representation: 1) the current index configuration of the database…2) the selectivity of indexes. The selectivity, or the filter factor of an index, is a good indicator of possible future benefits”. Pg. 181, ¶2, The selectivity is based in part on episodic workload.).
As to claim 7, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, discloses wherein the state of the environment is represented by features relating to at least three aspects: the episodic workload, meta information, and the current index configuration (Lai, Pg. 180, §3.2, ¶1, “Since the state observed by the agent determines the action of the agent we include two parts of information in our state representation: 1) the current index configuration of the database…2) the selectivity of indexes. The selectivity, or the filter factor of an index, is a good indicator of possible future benefits”. Pg. 181, ¶2, The selectivity is based in part on episodic workload and meta information such as columns, number of records, and counts.).
As to claim 9, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, discloses wherein the reward is determined based on an additional relative reduction of workload costs of an index selection per additional utilized storage (Lai, Pg. 180, Lines 1-7; Pg. 181-182, §3.3, Rewards are determined that maximize workload execution costs.).
As to claim 10, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, discloses wherein the end condition is at least one of: an index storage consumption exceeding a storage budget, a predefined maximum number of construction steps being reached, a predefined maximum number of indexes being reached, and no or no significant further improvement being achieved by adding an index candidate to the current index set (Pg. 180, §3.1, “This training process continues until the stop criterion is met, e.g., the policy (a mapping from states to probabilities of selecting each possible action [10], which tells the agent to select an index) stabilizes, and the expected return converges.” I.e. no significant further improvement.).
As to claim 11, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, discloses wherein preprocessing includes the step of determining a set of index candidates (Lai, Pg. 180, §3.2, ¶1, I.e. the determined action space.; Burger, [0032], [0070]; “identify candidate index columns”).
As to claim 12, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, discloses wherein the index selection agent takes the action based on a computation of the artificial neural network, wherein a second input of the artificial neural network is the state determined in step (a) of claim 1 (Lai, Pg. 181, ¶3, “To handle the huge space of state and action, we use a neural network to represent the policy of the agent, where the input to the neural network is the representation of the state and the output is the representation of the recommended index.”).
As to claim 13, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, discloses determining, by the computer system, the index set I using the index selection agent that results from the end condition having been met (Lai, Pg. 180 “Definition 1”, Pg. 181, ¶3, “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in Iconf will be set to 1.” A set I is determined and save for use when reduced execution workload is maximized and stopping occurs.); and
storing, by the computer system, the index set I determined by the computer system (Lai, Pg. 180 “Definition 1”, Pg. 181, ¶3, “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in Iconf will be set to 1.” A set I is determined and save for use when reduced execution workload is maximized and stopping occurs.).
As to claim 15, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, discloses wherein the queries in the episodic workload correspond to one or more representative query classes (Burger, Fig. 5; [0082], [0083]; Workload queries correspond to query classes corresponding to the operator types. ).
Additionally, while the prior art discloses the features of claim 16, these features merely describe the data being used, and do not affect the how the claimed method steps perform. No step is performed differently because a workload corresponds to a representative query class or not, or to any specific query class. The steps do not use the query class to do any specific function. As such, they are non-functional descriptive material with do not carry patentable weight and need not be disclosed by the prior art to teach or render obvious the claims. See MPEP §2111.05. Accordingly, the claim is fully rejected for the same reasons set forth in claim 1 above.
As to claim 16, the claim is rejected for the same reasons as claim 15 above. In addition, Lai, as previously modified with Burger, discloses wherein each of the one or more representative query classes has a corresponding frequency of occurrence, wherein each frequency of occurrence is generated such that the index selection agent handles different query-frequency pairs (Burger, Fig. 5; [0082], [0083]; E.g. workload frequency pared with the operator type in the vectorized representation. ).
Additionally, while the prior art discloses the features of claim 17, these features merely describe the data being used, and do not affect the how the claimed method steps perform. No step is performed differently because a workload corresponds to a representative query class or not, or to any specific query class, or frequency of occurrence of a class. The steps do not use the query class or related information thereto to do any specific function. As such, they are non-functional descriptive material with do not carry patentable weight and need not be disclosed by the prior art to teach or render obvious the claims. See MPEP §2111.05. Additionally, it is noted that the limitation “wherein each frequency of occurrence is generated such that the index selection agent handles different query-frequency pairs” does not require the method to necessarily perform any specific step. The limitation does not state that the method being claimed necessarily generates the frequency of occurrence, merely that it is somehow generated and thus can be done so outside the scope of the claim. Furthermore, the language “such that the index selection agent handles different query-frequency pairs” merely recites and intended use of the frequency occurrences, but the claimed method does not ever have a limitation where the index selection agent is actively handling this data. Rather, the claims only train the index selection agent using steps that do not use such information. Therefore, these features do not limit the claim to specific steps to be performed and do not carry patentable weight. See MPEP §2111.04. Accordingly, the claim is fully rejected for the same reasons set forth in claim 16 above.
As to claim 17, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, does not disclose wherein the episodic workload includes a first set of workloads and a second set of workloads, wherein each workload in the first set of workloads has a same set of query classes with a first set of different frequencies, and wherein each workload in the second set of workloads has a different set of query classes with a second set of different frequencies.
However, these features merely describe the data being used, and do not affect the how the claimed method steps perform. No step is performed differently because a workload corresponds to a representative query class or not, or to any specific query class, or frequency information. The steps do not use the query class or related information thereto to do any specific function. As such, they are non-functional descriptive material with do not carry patentable weight and need not be disclosed by the prior art to teach or render obvious the claims. See MPEP §2111.05. Accordingly, the claim is fully rejected for the same reasons set forth in claim 1 above.
As to claim 19, Lai discloses a computer system for training an index selection agent for iteratively determining an index set I to be used when running queries against a database (Pg. 178, §1, ¶1; Pg. 179-180, §1, Regarding index selection problem, ISP, with a database D containing tables with a set of attributes (columns).; Pg. 182, §4.1, regarding implementing on a computer system), the computer system comprising:
a memory, wherein the memory is configured to store the database with K attributes in a physical storage device (Pg. 178, §1, ¶1; Pg. 179-180, §1, Regarding index selection problem, ISP, with a database D containing tables with a set of attributes (columns).; Pg. 182, §4.1, regarding implementing on a computer system); and
a processor, wherein the processor is configured to control the computer system to execute a method comprising (Pg. 178, §1, ¶1; Pg. 179-180, §1, Regarding index selection problem, ISP, with a database D containing tables with a set of attributes (columns).; Pg. 182, §4.1, regarding implementing on a computer system):
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries (Pg. 180, §3.1, E.g. “We formulated the ISP as an episodic reinforcement learning task, i.e. broke the agent environment interaction naturally into subsequences (called episodes).”); and
(2) training, by the computer system, the index selection agent in at least one episode (Pg. 180, §3.1, E.g. “We formulated the ISP as an episodic reinforcement learning task, i.e. broke the agent environment interaction naturally into subsequences (called episodes).”), wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set (Pg. 180, §3.1, “the agent will take one action (recommend one index) according to current state and policy”, §3.2 ¶1, “Since the state observed by the agent determines the action of the agent, we include two parts of information in our state representation: 1) the current index configuration of the database. The current index configuration indicates the indexes that already existed in the database… 2) the selectivity of indexes.”; Pg. 181, ¶2-3, Selectivity is based on the workload. “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in I conf will be set to 1”. Thus, the current state is based on workload via selectivity, and also the current index configuration (index set).),
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set (Pg. 180, §3.1, “In each round of interaction between the agent (index tuner) and the environment (DBMS), the agent will take one action (recommend one index) according to current state and policy, and the environment (DBMS) will assign a reward to the agent as an evaluation of that action.”; §3.2 ¶1, “the state observed by the agent determines the action of the agent”; Pg. 181, ¶3 “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in I conf will be set to 1. Then the agent will be assigned a reward for this index and finish a round of interaction”. An action such as selecting an index from an action space of available beneficial indexes.),
(c) determining a reward based on the action taken (Pg. 180, §3.1, “In each round of interaction between the agent (index tuner) and the environment (DBMS), the agent will take one action (recommend one index) according to current state and policy, and the environment (DBMS) will assign a reward to the agent as an evaluation of that action.”; Pg. 181, ¶3, “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in Iconf will be set to 1. Then the agent will be assigned a reward for this index and finish a round of interaction.”), and
(d) repeating steps (a) to (c) until an end condition is met (Pg. 180, §Definition 1, §3.1, “This training process continues until the stop criterion is met, e.g., the policy (a mapping from states to probabilities of selecting each possible action [10], which tells the agent to select an index) stabilizes, and the expected return converges.”),
wherein the index selection agent comprises an artificial neural network (Pg. 181, ¶3, “To handle the huge space of state and action, we use a neural network to represent the policy of the agent, where the input to the neural network is the representation of the state and the output is the representation of the recommended index.”).
Lai does not specifically disclose wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, and
wherein an input of the artificial neural network is the numerical representation of the one or more operators.
However, Burger discloses wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries (Figs. 2, 4, and 5; [0079], [0083], Query workloads are vectorized, i.e. constructed into a numerical operations of the operators comprising the queries therein, to form an episodic workload format fed to a neural network.), and
wherein the index selection agent comprises an artificial neural network ([0007], [0063]), wherein an input of the artificial neural network is the numerical representation of the one or more operators (Figs. 2 and 4; [0079], Query workloads are vectorized, i.e. constructed into a numerical operations of the operators comprising the queries therein, to form an episodic workload format fed to a neural network.).
Before the effective filing date of the claimed invention, it would have been obvious to a person having ordinary skill in the art to combine the teachings of Lai with the teachings of Burger by modifying Lai such that the episodic workloads provided to the neural network used in index selection of Lai (Lai, §3.2) are vectorized and provided as input to the neural network like in Burger. Said artisan would have been motivated to do so in order to more efficiently input data into the neural network by using standardized formats obtained by vectorizing the workloads into standard vectors for the system like in Burger.
As to claim 20, Lai discloses a non-transitory computer-readable medium, comprising instructions which, when executed by a computer system, cause the computer system to carry out a method comprising (Pg. 178, §1, ¶1; Pg. 179-180, §1, Regarding index selection problem, ISP, with a database D containing tables with a set of attributes (columns).; Pg. 182, §4.1, regarding implementing on a computer system):
(1) preprocessing, wherein the preprocessing comprises determining at least one episodic workload, the episodic workload comprising queries (Pg. 180, §3.1, E.g. “We formulated the ISP as an episodic reinforcement learning task, i.e. broke the agent environment interaction naturally into subsequences (called episodes).”); and
(2) training, by the computer system, the index selection agent in at least one episode (Pg. 180, §3.1, E.g. “We formulated the ISP as an episodic reinforcement learning task, i.e. broke the agent environment interaction naturally into subsequences (called episodes).”), wherein training the index selection agent in an episode comprises following steps:
(a) determining a current state of an environment based on the episodic workload and a current index set (Pg. 180, §3.1, “the agent will take one action (recommend one index) according to current state and policy”, §3.2 ¶1, “Since the state observed by the agent determines the action of the agent, we include two parts of information in our state representation: 1) the current index configuration of the database. The current index configuration indicates the indexes that already existed in the database… 2) the selectivity of indexes.”; Pg. 181, ¶2-3, Selectivity is based on the workload. “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in I conf will be set to 1”. Thus, the current state is based on workload via selectivity, and also the current index configuration (index set).),
(b) taking an action from an action space based on the determined current state, wherein the action includes adding an index candidate to the current index set (Pg. 180, §3.1, “In each round of interaction between the agent (index tuner) and the environment (DBMS), the agent will take one action (recommend one index) according to current state and policy, and the environment (DBMS) will assign a reward to the agent as an evaluation of that action.”; §3.2 ¶1, “the state observed by the agent determines the action of the agent”; Pg. 181, ¶3 “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in I conf will be set to 1. Then the agent will be assigned a reward for this index and finish a round of interaction”. An action such as selecting an index from an action space of available beneficial indexes.),
(c) determining a reward based on the action taken (Pg. 180, §3.1, “In each round of interaction between the agent (index tuner) and the environment (DBMS), the agent will take one action (recommend one index) according to current state and policy, and the environment (DBMS) will assign a reward to the agent as an evaluation of that action.”; Pg. 181, ¶3, “When the index agent selects an index according to the current state and current policy, the corresponding position of the new index in Iconf will be set to 1. Then the agent will be assigned a reward for this index and finish a round of interaction.”), and
(d) repeating steps (a) to (c) until an end condition is met (Pg. 180, §Definition 1, §3.1, “This training process continues until the stop criterion is met, e.g., the policy (a mapping from states to probabilities of selecting each possible action [10], which tells the agent to select an index) stabilizes, and the expected return converges.”),
wherein the index selection agent comprises an artificial neural network (Pg. 181, ¶3, “To handle the huge space of state and action, we use a neural network to represent the policy of the agent, where the input to the neural network is the representation of the state and the output is the representation of the recommended index.”).
Lai does not specifically disclose wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries, and
wherein an input of the artificial neural network is the numerical representation of the one or more operators.
However, Burger discloses wherein determining the at least one episodic workload comprises:
generating, by the computer system, the episodic workload by constructing a numerical representation of one or more operators in a set of representative queries (Figs. 2, 4, and 5; [0079], [0083], Query workloads are vectorized, i.e. constructed into a numerical operations of the operators comprising the queries therein, to form an episodic workload format fed to a neural network.), and
wherein the index selection agent comprises an artificial neural network ([0007], [0063]), wherein an input of the artificial neural network is the numerical representation of the one or more operators (Figs. 2 and 4; [0079], Query workloads are vectorized, i.e. constructed into a numerical operations of the operators comprising the queries therein, to form an episodic workload format fed to a neural network.).
Before the effective filing date of the claimed invention, it would have been obvious to a person having ordinary skill in the art to combine the teachings of Lai with the teachings of Burger by modifying Lai such that the episodic workloads provided to the neural network used in index selection of Lai (Lai, §3.2) are vectorized and provided as input to the neural network like in Burger. Said artisan would have been motivated to do so in order to more efficiently input data into the neural network by using standardized formats obtained by vectorizing the workloads into standard vectors for the system like in Burger.
Claims 5 and 8 are rejected under 35 U.S.C. 103 as being unpatentable over Lai and Burger as applied above, and further in view of Adya et al. (US 6,266,658 B1), hereinafter Adya.
As to claim 5, the claim is rejected for the same reasons as claim 4 above. In addition, Lai, as previously modified with Burger, does not specifically disclose wherein the step of taking an action includes determining the restricted action space based on at least one of the current episodic workload, a storage budget, and at least one previous action taken by the index selection agent.
However, Adya discloses wherein the step of taking an action includes determining the restricted action space based on at least one of the current episodic workload, the remaining budget, and at least one previous action taken by the index selection agent (Fig. 7; Col. 9, Lines 34-35 and 64-67; Col. 10, Lines 1-35 and 44-54, A restricted access space of indexes, R, is determined and redetermined iteratively until a final configuration set of indexes F is determined. This is done based in part on the queries of a current workload, costs, and also a remaining budget indicated by whether a storage limit has been exceeded or not.).
Before the effective filing date of the claimed invention, it would have been obvious to a person having ordinary skill in the art to combine the teachings of Lai, as previously modified with Burger, with the teachings of Adya by modifying Lai such that the action space of Lai is determined based at least in part on the workload queries, their costs, and corresponding index storage limit like is done by Adya. Said artisan would have been motivated to do so in order to better endure that an index configuration recommended by Lai (Lai, Pg. 180, §3.2, ¶1) is not worse than and existing one, and to also better ensure indexes with low benefits are also not recommended (Adya, Col. 10, Lines 55-59).
As to claim 8, the claim is rejected for the same reasons as claim 7 above. In addition, Lai, as previously modified with Burger, discloses the meta information relates to one or more of a current storage consumption (Pg. 181, ¶2, The selectivity used for determining the current state is based in part on episodic workload and meta information such as counts of total number of records, i.e. related to a current storage consumption.).
Lai does not disclose the meta information relates to the storage budget, an initial cost for executing the episodic workload, and a current cost for executing the episodic workload.
However, Adya discloses that the meta information relates to a current storage consumption, the storage budget, an initial cost for executing the episodic workload, and a current cost for executing the episodic workload agent (Fig. 7; Col. 9, Lines 34-35 and 64-67; Col. 10, Lines 1-35 and 44-60, A restricted access space of indexes, R, is determined and redetermined iteratively until a final configuration set of indexes F is determined. This is done based in part on the queries of a current workload, costs which include both current and initial, and also a remaining budget indicated by whether a storage limit has been exceeded or not.).
Before the effective filing date of the claimed invention, it would have been obvious to a person having ordinary skill in the art to combine the teachings of Lai, as previously modified with Burger, with the teachings of Adya by modifying Lai such that the action space of Lai which takes into account the state of the environment (Lai, Pg. 180, §3.2, ¶1) is determined based at least in part on the workload queries, their costs, and corresponding index storage limit like is done by Adya. Said artisan would have been motivated to do so in order to better endure that an index configuration recommended by Lai (Lai, Pg. 180, §3.2, ¶1) is not worse than and existing one, and to also better ensure indexes with low benefits are also not recommended (Adya, Col. 10, Lines 55-59).
Claim 14 is rejected under 35 U.S.C. 103 as being unpatentable over Lai and Burger as applied above, and further in view of Potharaju et al. (US 2021/0357406 A1), hereinafter Potharaju
As to claim 14, the claim is rejected for the same reasons as claim 13 above. In addition, Lai does not disclose executing, by the computer system, a new query against the database using the index set I determined by the computer system using the index selection agent; and
outputting, by the computer system, a result of executing the new query.
However, Potharaju discloses executing, by the computer system, a new query against the database using the index set I determined by the computer system using the index selection agent (Fig. 14; [0006], [0201], A candidate index set I is determined and used to provide built indexes in response to a received workload. A new query is received and executed using the built indexes to provide a query result.); and
outputting, by the computer system, a result of executing the new query (Fig. 14; [0006], [0201], A candidate index set I is determined and used to provide built indexes in response to a received workload. A new query is received and executed using the built indexes to provide a query result.).
Before the effective filing date of the claimed invention, it would have been obvious to a person having ordinary skill in the art to combine the teachings of Lai with the teachings of Potharaju by further modifying Lai such that the indexes selected for a workload of Lai are then used to execute additional queries like in Potharaju. Said artisan would have been motivated to do so in order to use fewer resources when executing future queries that can benefit from the indexes (Potharaju, [0201].).
Claim 18 is rejected under 35 U.S.C. 103 as being unpatentable over Lai and Burger as applied above, and further in view of Rodriguez et al. (US 2020/0065334 A1), hereinafter Rodriguez.
As to claim 18, the claim is rejected for the same reasons as claim 1 above. In addition, Lai, as previously modified with Burger, does not disclose wherein constructing the numerical representation of the one or more operators includes performing dimensionality reduction on the numerical representation of the one or more operators.
However, Rodriguez discloses wherein constructing the numerical representation of the one or more operators includes performing dimensionality reduction on the numerical representation of the one or more operators ([0026], [0031], A feature vector corresponding to a query, and thus also any operators thereof, is generated, and the dimensions of the vector are reduced.).
Before the effective filing date of the claimed invention, it would have been obvious to a person having ordinary skill in the art to combine the teachings of Lai, as previously modified with Burger, with the teachings of Rodriguez by further modifying Lai such that the vectorized representations contributed by Burger are dimensionally reduced like the feature queries of Rodriguez. Said artisan would have been motivated to do so in order to simplify computation and reduce vector comparisons to more focused dimensional attributes as desired.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Shergill et al. (US 11,379,410 B2) discloses index management with workload.
Choudhuri et al (US 5,913,206) discloses receiving a workload, selecting candidate indexes, configuring indexes based in part on cost evaluation of the queries with what-if indexes, and outputting a final selected index configuration (Fig. 3).
Zilio et al. (US 2003/0088541 A1) discloses grouping workload queries such that each group will not exceed an execution memory constraint.
Welborn et al. (Learning Index Selection with Structured Action Spaces. 16 September 2019. https://arxiv.org/abs/1909.07440v1) discloses learning index selection using task-specific inductive biases.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JAMES E RICHARDSON whose telephone number is (571)270-1917. The examiner can normally be reached Mon-Fri 9:00-5:30.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Sherief Badawi can be reached at (571) 272-9782. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/James E Richardson/Primary Examiner, Art Unit 2169
