Scalable index build techniques for column stores

US10216777B2 · kind B2 · utility

Assignee

• MICROSOFT TECHNOLOGY LICENSING, LLC · 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: Jan 16, 2017
• Grant date: Feb 26, 2019
• Expiry date: Jan 16, 2037

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.