Scalable fine grained access control within a search engine
A system and method for providing fine-grained access control in a search engine. Access control predicates associated with a search query, including fixed-width and/or variable-width tokens, are received from the search engine, and are formatted in a machine-readable binary format to generate a single byte array. A pre-sorted memory index structure associated with the single byte array is generated, by sorting the access control predicates according to their token width. The pre-sorted memory index structure is merge joined with an uninverted terms index that includes a sorted list of all terms in a field associated with the search query, and a document index mapping the document identifier (ID) to a term ordinal for a specific field.
1. An access control method comprising:
receiving, via one or more processors, from a search engine at least one access control predicate;
generating, via the one or more processors, an array responsive to formatting the at least one access control predicate;
generating, via the one or more processors, a memory index structure associated with the array, the memory index structure being pre-sorted based on a sort order of a plurality of access control predicates received from the search engine;
merging, via the one or more processors, the memory index structure that has been presorted with an uninverted terms index that includes:
a sorted list of a plurality of search terms; and
a document index mapping a document identifier (ID) to a term ordinal for a predetermined value associated with one or more search terms; and
identifying, via the one or more processors, one or more matches for the document ID against one or more access control predicates by testing the term ordinal against a bitset of ordinal terms to determine whether the document ID matches against the one or more access control predicates.
2. The method of claim 1 , wherein the array is a single byte array.
3. The method of claim 1 , wherein the access control predicate is associated with a search query.
4. The method of claim 1 , wherein the at least one access control predicate is formatted in a machine-readable binary format.
5. The method of claim 1 , wherein the one or more access control predicates include fixed-width or variable-width tokens.
6. The method of claim 5 , wherein the plurality of access control predicates are sorted according to a respective fixed-width token or variable-width tokens.
7. The method of claim 6 , wherein sorting of the plurality of access control predicates comprises:
calculating offsets of the variable-width tokens of machine-readable binary-formatted access control; and
storing the offsets in an integer array associated with the array.
8. The method of claim 1 , wherein the merging comprises intersecting a pre-sorted memory index structure with a sorted list of terms in a field associated with a search query to collect a bitset of an ordinal number of an intersecting term.
9. The method of claim 8 , wherein the merging comprises iterating through document IDs in a document index and retrieving the term ordinal.
10. The method of claim 8 , wherein the merging comprises testing the ordinal terms against the bitset of a collected ordinal to determine whether the document ID matches against one or more access control predicates.
11. A non-transitory computer program product storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
receive, from a search engine, one or more access control predicates associated with a search query, the one or more access control predicates including fixed-width and/or variable-width tokens;
format the one or more access control predicates in a machine-readable binary format to generate a single byte array;
sort the one or more access control predicates according to their associated fixed-width and/or variable width tokens;
generate a pre-sorted memory index structure associated with the single byte array based on the sorting; and
merge join the pre-sorted memory index structure with an uninverted terms index, the uninverted terms index having a sorted list of all terms in a field associated with the search query, and having a document index mapping a document identifier (ID) to a term ordinal for a specific field, the merge joining identifying document ID matches against the one or more access control predicates.
12. The non-transitory computer program product in accordance with claim 11 , wherein the operations to sort the one or more access control predicates according to their associated fixed-width and/or variable width tokens further comprise operations to calculate offsets of any variable-width tokens of machine-readable binary-formatted access control.
13. The non-transitory computer program product in accordance with claim 12 , wherein the operations to sort the one or more access control predicates according to their associated fixed-width and/or variable width tokens further comprise operations to store in a memory the offsets in an integer array associated with the single byte array.
14. The non-transitory computer program product in accordance with claim 13 , wherein the operations to merge join the pre-sorted memory index structure with an uninverted terms index include operations to intersect the pre-sorted memory index structure with the sorted list of all terms in the field associated with the search query to collect a bitset of an ordinal number of an intersecting term.
15. The non-transitory computer program product in accordance with claim 14 , wherein the operations to merge join the pre-sorted memory index structure with an uninverted terms index further include operations to iterate through document IDs in the document index and retrieving the term ordinal.
16. The non-transitory computer program product in accordance with claim 15 , wherein the operations to merge join the pre-sorted memory index structure with an uninverted terms index further include operations to test an ordinal against the bitset of a collected ordinal to identify the document ID matches against the one or more access control predicates.
17. A system for providing fine-grained access control in a search engine, the system comprising:
at least one programmable processor; and
a machine-readable medium storing instructions that, when executed by the at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
receive, from the search engine, one or more access control predicates associated with a search query, the one or more access control predicates including fixed-width and/or variable-width tokens;
format the one or more access control predicates in a machine-readable binary format to generate a single byte array;
sort the one or more access control predicates according to their associated fixed-width and/or variable width tokens;
generate a pre-sorted memory index structure associated with the single byte array based on the sorting; and
merge join the pre-sorted memory index structure with an uninverted terms index, the uninverted terms index having a sorted list of all terms in a field associated with the search query, and having a document index mapping a document identifier (ID) to a term ordinal for a specific field, the merge joining identifying document ID matches against the one or more access control predicates.
18. The system in accordance with claim 17 , wherein the operations to sort the one or more access control predicates according to their associated fixed-width and/or variable width tokens further comprise operations to calculate offsets of any variable-width tokens of the machine-readable binary-formatted access control.
19. The system in accordance with claim 18 , wherein the operations to sort the one or more access control predicates according to their associated fixed-width and/or variable width tokens further comprise operations to store in a memory the offsets in an integer array associated with the single byte array.
20. The system in accordance with claim 17 , wherein the operations to merge join the pre-sorted memory index structure with an uninverted terms index include operations to intersect the pre-sorted memory index structure with the sorted list of all terms in the field associated with the search query to collect a bitset of an ordinal number of an intersecting term, wherein the operations to merge join the pre-sorted memory index structure with an uninverted terms index further include operations to iterate through document IDs in the document index and retrieving the term ordinal, and wherein the operations to merge join the pre-sorted memory index structure with an uninverted terms index further include operations to test the term ordinal against the bitset of the ordinal number to identify the document ID matches against the one or more access control predicates.