Vectorized queues for shortest-path graph searches

Patent metadata

Field	Value
Publication number	US-11630864-B2
Application number	US-202016803832-A
Country	US
Kind code	B2
Filing date	Feb 27, 2020
Priority date	Feb 27, 2020
Publication date	Apr 18, 2023
Grant date	Apr 18, 2023

Abstract

Techniques are described for a vectorized queue, which implements a vectorized ‘contains’ function that determines whether a value is in the queue. A three-phase vectorized shortest-path graph search splits each expanding and probing iteration into three phases that utilize vectorized instructions: (1) The neighbors of nodes that are in a next queue are fetched and written into a current queue. (2) It is determined whether the destination node is among the fetched neighbor nodes in the current queue. (3) The fetched neighbor nodes that have not yet been visited are put into the next queue. According to an embodiment, a vectorized copy operation performs vector-based data copying using vectorized load and store instructions. Specifically, vectors of data are copied from a source to a destination. Any invalid data copied to the destination is overwritten, either with a vector of additional valid data or with a vector of nonce data.

First claim

What is claimed is:

1. A computer-executed method for identifying a path, in a graph database, between a pair of nodes that comprises a source node and a destination node, the method comprising:
performing a first phase by identifying, in the graph database, one or more neighbor nodes of nodes in a next queue;
performing a second phase by determining whether the destination node is included in the one or more neighbor nodes;
in response to determining that the destination node is not included in the one or more neighbor nodes, performing a third phase by, for each node of the one or more neighbor nodes:
using at least a vectorized insert operation, attempting to insert said each node into a visited hash table,
wherein the vectorized insert operation successfully inserts a node into the visited hash table when the node is not already present in the visited hash table,
wherein successfully attempting to insert said each node into the visited hash table comprises:
identifying a hash bucket, of the visited hash table, based on an identifier of said each node,
loading a vector of values from the identified hash bucket into a register,
wherein the values in the identified hash bucket are stored contiguously at a first extreme of the vector of values,
using a single SIMD instruction, inserting the identifier into the vector by:
based, at least in part, on a permutation mask, shifting the values in the vector toward a second extreme of the vector, and
based, at least in part, on a value vector populated with the identifier, inserting the identifier at the first extreme of the vector;

responsive to determining that the attempt to insert said each node into the visited hash table was successful, determining that said each node has not previously been visited;
in response to determining that said each node has not previously been visited, including said each node in the next queue; and

wherein the method is performed by one or more computing devices.

2. The computer-executed method of claim 1 , wherein determining whether the destination node is included in the one or more neighbor nodes comprises:
populating a destination-node vector with an identifier of the destination node;
wherein information identifying the one or more neighbor nodes is stored in a current queue;
for each vector of data in the current queue:
using a vectorized instruction to compare said each vector of data to the destination-node vector to produce a result vector, and
determining whether the destination node is included in said each vector of data based, at least in part, on the result vector.

3. The computer-executed method of claim 1 , further comprising:
identifying, in an adjacency list, a first portion of data that stores a list of neighbor nodes of a first node in the next queue;
by a first copy operation, copying, by vectors to a current queue, the first portion of data.

4. The computer-executed method of claim 3 , wherein:
performance of the first copy operation results in neighbor node data stored in the current queue; and
performing the second phase is based, at least in part, on the neighbor node data stored in the current queue.

5. The computer-executed method of claim 3 , further comprising:
identifying a second portion of data, in the adjacency list, that stores a second list of neighbor nodes of a second node in the next queue;
by a second copy operation, copying, by vectors to a location in the current queue that marks an end of neighbor node information, the second portion of data;
wherein copying the second portion of data comprises overwriting data copied in the first copy operation.

6. The computer-executed method of claim 1 , wherein the one or more neighbor nodes comprise neighbor nodes of a first set of nodes, comprising less than all nodes from the next queue.

7. The computer-executed method of claim 6 , further comprising:
performing a second iteration of the first phase by identifying, in the graph database, second one or more neighbor nodes of a second set of nodes, from the next queue, that are other than the first set of nodes;
performing a second iteration of the second phase by determining whether the destination node is included in the second one or more neighbor nodes of the second set of nodes; and
performing a second iteration of the third phase by, for each node of the second one or more neighbor nodes of the second set of nodes:
using at least the vectorized insert operation, attempting to insert said each node into the visited hash table,
responsive to determining that the attempt to insert said each node into the visited hash table was successful, determining that said each node has not previously been visited, and
in response to determining that said each node has not previously been visited, including said each node in the next queue.

8. The computer-executed method of claim 1 , wherein attempting to insert a particular node into the visited hash table comprises:
determining that a bucket, of a set of buckets of the visited hash table, associated with an identifier of the particular node is full;
responsive to determining that the bucket is full, increasing a cardinality of buckets of the visited hash table to produce an expanded hash table; and
inserting the particular node into the expanded hash table.

9. The computer-executed method of claim 8 , wherein increasing the cardinality of buckets of the visited hash table comprises, for each bucket of the set of buckets, populating a first bucket and second bucket of the expanded hash table by:
executing a first vectorized instruction instance to produce a split mask, for said each bucket, based on a hash function for the expanded hash table;
executing at least one additional vectorized instruction instance, based at least in part on the split mask, to identify a first portion of a plurality of values in said each bucket for the first bucket and a second portion of the plurality of values for the second bucket.

10. The computer-executed method of claim 9 , further comprising:
determining a hash-target bit position based, at least in part, on a size of the expanded hash table;
wherein, for each bucket of the set of buckets:
said executing the first vectorized instruction instance to produce a split mask for said each bucket is based on bits, of the plurality of values in said each bucket, at the hash-target bit position,
each value, of the first portion of the plurality of values for said each bucket, has a set bit at the hash-target bit position, and
each value, of the second portion of the plurality of values for said each bucket, has an unset bit at the hash-target bit position.

11. The computer-executed method of claim 8 , wherein inserting the particular node into the expanded hash table comprises:
based, at least in part, on a size of the expanded hash table, identifying a target bucket, of a second set of buckets of the expanded hash table, that corresponds to the particular node;
determining whether the target bucket has any vacant slots; and
in response to determining that the target bucket has at least one vacant slot, adding the particular node to the target bucket.

12. One or more non-transitory computer-readable media storing one or more sequences of instructions that, when executed by one or more processors, cause identifying a path, in a graph database, between a pair of nodes that comprises a source node and a destination node, comprising:
performing a first phase by identifying, in the graph database, one or more neighbor nodes of nodes in a next queue;
performing a second phase by determining whether the destination node is included i

Assignees

• Oracle Int Corp

Inventors

• Schlegel Benjamin
• Sevenich Martin
• Fender Pit
• Brantner Matthias
• Chafi Hassan

Classifications

• G06F9/3887

  controlled by a single instruction for multiple data lanes [SIMD] · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/9014

  hash tables · CPC title

• G06F9/546

  Message passing systems or structures, e.g. queues · CPC title