Microsoft Technology Licensing, LLC

Jin Sun

Marc Todd Friedman

Jaliya Nishantha Ekanayake

Clemens Alden Szyperski

Haibo Lin

Shi Qiao

Raghunath Ramakrishnan

Zhicheng Yin

Omid Afnan

Yifung Lin

Tao Guan

Yongchul Kwon

José A Blakeley

Ming Li

Shuffling of into partitions by first grouping input vertices of a limited number. Each group of input vertices may then be simply shuffled into a corresponding group of intermediate vertices, such as by broadcasting. A second grouping occurs in which the intermediate vertices are grouped by partition. The intermediate vertices then shuffle into corresponding output vertices for the respective partitions of that group. If the intermediate vertices are still too large, then this shuffling may involve recursively performing the shuffling just described, until ultimately the number of intermediate vertices shuffling into the output vertices is likewise limited. Thus, the final shuffling into the output vertices might also be simply performed by broadcasting.

Grouped shuffling of partition vertices

Reducing data skew when performing computational jobs (such as responding to complex queries or queries on big data sets). To gather performance information for a vertex in a distributed stage, the distributed stage is processed and the resulting performance information being generated. The system then identifies a performance outlier of the vertices, which varies from a performance norm of other vertices. A trigger instruction is then generated that is structured to trigger the performance outlier vertex to gather data distribution information of the data that the performance outlier vertex previously processed. The trigger instruction may thus be executed to cause the performance outlier vertex to gather the data distribution information for evaluation for data skew.

Data skew finding and analysis

Aspects extend to methods, systems, and computer program products for optimally pipelining result sets with fault tolerance in distributed query execution. Distributed computing jobs are optimized by dividing the distributed computing jobs into one or more bubbles for execution. Each bubble can be independently executed, potentially in parallel with other bubbles, when resources to handle the bubble are available. Intra-bubble communication can be streamed between vertices within a bubble. Inter-bubble communication can be stored to durable storage. Bubbles provide a failure boundary for a job graph and re-executing a bubble along with storage of intermediate results in durable storage can be used to recover from failures. When a vertex inside a bubble fails, computation can resume by rescheduling the execution of the failed bubble from the durable inputs for that bubble. Durable storage provides a light-weight failover to handle non-deterministic behavior. Jobs can also leverage streaming to increase performance.

Optimizing pipelining result sets with fault tolerance in distributed query execution

Growing community of inventors

Sammamish, WA, United States of America

Jin Sun