| Patent application number | Description | Published |
|---|
| 20080256073 | Transactional memory using buffered writes and enforced serialization order - Various technologies and techniques are disclosed that support buffered writes and enforced serialization order in a software transactional memory system. A buffered write process is provided that performs writes to shadow copies of objects and writes content back to the objects after validating a respective transaction during commit. When a write lock is first obtained for a particular transaction, a shadow copy is made of a particular object. Writes are performed to and reads from the shadow copy. After validating the particular transaction during commit, content is written from the shadow copy to the particular object. A transaction ordering process is provided that ensures that an order in which the transactions are committed matches an abstract serialization order of the transactions. Transactions are not allowed to commit until their ticket number matches a global number that tracks the next transaction that should commit. | 10-16-2008 |
| 20090006404 | Handling falsely doomed parents of nested transactions - Various technologies and techniques are disclosed for detecting falsely doomed parent transactions of nested children in transactional memory systems. When rolling back nested transactions, a release count is tracked each time that a write lock is released due to rollback for a given nested transaction. For example, a write abort compensation map can be used to track the release count for each nested transaction. The number of times the nested transactions releases a write lock is recorded in their respective write abort compensation map. The release counts can be used during a validation of a parent transaction to determine if a failed optimistic read is really valid. If an aggregated release count for the nested children transactions accounts for the difference in version numbers exactly, then the optimistic read is valid. | 01-01-2009 |
| 20090006407 | Parallel nested transactions in transactional memory - Various technologies and techniques are disclosed for supporting parallel nested transactions in a transactional memory system. For example, pessimistic reads are supported. A pessimistic duplication detection data structure is created for a parallel nested transaction. An entry is made into the data structure for each pessimistic read in the parallel nested transaction. When committing the parallel nested transaction, new pessimistic read locks are passed to an immediate parent, and an entry is made into a separate pessimistic duplication detection data structure of the immediate parent with synchronization between sibling transactions. The pessimistic duplication detection data structures can also be used for upgrades from pessimistic reads to write locks. Retry operations are supported with parallel nested transactions. Write abort compensation maps can be used with parallel nested transactions to detect and handle falsely doomed parent transactions. | 01-01-2009 |
| 20090007070 | Efficient retry for transactional memory - Various technologies and techniques are disclosed for implementing retrying transactions in a transactional memory system. The system allows a transaction to execute a retry operation. The system registers for waits on every read in a read set of the retrying transaction. The retrying transaction waits for notification that something in the read set has changed. A transaction knows if notification is required in one of two ways. If the transactional memory word contained a waiters bit during write lock acquisition, then during release the transactional memory word is looked up in an object waiters map, and waiting transactions are signaled. If a writing transaction finds a global count of waiting transactions to be greater than zero after releasing write locks, a transaction waiters map is used to determine which waiting transactions need to be signaled. In each case, the write lock is released using a normal store operation. | 01-01-2009 |
| 20090077082 | Parallel nested transactions in transactional memory - Various technologies and techniques are disclosed for supporting parallel nested transactions in a transactional memory system. Releasing a duplicate write lock for rollback is supported. During rollback processing of a parallel nested transaction, a write log entry is encountered that represents a write lock. If the write lock is a duplicate, a global lock is used to synchronize access to a global versioned write lock map. Optimistic read validation is supported. During validation, if a versioned write lock indicates a sibling conflict, consult information to determine if a parallel nested transaction should be doomed. Write lock acquisition is supported. Upon attempting to acquire a write lock for a parallel nested transaction, a transactional memory word is analyzed to determine if the write lock can be obtained. If the transactional memory word indicates a versioned write lock, retrieve a write log entry pointer from a global versioned write lock map. | 03-19-2009 |
| 20090077083 | Parallel nested transactions in transactional memory - Various technologies and techniques are disclosed for supporting parallel nested transactions in a transactional memory system. Multiple closed nested transactions are created for a single parent transaction, and the closed nested transactions are executed concurrently as parallel nested transactions. Various techniques are used to ensure effects of the parallel nested transactions are hidden from other transactions outside the parent transaction until the parent transaction commits. For example, versioned write locks are used with parallel nested transactions. When a transactional memory word changes from a write lock to a versioned write lock, an entry is made in a global versioned write lock map to store a pointer to a write log entry that the versioned write lock replaced. When the versioned write lock is encountered during transaction processing, the global versioned write lock map is consulted to translate the versioned write lock to the pointer to the write log entry. | 03-19-2009 |
| 20100082599 | Characterizing Queries To Predict Execution In A Database - One embodiment is a method that obtains query plans for queries in the workload. The query plans include a tree of operators and estimated cardinalities for nodes in the tree. The method then groups the operators for the queries and characterizes the workload in terms of grouped operators to predict performance of the queries before the queries execute in a database. | 04-01-2010 |
| 20100106711 | COMBINED JOIN - Computer-implemented systems and associated operating methods perform a combined join. A computer-implemented system comprises a processor that performs query processing in a relational database by receiving inputs of a variety of cases and sizes, and performing a combined database join of two of the received inputs using an index in memory formed from records of the first input and probed with records from the second input by optimizing the index for increased-speed searching using fast parent-to-child navigation. The variety of cases comprise combinations of unsorted, sorted, and indexed inputs, and the variety of sizes comprise input sizes from smaller than the available memory to input sizes substantially larger than available memory. | 04-29-2010 |
| 20100191717 | OPTIMIZATION OF QUERY PROCESSING WITH TOP OPERATIONS - A query processing system performs multiple optimizations of a merge sort for “top” operations. An illustrative query processing system comprises a receiver that receives database query inputs with a top request, and a sort logic that sorts the inputs using temporary files to store intermediate sort data and applies top qualifications to sorted output. An optimizing logic that modifies operation of the sort logic and reduces the number of records in the inputs copied into temporary files. | 07-29-2010 |
| 20100198806 | EVALUATION OF SET OF REPRESENTATIVE QUERY PERFORMANCE USING ROBUSTNESS MAPPING - Computer-implemented systems and associated operating methods use atomic query maps to identify and evaluate database query plan robustness landmarks. The computer-implemented system comprises logic that evaluates robustness of a selected atomic query by measuring performance of atomic query execution in a predetermined range of runtime conditions that include data characteristics. The logic produces a set of measurements that can be displayed as one or more performance maps and analyzes the measured performance to identify landmarks indicative of database atomic query performance degradation greater than a predetermined amount. | 08-05-2010 |
| 20100198807 | WORKLOAD MANAGEMENT USING ROBUSTNESS MAPPING - Computer-implemented systems and associated operating methods use performance maps created by evaluating robustness of a database operator, query plan, or query to analyze health of a currently-executing query. The computer-implemented system comprises logic that receives one or more robustness maps of measured database system performance acquired during database execution in a predetermined range of runtime conditions. The logic analyzes state of a currently-executing query by locating the query's performance on the robustness maps. | 08-05-2010 |
| 20100198808 | DATABASE SYSTEM IMPLEMENTATION PRIORITIZATION USING ROBUSTNESS MAPS - Computer-implemented systems and associated operating methods take measurements and landmarks associated with robustness maps and perform tests evaluating the robustness of a database engine's operator implementations and/or query components. The illustrative computer-implemented system comprises logic that receives one or more robustness maps of measured database system performance acquired during database execution in a predetermined range of runtime conditions and uses information from the robustness map or maps to prioritize potential changes that improve robustness of a database system implementation wherein landmarks in the robustness map or maps are operated upon as a robustness bug describing conditions under which a predetermined implementation of a database operator or query component degrades in a manner different from a predetermined expected manner. | 08-05-2010 |
| 20100198809 | DATABASE SYSTEM TESTING USING ROBUSTNESS MAPS - Computer-implemented systems and associated operating methods take measurements and landmarks associated with robustness maps and perform tests evaluating the robustness of a database engine's operator implementations and/or query components. The illustrative computer-implemented system comprises logic that receives one or more robustness maps of measured database system performance acquired during database execution in a predetermined range of runtime conditions and uses information from the robustness map or maps to perform regression testing wherein landmarks in the robustness maps are operated upon as a robustness bugs describing conditions under which a predetermined implementation of a database operator or query component degrades in a manner different from a predetermined expected manner. | 08-05-2010 |
| 20100198810 | EVALUATION OF DATABASE QUERY PLAN ROBUSTNESS LANDMARKS USING OPERATOR MAPS OR QUERY MAPS - Computer-implemented systems and associated operating methods create and use an operator map to identify and evaluate database query plan robustness landmarks. The computer-implemented system comprises logic that creates a map evaluating performance of an implementation of a database engine operator during execution under actual operating conditions. The logic measures and maps performance for a selected range of runtime conditions including resource availability and data characteristics. | 08-05-2010 |
| 20100198811 | QUERY PLAN ANALYSIS OF ALTERNATIVE PLANS USING ROBUSTNESS MAPPING - Computer-implemented and associated operating methods evaluate robustness of a query plan by measuring performance with regard to a range of runtime conditions and producing a map of relative performance of the given query plan when compared with alternative plans for a range of conditions. The computer-implemented system comprises logic that evaluates the selected query plan in comparison to multiple alternative query plans in a predetermined range of runtime conditions that include data characteristics. The logic produces a set of performance measurements and analyzes the measured performance to map performance of the selected query plan in comparison to performance of one or more alternative query plans. | 08-05-2010 |
| 20100205351 | DATABASE JOIN OPTIMIZED FOR FLASH STORAGE - Computer-implemented systems and associated operating methods implement a fast join for databases which is adapted for usage with flash storage. A system comprises a processor that performs a join of two tables stored in a storage in pages processed in a column orientation wherein column values for all rows on a page are co-located in mini-pages within the page. The processor reduces input/output operations of the join by accessing only join columns and mini-pages containing join results. | 08-12-2010 |
| 20100281013 | ADAPTIVE MERGING IN DATABASE INDEXES - A method for implementing adaptive merging in database indexes includes selecting a key range from a database query having a range predicate and searching a database for data matching the key range. The data matching the key range is merged to form a collected dataset which is stored for future retrieval. A method for optimizing B-tree representation of a database using actual queries is also provided. | 11-04-2010 |
| 20100306212 | Fetching Optimization in Multi-way Pipelined Database Joins - A method of performing a multi-way join of a plurality of database relations includes executing a plurality of pipelined two-way joins with the database relations. Each two-way join has two sequential phases. In the first phase, missing attributes of the input relations that are required to evaluate a joining criterion specific to said two-way join are fetched from a non-volatile memory device, and the input relations are joined according to the criterion. In the second phase, any additional missing attributes of the input relations are fetched from the non-volatile memory device as assigned by an optimization process executed prior to commencing the multi-way join. | 12-02-2010 |
| 20100332457 | Database segment searching - A segment encompasses a number of segment records less than the total number of records of a database. The segment records have values for a field of the database. Lowest and highest values of the segment records for the field, and a bitmap for the segment, can be determined and stored. Selected bits of the bitmap each correspond to a value for the field. Each selected bit is set to one where at least one segment record has the value to which the bit corresponds. An index relating to just the segment records can be determined and stored. The lowest and highest values, and the bitmap, are adapted to permit determination of whether the segment has to be loaded into memory to locate records that satisfy a query. The index is adapted to permit searching of the segment records after the segment has been loaded into the memory. | 12-30-2010 |
| 20100332472 | QUERY PROGRESS ESTIMATION BASED ON PROCESSED VALUE PACKETS - A data processing system performs query progress estimation based on processed value packets. In the illustrative data processing system, a database query processor comprises a query optimizer that creates a query plan, and a database plan executor that executes the query plan and observes intermediate result streams processed as the query plan is executed. A value packet manager anticipates value packets during query optimization, creates value packets as the intermediate result streams are processed, and compares anticipated value packets with created value packets to determine accuracy of the anticipated value packets and estimate query progress. | 12-30-2010 |
| 20100332494 | HISTOGRAM PROCESSING BY TREND AND PATTERN REMOVAL - A data processing system compress a histogram with less information loss than simply reducing the number of steps (or intervals) in the histogram. The data processing system uses a very detailed histogram as a starting point and comprises histogram compression logic that compresses a detailed histogram by detecting trends and periodic patterns in the detailed histogram. The histogram compression logic extracts the detected trends and periodic patterns from the detailed histogram, and forms a compressed histogram as a distribution of data remaining after extraction of the trends and periodic patterns. | 12-30-2010 |
| 20110022586 | Determining whether change in workload of database system has occurred, and/or whether executing current workload will likely result in problem developing with database system - Whether a change in workload of a database system has occurred can be determined. Investigative queries are formulated. Each investigative query is adapted to test a different resource or a different combination of resources of the database system. The investigative queries are run when the database system is in an unloaded state to acquire unloaded performance metrics. The investigative queries are run when the database system is in a loaded state to acquire loaded performance metrics. Whether executing a current workload of the database system, using a current configuration of the database system, will likely result in a problem developing at a later point in time can also be determined. Simultaneously with actual execution of the current workload on the database system using the current configuration, a simulation of execution of the current workload using the current configuration is performed. The simulation is performed more quickly than the actual execution. | 01-27-2011 |
| 20110040738 | PARALLEL NESTED TRANSACTIONS IN TRANSACTIONAL MEMORY - Various technologies and techniques are disclosed for supporting parallel nested transactions in a transactional memory system. Releasing a duplicate write lock for rollback is supported. During rollback processing of a parallel nested transaction, a write log entry is encountered that represents a write lock. If the write lock is a duplicate, a global lock is used to synchronize access to a global versioned write lock map. Optimistic read validation is supported. During validation, if a versioned write lock indicates a sibling conflict, consult information to determine if a parallel nested transaction should be doomed. Write lock acquisition is supported. Upon attempting to acquire a write lock for a parallel nested transaction, a transactional memory word is analyzed to determine if the write lock can be obtained. If the transactional memory word indicates a versioned write lock, retrieve a write log entry pointer from a global versioned write lock map. | 02-17-2011 |
| 20110055232 | Data restructuring in multi-level memory hierarchies - A method, executed on a suitably programmed processor, provides for ordering records using a memory hierarchy. The memory hierarchy includes and two or more lower levels of the memory hierarchy. The method includes the steps of (a) receiving unsorted input records; (b) reading the input records in pages and writing one or more pages of the input records to the primary memory; (c) sorting the pages of input records to create a run; (d) if a size of the run exceeds primary memory capacity, moving data that just exceeds the primary memory capacity to a secondary level of the memory hierarchy; (e) repeating steps (a)-(d) until either (i) all unsorted input records have been read into primary memory and sorted, or (ii) a capacity of the secondary level of the memory hierarchy is exceeded; (f) following step (e)(ii), moving data that just exceeds the secondary memory capacity from the secondary level to a tertiary level of the memory hierarchy until the capacity of the secondary level no longer is exceeded; and (g) following either of steps (c), (e)(i), or (f), merging runs to create a merge output. | 03-03-2011 |
| 20110099160 | SYSTEM AND METHOD FOR EXECUTING QUERIES - There is provided a computer-implemented method of executing a query plan against a database. An exemplary method comprises accessing a first subset of rows of a database table using a direct access method. The query plan may comprise the direct access method. The exemplary method also comprises determining a processing cost of accessing the first subset of rows. The exemplary method further comprises modifying the direct access method in response to determining that the processing cost exceeds a specified threshold. Additionally, the exemplary method comprises accessing a second subset of rows of the database table using the modified direct access method. | 04-28-2011 |
| 20110138145 | PARALLEL NESTED TRANSACTIONS IN TRANSACTIONAL MEMORY - Various technologies and techniques are disclosed for supporting parallel nested transactions in a transactional memory system. Multiple closed nested transactions are created for a single parent transaction, and the closed nested transactions are executed concurrently as parallel nested transactions. Various techniques are used to ensure effects of the parallel nested transactions are hidden from other transactions outside the parent transaction until the parent transaction commits. For example, versioned write locks are used with parallel nested transactions. When a transactional memory word changes from a write lock to a versioned write lock, an entry is made in a global versioned write lock map to store a pointer to a write log entry that the versioned write lock replaced. When the versioned write lock is encountered during transaction processing, the global versioned write lock map is consulted to translate the versioned write lock to the pointer to the write log entry. | 06-09-2011 |
