Patent application EP20178865A (EP), filed 2020-06-09
Publication number: EP3751428A1
Title: IMPLICIT PARTITIONING
Abstract: A method, a system and a computer program product for implicitly partitioning data. An index in a plurality of indexes is selected. The index corresponds to a plurality of ranges of data values stored in a plurality of database slices of a database. A partitioning structure for the selected index is generated. The partitioning structure includes a plurality of hierarchically arranged nodes. Each node corresponds to a range of data values in the plurality of ranges of data values stored and at least one database slice storing corresponding range of data values. Another range of data values is received for storage in the database. Using the partitioning structure, a node in the partitioning structure corresponding to the received range of data values and a corresponding database slice for storing the received range of data values are identified. The received range of data values is stored in the identified database slice.
IPC codes: G06F  16/    22            A I
G06F  16/    27            A I
Claims: number: 1
text: A computer-implemented method, comprising:
number: 2
text: The method according to claim 1, wherein the identifying includes identifying another database slice configured to store the received another range of data values upon a determination that the identified database slice is unable to store the received another range of data values.
number: 3
text: The method according to claim 2, wherein the storing includes storing the received another range of data values in the identified another database slice.
number: 4
text: The method according to claim 1, wherein the identifying includes generating another database slice configured to store the received another range of data values.
number: 5
text: The method according to claim 4, further comprising modifying the generated partitioning structure to include at least another node corresponding to the received another range of data values.
number: 6
text: The method according to claim 4, wherein the another database slice is generated upon a determination that the identified database slice is unable to store the received another range of data values.
number: 7
text: The method according to claim 6, wherein the storing includes storing the received another range of data values in the generated another database slice.
number: 8
text: The method according to claim 1, wherein at least one of the node and the database slice are identified using the selected index.
number: 9
text: The method according to claim 1, wherein the identifying is performed using at least one insert policy defining at least one of the node in the generated partitioning structure corresponding to the received another range of data values and at least one corresponding database slice configured to store the received another range of data values.
number: 10
text: The method according to claim 9, wherein the identifying includes identifying, in accordance with the insert policy, using the generated partitioning structure, another node in the generated partitioning structure corresponding to the received another range of data values using a predetermined threshold hop distance between the identified node and the another node and identifying at least one database slice corresponding to the another node configured to store the received another range of data values.
number: 11
text: The method according to claim 10, wherein the predetermined threshold hop distance is at least two hops.
number: 12
text: The method according to claim 1, wherein the storing includes at least one of the following: insertion of the received another range of data into the identified at least one database slice, modification of data stored in the identified at least one database slice using the received another range of data, deletion of data stored in the identified at least one database slice, and any combination thereof.
number: 13
text: The method according to claim 1, further comprising
selecting another index in a plurality of indexes, the another index corresponding to a another plurality of ranges of data values stored in the plurality of database slices of the database;
generating another partitioning structure for the selected another index, the another partitioning structure including another plurality of hierarchically arranged nodes, each node corresponding to another range of data values in the plurality of another ranges of data values stored and the at least one database slice storing the corresponding another range of data values;
identifying, using the generated another partitioning structure and the generated partitioning structure, at least one database slice configured to store the received another range of data values; and
storing the received another range of data values in the identified at least one database slice.
number: 14
text: A system comprising:
number: 15
text: A computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform the method as claimed in any one of claims 1-13.
Office action: search_report, dated 2020-12-16
Rejection reasons: novelty_epc_54
Prior art cited: ref_id: US2018129696A1
ref_type: patent
severity: background
ref_id: US8738657B2
ref_type: patent
severity: background
ref_id: - TOBIN J LEHMAN ET AL: "A Study of Index Structures for Main Memory Database Management Systems", 1 January 1986 (1986-01-01), XP055088964, Retrieved from the Internet <URL:http://library.riphah.edu.pk/acm/disk_1/text/1-4/VLDB86/P294.PDF> [retrieved on 20131118]
ref_type: npl
severity: background
ref_id: - STRATOS IDREOS ET AL: "Self-organizing tuple reconstruction in column-stores", SIGMOD-PODS '09 : COMPILATION PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON MANAGEMENT DATA & 28TH SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS ; PROVIDENCE, RHODE ISLAND, USA, ASSOCIATION FOR COMPUTING MACHINERY, NEW YORK, NY, 29 June 2009 (2009-06-29), pages 297 - 308, XP058221486, ISBN: 978-1-60558-551-2, DOI: 10.1145/1559845.1559878
ref_type: npl
severity: background
ref_id: - ORESTIS POLYCHRONIOU ET AL: "A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort", PROCEEDINGS OF THE 2014 ACM SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, SIGMOD '14, 22 June 2014 (2014-06-22), New York, New York, USA, pages 755 - 766, XP055735005, ISBN: 978-1-4503-2376-5, DOI: 10.1145/2588555.2610522
ref_type: npl
severity: background
ref_id: US8738657
ref_type: patent
severity: background
ref_id: US2018129696
ref_type: patent
severity: background
ref_id: - Tobin J Lehman ET AL, "A Study of Index Structures for Main Memory Database Management Systems", (19860101), URL: http://library.riphah.edu.pk/acm/disk_1/text/1-4/VLDB86/P294.PDF, (20131118), XP055088964 [X] 1,14-15 * page  298, column  l, paragraph  l  - column  r, paragraph  1 * * page  296, column  r, paragraph  1 * * page  297, column  l, paragraph  2  - paragraph  3 * [I] 2-13
ref_type: npl
severity: novelty_destroying
ref_id: - STRATOS IDREOS ET AL, "Self-organizing tuple reconstruction in column-stores", SIGMOD-PODS '09 : COMPILATION PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON MANAGEMENT DATA & 28TH SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS ; PROVIDENCE, RHODE ISLAND, USA, ASSOCIATION FOR COMPUTING MACHINERY, NEW YORK, NY, (20090629), doi:10.1145/1559845.1559878, ISBN 978-1-60558-551-2, pages 297 - 308, XP058221486 [A] 1-15 * page  299  - page  301 *
ref_type: npl
severity: background
ref_id: - ORESTIS POLYCHRONIOU ET AL, "A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort", PROCEEDINGS OF THE 2014 ACM SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, SIGMOD '14, New York, New York, USA, (20140622), doi:10.1145/2588555.2610522, ISBN 978-1-4503-2376-5, pages 755 - 766, XP055735005 [A] 1-15 * page  760 * * page  763, column  l, paragraph  l  - column  r, paragraph  4 *
ref_type: npl
severity: background
Final disposition: pending (2020-12-16)