Back to results
US 10,380,269 B2Granted
Sideways information passing
AssigneeEntit Software LLC
InventorsChuck Bear, Lakshmikant Shrinivas, Andrew Lamb
Life of this patent
Estimating the term…
Abstract
Methods, systems and program products for query optimization using sideways information passing. In one implementation, a join clause in a query is identified that specifies an outer table of tuples to be joined with an inner table, the outer table having one or more attributes, and each of the attributes of the outer table having values stored in an attribute file that is distinct from attribute files in which the values of other attributes are stored. A plan for the query is created which, when executed, causes selection of a subset of tuples of the outer table to serve as input to the join clause in place of the outer table based on one or more predicates applied to the inner table.
Claims18
A method comprising:
- identifying, by a processor, a join clause in a query, the join clause specifying an outer table of tuples to be joined with an inner table, the join clause including an equality predicate equating a first attribute of the outer table to a second attribute of the inner table;
- in response to identifying the join clause in the query, the processor creating a hash table for second attribute values of inner table tuples using the first attribute of the outer table from the equality predicate that satisfies one or more predicates applied to the inner table;
- filtering, by the processor, each tuple of the outer table using the hash table to create a filtered subset of tuples of the outer table, wherein the filtering includes:
- storing values for the first attribute of the outer table in a dedicated attribute file as a sequence of blocks and according to a sort order, the dedicated attribute file having an index;
- utilizing the index and the sort order to read values from a plurality of non-contiguous portions of the dedicated attribute file that are necessary for the filtering, without reading other portions of the attribute file that are not necessary;
- and
- utilizing the values from the plurality of non-contiguous portions of the dedicated attribute file to create the filtered subset of tuples of the outer table;
- and
- performing, by the processor, a join operation to join the filtered subset of the outer table to the inner table, the join operation corresponding to the join clause in the query.
6 more elements
A computing device comprising:
- a processor;
- a non-transitory storage medium storing instructions executable by the processor to:
- identify a join clause in a query, the join clause specifying an outer table of tuples to be joined with an inner table, the join clause including an equality predicate equating a first attribute of the outer table to a second attribute of the inner table;
- in response to identifying the join clause in the query, create a hash table for second attribute values of inner table tuples using the first attribute of the outer table from the equality predicate that satisfies one or more predicates applied to the inner table;
- filter each tuple of the outer table using the hash table to create a filtered subset of tuples of the outer table, wherein to filter each tuple, the instructions are further executable to:
- store values for the first attribute of the outer table in a dedicated attribute file as a sequence of blocks and according to a sort order, the dedicated attribute file having an index;
- utilize the index and the sort order to read values from a plurality of non-contiguous portions of the dedicated attribute file that are necessary for the filtering, without reading other portions of the attribute file that are not necessary;
- and
- utilize the values from the plurality of non-contiguous portions of the dedicated attribute file to create the filtered subset of tuples of the outer table;
- and
- perform a join operation to join the filtered subset of the outer table to the inner table, the join operation corresponding to the join clause in the query.
8 more elements
An article comprising a non-transitory storage medium storing instructions that upon execution cause a processor to:
- identify a join clause in a query, the join clause specifying an outer table of tuples to be joined with an inner table, the join clause including an equality predicate equating a first attribute of the outer table to a second attribute of the inner table;
- in response to identifying the join clause in the query, create a hash table for second attribute values of inner table tuples using the first attribute of the outer table from the equality predicate that satisfies one or more predicates applied to the inner table;
- filter each tuple of the outer table using the hash table to create a filtered subset of tuples of the outer table, wherein to filter each tuple, the instructions are further executable to:
- store values for the first attribute of the outer table in a dedicated attribute file as a sequence of blocks and according to a sort order, the dedicated attribute file having an index;
- utilize the index and the sort order to read values from a plurality of non-contiguous portions of the dedicated attribute file that are necessary for the filtering, without reading other portions of the attribute file that are not necessary;
- and
- utilize the values from the plurality of non-contiguous portions of the dedicated attribute file to create the filtered subset of tuples of the outer table;
- and
- perform a join operation to join the filtered subset of the outer table to the inner table, the join operation corresponding to the join clause in the query.
6 more elements
Dependencies are inferred from the claim text.