Method and apparatus for facilitating wildcard searches within a relational database

• US 6,556,990 B1
• Filed: 05/16/2000
• Issued: 04/29/2003
• Est. Priority Date: 05/16/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Lane, Robert M.
• Primary Examiner(s): Homere, Jean R.
• Assistant Examiner(s): Wong, Leslie
• Application Number:
  US09/573,051
• Time in Patent Office: 1,078 Days
• Field of Search: 707/2, 707/3, 707/6, 707/5, 704/1, 704/243
• US Class Current: 707/774
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

One embodiment of the present invention provides a system that facilitates performing an efficient wildcard search on a field within a relational database table. The system operates by receiving a query with a search string that includes a wildcard and a sub-string. In order to process this query, the system identifies rows in a table in which a target column contains a string that matches search string. This is accomplished by looking up rows in the table that match the search string by looking up the sub-string in a sub-string index for the target column, wherein this sub-string index allows a given string in the target column to be rapidly identified based upon a sub-string of the given string. Next, the system accesses the matching rows in order to process the query. In one embodiment of the present invention, the wildcard is a leading wildcard that precedes the sub-string. In a variation on this embodiment, the search string additionally includes a trailing wildcard that follows the sub-string.

Claims

1. A method for facilitating an efficient wildcard search on a field within a relational database, comprising:

receiving a query with a search string that includes a wildcard and a sub-string;

wherein processing the query involves identifying rows in a table in the relational database in which a target column contains a string that matches search string;

wherein matching the search string includes matching an expansion for the wildcard in the search string;

looking up matching rows in the table that match the search string by looking up the sub-string in a sub-string index for the target column, the sub-string index allowing a given string in the target column to be rapidly identified based upon a sub-strings of the given string, wherein the sub-string index includes a second table in the relational database, and wherein the second table includes a first column containing strings from the target column and second column containing corresponding sub-strings of the strings from the target column; and

accessing the matching rows in order to process the query.

2. The method of claim 1, wherein the wildcard is a leading wildcard that precedes the sub-string.

3. The method of claim 2, wherein the search string additionally includes a trailing wildcard that follows the sub-string.

4. The method of claim 1, further comprising creating the sub-string index for the target column prior to receiving the query.

5. The method of claim 1, wherein the sub-string index includes an internal index within the relational database that facilitates using a given sub-string to lookup at least one row in the table having a matching string in the target column which contains the given sub-string.

6. The method of claim 1, wherein the sub-string index is structured to lookup all sub-strings of the given string that are equal to or less than a maximum sub-string size.

7. The method of claim 1, wherein the sub-string index is structured to lookup all sub-strings of the given string that include the last character of the given string.

8. A method for producing an index to facilitate an efficient wildcard search on a target column within a table in a relational database, comprising:

receiving a row for the table in the relational database;

retrieving a string from within the target column of the row;

producing a plurality of sub-strings of the string;

using the plurality of sub-strings to construct a sub-string index that facilitates looking up the row containing the string based upon one of the plurality of sub-strings; and

integrating the sub-string index into a global sub-string index for all strings in the target column in the table, wherein the global sub-string index facilitates looking up all strings in the target column that contain a given sub-string and wherein the global sub-string index includes a second table in the relational database, and wherein the second table includes a first column containing strings from the target column and second column containing corresponding sub-strings of the strings from the target column.

9. The method of claim 8, further comprising inserting the row into the table in the relational database.

10. The method of claim 8, wherein the global sub-string index includes an internal index within the relational database that facilitates using the given sub-string to lookup at least one row in the table having a matching string in the target column which contains the given sub-string.

11. The method of claim 8, wherein the plurality of sub-strings include all sub-strings of the string that are equal to or less than a maximum sub-string size.

12. The method of claim 8, wherein the plurality of sub-strings include all sub-strings of the string that include the last character of the string.

13. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for facilitating an efficient wildcard search on a field within a relational database, the method comprising:

receiving a query with a search string that includes a wildcard and a sub-string;

wherein processing the query involves identifying rows in a table in the relational database in which a target column contains a string that matches search string;

wherein matching the search string includes matching an expansion for the wildcard in the search string;

looking up matching rows in the table that match the search string by looking up the sub-string in a sub-string index for the target column, the sub-string index allowing a given string in the target column to be rapidly identified based upon a sub-strings of the given string, wherein the sub-string index includes a second table in the relational database, and wherein the second table includes a first column containing strings from the target column and second column containing corresponding sub-strings of the strings from the target column; and

accessing the matching rows in order to process the query.

14. The computer-readable storage medium of claim 13, wherein the wildcard is a leading wildcard that precedes the sub-string.

15. The computer-readable storage medium of claim 14, wherein the search string additionally includes a trailing wildcard that follows the sub-string.

16. The computer-readable storage medium of claim 13, wherein the method further comprises creating the sub-string index for the target column prior to receiving the query.

17. The computer-readable storage medium of claim 13, wherein the sub-string index includes an internal index within the relational database that facilitates using a given sub-string to lookup at least one row in the table having a matching string in the target column which contains the given sub-string.

18. The computer-readable storage medium of claim 13, wherein the sub-string index is structured to lookup all sub-strings of the given string that are equal to or less than a maximum sub-string size.

19. The computer-readable storage medium of claim 13, wherein the sub-string index is structured to lookup all sub-strings of the given string that include the last character of the given string.

20. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for producing an index to facilitate an efficient wildcard search on a target column within a table in a relational database, the method comprising:

receiving a row for the table in the relational database;

retrieving a string from within the target column of the row;

producing a plurality of sub-strings of the string;

using the plurality of sub-strings to construct a sub-string index that facilitates looking up the row containing the string based upon one of the plurality of sub-strings; and

integrating the sub-string index into a global sub-string index for all strings in the target column in the table, wherein the global sub-string index facilitates looking up all strings in the target column that contain a given sub-string, wherein the global sub-string index includes a second table in the relational database, and wherein the second table includes a first column containing strings from the target column and second column containing corresponding sub-strings of the strings from the target column.

21. The computer-readable storage medium of claim 20, wherein the method further comprises inserting the row into the table in the relational database.

22. The computer-readable storage medium of claim 20, wherein the global sub-string index includes an internal index within the relational database that facilitates using the given sub-string to lookup at least one row in the table having a matching string in the target column which contains the given sub-string.

23. The computer-readable storage medium of claim 20, wherein the plurality of sub-strings include all sub-strings of the string that are equal to or less than a maximum sub-string size.

24. The computer-readable storage medium of claim 20, wherein the plurality of sub-strings include all sub-strings of the string that include the last character of the string.

25. An apparatus that facilitates an efficient wildcard search on a field within a relational database, comprising:

a receiving mechanism that is configured to receive a query with a search string that includes a wildcard and a sub-string;

wherein processing the query involves identifying rows in a table in the relational database in which a target column contains a string that matches search string;

wherein matching the search string includes matching an expansion for the wildcard in the search string;

a lookup mechanism that is configured to look up matching rows in the table that match the search string by looking up the sub-string in a sub-string index for the target column, the sub-string index allowing a given string in the target column to be rapidly identified based upon a sub-strings of the given string, wherein the sub-string index includes a second table in the relational database, and wherein the second table includes a first column containing strings from the target column and second column containing corresponding sub-strings of the strings from the target column; and

an access mechanism that is configured to access the matching rows in order to process the query.

26. The apparatus of claim 25, wherein the wildcard is a leading wildcard that precedes the sub-string.

27. The apparatus of claim 26, wherein the search string additionally includes a trailing wildcard that follows the sub-string.

28. The apparatus of claim 25, further comprising an index creation mechanism that is configured to create the sub-string index for the target column prior to receiving the query.

29. The apparatus of claim 25, wherein the sub-string index includes an internal index within the relational database that facilitates using a given sub-string to lookup at least one row in the table having a matching string in the target column which contains the given sub-string.

30. The apparatus of claim 25, wherein the sub-string index is structured to lookup all sub-strings of the given string that are equal to or less than a maximum sub-string size.

31. The apparatus of claim 25, wherein the sub-string index is structured to lookup all sub-strings of the given string that include the last character of the given string.

32. An apparatus that produces an index to facilitate an efficient wildcard search on a target column within a table in a relational database, comprising:

a receiving mechanism that is configured to receive a row for the table in the relational database;

a retrieving mechanism that is configured to retrieve a string from within the target column of the row;

a sub-string generation mechanism that is configured to generate a plurality of sub-strings of the string;

an index creation mechanism that is configured to use the plurality of sub-strings to construct a sub-string index that facilitates looking up the row containing the string based upon one of the plurality of sub-strings; and

an index integration mechanism that is configured to integrate the sub-string index into a global sub-string index for all strings in the target column in the table, wherein the global sub-string index facilitates looking up all strings in the target column that contain a given sub-string, wherein the global sub-string index includes a second table in the relational database, and wherein the second table includes a first column containing strings from the target column and second column containing corresponding sub-strings of the strings from the target column.

33. The apparatus of claim 32, further comprising an insertion mechanism that is configured to insert the row into the table in the relational database.

34. The apparatus of claim 32, wherein the global sub-string index includes an internal index within the relational database that facilitates using the given sub-string to lookup at least one row in the table having a matching string in the target column which contains the given sub-string.

35. The apparatus of claim 32, wherein the plurality of sub-strings include all sub-strings of the string that are equal to or less than a maximum sub-string size.

36. The apparatus of claim 32, wherein the plurality of sub-strings include all sub-strings of the string that include the last character of the string.