Join algorithms over full text indexes
According to one embodiment of the present invention, a method for processing join predicates in full-text indexes is provided. The method includes evaluating local predicates of an outer full text index to generate a first posting list of documents. For each document in the first posting list, the value of a join attribute is determined and an inner full text index is probed to obtain a second posting list of documents containing one of the join attributes determined for each document. Local predicates of an inner full text index are evaluated to generate a third posting list of documents, and the second posting list is merged with the third posting list to generate a merge list of documents. Documents in the first posting list may be paired up with documents in the merge list.
1. A computer hardware implemented method comprising:
receiving a query by a processor, the query comprising:
an inner full text index which comprises a first set of document ids, each of the documents ids having a first attribute and a first value;
an outer full text index which comprises a second set of document ids, each of the documents ids having a second attribute and a second value;
one or more inner local predicates comprising a first search term for the inner full text index;
one or more outer local predicates comprising a second search term for the outer full text index,
an inner join attribute comprising a third search term corresponding to the first value; and
an outer join attribute comprising a fourth search term corresponding to the second value; and
using said processor to:
evaluate the one or more outer local predicates from said query of the outer full text index to generate a first posting list of documents;
determine the second value of the outer join attribute from said query for each document in said first posting list;
probe the inner full text index to obtain a second posting list of documents containing one of said inner join attributes determined for each document in said first posting list;
evaluate the one or more inner local predicates of the inner full text index to generate a third posting list of documents;
merge said second posting list with said third posting list to generate a merge list of documents; and
pair up each document in said first posting list with documents in said merge list.
2. The method according to claim 1 wherein said first, second and third posting lists contain lists of document identifiers.
3. The method according to claim 1 wherein said inner and outer full text indexes comprise lists of documents that result from different full-text searches.
4. The method according to claim 1 wherein at least one of said local predicates is a full-text query including single keywords.
5. The method according to claim 4 wherein at least one of said full text queries is a complex query and wherein said method further comprises caching said third posting list.
6. The method according to claim 1 wherein said join attribute is a join condition on meta-data.