Ex Parte Bhattacharjee et alDownload PDFPatent Trial and Appeal BoardFeb 17, 201512423247 (P.T.A.B. Feb. 17, 2015) Copy Citation UNITED STATES PATENT AND TRADEMARK OFFICE ____________ BEFORE THE PATENT TRIAL AND APPEAL BOARD ____________ Ex parte BISHWARANJAN BHATTACHARJEE, MUSTAFA CANIM, and GEORGE ANDREI MIHAILA ____________ Appeal 2012-009100 Application 12/423,247 Technology Center 2100 ____________ Before JEAN R. HOMERE, CARLA M. KRIVAK, and CHARLES J. BOUDREAU, Administrative Patent Judges. BOUDREAU, Administrative Patent Judge. DECISION ON APPEAL Appellants1 appeal under 35 U.S.C. § 134(a) from the Examiner’s Final Rejection of claims 8–14. We have jurisdiction under 35 U.S.C. § 6(b). We reverse. 1 Appellants identify International Business Machines as the real party in interest. App. Br. 2. Appeal 2012-009100 Application 12/423,247 2 STATEMENT OF THE CASE Appellants’ Claimed Invention The claimed invention relates to a method, information processing system, and computer program storage product for optimizing the placement of database objects on a multiplicity of storage devices. Abstract. Representative Claim Independent claim 8, reproduced below, is representative of the subject matter on appeal. 8. An information processing system for optimizing placement of database objects on a plurality of storage devices, the information processing system comprising: a memory; a processor communicatively coupled to the memory; and a database object placement advisor communicatively coupled to the memory and the processor, wherein the database object placement advisor is configured to: place a set of database objects on a first storage device in a plurality of storage devices, wherein each storage device in the plurality of storage device comprises differing characteristics; run a query workload on the set of database objects that have been placed on the first storage device; collect profiling information associated with the query workload that is running; determine, based on collecting the profiling information, a number of pages read and written for each database object in the set of database objects, and a total time spent through sequential and random access for each data base object in the set of database objects; select, based on the number pages read and written and the total time spent through sequential and random access for each data base object, a subset of database objects from the set of the database objects to be stored on a second storage device in the plurality of storage devices, wherein the second storage device is a separate Appeal 2012-009100 Application 12/423,247 3 physical device from, and performs faster than, the first storage device; and store the subset of database objects on the second storage device and all remaining database objects in the set of database objects on the first storage device, where each database object in the set of database objects is a randomly accessed database object, and where each remaining database object is a sequentially accessed database object. Rejections on Appeal Claims 8–12 and 14 stand rejected under 35 U.S.C. § 102(a) as being anticipated by Ioannis Koltsidas & Stratis D. Viglas, Flashing Up the Storage Layer, 1 PROCEEDINGS VERY LARGE DATABASE ENDOWMENT 514 (2008) (“Koltsidas”). Ans. 5–8. Claim 13 stands rejected under 35 U.S.C. § 103(a) as being unpatentable over the combination of Koltsidas and Bullen (US 7,707,351 B2; issued Apr. 27, 2010 (filed Oct. 31, 2002)). Ans. 9. ISSUE ON APPEAL The dispositive issue before us is whether the Examiner erred in finding Koltsidas discloses “determin[ing] . . . a number of pages read and written for each database object in the set of database objects, and a total time spent through sequential and random access for each data base object in the set of database objects,” as recited in claim 8. ANALYSIS We have reviewed Appellants’ arguments in the Briefs, the Examiner’s rejection, and the Examiner’s response to Appellants’ Appeal 2012-009100 Application 12/423,247 4 arguments. We concur with Appellants’ conclusions that the Examiner erred in finding Koltsidas discloses the disputed limitations set forth above. Koltsidas describes using flash memory and magnetic disks at the same level of memory hierarchy in commodity hardware systems and placing a data page on one or the other storage medium according to the workload of the page. See Koltsidas, p. 514, col. 1, para. 1. Pages with a read-intensive workload are placed on the flash disk, for example, whereas pages with a write-intensive workload are placed on the magnetic disk. Id. Koltsidas presents a family of on-line algorithms “to decide the optimal placement of a page and study their theoretical properties.” Id. With respect to the disputed claim limitation, “determin[ing] . . . a number of pages read and written for each database object in the set of database objects,” the Examiner finds Koltsidas discloses “page count and read/write cost data is used in an algorithm to determine what pages should be migrated to the second, faster, storage device, which in this case is a flash disk,” Ans. 6 (citing Koltsidas Fig. 1; p. 516, col. 2, para. 2; p. 517, col. 1, para. 4 – col. 2, para. 2). According to the Examiner, [A] cost counter is maintained for both reads and writes of pages. This can be seen as cited on p. 517 col 1 section 4.1. As seen in section 4.1 "Conservative Algorithm", the variable r represents the cost of reading a page and w represents the cost of writing a page. Further support can be found in fig. 4, note on lines 5 and 7 that for each page the pg. reads variable is incremented for each read, and that [pg. writes] is incremented for each write. Also note on p. 518, col. 1. para. 2 the explanation of the figure disclosing that for each page a read and write counter is maintained. Examiner has interpreted the disclosures of both a counter and the ability to determine both when pages are read Appeal 2012-009100 Application 12/423,247 5 and written as sufficient to anticipate “determining a number of pages read and written.” Ans. 12. Appellants argue, and we agree, that although Koltsidas maintains a counter that is incremented by a cost difference representing the cost units that would have been saved if the page would have been read or written on the other storage medium, that counter does not maintain the number of pages read and written for each database object in the set of database objects. App. Br. 10. With respect to the disputed claim limitation, “determin[ing] . . . a total time spent through sequential and random access for each data base object in the set of database objects,” the Examiner finds that “B+ trees used in the presentation use both random and sequential access patterns” and that “a buffer manager can employ sequential access costs as opposed to random access costs.” Ans. 6 (citing Koltsidas, p. 520, col. 2, para. 2; p. 524, col. 2, para. 4). According to the Examiner, The Office Action cites page 520, column 2 of the Koltsidas reference, section 6, titled Experimental Study. Paragraph one of the Experimental Study discloses evaluating algorithms using a B+ tree. The B+ tree is disclosed to have been chosen for the performance study because it exhibits “both random and sequential access patterns.” As can be seen in table 1 and figure 9, total access times are being measured in seconds. Further evidence is shown on page 524, column two. The last sentence of the first paragraph in column two explicitly states that “Our benchmarks show that writing pages sequentially to the flash disk is over 10 times faster than writing them in a random fashion”, indicating that both sequential and random access times are measured. Appeal 2012-009100 Application 12/423,247 6 Further support for the limitation is also found on page 524, column two, paragraph 4, titled “Sequential Access Patterns.” This paragraph discloses that sequential access costs can be measured for page replacement and also for page placement. Applicant suggests that this paragraph teaches away from measuring both random and sequential access. However, the context of the paragraph when read as a whole indicates only that it is suggesting an alternative embodiment to utilizing the random access costs in the page replacement algorithm. The standard embodiment appears from this paragraph to use random costs for page placement and sequential costs for page replacement, which together would result in a total time for sequential and random access for a query that consisted of both a page placement and a page replacement. Ans. 10–11. Appellants argue, and we agree, that “Koltsidas . . . explicitly teaches that either random access (read/writes) costs or sequential access (read/writes) costs are used in the placement algorithms, not both.” App. Br. 11. As Appellants point out, the passage from page 524 of Koltsidas relied upon by the Examiner states that a buffer manager “can employ sequential access costs in the page placement algorithm as opposed to random access ones” (emphasis added). We agree with Appellants that the use of the phrase “as opposed to” shows that Koltsidas “only uses costs associated with either random access read/writes or sequential reads/write, but not both.” App. Br. 6. Appellants further argue, and we again agree, that: [T]he information shown in Table 1 and FIG. 9 of the Koltsidas reference is with respect to experiments performed by the authors of the paper, as compared to measurements that are utilized by the algorithms of Koltsidas reference. For example, Table 1 of the Koltsidas reference merely shows the average Appeal 2012-009100 Application 12/423,247 7 time for read and writes on magnetic and flash disks for pages placed on these disks. . . . . . . . . . . [E]ven assuming arguendo that the information in Table 1 and FIG. 9 of the Koltsidas reference is used in the placement/replacement algorithms (which it is not), the average time . . . of all read/writes on the disk and the total execution time of a query set (i.e., 50,000 queries) is clearly not the same as “. . . a total time spent through sequential and random access for each data base object in the set of database objects”. Reply Br. 2–3. Because we agree with Appellants that the Examiner erred in finding Koltsidas discloses “determin[ing] . . . a number of pages read and written for each database object in the set of database objects, and a total time spent through sequential and random access for each data base object in the set of database objects,” as recited in independent claim 8, we will not sustain the Examiner’s rejection of claim 8 or its dependent claims 9–14. DECISION We reverse the Examiner’s rejection of claims 8–12 and 14 under 35 U.S.C. § 102(a) as being anticipated by Koltsidas.2 We reverse the Examiner’s rejection of claim 13 under 35 U.S.C. § 103(a) as being unpatentable over the combination of Koltsidas and Bullen. 2 In the event of further prosecution, we leave it to Appellants and the Examiner to determine whether the word “set” in the clause “where each database object in the set of database objects is a randomly accessed database object” in the last paragraph of claim 8 should more properly be replaced with the word “subset.” Appeal 2012-009100 Application 12/423,247 8 REVERSED tj Copy with citationCopy as parenthetical citation