Microsoft Technology Licensing, LLC

Panagiotis Antonopoulos

Hanumantha Rao Kodavalla

Raghavendra Thallam Kodandaramaih

Adrian-Leonard Radu

Craig Steven Freedman

Naveen Prakash

Raghav Kaushik

Kapil Vaswani

Alejandro Hernandez Saenz

Daniel Georg Schall

Michael James Zwilling

Arvind Arasu

Donald Kossmann

Girish Mittur Venkataramanappa

Kenneth Hiroshi Eguro

Peter Byrne

Wei Ting Chen

Haohai Yu

Jakub J Szymaszek

Ravi Ramamurthy

Ajay S Manchepalli

Ramarathnam R Venkatesan

Conor J Cunningham

Nishanth Chandran

Alexander Thien Tran

Nikhil Vithlani

Aditya Nigam

Neerumalla Bala Rama Koteswara Rao

Krishna Nibhanupudi

Cesar Alejandro Galindo-Legaria

Ravishankar Ramamurthy

Erik Ismert

Raul Garcia

Srinath Setty

Jack Smith Richins

Varun Kunjbihari Tibrewal

Srinath T V Setty

Satyanarayana V Lokam

Joachim Hammer

Michael I Zwilling

Rajat Jain

Bala Neerumalla

Prashanth Purnananda

Nikolas Christopher Ogg

Nitish Gupta

Daniel John Carroll, Jr

Kedar Dubhashi

Nitish Upreti

Kunal Deep Singh

Jeffrey Michael Trimmer

Wei Chen

Basil Cherian

Jason Sydney Barnwell

Donald Alan Kossmann

Methods for asynchronously determining relational data integrity using cryptographic data structures are performed by systems and devices. Changes in current tables of relational databases are reflected in associated history tables. Cryptographic hybrid blockchain ledgers are updated with transaction records, for entry changes in current and history tables, including transaction information and hash values of corresponding entry changes. Hybrid blockchain ledgers also include root hash values of Merkle trees of transaction records in current blocks, and hash values of prior blocks. A current block receipt is asynchronously generated and provided as a single hash value from which the validity states of the tables and ledger are able to be verified. Cryptographic receipts of specific transactions reflected in table entry changes are generated and provide immutable evidence of specific transaction existence for users. Ledger-enabled tables are provided for mixed database operations with ledger-disabled tables, and temporal history table database operations are enabled.

Asynchronously determining relational data integrity using cryptographic data structures

Methods for database recovery for encrypted indexes are performed by systems and devices. A query with a decryption key is received from a client device, where the query modifies an encrypted index of a database using a secure enclave. When events requiring remedial actions for the database occur during the querying, some transactions of the query and later queries are deferred, and a remedial action is initiated that includes restarting the database. A determination of the remedial action being unsuccessful in recovering the encrypted index causes the action to be re-performed until another query having the decryption key is received whereupon the action is performed again to recover the encrypted index utilizing the decryption key. Deferred transactions are then performed with the decryption key. When a database restarts for access without secure enclaves, the encrypted index for the database is invalidated, and the remedial actions are otherwise completed or discarded.

System and method for database recovery for encrypted indexes

Embodiments described herein are directed to a verifiable identity map that maintains identities and public keys associated with the identities. The map is maintained by a ledger database that provides tamper-resistant/evident capabilities for tables (comprising the map) thereof. For instance, when a materialized view of the database is generated, the database provides a digest representative of a state thereof to computing devices that access the map for the keys. When the database receives a request from a device to access the map, the digest is received along therewith. The database is validated based on the digest to determine whether the database has been tampered with since the provision of the digest. Responsive to a successful validation, the database provides access in accordance with the request. When a key in the map is updated, the database subsequently generates a new digest, which is provided to the computing device.

Verifiable identity map maintaining identities and associated public keys

Embodiments described herein enable at least one of a plurality of entities to access data protected by a security policy in response to validating respective digital access requests from the entities. The respective digital access requests are received, each comprising a proof. For each request, an encrypted secret share is obtained from a respective ledger database. Each request is validated based at least on the respective encrypted secret share and the proof, without decrypting the respective encrypted secret share. In response to validating all of the requests, a verification that an access criteria of a security policy is met is made. If so, at least one of the entities is provided with access to data protected by the security policy. In an aspect, embodiments enable a blind subpoena to be performed. In another aspect, embodiments enable the at least one entity to access the data for an isolated purpose.

Blind subpoena protection

Methods for operation fragmentation with metadata serialization in query processing pushdowns are performed by systems and devices. A compute node receives a query directed to database data, and generates query text fragments. Portions of metadata of the database are read from different page servers, and are serialized by the compute node. Page identities of data pages in a page server that stores the data are determined from a page index at the compute node, and the compute node provides the text fragments, the serialized metadata, and the page identities to the page server storing the data. The page server compiles the text fragments based on the serialized metadata to generate an executable query plan for the query. The page server initializes and performs execution of the executable query plan against the data as a pushdown query operation, and a result of pushdown query operation is provided to the compute node.

Operation fragmentation with metadata serialization in query processing pushdowns

Distributed database systems including compute nodes and page servers are described herein that enable compute nodes to pushdown certain query processing compute tasks to the page servers to take advantage of otherwise idle compute resources at the page servers, and to reduce the quantity of data that moves between compute nodes and page servers. A distributed database system includes a page server and a compute node, wherein the page server is configured to maintain multiple versions of stored data objects. The compute node is configured to receive a query and generate a transaction context (TC) and modified table schemas (MTS) scoped to the query, and pushdown the query, TC and MTS to the page server that is configured to determine which data objects at the page server satisfy the query, and for each such object, which version of the object should be returned based on the TC.

Schema and data modification concurrency in query processing pushdown

Embodiments described herein are directed to generating a tree-based data structure representative of a data set and the verification thereof. As each data item of a data set is updated, a leaf node is generated that stores a hash value therefor. For every even leaf node generated, a parent node storing a hash value based on the hash values of its child nodes is generated. For each level of the tree, the hash value of the last odd node generated therefor is maintained. The foregoing process is performed recursively at each level of the tree. During verification, a new root hash value is determined for a new tree-based data structure generated for the data set to be verified. The old and new root hash values are compared. If the hash values do not match, a remediation is performed to restore the data set.

System and method for representing and verifying a data set using a tree-based data structure

Methods for page split detection and affinity in query processing pushdowns are performed by systems and devices. Page servers perform pushdown operations based on specific, and specifically formatted or generated, information, instructions, and data provided thereto from a compute node. Page servers also determine that page splits have occurred during reading of data pages maintained by page servers during pushdown operations, and also during fulfillment of compute node data requests. To detect a data page has split, page servers utilize information from a compute node of an expected next data page which is compared to a next data page in the page server page index. A mismatch in the comparison by page servers indicates data page was split. Compute nodes and page servers store and maintain off-row data generated during data operations via page affinity considerations where the off-row data is stored at the same page server as the data.

Page split detection and affinity in query processing pushdowns

A computing device is provided, including non-volatile memory storing a database including a table having a plurality of rows. The computing device may further include a processor configured to receive a request to perform a first transaction on a row. The processor may assign a first transaction identifier (TID) of the first transaction to the row. The processor may impose a first exclusive TID lock on the first TID of the row and may impose a first exclusive data lock associated with the first transaction on the row. The processor may perform the first transaction on the row. Performing the first transaction may include modifying the table as stored in the memory. In response to completing the first transaction, the processor may release the first exclusive data lock on the row and release the first exclusive TID lock on the first TID of the row.

Transaction identifier locking with data row locks

A relational database system that implements persistent version storage may include an in-row module that is executable by one or more processors to implement an in-row scheme by storing in-row previous version information within a payload of a row within a database page. The relational database system may additionally include an off-row module that is executable by the one or more processors to implement an off-row scheme by storing off-row previous version information in an off-row page that is separate from the database page. The relational database system may additionally include a storage policy that defines when previous version information is stored in accordance with the in-row scheme and when the previous version information is stored in accordance with the off-row scheme. The relational database system may additionally include a cleanup module that cleans up older versions when they are deemed unnecessary by the system.

Persistent version storage for relational database management system

Transforming a database while allowing the data in the database to be available to database users during the transformation of the database. A method includes creating a new version of metadata for an old copy of database items. The method further includes creating a copy of data items to be transformed in the old copy of database items while applying a transformation to the data while migrating data from the old copy of database items to the new copy of database according to the new version of metadata. The method further includes while migrating data from the old copy of database items to the new copy of database items, servicing user queries made against the old copy of database items to allow the database to remain online while transforming data items in the database.

Online schema and data transformations

Database recovery can be performed in substantially constant time. From a database transaction log, the state of one or more transactions is identified including those that were active at a time of a crash but not committed. Transactions can be reapplied sequentially starting from the beginning of a last successful checkpoint to the end of the transaction log. Uncommitted user transactions are not undone synchronously, but simply marked as aborted. Subsequently, versions of affected data elements can be reverted back to a prior saved version asynchronously.

Constant time database recovery

Growing community of inventors

Redmond, WA, United States of America

Panagiotis Antonopoulos