Scalable index build techniques for column stores

US8990216B2 · kind B2 · utility

Assignee

• Microsoft Corporation · US

Inventors

• Artem Oks · Bellevue, US
• Qingqing Zhou · Santa Clara, US
• Srikumar Rangarajan · Redmond, US
• Aleksandras Surna · Redmond, US
• Wey-Yi Guy · Beaverton, US
• Cipri Clinciu · Sammamish, US
• Ashit Gosalia · Bellevue, US

Key dates

• Filing date: Mar 19, 2010
• Grant date: Mar 24, 2015
• Expiry date: May 3, 2030

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F16/24549
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

Architecture that includes an index creation algorithm that utilizes available resources and dynamically adjusts to successfully scale with increased resources and be able to do so for any data distribution. The resources can be processing resources, memory, and/or input/output, for example. A finer level of granularity, called a segment, is utilized to process tuples in a partition while creating an index. The segment also aligns with compression techniques for the index. By choosing an appropriate size for a segment and using load balancing the overall time for index creation can be reduced. Each segment can then be processed by a single thread thereby limiting segment skew. Skew is further limited by breaking down the work done by a thread into parallelizable stages.