Microsoft Technology Licensing, LLC

Singlestore, Inc.

Amazon Technologies, Inc.

Eric Boutin

Michal Nowakiewicz

Jingren Zhou

Jaliya Nishantha Ekanayake

Haibo Lin

Xiaoyu Chen

Eric Norman Hanson

Zhicheng Yin

Tao Guan

Nan Zhang

Anna Korsun

Pavel N Iakovenko

Paul Michael Brett

Alexandre Olegovich Verbitski

Srikanth Kandula

Kamal Kant Gupta

James Charles Finger, Ii

Peter Bodik

Bin Shi

Wei Lin

Shriram Sridharan

Damien Katz

Pallavi Maheshwara Kakunje

Andrew D Ferguson

Pavel Yatsuk

There is provided a method of using a bitmap filter to filter a data source as part of a join operation. A set bit at a bit location of the bitmap filter is associated with an entry of the data source that comprises an identifier that matches a filter parameter. A row identifier of a row in another data source that corresponds to the identifier is determined based on a sum of a number of bits set in bit locations that are between the bit location of the set bit associated with the entry of the data source and a bit location in the bitmap filter corresponding to a different, known, row identifier of a different row in the another data source. The row of the another data source corresponding to the determined row identifier is interrogated to obtain information defining the identifier that matches the filter parameter.

Bitmap filter, a method of generating the same, and a method of using a bitmap filter to perform a join

A method for causing a processor to perform a query on a column-store table of encoded values is provided. The method includes configuring the processor to receive the query, comprising a filter to be applied to at least a first column vector of the encoded values. The processor processes the query for the encoded values in the first column vector, to generate a first vector indicative of respective encoded values passing or failing the filter. The processor determines, from the first vector, an indicator of encoded values passing the filter and encoded values failing the filter, relative to the encoded values in the first column vector. The processor determines a bit length of the encoded values. The processor selects an algorithm for processing the query based on the indicator and the determined bit length of the encoded values. A system and a non-transitory, computer-readable medium are also provided.

Accelerated filtering, grouping and aggregation in a database system

There is provided a system of generating a bitmap filter as part of a join operation. A query comprising a filter parameter is received and a first data source associated with the filter parameter is queried to identify an entry therein with an identifier corresponding to the filter parameter. Each entry of the first data source is identified by a corresponding identifier to differentiate the entries from one another. The system generates a bitmap filter corresponding to the filter parameter by identifying a single bit location in the bitmap filter that corresponds to an identifier of the entry corresponding to the filter parameter. Each identifier has a numerical value used to identify the bit location. A single bit location is assigned to the identifier and a bit is set at the assigned bit location such that there is one-to-one mapping between the identifier and the assigned bit location.

This application relates to multi-level replication filtering for a distributed database. A primary node of the database can generate log records that describe write requests performed to the database. The primary node can, in some embodiments, identify a portion of the data of the database that is stored at a second node, such as data stored by a read replica node that can be used in responding to read requests from clients. The primary node can select log records that are applicable to this identified portion of the data to send to the second node. Log records are not selected based on a determination that those unselected log records are not applicable to the identified portion of the data. The primary node can then send the selected log records to the second node, for the second node to apply the log records to its stored database data.

Multi-level replication filtering for a distributed database

There is provided a computer-implemented method of generating a bitmap filter. A filter parameter is received, and a first data source associated with the filter parameter is queried to identify at least one entry in the first data source with an identifier corresponding to the filter parameter. A first process is performed where zero or one single bit location of a plurality of bit locations in a bitmap filter is identified that corresponds to an identifier of an entry of the first data source corresponding to the filter parameter. Each identifier has a numerical value and the bit location is identified based on the numerical value of the corresponding identifier. The single bit location is assigned to the identifier, such that there is one-to-one mapping between each identifier corresponding to the filter parameter and an assigned bit location in the bitmap filter. A bit is set at the assigned bit location. The first process is repeated for another entry in the first data source with an identifier corresponding to the filter parameter.

Processing a job request for multiple versions of a distributed computing service. The service processing node does this by at least interleavingly (e.g., via time sharing with rapid context switching, or by actually concurrently) running a first runtime library associated with a first service version of the distributed computerized service and a second runtime library associated with a different service version of the distributed computerized service. While running the first runtime library, job requests of a first service version may be at least partially processed using a first set of one or more executables that interact with the first runtime library. While running the second runtime library, job requests of a second service version may be at least partially processed using a second set of one or more executables that interact with the second runtime library.

Processing requests for multi-versioned service

Processing received job requests for a multi-versioned distributed computerized service. For each received job request, the job request is channeled to an appropriate service processing node that depends on the version of the distributed computing service that is to handle the job request. A version of the distributed computing service is assigned to the incoming job request. A service processing node that runs a runtime library for the assigned service version is then identified. The identified service processing node also has an appropriate set of one or more executables that allows the service processing node to plan an appropriate role (e.g., compiler, scheduler, worker) in the distributed computing service. The job request is then dispatched to the identified service processing node.

Processing request for multi-versioned service

A job scheduler that schedules ready tasks amongst a cluster of servers. Each job might be managed by one scheduler. In that case, there are multiple job schedulers which conduct scheduling for different jobs concurrently. To identify a suitable server for a given task, the job scheduler uses expected server performance information received from multiple servers. For instance, the server performance information might include expected performance parameters for tasks of particular categories if assigned to the server. The job management component then identifies a particular task category for a given task, determines which of the servers can perform the task by a suitable estimated completion time, and then assigns based on the estimated completion time. The job management component also uses cluster-level information in order to determine which server to assign a task to.

Job scheduling using expected server performance information

A computing cluster operated according to a resource allocation policy based on a predictive model of completion time. The predictive model may be applied in a resource control loop that iteratively updates resources assigned to an executing job. At each iteration, the amount of resources allocated to the job may be updated based on of the predictive model so that the job will be scheduled to complete execution at a target completion time. The target completion time may be derived from a utility function determined for the job. The utility function, in turn, may be derived from a service level agreement with service guarantees and penalties for late completion of a job. Allocating resources in this way may maximize utility for an operator of the computing cluster while minimizing disruption to other jobs that may be concurrently executing.

Computing cluster with latency control

A multi-tier scheduling approach includes a first tier comprising virtual cluster allocators that receive scheduling requests from processes and aggregate those requests and provide them to a second tier, namely a single resource distributor for the entire set of computing devices. The resource distributor, based on the requests from virtual cluster allocators, and also from information received from the computing devices themselves, generates a flow graph to identify an optimal scheduling of the assignment of resources to specific ones of the virtual clusters. Each virtual cluster allocator then, based on the assignment of resources assigned to it by the resource distributor, solves its own flow graph to identify an optimal scheduling of processes on the resources assigned. The scheduling of processes is performed iteratively by initially assigning resources to those processes having a high priority, and then, in subsequent iterations, assigning opportunistic resources to those processes having a lower priority.

Growing community of inventors

Bellevue, WA, United States of America

Eric Boutin