Multi-partitioning data for combination operations

Patent metadata

Field	Value
Publication number	US-11860874-B2
Application number	US-202218051470-A
Country	US
Kind code	B2
Filing date	Oct 31, 2022
Priority date	Sep 25, 2017
Publication date	Jan 2, 2024
Grant date	Jan 2, 2024

Abstract

Systems and methods are disclosed for processing and executing queries against one or more dataset. As part of processing the query, the system determines whether the query is susceptible to a significantly imbalanced partition. In the event, the query is susceptible to an imbalanced partition, the system monitors the query and determines whether to perform a multi-partitioning determination to avoid a significantly imbalanced partition.

First claim

What is claimed:

1. A method comprising:
identifying a first group of data entries and a second group of data entries, wherein the first group of data entries includes a first data entry associated with a first field value and the second group of data entries includes a second data entry associated with the first field value;
assigning the first data entry to a partition; and
forming a combined subgroup for the partition, the combined subgroup including:
a first field corresponding to the first field value,
a second field corresponding to a second field value of the first data entry, and
a third field corresponding to a third field value of the second data entry.

2. The method of claim 1 , the method further comprising calculating a seed value based on a quantity of the first group of data entries and a quantity of the second group of data entries.

3. The method of claim 2 , wherein assigning the first data entry to the partition comprises assigning the first data entry to the partition based on the seed value.

4. The method of claim 2 , wherein the seed value is further based on a combination of the quantity of the first group of data entries and the quantity of the second group of data entries.

5. The method of claim 2 , further comprising assigning each data entry of the second group of data entries to one or more respective partitions based on the seed value.

6. The method of claim 1 , wherein each data entry of the first group of data entries and each data entry of the second group of data entries includes a respective field value for at least two fields.

7. The method of claim 1 , wherein each data entry of the first group of data entries and each data entry of the second group of data entries includes the first field value.

8. The method of claim 1 , the method further comprising determining, based at least in part on an inverted index corresponding to the first field value, that the first data entry and the second data entry satisfy a data entries threshold.

9. The method of claim 8 , the method further comprising based at least in part on determining that the first data entry and the second data entry satisfy the data entries threshold, determining that a search query is susceptible to generating a first partition that includes more data entries than a second partition.

10. The method of claim 8 , wherein assigning the first data entry to the partition comprises assigning the first data entry to the partition based at least in part on determining that the first data entry and the second data entry satisfy the data entries threshold.

11. The method of claim 1 , further comprising identifying the first field value and the second field value based at least in part on a search query.

12. The method of claim 1 , wherein the first group of data entries corresponds to a first dataset and the second group of data entries corresponds to a second dataset.

13. The method of claim 1 , wherein the first group of data entries and the second group of data entries correspond to a same dataset.

14. The method of claim 1 , further comprising performing a reduction operation on the combined subgroup.

15. The method of claim 1 , wherein the first field value and the second field value are associated with a field to be used in a combination operation.

16. The method of claim 1 , wherein the combined subgroup comprises a third group of data entries, wherein each data entry of the third group of data entries includes the first field value.

17. The method of claim 1 , assigning each data entry of the second group of data entries to one of a plurality of partitions, the plurality of partitions comprising the partition.

18. The method of claim 1 , further comprising:
determining that a combination of the combined subgroup and a third group of data entries satisfies a threshold;
identifying one of the combined subgroup or the third group of data entries as a partitioning group;
assigning a third data entry of the partitioning group to a sub-partition; and
forming a second combined subgroup based on the combined subgroup and the third group of data entries.

19. A computing system, comprising:
memory; and
one or more processing devices coupled to the memory and configured to:
identify a first group of data entries and a second group of data entries, wherein the first group of data entries includes a first data entry associated with a first field value and the second group of data entries includes a second data entry associated with the first field value;
assign the first data entry to a partition; and
form a combined subgroup for the partition, the combined subgroup including:
a first field corresponding to the first field value,
a second field corresponding to a second field value of the first data entry, and
a third field corresponding to a third field value of the second data entry.

20. A non-transitory computer readable media comprising computer-executable instructions that, when executed by a computing system, cause the computing system to:
identify a first group of data entries and a second group of data entries, wherein the first group of data entries includes a first data entry associated with a first field value and the second group of data entries includes a second data entry associated with the first field value;
assign the first data entry to a partition; and
form a combined subgroup for the partition, the combined subgroup including:
a first field corresponding to the first field value,
a second field corresponding to a second field value of the first data entry, and
a third field corresponding to a third field value of the second data entry.

Assignees

• Splunk Inc

Inventors

• Bhattacharjee Arindam
• Pal Sourav
• Pride Christopher

Classifications

• G06F16/24554 Primary

  Unary operations; Data partitioning operations · CPC title

• G06F7/5324

  partitioned, i.e. using repetitively a smaller parallel parallel multiplier or using an array of such smaller multipliers · CPC title

• G06F11/3006 Primary

  where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems (multiprogramming arrangements G06F9/46; allocation of resources G06F9/50) · CPC title

• G06F11/3086

  where the reporting involves the use of self describing data formats, i.e. metadata, markup languages, human readable formats · CPC title

• G06F11/3433

  for load management (allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029) · CPC title