Oracle International Corporation

Angela Amor

Andrew Witkowski

Cetin Ozbutun

Rafi Ahmed

Sankar Subramanian

Huagang Li

Hassan Chafi

Sungpack Hong

William H Waddington

Mohamed Ziauddin

Laurent Daynes

Vlad Ioan Haprian

Michael Charles Depledge

Hugo Kapp

Ioannis Alagiannis

Srikanth Bondalapati

Vinita Subramanian

Chun-Chieh Lin

A breadth first search (BFS) algorithm is provided that uses out-of-core external storage in a memory constrained system. Memory resources are used as long as they are available and external storage is used when necessary due to memory pressure. The BFS algorithm uses a disk-spilling hash-table (DSH) as the visited set and disk-spilling queues (DSQs) as the BFS frontier queue. To get the most out of the DSH, subsequent inserts and lookups must happen in the same DSH partition. To ensure that consecutive lookups happen in the same DSH partition, the BFS frontier queue is partitioned in a manner similar to the DSH partitions.

Out-of-core BFS for shortest path graph queries

A new type of table join operation, outer semi join (OSJ), is provided, which can be used by an optimizer layer and an execution layer of a database management system (DBMS). OSJ combines the semantics of both left outer-join and semi-join. The concept of an anti-join marker (AJM) is also introduced, which specifies whether a matching row was not found between joined tables for each result row in an OSJ operation. The OSJ operation supports unnesting of a class of disjunctive ANY, ALL, EXISTS, NOT EXISTS, IN, and NOT IN subqueries for execution plan optimization. The disjunction may contain filter predicates. For unnesting, OSJ avoids the need of using a distinct operator on the right table and also supports using inequality (e.g. >, >=, <, <=) in connecting or correlating conditions of subqueries, rather than being limited to equality only.

Outer semi join for disjunctive subquery unnesting

Techniques are described herein for processing queries comprising joins specifying a plurality of tables. The techniques involve partitioning the tables by assigning rows to partitions. One or more partition maps may be generated to indicate the partitions. Subsequent tables may be partitioned based on the generated partition maps. The partitions may be used to determine results for the joins.

N-way hash join

Techniques are described for leveraging column dictionaries of tables for join, group-by and expression evaluation operations. In an embodiment, a table is stored in one or more data units, each data unit's metadata containing dictionaries for stored columns. Rather than storing unencoded column values, the data units may store columns as column vectors of dictionary-encoded values, in an embodiment. When performing a join operation, a matching of values may be performed on the build-side table using the unencoded, unencoded, values stored in the join-key dictionary(s) of the probe-side table, thus, significantly reducing the number of searching and matching operations. In an embodiment, a group-by operation may be executed by performing partial aggregations based on unique group-by key values as stored in the one or more group-by key dictionaries. For an expression evaluation, only a single evaluation may be performed for each unique combination of expression-key values in a data unit by leveraging the one or more expression-key dictionaries.

Leveraging columnar encoding for query operations

Techniques for performing a 'null-aware' anti-join operation are described. Unnesting using anti-join of NOT IN/ALL subquery uses null-aware anti-join operation, resulting in a rewritten query that, when computed, produces results consistent with the NULL semantics of NOT IN/ALL subquery. The semantics of the 'null-aware' anti-join operation allow the query having the NOT IN/ALL subquery to be rewritten even though a no-NULL restriction requirement, for the operands of the anti-join condition in the query, may not be met.

Null aware anti-join

A technique and mechanism for transforming a query is described. A given query is transformed into a transformed query that references a global temporary table. Specifically, the given query contains a join between a given table and one or more other tables referenced by constraints (e.g. predicates). References to one or more of the constrained tables are replaced by a reference to a global temporary table. Before executing the transformed query, data that satisfies the constraints placed on the constrained table is inserted into the global temporary table.

Using global temporary tables to transform queries

A method and mechanism is provided for executing a query that includes a subquery, where the subquery includes an ORDER BY clause. The results generated by executing the subquery are ordered as specified by the ORDER BY clause. When the results of the subquery are referenced by the outer query, the results generated for the subquery satisfy the restriction. For example, the restriction may specify that the row number pseudo-column be less than a threshold. In response, a TOP N operation is performed to return the rows that are TOP N in order. The order is based on the ORDER BY clause.

Growing community of inventors

Menlo Park, CA, United States of America

Angela Amor