Oracle International Corporation

International Business Machines Corporation

Cagri Balkesen

Nipun Agarwal

Sam Idicula

Nitin Kunal

Markus Buehler

Thomas Schwarz

Rainer Dorsch

Guenther Hutzl

Stefanie Scherzinger

Negar Koochakzadeh

Michael W Kaufmann

Daniel Pfefferkorn

David Rohr

Pit Fender

Benjamin Schlegel

Matthias Brantner

The manner in which tables are joined can affect the outcome of the query and database performance. Example types of join operations include semi-join and inner-join. The techniques described herein are approaches that may be used to substitute a semi-join operator with an inner-join operator and may be used to transform and optimize representations of queries.

Methods for substituting a semi-join operator with alternative execution strategies and selection methods to choose the most efficient solution under different plans

Techniques for non-power-of-two partitioning of a data set as well as generation and selection of partition schemes for the data set. In an embodiment, one or more iterations of a partition scheme is for a non-power-of-two number of partitions. Extended hash partitioning may be used to partition a data set into a non-power-of-two number of partitions by determining the partition identifier of each tuple of the data set using the extended hash partitioning algorithm. In an embodiment, multiple partition schemes are generated for multiple data sets, based on properties of the data sets and/or availability of computing resources for the partition operation or the subsequent operation to the partition operation. The generated partition schemes may use non-power-of-two partitioning for one or more iterations of a generated partition scheme. The most optimal partition scheme may be selected from the generated partition schemes based on optimization policies.

Efficient partitioning of relational data

A processor receives a payload array and generates a hash table in a cache that includes a hash bucket array. Each hash bucket element contains an identifier that defines a location of a build key array element in the payload array. For a particular build key array element, the processor determines a hash bucket element that corresponds to the payload array. The processor copies the identifier for particular build key array element into the hash bucket element. If the cache is unable to insert additional build key array elements into the hash table in the cache, then the processor generates a second hash table for the remaining build key array elements in local volatile memory. When probing, the processor probes both hash tables in the cache and local volatile memory for identifiers in hash bucket elements that are used to locate matching build key array elements.

Limited memory and statistics resilient hash join execution

Techniques are described for generation of an efficient hash table for probing during join operations. A node stores a partition and generates a hash table that includes a hash bucket array and a link array, where the link array is index aligned to the partition. Each hash bucket element contains an offset that defines a location of a build key array element in the partition and a link array element in the link array. For a particular build key array element, the node determines a hash bucket element that corresponds to the build key array. If the hash bucket element contains an existing offset, the existing offset is copied to the link array element that corresponds to the offset of the particular build key array element and the offset for the particular build key array element is copied into the hash bucket element. When probing, the offset in a hash bucket element is used to locate a build key array element and other offsets stored in the link array for additional build key array elements.

Partitioning-based vectorized hash join with compact storage footprint

Embodiments comprise a distributed join processing technique that reduces the data exchanged over the network. Embodiments first evaluate the join using a partitioned parallel join based on join tuples that represent the rows that are to be joined to produce join result tuples that represent matches between rows for the join result. Embodiments fetch, over the network, projected columns from the appropriate partitions of the tables among the nodes of the system using the record identifiers from the join result tuples. To further conserve network bandwidth, embodiments perform an additional record-identifier shuffling phase based on the respective sizes of the projected columns from the relations involved in the join operation. Specifically, the result tuples are shuffled such that transmitting projected columns from the join relation with the larger payload is avoided and the system need only exchange, over the network, projected columns from the join relation with the smaller payload.

Boomerang join: a network efficient, late-materialized, distributed join technique

The present invention relates to a method and respective system for operating a DRAM main memory. One buffer line is provided for multiple pages. When writing data to the buffer it is decided which to which buffer-line the data is written to based on its destination main memory address. A tuple consisting of lower memory address and data is stored. Data entered into the buffer-line will be sorted by page in case the line is flushed to the main memory. Sorting the buffer entries results in less page openings and closings, since the data is re-arranged by memory address and therefore in logical order. By using one line for multiple pages only a fraction of memory of a common set-associative cache is needed, thus decreasing the amount of overhead significantly.

Write buffer for improved DRAM write access patterns

First and second sets of numbers are received in an input range, which is separated into sub ranges. A first sub range is processed by initializing bits of a memory to a first logical state and by changing the initial state of each of the bits corresponding to a received number of the first set that is within the first sub range. Each number received in the second set is compared to a bit in the memory to identify a set of received numbers that are in the first sub range and that are in both the first set and the second set. The comparing is responsive to detecting a change of initial state of any bit in the memory during the processing of the first sub range. The processing and comparing is repeated for remaining sub ranges to identify received numbers that are in both the sets.

Growing community of inventors

Zurich, Switzerland

Cagri Balkesen