Accelerated detection of matching patterns

• US 10,241,979 B2
• Filed: 07/21/2015
• Issued: 03/26/2019
• Est. Priority Date: 07/21/2015
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chavan, Shasank, Palakodety, Ravi, Lui, Dennis
• Primary Examiner(s): Ly, Anh
• Application Number:
  US14/805,414
• Publication Number:
  US 20170024439A1
• Time in Patent Office: 1,344 Days
• CPC Class Codes: G06F 40/126 Character encoding

Abstract

Techniques related to accelerated detection of matching patterns are disclosed. In an embodiment, a method may involve, for a single field of a body of records, contiguously storing field values, thereby storing the field values as a concatenation. The method may also involve identifying a match in the concatenation that matches a value pattern specified by a value pattern expression. The value pattern may include a first partial pattern and a second partial pattern. Further, the method may involve determining that the match is contained in a single field value of the body of records. Still further, the method may involve establishing the match as a matching value. The match may be determined to be contained in the single field value based on searching a data structure comprising length information or offset information for a subset of the field values stored as the concatenation.

Claims

1. A method comprising:

for a single field of a plurality of records, contiguously storing a plurality of field values from said single field, thereby storing said field values as a concatenation in a memory in a contiguous range of an address space of said memory, wherein each field value of said plurality of field values is from a different record of said plurality of records;

identifying a match in said concatenation that matches a value pattern specified by a value pattern expression;

determining that said match is contained in a single field value of said plurality of field values;

establishing said single field value as a matching value,

wherein said method is performed by one or more computing devices.

2. The method of claim 1, wherein determining that said match is contained in said single field value of said plurality of field values comprises finding a particular field value that corresponds to a portion of said match based on searching a data structure comprising length information or offset information for a subset of said field values stored as said concatenation.

3. The method of claim 1, wherein establishing said single field value as said matching value comprises:

obtaining, from a record of said plurality of records that contains said single field value, a code that represents said single field value in a different plurality of records;

identifying one or more records of said different plurality of records that contain said code;

establishing that said one or more records contain said matching value.

4. The method of claim 1, wherein storing said field values as said concatenation comprises sorting said field values prior to contiguously storing said field values.

5. The method of claim 4, wherein identifying said match in said concatenation that matches said value pattern specified by said value pattern expression comprises skipping any portion of said concatenation that is determined, based on said sorting, to be unable to match said value pattern.

6. The method of claim 1, wherein identifying said match in said concatenation that matches said value pattern specified by said value pattern expression comprises skipping any portion of said concatenation that is determined, based on a sequential order indicated by said value pattern, to be unable to match said value pattern.

7. The method of claim 1, wherein identifying said match in said concatenation that matches said value pattern specified by said value pattern expression comprises searching for, in turn, each partial pattern of a plurality of partial patterns of said value pattern.

8. A method comprising:

for a single field of a plurality of records, contiguously storing a plurality of field values from said single field, thereby storing said field values as a concatenation in a memory in a contiguous range of an address space of said memory, wherein each field value of said plurality of field values is from a different record of said plurality of records;

identifying a field value of said plurality of field values in said concatenation that matches a value pattern specified by a value pattern expression, wherein identifying said field value comprises;

based on said value pattern, generating a sequence of partial patterns, each of said partial patterns specifying a portion of said value pattern, said sequence of partial patterns having a sequential order;

in said sequential order, iteratively finding a respective match for each of said partial patterns until each respective match is found in a same record of said plurality of records;

when a respective match for each said partial patterns is found in said same record, storing data specifying that said same record contains said field value that matches said value pattern,

wherein said method is performed by one or more computing devices.

9. The method of claim 8, wherein finding a respective match for each of said partial patterns until each respective match is found in a same record includes searching a data structure comprising length information or offset information for a subset of said field values stored as said concatenation.

10. The method of claim 8, wherein identifying said field value comprises:

obtaining, from said same record of said plurality of records, a code that represents said field value in a different plurality of records;

identifying one or more records of said different plurality of records that contain said code;

establishing that said one or more records of said different plurality of records contain said field value.

11. The method of claim 8, the method further including sorting said field values prior to being stored as said concatenation.

12. The method of claim 11, wherein identifying a field value of said plurality of field values in said concatenation that matches a value pattern includes skipping any portion of said concatenation that is determined, based on said sorting, to be unable to match each of said partial patterns.

13. The method of claim 8, wherein identifying a field value of said plurality of field values in said concatenation that matches a value pattern includes skipping any portion of said concatenation that is determined, based on said sequential order, to be unable to match each of said partial patterns.

14. One or more non-transitory storage media storing instructions which, when processed by one or more computing devices, cause:

for a single field of a plurality of records, contiguously storing a plurality of field values from a single field, thereby storing the field values as a concatenation in a memory in a contiguous range of an address space of said memory, wherein each field value of said plurality of field values is from a different record of said plurality of records;

identifying a match in said concatenation that matches a value pattern specified by a value pattern expression;

determining that said match is contained in a single field value of said plurality of field values;

establishing said single field value as a matching value.

15. The one or more non-transitory storage media of claim 14, wherein determining that said match is contained in said single field value of said plurality of field values comprises finding a particular field value that corresponds to a portion of said match based on searching a data structure comprising length information or offset information for a subset of said field values stored as said concatenation.

16. The one or more non-transitory storage media of claim 14, wherein establishing said single field value as said matching value comprises:

obtaining, from a record of said plurality of records that contains said single field value, a code that represents said single field value in a different plurality of records;

identifying one or more records of said different plurality of records that contain said code;

establishing that said one or more records contain said matching value.

17. The one or more non-transitory storage media of claim 14, wherein storing said field values as said concatenation comprises sorting said field values prior to contiguously storing said field values.

18. The one or more non-transitory storage media of claim 17, wherein identifying said match in said concatenation that matches said value pattern specified by said value pattern expression comprises skipping any portion of said concatenation that is determined, based on said sorting, to be unable to match said value pattern.

19. The one or more non-transitory storage media of claim 14, wherein identifying said match in said concatenation that matches said value pattern specified by said value pattern expression comprises skipping any portion of said concatenation that is determined, based on a sequential order indicated by said value pattern, to be unable to match said value pattern.

20. The one or more non-transitory storage media of claim 14, wherein identifying said match in said concatenation that matches said value pattern specified by said value pattern expression comprises searching for, in turn, each partial pattern of a plurality of partial patterns of said value pattern.

21. One or more non-transitory storage media storing instructions, which when processed by one or more computing devices, cause:

for a single field of a plurality of records, contiguously storing a plurality of field values from said single field, thereby storing said field values as a concatenation in a memory in a contiguous range of an address space of said memory, wherein each field value of said plurality of field values is from a different record of said plurality of records;

identifying a field value of said plurality of field values in said concatenation that matches a value pattern specified by a value pattern expression, wherein identifying said field value comprises;

based on said value pattern, generating a sequence of partial patterns, each of said partial patterns specifying a portion of said value pattern, said sequence of partial patterns having a sequential order;

in said sequential order, iteratively finding a respective match for each of said partial patterns until each respective match is found in a same record of said plurality of records; and

when a respective match for each said partial patterns is found in said same record, storing data specifying that said same record contains said field value that matches said value pattern.

22. The one or more non-transitory storage media of claim 21, wherein finding a respective match for each of said partial patterns until each respective match is found in a same record includes searching a data structure comprising length information or offset information for a subset of said field values stored as said concatenation.

23. The one or more non-transitory storage media of claim 21, wherein identifying said field value comprises:

obtaining, from said same record of said plurality of records, a code that represents said field value in a different plurality of records;

identifying one or more records of said different plurality of records that contain said code;

establishing that said one or more records of said different plurality of records contain said field value.

24. The one or more non-transitory storage media of claim 21, wherein the instructions include instructions that, when processed by said one or more computing devices, cause sorting said field values prior to being stored as said concatenation.

25. The one or more non-transitory storage media of claim 24, wherein identifying a field value of said plurality of field values in said concatenation that matches a value pattern includes skipping any portion of said concatenation that is determined, based on said sorting, to be unable to match each of said partial patterns.

26. The one or more non-transitory storage media of claim 21, wherein identifying a field value of said plurality of field values in said concatenation that matches a value pattern includes skipping any portion of said concatenation that is determined, based on said sequential order, to be unable to match each of said partial patterns.