Patent Document ID: 10049134
Application ID: 14303077
Patent Status: 1

Claim One:
1. A system for processing a query of a tree-based dataset, comprising: a memory and at least one processor coupled to the memory, wherein the at least one processor is configured to: receive the query; analyze the query and the dataset to create an execution plan for the query, wherein, in analyzing the query and the dataset to create the execution plan, the at least one processor is further configured to: partition traversals over the dataset into sequential and parallel components; distribute the sequential and the parallel components across a plurality of processing threads that independently traverse their portion of the dataset and compute local results; and compare, prior to partitioning the traversals, an allowed number of running work units to an actual number of running work units for the query; wherein the allowed number of running work units is a function of a ceiling of a number of operation threads used for a given transaction with respect to a number of parallelized transactions; and wherein, in partitioning the traversals over the dataset, the at least one processor is configured to: split a current work unit for parallelization in response to the allowed number of running work units exceeding the actual number of running work units and queried work units for the query; split a current work unit for interruption in response to the allowed number of running work units being exceeded by the actual number of running work units for the query; and merge the local results to compute a final result, wherein, in merging the local results to compute the final result, the at least one processor is configured to merge nodes of a plurality of sub-trees to create a merged sub-tree; wherein, in splitting the current work unit for parallelization, the at least one processor is further configured to: split an unvisited portion of the current work unit to distribute the current work unit across a plurality of work units; and determine a number of the plurality of work units based on a minimum of a number of nodes left unvisited at a level where the splitting occurs and a number of available processing threads plus one operation thread to account for the current work unit.