Teradata Corp v. SAP Se

1. Case Identification

• Case #: IPR2020-00943
• Patent #: 7,617,179
• Filed: May 21, 2020
• Petitioner(s): Teradata Corporation
• Patent Owner(s): SAP Se
• Challenged Claims: 1-8, 10, 13-26, 28, and 31-37

2. Patent Overview

• Title: Method for Optimizing a Database Query
• Brief Description: The ’179 patent discloses a method for optimizing a database query to be more efficient and less memory-intensive. The method involves dividing a query into "query blocks," creating a "Query Optimization Graph" (QOG) for each block, and determining an optimal execution plan without transforming or rewriting the subqueries during the optimization process.

3. Grounds for Unpatentability

Ground 1: Claims 1-8, 10, 21-26, and 28 are obvious over Paulley in view of Lucent ’144.

• Prior Art Relied Upon: Paulley (Application # 2002/0116357) and Lucent ’144 (Patent 6,032,144).
• Core Argument for this Ground:
  • Prior Art Mapping: Petitioner argued that Paulley taught a nearly identical database query optimization process, including receiving a query with subqueries, converting it into a QOG, using a branch-and-bound method to find the lowest-cost execution plan, and creating a detailed access plan. However, Paulley did not explicitly teach breaking a single complex query into multiple "query blocks" for separate optimization. Lucent ’144 supplied this missing element, disclosing that a complex SQL query can be broken into smaller blocks, with an optimal plan determined for each block locally before completing the plan for the entire query. For the negative limitation of optimizing "without transformation of the subqueries," Petitioner contended that Paulley's disclosure was silent on performing such transformations during optimization, and its described process did not require them.
  • Motivation to Combine: A POSITA would combine the teachings of Lucent ’144 with Paulley to improve Paulley's memory-efficient optimization process. Since Paulley's system was designed for memory-constrained portable devices, applying Lucent ’144's technique of breaking a query into smaller, separately optimized blocks would further reduce the complexity and memory requirements of the optimization process, making it more efficient.
  • Expectation of Success: A POSITA would have a reasonable expectation of success in this combination, as it involved applying a known technique for simplifying complex queries (block-by-block optimization from Lucent ’144) to a standard query optimization framework (Paulley) to achieve the predictable benefit of increased efficiency.

Ground 2: Claims 13-20 and 31-37 are obvious over Paulley, in view of Lucent ’144, and in further view of Young-Lai.

• Prior Art Relied Upon: Paulley (Application # 2002/0116357), Lucent ’144 (Patent 6,032,144), and Young-Lai (Application # 2004/0030677).
• Core Argument for this Ground:
  • Prior Art Mapping: This ground builds upon the combination of Paulley and Lucent ’144 from Ground 1 and adds Young-Lai to address limitations in dependent claims related to the specifics of the optimization and plan-pruning process. While Paulley taught a general "branch-and-bound" search method, Young-Lai provided explicit details for its implementation. Young-Lai taught building an access plan from a sequence of "triples" (a quantifier, join method, and index), which correspond to the claimed "candidate plan segment." It further disclosed estimating the cost of a partial access plan ("current prefix") and pruning the search if its cost exceeded that of the best complete plan found so far, directly mapping to claim limitations regarding pruning unfavorable access plans.
  • Motivation to Combine: A POSITA implementing the general branch-and-bound method disclosed in the primary reference (Paulley) would have been motivated to consult a reference like Young-Lai for a known, detailed implementation. Using Young-Lai's specific method of building and costing partial plans would be a straightforward way to implement Paulley's broader concept, leading to a faster and more efficient search for the optimal query plan.
  • Expectation of Success: The combination involved implementing a general, known optimization heuristic (Paulley's branch-and-bound) with a specific, well-documented algorithm for performing that heuristic (Young-Lai's search tree pruning). This substitution of a specific method for a general one would have yielded predictable improvements in optimization performance.

Ground 3: Claims 1-8, 10, 21-26, and 28 are obvious over Paulley, in view of Lucent ’144, and in further view of Galindo-Legaria.

• Prior Art Relied Upon: Paulley (Application # 2002/0116357), Lucent ’144 (Patent 6,032,144), and Galindo-Legaria (a 1994 conference proceeding entitled "Fast, Randomized Join-Order Selection – Why Use Transformations?").

• Core Argument for this Ground:

  • Prior Art Mapping: This ground presented an alternative to Ground 1 for satisfying the negative limitation "without transformation of the subqueries." Instead of relying on Paulley's silence, Petitioner asserted that Galindo-Legaria explicitly taught the benefits of a "transformation-free" optimization strategy. Galindo-Legaria stated that techniques that do not use transformations require less memory and can simplify the optimization process. Petitioner noted that discussion of this very article was present in the parent application of the ’179 patent but was removed from the application that was ultimately issued.
  • Motivation to Combine: A POSITA seeking to enhance the memory-constrained optimizer of Paulley would be motivated to incorporate the explicit teachings of Galindo-Legaria. Galindo-Legaria directly addressed the goal of reducing memory and computational overhead by advocating for a transformation-free approach. Applying this known principle to the Paulley/Lucent ’144 framework would be a logical step to further improve efficiency.
  • Expectation of Success: Combining the explicit teaching of transformation-free optimization from Galindo-Legaria with the Paulley/Lucent ’144 framework would predictably result in a system that uses less memory, as this was the stated advantage of the technique in Galindo-Legaria.

• Additional Grounds: Petitioner asserted an additional obviousness challenge (Ground 4) against claims 13-20 and 31-37 based on the combination of Paulley, Lucent ’144, Galindo-Legaria, and Young-Lai, relying on similar arguments.

4. Key Claim Construction Positions

Petitioner adopted, for the purposes of the IPR, the claim constructions proposed by the Patent Owner in a related district court litigation. The key constructions material to the Petition included:

• query block: Construed as "an atomic portion of a query that can be separately optimized." This construction was central to Petitioner's argument for combining Paulley with Lucent ’144.
• each query block is optimized without transformation of subqueries: Construed as "subqueries are not rewritten during the process of optimizing the containing query block." This construction defined the key negative limitation that Petitioner argued was either implicitly present or explicitly taught by the prior art.

5. Relief Requested

• Petitioner requests institution of an inter partes review and cancellation of claims 1-8, 10, 13-26, 28, and 31-37 of the ’179 patent as unpatentable.