Text search of database with one-pass indexing including filtering

Patent metadata

Field	Value
Publication number	US-10977284-B2
Application number	US-201616070895-A
Country	US
Kind code	B2
Filing date	Jan 29, 2016
Priority date	Jan 29, 2016
Publication date	Apr 13, 2021
Grant date	Apr 13, 2021

Abstract

A system and method for a text search of a database. A text search expression is converted to a query plan having multiple search tokens. A one-pass indexing of an invested word index filters the inverted word index based on a search condition and identifies the applicable documents having the multiple search tokens.

First claim

What is claimed is:

1. A method comprising:
receiving a text search expression and a search condition for a text search of a database comprising documents;
converting the text search expression to a query plan comprising multiple search tokens, wherein each search token corresponds to a word of the text search expression;
filtering an inverse word index of the database based on the search condition to determine applicable documents of the database that satisfy the search condition;
identifying and counting each document of the applicable documents when the document matches any search token of the multiple search tokens;
identifying documents among the counted documents that have a count equal to a number of search tokens included in the multiple search tokens; and
generating a result of the text search including the documents that have the count equal to the number of search tokens.

2. The method of claim 1 , further comprising:
retrieving, from the database, the documents having the count equal to the number of search tokens included in the multiple search tokens.

3. The method of claim 1 , wherein:
the multiple search tokens comprise a first search token corresponding to a first word of the text search expression and a second search token corresponding to a second word of the text search expression, and
the identifying and counting comprises:
identifying and counting the applicable documents that match the first search token to generate a first set of applicable documents, and
identifying and counting the applicable documents that match the second search token to generate a second set of applicable documents.

4. The method of claim 3 , further comprising:
combining the first set with the second set to generate a union bag of applicable documents.

5. The method of claim 4 , wherein the number of search tokens is two, and
wherein identifying the documents that have the count equal to the number of search tokens comprises identifying the applicable documents in the union bag that have a count of two as applicable documents that match both the first search token and the second search token.

6. The method of claim 1 , wherein the database comprises a relational database, wherein the query plan comprises a structured query language (SQL) query plan, and wherein the converting comprises converting, via a text-search SQL-query generator, the text search expression into the SQL query plan to provide for direct leveraging of SQL operators in the text search.

7. The method of claim 1 , wherein the identifying and counting comprises:
for each search token of the multiple search tokens, performing a one-pass scan of the inverse word index of the database to identify the applicable documents that match the search token.

8. A computing device comprising:
a processor;
a network interface to couple the computing device to a database; and
memory to store instructions that, when executed by the processor, cause the processor to:
accept a text search expression and a search condition for a text search of the database;
rewrite the text search expression into a query plan comprising multiple search tokens, wherein each search token corresponds to a word in the text search expression; and
filter an inverse index table of the database based on the search condition to ascertain applicable documents of the database that satisfy the search condition;
identify and count each document of the applicable documents when the document matches any search token of the multiple search tokens;
identify documents among the counted documents that have a count equal to a number of search tokens included in the multiple search tokens; and
generate a result of the text search including the documents that have the count equal to the number of search tokens.

9. The computing device of claim 7 , wherein the instructions, when executed by the processor, further cause the processor to:
retrieve, from the database, the documents that have the count equal to the number of search tokens included in the multiple search tokens.

10. The computing device of claim 8 , wherein the multiple search tokens comprise a first search token corresponding to a first word in the text search expression and a second search token corresponding to a second word in the text search expression, and
wherein the instructions that cause the processor to identify and count each document when the document matches any search token include instructions that cause the processor to:
identify and count the applicable documents of the database matching the first search token to generate a first set of applicable documents, and
identify and count the applicable documents of the database matching the second search token to generate a second set of applicable documents.

11. The computing device of claim 10 , wherein the instructions further cause the processor to:
combine the first set with the second set to generate a union bag of applicable documents to determine documents that match both the first search token and the second search token.

12. The computing device of claim 11 , wherein, to determine documents that match both the first search token and the second search token, the instructions cause the processor to:
identify the applicable documents in the union bag that have a count of two.

13. The computing device of claim 8 , wherein the database comprises a relational database, wherein the query plan comprises a structured query language (SQL) query plan, and wherein the instructions, when executed by the processor, further cause the processor to rewrite the text search expression into the SQL query plan that directly utilizes SQL operators in the text search implemented as the SQL query plan.

14. The computing device of claim 8 , wherein the instructions that cause the processor to identify and count each document of the applicable documents when the document matches any search token of the multiple search tokens include instructions that cause the processor to:
for each search token of the multiple search tokens, perform a one-pass scan of the inverse index table of the database to identify the applicable documents that match the search token.

15. A tangible, non-transitory, computer-readable medium comprising instructions that, when executed by a processor, cause the processor to:
receive a text search expression and a filter condition for a text search of a database by a text search engine;
transform the text search expression to a query plan comprising multiple search tokens, wherein each search token corresponds to a word in the text search expression;
filter an inverse word index based on the filter condition to determine applicable documents of the database that satisfy the filter condition;
identify and count each document of the applicable documents when the document matches any search token of the multiple search tokens;
identify documents among the counted documents that have a count equal to a number of search tokens included in the multiple search tokens; and
generate a result of the text search including the documents that have the count equal to the number of search tokens.

16. The tangible, non-transitory, computer-readable medium of claim 15 , wherein the instructions, when executed by the processor, further cause the processor to retrieve, from the database, the documents that have the count equal to the number of search tokens included in the multiple search tokens.

17. The tangible, non-transitory, computer-readable medium of claim 15 , wherein the database comprises a relationa

Assignees

• Entit Software Llc
• Micro Focus Llc

Inventors

• Chen Qiming
• Hsu Meichun
• Castellanos Malu G

Classifications

• G06F16/3341 Primary

  using boolean model · CPC title

• G06F16/3338 Primary

  Query expansion · CPC title

• G06F16/24542

  Plan optimisation · CPC title

• G06F16/319

  Inverted lists · CPC title

• G06F16/243

  Natural language query formulation · CPC title