HIGHCONCURRENCY QUERY OPERATOR AND METHOD

• US 20100293135A1
• Filed: 05/12/2010
• Published: 11/18/2010
• Est. Priority Date: 05/12/2009
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Aster Data Systems, Inc. (Teradata Corporation)
• Inventors: Polyzotis, Neoklis, CANDEA, GEORGE
• Granted Patent: US 8,285,709 B2
• Time in Patent Office: Days
• US Class Current: 707/602
• CPC Class Codes: G06F 16/2453 Query optimisation

Abstract

In one embodiment, a method includes concurrently executing a set of multiple queries, through a processor, to improve a resource usage within a data warehouse system. The method also includes permitting a group of users of the data warehouse system to simultaneously run a set of queries. In addition, the method includes applying a high-concurrency query operator to continuously optimize a large number of concurrent queries for a set of highly concurrent dynamic workloads.

Claims

1. A method comprising:

concurrently executing a set of multiple queries, through a processor, to improve a resource usage within a data warehouse system;

permitting a group of users of the data warehouse system to simultaneously run a set of queries; and

applying a high-concurrency query operator to continuously optimize a large number of concurrent queries for a set of highly concurrent dynamic workloads.

2. The method of claim 1, further comprising:

efficiently evaluating the set of queries through the high-concurrency query operator;

increasing a query throughput and adjusting a query response time when the number of concurrent queries increases; and

sharing a set of resources associated with the data warehouse system across the set of queries.

3. The method of claim 2, wherein the high concurrency query operator is a physical operator that allows a high-concurrency in a query and other queries that involve at least one of a JOIN operator.

4. The method of claim 3, wherein the set of resources associated with the data warehouse system is at least one of a disk I/O resource, a computation resource, and an in-memory data resource.

5. The method of claim 4, further comprising:

limiting a redundancy of a workload by answering the set of queries during a first scan of a fact table; and

reducing an output time and a set of costs associated with a corresponding set of results of the set of queries.

6. The method of claim 5, further comprising:

assigning a unique positive identifier information to a particular query in the set of queries when the particular query registers with the operator;

reusing the unique positive identifier information after an evaluation of the particular query is complete; and

utilizing a set of system parameters to organize, denote and bound the set of concurrent queries.

7. The method of claim 6, further comprising:

applying the high concurrency query operator to a set of star queries,

wherein a star query filters the fact table through a set of dimension predicates.

8. The method of claim 7, further comprising:

continuously performing a scan of the fact table; and

utilizing a pipeline to receive an input from a continuous scan of the fact table and to pipe an output to set of aggregation operators to compute a set of results associated with the set of queries,

wherein the pipeline comprises of at least one of a preprocessor, a filter, a pipeline manager and a distributor.

9. The method of claim 8, further comprising:

processing a fact tuple through a special filter designated for a particular dimension table,

wherein the fact tuple is a sequence of a specific number of values gathered from a set of dimension tables.

10. The method of claim 9, further comprising:

marking, through the preprocessor, a particular point where a given query enters the high-concurrency query operator;

signaling, through the preprocessor, a completion of the given query when the continuous scan of the fact table wraps back to the particular point; and

receiving from the continuous scan and forwarding, through the preprocessor, a set of fact tuples to a remainder of the pipeline.

11. The method of claim 10, further comprising:

augmenting the fact tuple with a bit vector containing a bit for at least one query in a given workload.

12. The method of claim 11, further comprising:

receiving, examining and subsequently routing to at least one aggregation operator, a set of relevant fact tuples for at least one query in the given workload through the distributor.

13. The method of claim 12, further comprising:

storing a tuple of the particular dimension table that satisfies a set of corresponding dimension predicates in a dimension hash table.

14. The method of claim 13, further comprising:

applying the filter to encode the set of corresponding dimension predicates associated with the set of queries; and

probing, through the filter, a corresponding dimension hash table to identify a set of joining dimension tuples.

15. The method of claim 14, further comprising:

designating one of at least two values for the bit vector based on a predefined criteria if the value of a joining dimension tuple corresponds to a foreign key value of a specific fact tuple;

designating another one of at least two values for the bit vector based on the predefined criteria if the value of the joining dimension tuple does not correspond to the foreign key value of the specific fact tuple; and

discarding the specific fact tuple when the value of the joining dimension tuple does not correspond to the foreign key value of the specific fact tuple.

16. The method of claim 15, further comprising:

applying the pipeline manager to regulate an operation of the pipeline, to register a new query with the high-concurrency query operator and to clean up after an execution of a set of registered queries;

monitoring a performance of the pipeline and optimizing the performance of the pipeline as needed to maximize the query throughput through the pipeline manager; and

utilizing a separate execution context for the pipeline manager.

17. The method of claim 16, further comprising:

sharing the fact table among the set of queries;

filtering an individual fact tuple against the set of queries with a single dimension table probe to generate a set of dimension tuples for the individual fact tuple; and

storing a union of the dimension tuples.

18. The method of claim 17, further comprising:

permitting a change in an order in which a sequence of filters is applied; and

permitting a set of filter operators to run in parallel.

19. The method of claim 18, further comprising:

associating a corresponding dimension filter with a dimension table; and

annotating the fact tuple based on a set of join properties associated with the fact tuple and the dimension table.

20. The method of claim 19, further comprising:

performing an update on the dimension hash table, through a dimension preprocessor when the new query is introduced;

reading and augmenting the fact tuple with a set of necessary metadata through a fact preprocessor;

applying a set of dimension filters to the fact tuple;

annotating the fact tuple, through at least one dimension filter of the set of dimension filters; and

applying the distributor to receive the annotated fact tuple and to distribute a copy of the fact tuple into a result set of the new query.

21. The method of claim 20, further comprising:

mapping a particular dimension table on the dimension hash table when the particular dimension table is referenced by at least one query in the set of queries;

storing a set of dimension tuples associated with the particular dimension table in the dimension hash table to be selected by at least one query in the workload; and

storing a particular dimension tuple exactly one time regardless of a number of queries referencing the particular dimension tuple.

22. The method of claim 21, further comprising:

augmenting the particular dimension table with a selection predicate, through the dimension preprocessor; and

propagating an information associated with the selection predicate to the set of dimension tuples, through the dimension preprocessor, when the new query is introduced.

23. The method of claim 22, further comprising:

updating a corresponding predicate bitvector when the new query is introduced; and

utilizing a static structure architecture to implement the dimension hash tables to improve a cache hit rate.

24. The method of claim 23, further comprising:

including a pointer in the corresponding predicate bitvector to improve a hit rate of an L1 and an L2 cache memory.

25. The method of claim 8, further comprising:

applying the preprocessor to process a fact tuple through the pipeline;

attaching a bitvector to the fact tuple to trace a relevance of the fact tuple to a set of queries;

modifying the bitvector when the fact tuple is processed by the filter; and

utilizing the bitvector to route the fact tuple to the set of aggregation operators.

26. The method of claim 25, further comprising:

directly extracting a needed fact table attribute from the fact tuple through an aggregation operator; and

utilizing the foreign key in the fact tuple to probe for a joining dimension tuple to access a set of attributes associated with a particular dimension table.

27. The method of claim 26, further comprising:

permitting the joining dimension tuple to remain in a memory state until the fact tuple reaches the distributor by attaching a set of memory pointers to the joining dimension tuple; and

simultaneously permitting the aggregation operator to access a set of needed information associated with the fact tuple.

28. The method of claim 27, further comprising:

satisfying a set of multiple concurrent queries with one scan of the fact table;

continuously scanning the fact table in a circular fashion to generate a bandwagon of a given set of fact tuples; and

transporting the given set of fact tuples to the fact preprocessor through the bandwagon.

29. The method of claim 28, further comprising:

augmenting a given fact tuple with a join bitvector through the fact preprocessor; and

recording, through the join bitvector, a join status of the given fact tuple based on a set of predefined join criteria.

30. The method of claim 29, further comprising:

generating a key having a numerical value to an individual fact tuple at a load time at a worker node;

organizing a set of keys in an ascending order;

when the individual fact tuple is moved from one worker node to an other worker node, regenerating the key upon the load time at the other worker node; and

individually assigning a specific offset of the set of keys to every worker node within a set of worker nodes to prevent an overlap of the generated key values.

31. The method of claim 30, further comprising:

permitting the bandwagon to go through a set of dimension filters after leaving the fact preprocessor;

utilizing the key of the fact tuple to find a corresponding dimension tuple that it joins with;

performing an AND operation between the join bitvector of the fact tuple and the predicate bitvector of the dimension tuple;

designating one of at least two values for a bit vector associated with the query based on the results of the AND operation; and

discarding the fact tuple based on a negative result of the AND operation.

32. The method of claim 31, further comprising:

determining, through the distributor, an appropriate query result set for an individual tuple;

completing a result set for the individual query when the individual query has considered an entire set of fact tuples;

tracking, through the distributor, an identification information for the first fact tuple of the query; and

flushing out the result set to a queen node when the distributor encounters the identification information for the first fact tuple of the query.

33. The method of claim 32, further comprising:

identifying a dimension table relevant to a given query through a bit vector associated with the given query; and

updating the bit vector when a new query is introduced.

34. The method of claim 8, further comprising:

automatically augmenting a distribution when a specific query involves a GROUP BY statement on a column;

grouping the fact tuples based on the GROUP by statement; and

augmenting an in-memory dimension table entry with a hash of an individual column.

35. The method of claim 8, further comprising:

registering a query through the pipeline manager;

updating an information associated with a newly registered query in the remaining components, through the pipeline manager; and

installing the newly registered query in the preprocessor and the distributor.

36. The method of claim 35, further comprising:

suspending a processing of an input tuple in the preprocessor to stall the pipeline;

enabling an addition of a set of new filters in the pipeline to cover the dimension tables referenced by the query;

marking a first unprocessed input fact tuple of a stream as the first fact tuple that the query need not process;

identifying an end of the query processing through the marking of the first unprocessed input fact tuple; and

appending a special query-start control tuple in an output queue of the preprocessor.

37. The method of claim 36, further comprising:

facilitating a query registration in the pipeline manager;

proceeding with the query registration in the pipeline manager in parallel with the processing of the fact tuples through the pipeline; and

ensuring a minimal disruption of the set of other queries.

38. The method of claim 8, further comprising:

finalizing a query when a continuous scan wraps around to reach a first fact tuple identification information;

removing the query from the set of queries after the first fact tuple identification information is reached; and

ensuring that a corresponding bit of the bit vector of the first fact tuple is switched off.

39. The method of claim 38, further comprising:

forwarding a control tuple through the pipeline to the distributor; and

finalizing the aggregation operators for the query and outputting a result set through the distributor.

40. The method of claim 39, further comprising:

clearing a set of information pertinent to the query from the dimension hash table after finalization.

41. The method of claim 8, further comprising:

determining an order of a set of filters in the pipeline to minimize an expected number of probes for a fact tuple;

monitoring, at runtime, a selectivity of a particular filter to generate a set of gathered statistics associated with the particular filter;

optimizing the order of set of filters based on the set of gathered statistics associated with the particular filter; and

continuously monitoring and reoptimizing the order of the filters through the pipeline manager.

42. The method of claim 8, further comprising:

serializing an admission of a set of new queries in the high concurrency query operator when there is an update on a dimension table;

returning a set of fact tuples corresponding to a set of snapshots in a current query mix when there is an update on the dimension table;

creating a high concurrency query join operator for each snapshot to be referenced; and

registering the set of new queries to a respective operator.

43. The method of claim 8, further comprising:

reordering a sequence of dimension filters to dispose a set of unnecessary fact tuples as early as possible; and

optimizing an order of the sequence of the dimension filters to achieve a higher disposal rate of the set of unnecessary fact tuples within a smaller period of time.

44. The method of claim 8, further comprising:

mapping at least one of the preprocessor, the filter, and the distributor to a set of multiple threads; and

mapping the set of multiple threads to a set of different processor cores through an operating system.

45. The method of claim 44, further comprising:

permitting a flexible mapping of a filter to a thread by collapsing multiple adjacent filters to a stage; and

assigning multiple threads to each stage to maximize parallelism.

46. The method of claim 45, further comprising:

assigning a single stage to each filter, with the option of having a different number of threads per stage, through a vertical configuration; and

assigning a single stage to a complete sequence of filters and all the threads to the single stage, through a horizontal configuration.

47. The method of claim 8, further comprising:

reducing a cost associated with a memory management synchronization through a specialized allocator;

preallocating a data structure for an in-flight tuple based on a special number associated with the in-flight tuple;

determining the special number associated with the in-flight tuple based on a maximum length of a queue and an upper bound of a number of threads; and

applying the specialized allocator to reserve and release a set of tuples using a set of bitmap operations.

48. The method of claim 47, further comprising:

reducing a signaling and a scheduling overhead by waking up a consuming thread only when an input queue associated with the consuming thread is almost full.

49. The method of claim 8, further comprising:

measuring a performance through the query throughput and a set of values associated with a mean of a set of response times and a set of values associated with a standard deviation of the set of response times.

50. A pipeline system to evaluate concurrent queries comprising:

a dimension preprocessor to perform updates and to augment at least one dimension table with a selection predicate;

a fact preprocessor to read fact data and to augment the fact data with necessary metadata;

at least one dimension filter to retrieve the fact data from an input queue to probe a corresponding dimension hash table to identify a joining dimension data, and to annotate the fact data augmented by the fact preprocessor; and

a distributor to receive the annotated fact data from at least one dimension filter and to distribute copies of the annotated fact data into queries'"'"' result sets.

51. The system of claim 50, further comprising a fact table in the fact preprocessor configured to store the fact data.

52. The system of claim 51, wherein the dimension table is data table configured to store information associated with other data that affects how it is processed and stored in a database.

53. The system of claim 52, wherein the fact data comprises a data point associated with a time.

54. The system of claim 53, further comprising a pipeline manager to regulate an operation of the pipeline, to register a new query with the high-concurrency query operator and to clean up after an execution of a set of registered queries

55. A method of evaluating concurrent queries in the pipeline comprising:

performing updates through a dimension preprocessor to augment at least one dimension table with a selection predicate;

reading a fact data and augmenting the fact data with necessary metadata through a fact preprocessor;

retrieving fact data through at least one dimension filter from an input queue to probe a corresponding dimension hash table to identify a joining dimension data, wherein the dimension filter to annotate the fact data augmented by the fact preprocessor; and

receiving through a distributor, the annotated fact data from the at least one dimension filter and distributing copies of the annotated fact data into queries'"'"' result sets.

56. The method of claim 55, further comprising:

configuring a fact table in the fact preprocessor to store the fact data.

57. The method of claim 56, wherein the dimension table is a data table configured to store information associated with other data that affects how it is processed and stored in a database.

58. The method of claim 57, wherein the fact data comprises a data point associated with a time.

59. The method of claim 58, further comprising:

receiving an input from a continuous scan of the fact table; and

receiving, examining and subsequently routing to at least one aggregation operator, a set of relevant fact data for at least one query in the given workload through the distributor.

60. The method of claim 59, further wherein the pipeline comprises of at least one of a preprocessor, a filter, a pipeline manager and the distributor.

61. The method of claim 60, further comprising:

applying the pipeline manager to regulate an operation of the pipeline, to register a new query with the high-concurrency query operator and to clean up after an execution of a set of registered queries;

monitoring a performance of the pipeline and optimizing the performance of the pipeline as needed to maximize the query throughput through the pipeline manager; and

utilizing a separate execution context for the pipeline manager.

62. The method of claim 61, further comprising:

reordering a sequence of the dimension filters to dispose a set of unnecessary fact tuples as early as possible; and

optimizing an order of the sequence of the dimension filters to achieve a higher disposal rate of the set of unnecessary fact tuples in a smaller period of time.