System and method for executing computational queries
AssigneeShopify Inc.
InventorPhilip John Messenger
Life of this patent
Estimating the term…
Abstract
A computer system and computer-implemented method are provided for executing computational queries. The method includes executing a query comprising at least one predicate, each predicate determining whether each of a plurality of entities is a member of a corresponding set for that predicate. The method also includes storing a bitset indicating set membership for the entities at each node in a graph representative of the query, wherein the bitset stored at a terminal vertex in the graph provides an output indicative of set membership for the query.
Claims20
A computer-implemented method, comprising:
- executing a query comprising a plurality of predicates a first time, each predicate determining whether each of a plurality of entities is a member of a corresponding set for that predicate;
- storing a bitset indicating set membership for the entities at each node in a graph representative of the query, the nodes in the graph corresponding to Boolean operations to be applied to the bitsets associated with that node to combine the predicates in the query, wherein the bitset stored at a terminal vertex in the graph is indicative of a set membership for the query;
- executing the query a second time;
- using the bitset stored at the terminal vertex in the graph to determine the set membership;
- and
- using the set membership to initiate an output associated with corresponding entities of the plurality of entities, to complete the query executed the second time.
A computer system comprising:
- at least one processor;
- and
- at least one memory, the at least one memory comprising processor-executable instructions that, when executed by the at least one processor, cause the computer system to:
- execute a query comprising a plurality of predicates a first time, each predicate determining whether each of a plurality of entities is a member of a corresponding set for that predicate;
- store a bitset indicating set membership for the entities at each node in a graph representative of the query, the nodes in the graph corresponding to Boolean operations to be applied to the bitsets associated with that node to combine the predicates in the query, wherein the bitset stored at a terminal vertex in the graph is indicative of a set membership for the query;
- execute the query a second time;
- use the bitset stored at the terminal vertex in the graph to determine the set membership;
- and
- use the set membership to initiate an output associated with corresponding entities of the plurality of entities, to complete the query executed the second time.
A non-transitory computer-readable medium comprising processor executable instructions that, when executed by a processor of a computer system, cause the computer system to:
- execute a query comprising a plurality of predicates a first time, each predicate determining whether each of a plurality of entities is a member of a corresponding set for that predicate;
- store a bitset indicating set membership for the entities at each node in a graph representative of the query, the nodes in the graph corresponding to Boolean operations to be applied to the bitsets associated with that node to combine the predicates in the query, wherein the bitset stored at a terminal vertex in the graph is indicative of a set membership for the query;
- execute the query a second time;
- use the bitset stored at the terminal vertex in the graph to determine the set membership;
- and
- use the set membership to initiate an output associated with corresponding entities of the plurality of entities, to complete the query executed the second time.
Dependencies are inferred from the claim text.