MANAGING LARGE SCALE ASSOCIATION SETS USING OPTIMIZED BIT MAP REPRESENTATIONS

• US 20180268009A1
• Filed: 03/15/2017
• Published: 09/20/2018
• Est. Priority Date: 03/15/2017
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Desai, Rajesh M., Jayapandian, Magesh, Leong, Iun V., Perez, Justo L., Raphael, Roger C., Valencia, Gabriel
• Granted Patent: US 10,452,631 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2455 Query execution

Abstract

Processing a database query for sets of data includes assigning a unique identifier from an integer space to each entity within data and creating one or more sets of entities each pertaining to a corresponding entity within the data. A representation is then generated on disk for each set of entities, wherein each representation encompasses and is suited for a range of the unique identifiers of entities within a corresponding set and indicates a presence of an entity within that corresponding set. Finally, a query is processed based on the representation for each set of entities to retrieve data satisfying the query, wherein the representation provides a constant time for association and dissociation operations that are append-only operations with deferred merge and automatic filtering of deleted and duplicate entities at query time.

Claims

1. A method of processing a database query for sets of data comprising:

assigning a unique identifier from an integer space to each entity within data and creating one or more sets of entities each pertaining to a corresponding entity within the data;

generating a representation on disk for each set of entities, wherein each representation encompasses and is suited for a range of the unique identifiers of entities within a corresponding set and indicates a presence of an entity within that corresponding set; and

processing a query based on the representation for each set of entities to retrieve data satisfying the query, wherein the representation provides a constant time for association and dissociation operations that are append-only operations with deferred merge and automatic filtering of deleted and duplicate entities at query time.

2. The method of claim 1, wherein at least one set of entities includes entities associated with a specific entity.

3. The method of claim 1, wherein at least one set of entities includes entities dissociated with a specific entity.

4. The method of claim 1, wherein an entity represents one or more instances from a group of a person, a document, an event, and an object.

5. The method of claim 1, wherein each of the set of entities is partitioned into a plurality of segments of entity identifiers, and metadata for an entity identifier of a segment of a set of entities is stored inline with the segment as a payload.

6. The method of claim 1, further comprising:

partitioning a set of entities represented by entity identifiers into a plurality of segments, wherein content of each segment and metadata for each segment is stored in separate data objects, wherein each segment is one of an insert type to indicate association and a delete type to indicate dissociation, and a segment size is based on a request size, compression type, and run-time optimizations, and wherein the plurality of segments are chronologically ordered and used to generate content of the set of entities by merging, inserting, and deleting segments; and

performing operations on the plurality of segments concurrently.

7. The method of claim 6, wherein processing the query further comprises:

evaluating the query for the plurality of segments and combining results from each of the evaluated segments.

8. The method of claim 1, wherein a set of entities includes a multi-set containing non-unique entities with duplicate entity identifiers preserved in a physical representation of the set of entities, and wherein the query requests the set or multi-set representation.

9. A system for processing a database query for sets of data comprising:

a processor configured to;

assign a unique identifier from an integer space to each entity within data and creating one or more sets of entities each pertaining to a corresponding entity within the data;

generate a representation on disk for each set of entities, wherein each representation encompasses and is suited for a range of the unique identifiers of entities within a corresponding set and indicates a presence of an entity within that corresponding set; and

process a query based on the representation for each set of entities to retrieve data satisfying the query, wherein the representation provides a constant time for association and dissociation operations that are append-only operations with deferred merge and automatic filtering of deleted and duplicate entities at query time.

10. The system of claim 9, wherein at least one set of entities includes entities associated with a specific entity.

11. The system of claim 9, wherein at least one set of entities includes entities dissociated with a specific entity.

12. The system of claim 9, wherein an entity represents one or more instances from a group of a person, a document, an event, and an object.

13. The system of claim 9, wherein each of the set of entities is partitioned into a plurality of segments of entity identifiers, and metadata for an entity identifier of a segment of a set of entities is stored inline with the segment as a payload.

14. The system of claim 9, wherein the processor is further configured to:

partition a set of entities represented by entity identifiers into a plurality of segments, wherein content of each segment and metadata for each segment is stored in separate data objects, wherein each segment is one of an insert type to indicate association and a delete type to indicate dissociation, and a segment size is based on a request size, compression type, and run-time optimizations, and wherein the plurality of segments are chronologically ordered and used to generate content of the set of entities by merging, inserting, and deleting segments; and

perform operations on the plurality of segments concurrently.

15. The system of claim 14, wherein processing the query further comprises:

evaluating the query for the plurality of segments and combining results from each of the evaluated segments.

16. The system of claim 9, wherein a set of entities includes a multi-set containing non-unique entities with duplicate entity identifiers preserved in a physical representation of the set of entities, and wherein the query requests the set or multi-set representation.

17. A computer program product for processing a database query for sets of data, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:

assign a unique identifier from an integer space to each entity within data and creating one or more sets of entities each pertaining to a corresponding entity within the data;

generate a representation on disk for each set of entities, wherein each representation encompasses and is suited for a range of the unique identifiers of entities within a corresponding set and indicates a presence of an entity within that corresponding set; and

process a query based on the representation for each set of entities to retrieve data satisfying the query, wherein the representation provides a constant time for association and dissociation operations that are append-only operations with deferred merge and automatic filtering of deleted and duplicate entities at query time.

18. The computer program product of claim 17, wherein at least one set of entities includes entities associated with a specific entity.

19. The computer program product of claim 17, wherein at least one set of entities includes entities dissociated with a specific entity.

20. The computer program product of claim 17, wherein an entity represents one or more instances from a group of a person, a document, an event, and an object.

21. The computer program product of claim 17, wherein each of the set of entities is partitioned into a plurality of segments of entity identifiers, and metadata for an entity identifier of a segment of a set of entities is stored inline with the segment as a payload.

22. The computer program product of claim 17, further comprising:

partitioning a set of entities represented by entity identifiers into a plurality of segments, wherein content of each segment and metadata for each segment is stored in separate data objects, wherein each segment is one of an insert type to indicate association and a delete type to indicate dissociation, and a segment size is based on a request size, compression type, and run-time optimizations, and wherein the plurality of segments are chronologically ordered and used to generate content of the set of entities by merging, inserting, and deleting segments; and

performing operations on the plurality of segments concurrently.

23. The computer program product of claim 22, wherein processing the query further comprises:

evaluating the query for the plurality of segments and combining results from each of the evaluated segments.

24. The computer program product of claim 17, wherein a set of entities includes a multi-set containing non-unique entities with duplicate entity identifiers preserved in a physical representation of the set of entities, and wherein the query requests the set or multi-set representation.