Method and apparatus for processing and optimizing queries having joins between structured data and text data

• US 5,608,904 A
• Filed: 02/13/1995
• Issued: 03/04/1997
• Est. Priority Date: 02/13/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Chaudhuri, Surajit, Yan, Tak W., Dayal, Umeshwar
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/387,527
• Time in Patent Office: 750 Days
• Field of Search: 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

Probe-based query processing for a database system that loosely integrates a structured database and a text retrieval system is described. The query processing constructs a query plan that efficiently evaluates a conjunctive query having joins of structured and textual data by sending to the text retrieval system one or more text search/retrieve operations.

Claims

1. A method for executing a conjunctive query that includes joins of structured data from a structured database system and external textual data from a text retrieval system, the joins having multiple join predicates, comprising:

(a) selecting at least one probing column from the multiple join predicates; and

(b) reducing execution time of the conjunctive query by probing the external textual database to eliminate redundant queries to the external textual database which produce no matching documents.

2. A method for processing a conjunctive query that includes joins of structured data from a structured database and external textual data from a text retrieval system, comprising:

(a) selecting at least one probing column from the multiple join predicates if one or more of the joins has multiple join predicates;

(b) determining an estimated cost of at least one probe-based optimization plan;

(c) determining an estimated cost of at least one conventional optimization plan;

(d) selecting one of the optimization plans based on the lowest estimated cost; and

(e) evaluating the conjunctive query in accordance with the selected optimization plan.

3. A method as recited in claim 2, wherein when the selected optimization plan is a probe-based optimization plan, said evaluating (e) comprises:

(e1) sending text search/retrieve operations to the text retrieval system to obtain a result set of matching text documents;

(e2) probing the external textual database to determine presence of matching text documents; and

(e3) avoiding said sending (e1) of certain of the text search/retrieve operations if said probing (e2) indicates that the certain of the text search/retrieve operations find no matching documents.

4. A method as recited in claim 3, wherein said evaluating (e) further comprises (e4) joining the result set with relations of the conjunctive query associated with the structured data.

5. A method as recited in claim 3, wherein when the selected optimization plan is a conventional optimization plan, said evaluating (e) comprises:

sending text search/retrieve operations to the text retrieval system to obtain a result set of matching text documents without probing the external textual database.

6. An apparatus as recited in claim 5, wherein said structured database system further includes a probe cache for storing results of previously performed probes.

7. An apparatus as recited in claim 6, wherein said query executor further reduces execution time by performing said probing only when the optimal execution plan is a probe-based execution plan and when said probe cache does not already store the results of said probing.

8. An apparatus as recited in claim 7, wherein said structured database system further includes a document cache for storing the matching documents retrieved from the external textual database, the matching documents stored in said document cache being associated with entries in said probe cache.

9. A loosely integrated database system capable of evaluating a conjunctive query that includes joins of structured data and external textual data, the joins having multiple join predicates, comprising:

a text retrieval system having textual data; and

a structured database system having structured data, said structured database system comprising;

a query optimizer for selecting an optimal execution plan from a plurality of available execution plans based on cost; and

a query executor for executing the optimal execution plan to evaluate the conjunctive query,

wherein when the optimal execution plan is a probe-based execution plan, said query executor reduces execution time of the conjunctive query by probing the external textual database to eliminate redundant queries to the external textual database which produce no matching documents.