Method and apparatus for facilitating wildcard searches within a relational database

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.

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.

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.

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.

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.