本申请涉及计算机技术，尤其涉及智能搜索技术领域。
背景技术：
在图数据库中，遍历操作是最基本的操作。现有技中，在获取到用户输入的图遍历语句后，会根据图遍历语句中所包含的多个算子之间的嵌套调用、或者按照各算子的执行顺序对前一算子的执行结果依次筛选，最终得到目标元素。
然而，上述两种方式在大规模数据并发的情况下，目标元素查询效率较低，导致系统资源利用率低下。
技术实现要素：
本申请实施例提供了一种图数据库遍历方法、装置、设备及存储介质，以提高对图数据库中目标元素的查询效率和系统资源利用率。
第一方面，本申请实施例提供了一种图数据库遍历方法，包括：
获取输入的图遍历语句，确定所述图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列；
对于每两个相邻算子，通过所述两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入所述两个相邻算子对应的缓冲队列中；以及，通过所述两个相邻算子中后一算子对应的线程，并行从所述缓冲队列中读取所述两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。
本申请实施例通过获取输入的图遍历语句，确定图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列；对于每两个相邻算子，通过两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入两个相邻算子对应的缓冲队列中；以及，通过两个相邻算子中后一算子对应的线程，并行从缓冲队列中读取两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。上述技术方案通过在每两个相邻算子之间创建缓冲队列，使得在两个相邻算子中的前一算子产生执行结果数据并被写入缓冲队列中后，即可开始读取缓冲队列中的数据以执行后一算子，从而实现了算子的并行执行，提高了遍历操作的执行效率和系统资源利用率。
可选的，所述方法还包括：
按照各算子的执行顺序，将令牌数据在各算子对应的线程间传递，以使接收到令牌数据的线程开始执行本线程对应算子的操作，并将所述令牌数据传递至下一算子对应的线程。
上述申请中的一个可选实施方式，通过令牌数据在各算子对应的线程间的传递，关联触发下一算子对应的线程的启动，缩短了相邻算子对应的线程之间的等待时间，进而提高了执行效率。
可选的，为各算子分别分配线程，包括：
根据可用线程的数量，按照各算子的执行顺序，为各算子分别分配线程。
上述申请中的一个可选实施方式，根据可用线程的数据以及各算子的执行顺序为各算子分别分配线程，完善了线程的分配机制，为算子的并行执行提供保障。
可选的，若所述可用线程的数量小于算子的数量，在按照各算子的执行顺序，将令牌数据在各算子对应的线程间传递时，所述方法还包括：
接收到所述令牌数据的线程判断下一算子是否具有对应的线程；
若接收到所述令牌数据的线程判断下一算子不具有对应的线程，则在出现满足预设条件的已分配线程时，将所述已分配线程重新分配给所述下一算子，并将所述令牌数据传递至所述已分配线程，以使所述已分配线程执行所述下一算子的操作；
其中，所述预设条件为所述已分配线程已执行完本线程对应的算子的操作。
上述申请中的一个可选实施方式，在可用线程数量小于算子的数量时，为已执行完本线程对应的算子操作的已分配线程重新分配下一算子，完善了可用线程无法一次覆盖所有算子时的线程分配机制，为算子的并行执行提供了保障。
可选的，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列，包括：
为各算子分别分配本地计算机设备的线程，并为每两个相邻算子在所述本地计算机设备分别创建缓冲队列；或者，
针对各算子，从至少两个计算机设备中确定用于执行所述算子的计算机设备，并为所述算子分配所确定的计算机设备的线程；
针对每两个相邻算子，从至少两个计算机设备中确定用于创建缓冲队列的计算机设备，并在所确定的计算机设备中创建所述两个相邻算子对应的缓冲队列。
上述申请中的各个可选实施方式，通过在本地计算机设备中为各算子进行线程分配，以及为每两个相邻算子创建缓冲队列；或者，通过在至少两个计算机设备中为各算子进行线程分配，以及为每两个相邻算子创建缓冲队列，使得通过单个计算机设备实现对图数据库的遍历操作，活着通过多个计算机设备联合实现对图数据库的遍历操作。
可选的，所述方法还包括：
针对第一个算子，将用于保存所述第一个算子的执行结果数据的缓冲队列的地址信息发送至用于执行所述第一个算子的计算机设备，以使执行所述第一个算子的计算机设备基于接收到的所述地址信息定位对应的缓冲队列；
针对除所述第一个算子以外的任一目标算子，将用于保存所述任一目标算子的前一算子的执行结果数据的第一缓冲队列的地址信息和用于保存所述任一目标算子的执行结果数据的第二缓冲队列的地址信息，发送至用于执行所述任一目标算子的计算机设备，以使执行所述任一目标算子的计算机设备基于接收到的地址信息定位对应的所述第一缓冲队列和所述第二缓冲队列。
上述申请中的一个可选实施方式，通过在执行算子操作的计算机设备中保存所需前一算子的执行结果数据的第一缓冲队列的地址信息，以及用于存储本算子的执行结果数据的第二缓冲队列的地址信息，以便执行算子操作的线程能够实现队列的准确定位，为图数据库的遍历操作提供保障。
可选的，若所述缓冲队列创建于队列集群中，则所述缓冲队列的地址信息包括队列标识；
若所述缓冲队列创建于计算机设备中，则所述缓冲队列的地址信息包括队列所在计算机设备的设备标识、端口信息和队列标识中的至少一个。
上述申请中的一个可选实施方式，通过细化在不同位置所创建的缓冲队列对应的地址信息，体现了缓冲队列创建位置的多样性，同时为图数据库的遍历操作提供支撑。
可选的，所述方法还包括：
在除第一个算子以外的任一目标算子对应的线程确定满足算子执行终止条件时，执行预设操作以通知所述任一目标算子之前的各算子对应的线程终止对应算子的操作。
上述申请中的一个可选实施方式，通过在后一算子在确定满足终止条件时，执行预设操作以通知前面所有算子终止执行，从而通过反馈机制消除了潜在的大量无效计算。
可选的，执行预设操作以通知所述任一目标算子之前的各算子对应的线程终止对应算子的操作，包括：
将所述任一目标算子作为当前算子；将用于保存当前算子的前一算子的执行结果数据的缓冲队列的读端状态关闭，以使前一算子对应的线程在检测到该缓冲队列的读端状态被关闭时，停止向该缓冲队列写入数据并关闭该缓冲队列的写端状态，以终止前一算子的执行；将前一算子作为新的当前算子，并返回执行将用于保存当前算子的前一算子的执行结果数据的缓冲队列的读端状态关闭的操作，直至所述第一个算子的执行被终止；或者，
在预设全局信息表上登记终止信息，以使所述任一目标算子之前的各算子对应的线程读取到所述终止信息时，终止执行对应算子的操作。
上述申请中的一个可选实施方式，通过对缓冲队列读写状态的控制，实现与缓冲队列所关联算子对应的线程的关联控制，从而达到通过缓冲队列的关联触发，依照算子执行顺序的相反顺序，依次终止各算子对应的线程，从而达到避免无效计算的效果。
上述申请中的另一可选实施方式，通过预先设置登记终止信息的全局信息表，使得任一目标算子之前的各算子对应的线程读取到终止信息时，终止执行算子的操作，从而达到避免无效计算的效果。
第二方面，本申请实施例还提供了一种图数据库遍历装置，包括：
遍历语句获取模块，用于获取输入的图遍历语句，确定所述图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列；
算子并行执行模块，用于对于每两个相邻算子，通过所述两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入所述两个相邻算子对应的缓冲队列中；以及，通过所述两个相邻算子中后一算子对应的线程，并行从所述缓冲队列中读取所述两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。
第三方面，本申请实施例还提供了一种电子设备，包括：
至少一个处理器；以及
与所述至少一个处理器通信连接的存储器；其中，
所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行如第一方面实施例所提供的一种图数据库遍历方法。
第四方面，本申请实施例还提供了一种存储有计算机指令的非瞬时计算机可读存储介质，所述计算机指令用于使所述计算机执行如第一方面实施例所提供的一种图数据库遍历方法。
上述可选方式所具有的其他效果将在下文中结合具体实施例加以说明。
附图说明
附图用于更好地理解本方案，不构成对本申请的限定。其中：
图1a是申请实施例一中的一种图数据库遍历方法的流程图；
图1b是申请实施例一中的两个相邻算子执行过程示意图；
图2是本申请实施例二中的一种图数据库遍历方法的流程图；
图3a是本申请实施例三中的一种图数据库遍历方法的流程图；
图3b是本申请实施例三中两个相邻算子进行终止信息传递的示意图；
图4是本申请实施例四中的一种图数据库遍历装置的结构图；
图5是用来实现本申请实施例的图数据库遍历方法的电子设备的框图。
具体实施方式
以下结合附图对本申请的示范性实施例做出说明，其中包括本申请实施例的各种细节以助于理解，应当将它们认为仅仅是示范性的。因此，本领域普通技术人员应当认识到，可以对这里描述的实施例做出各种改变和修改，而不会背离本申请的范围和精神。同样，为了清楚和简明，以下的描述中省略了对公知功能和结构的描述。
实施例一
图1a是申请实施例一中的一种图数据库遍历方法的流程图，本申请实施例适用于在图数据库中进行数据遍历的情况，该方法由图数据库遍历装置执行，该装置采用软件和/或硬件实现，并具体配置于具备一定数据运算能力的电子设备中。
如图1a所示的一种图数据库遍历方法，包括：
s101、获取输入的图遍历语句，确定所述图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列。
其中，对图遍历语句的获取可以通过用户运行已编写的图遍历语句加以实现。其中，图遍历语句中包括至少两个算子，各算子用于在图数据库中执行下述操作中的至少一种：游走、过滤、变换和查找等，进而实现相应功能。
其中，缓冲队列用于存储相邻两个算子中前一算子的执行结果数据，以供相邻两个算子中的后一算子基于前一算子的执行结果数据，执行本算子对应的操作。
在本申请实施例的一种可选实施方式中，可以通过单个计算机设备实现线程分配以及缓冲队列的创建操作。示例性地，为各算子分别分配本地计算机设备的线程，并为每两个相邻算子在所述本地计算机设备分别创建缓冲队列。
在申请实施例的另一可选实施例方式中，还可以通过多个计算机设备联合实现线程分配以及缓冲队列的创建操作，以将图数据库遍历方案拓展至分布式环境。
示例性地，针对各算子，从至少两个计算机设备中确定用于执行所述算子的计算机设备，并为所述算子分配所确定的计算机设备的线程；针对每两个相邻算子，从至少两个计算机设备中确定用于创建缓冲队列的计算机设备，并在所确定的计算机设备中创建所述两个相邻算子对应的缓冲队列。
需要说明的是，存储算子执行结果数据的缓冲队列与执行相应算子的线程可以位于同一或不同的计算机设备中。当然，为了缩短数据传输所耗费的时间，进而提高图数据库的遍历效率，优选是存储算子执行结果数据的缓冲队列与执行相应算子的线程设置于同一计算机设备中。
可以理解的是，在执行图数据库的遍历操作过程中，为了避免各算子的执行结果数据较多导致计算机设备存储量较大而影响计算机设备的运行性能，还可以在队列集群中为每两个相邻算子创建缓冲队列。示例性地，队列集群可以采用开源分布式消息订阅系统卡夫卡(kafka)。
可选的，为各算子分别分配线程，可以是：根据可用线程的数量，按照各算子的执行顺序，为各算子分别分配线程。或者，可选的，为各算子分配线程，还可以是根据预先设定的线程与算子之间的对照关系，为各算子分配相应的线程。
示例性地，线程与算子之间的对照关系可以根据线程的功能进行划分，例如查询线程用于执行与查询操作对应的算子、变换线程用于执行与变换操作对应的算子、以及过滤线程用于执行与过滤操作对应的算子等。示例性地，线程与算子之间的对照关系可以根据可用线程总数量和算子总数量分组划分，例如可用线程为5个(编号对应1-3)，算子总数量为3个(编号对应1-3)，则可以通过算子编号与可用线程总数量相除取余，并根据余数的数值进行分组加以实现。例如，算子编号为1时，对3取余结果为1，对应分配线程1；算子编号为2时，对3取余结果为2，对应分配线程2；算子编号为3时，对3取余结果为3，对应分配线程3。
需要说明的是，当可用线程的数量大于或等于算子的数量时，各算子均可分配不同的线程执行相应的算子操作。然而，当可用线程的数量小于算子的数量时，将会存在不具有对应线程的算子，致使并发线程数量受限，则可以通过已分配线程复用的方式实现线程的再分配。示例性地，可以在所有线程分配完毕之后，监控各已分配线程的执行状态，并在存在已分配线程执行完毕本线程已分配算子的操作后，重新为该线程分配待分配算子，直至所有算子分配完毕。
s102、对于每两个相邻算子，通过所述两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入所述两个相邻算子对应的缓冲队列中；以及，通过所述两个相邻算子中后一算子对应的线程，并行从所述缓冲队列中读取所述两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。
参见图1b所示的两个相邻算子执行过程示意图，当前一算子对应的线程执行该算子得到执行结果数据①、②、③和④并依次写入缓冲队列中；后一算子对应线程从缓冲队列中读取执行结果数据①，并将执行结果数据①作为自身输入，对执行结果数据①进行本线程对应的算子操作，同时，前一算子对应的线程并行执行本线程对应的算子操作，产出执行结果数据⑤，并将执行结果数据⑤写入缓冲队列中，使得后一算子在获得部分执行结果数据后立刻启动自身线程进行相应的算子操作，节约了相邻算子处理之间的数据等待时间。
而现有技术中在进行图数据库遍历时，通常采用以下两种方法：
方式(1)：将每一层操作抽象成一个算子，每个算子被抽象成可迭代对象。后一层算子执行时迭代地调用前一层算子，所有算子逻辑上形成一个嵌套的多层迭代，所有层迭代有序执行一轮，产出一个最终结果。比如，对于语句g.v(1).out("friend").has('age',eq(25)).properties('name')，其含义是找到编号为1的实体年龄为25岁的朋友的名字，properties算子执行一次，需要调用一次has算子,获得一个结果，has算子的调用将导致一次对out算子的调用，而out算子的执行将导致一次v算子的执行。所有算子执行一轮，产出一个最终结果，不存在任何并发逻辑，在大规模数据量上执行效率较低，导致系统资源利用率低下。
方式(2)：每层算子按严格顺序进行计算，下一层算子以上一层算子的输出作为其输入。例如在上面所举例的遍历语句执行时，首先执行v(1)，找出编号为1的实体，然后执行out算子，找出该实体所有的朋友实体。再然后，对这些实体进行过滤操作，筛选出其中年龄为25的实体，并输出其姓名。由于每一层算子的执行严格有序，下一层算子必须等到上一层算子的全部执行结果后，层能够启动，每一层算子执行都将阻塞整个执行流，同样在大规模数据量上实行效率较低。
可以理解的是，本申请通过将不同算子分配至不同的线程，使得前一算子的部分而非全部执行结果数据生成之后，即可通过后一算子的线程对该执行结果数据进行处理，而此时前一算子则继续执行相应的算子操作，生成其他执行结果数据。由于无需前一算子执行完毕后再进行后一算子的执行，减少了相邻算子执行的等待时间，同时达到了多个算子对应线程并行运行的效果，从而提高了对图数据库的遍历效率。
需要说明的是，当图遍历语句中包含多个算子，致使所创建缓冲队列数量较多时，为了便于对不同缓冲队列的区分，可以为各队列设置相应的地址信息，以便各线程在执行算子操作时，能够实现缓冲队列的准确定位。
示例性地，当在单个计算机设备中为各算子分配线程，以及为每两个相邻算子创建缓冲队列时，地址信息可以是各缓冲队列的队列标识，例如队列编号或所占用端口的端口信息。为了便于各线程进行缓冲队列的地址信息的查找，可以在计算机设备中设置一线程队列关系表，在该线程队列关系表中，针对任一线程，登记有存储该线程所执行算子的执行结果数据的缓冲队列的队列标识，以及存储有该线程所执行算子对应的前一算子的执行结果数据的缓冲队列的队列标识。需要说明的是，第一个算子不存在前一算子，因此其存储前一算子的执行结果数据的缓冲队列的队列标识可设置为空或其他默认值。
示例性地，当在多个计算机设备中为各算子分配线程，以及为每两个相邻算子创建缓冲队列时，针对第一个算子，将用于保存所述第一个算子的执行结果数据的缓冲队列的地址信息发送至用于执行所述第一个算子的计算机设备，以使执行所述第一个算子的计算机设备基于接收到的所述地址信息定位对应的缓冲队列；针对除所述第一个算子以外的任一目标算子，将用于保存所述任一目标算子的前一算子的执行结果数据的第一缓冲队列的地址信息和用于保存所述任一目标算子的执行结果数据的第二缓冲队列的地址信息，发送至用于执行所述任一目标算子的计算机设备，以使执行所述任一目标算子的计算机设备基于接收到的地址信息定位对应的所述第一缓冲队列和所述第二缓冲队列。
若缓冲队列创建于队列集群中，则缓冲队列的地址信息包括队列标识；若缓冲队列创建于计算机设备中，则缓冲队列的地址信息包括队列所在计算机设备的设备标识、端口信息和队列标识中的至少一个。示例性地，可以通过使用ip:port:id这一轻量级实现的方式确定缓冲队列的地址信息。其中，ip对应计算机设备的设备标识，port对应计算机设备的端口信息，id对应缓冲队列的全局队列标识。具体的，可以通过设备标识ip和端口信息port定位队列位置，通过队列标识id定位具体的缓冲队列。
本申请实施例通过获取输入的图遍历语句，确定图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列；对于每两个相邻算子，通过两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入两个相邻算子对应的缓冲队列中；以及，通过两个相邻算子中后一算子对应的线程，并行从缓冲队列中读取两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。上述技术方案通过在每两个相邻算子之间创建缓冲队列，使得在两个相邻算子中的前一算子产生执行结果数据并被写入缓冲队列中后，即可开始读取缓冲队列中的数据以执行后一算子，从而实现了算子的并行执行，提高了遍历操作的执行效率和系统资源利用率。
实施例二
图2是本申请实施例二中的一种图数据库遍历方法的流程图，本申请实施例在上述各实施例的技术方案的基础上进行了优化改进。
进一步地，在图数据库遍历方法中，追加以下操作“按照各算子的执行顺序，将令牌数据在各算子对应的线程间传递，以使接收到令牌数据的线程开始执行本线程对应算子的操作，并将所述令牌数据传递至下一算子对应的线程”，以关联触发下一算子对应的线程的启动。
如图2所示的一种图数据库遍历方法，包括：
s201、获取输入的图遍历语句，确定所述图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列。
s202、按照各算子的执行顺序，将令牌数据在各算子对应的线程间传递，以使接收到令牌数据的线程开始执行本线程对应算子的操作，并将所述令牌数据传递至下一算子对应的线程。
其中，令牌数据可以由设定长度的字符串组成，并预先存储在电子设备中，并在各算子对应的线程执行算子操作前，在不同线程之间进行传递。
示例性地，第一个算子对应的线程接收到令牌数据后，该接收到令牌数据的线程开始执行本线程对应的算子的操作，并将令牌数据传递至第二个算子对应的线程，进行相应线程执行本线程对应的算子操作的启动触发，一次类推，在前一线程开始执行相应线程对应的算子的操作后，将令牌数据传递至下一算子对应的线程，从而达到了各线程自动启动执行算子操作的目的。
可以理解的是，当可用线程的数量大于或等于算子的数量时，各算子均可分配不同的线程执行相应的算子操作，并通过令牌数据的传递依次触发各算子对应的线程进行相应算子操作的执行。
然而，当可用线程的数量小于算子的数量时，将会存在不具有对应线程的算子，致使并发线程数量受限，则可以通过已分配线程复用的方式实现线程的再分配。
示例性地，可以在所有线程分配完毕之后，监控各已分配线程的执行状态，并在存在已分配线程执行完毕本线程已分配算子的操作后，重新为该线程分配待分配算子，直至所有算子分配完毕。
相应的，在按照各算子的执行顺序，将令牌数据在各算子对应的线程间传递时，还可以通过如下方式对复用的已分配线程进行启动触发：接收到所述令牌数据的线程判断下一算子是否具有对应的线程；若接收到所述令牌数据的线程判断下一算子不具有对应的线程，则在出现满足预设条件的已分配线程时，将所述已分配线程重新分配给所述下一算子，并将所述令牌数据传递至所述已分配线程，以使所述已分配线程执行所述下一算子的操作；其中，所述预设条件为所述已分配线程已执行完本线程对应的算子的操作。
举例说明，当可用线程为4个，而图遍历语句对应的算子数量为5时，第一个算子对应的线程开始执行本线程对应的算子操作，并将令牌数据传递至第二个算子对应的线程，使得第二个算子对应的线程开始执行本线程对应的算子操作，并将令牌数据传递至下一个算子对应的线程，以此类推，第四个算子开始执行时，需要将令牌数据传递至第五个算子对应的线程，然而此时已耗尽并发资源，需要等待已分配的线程执行完相应的算子操作，释放并发资源。若此时第一个算子对应的线程执行完成，释放并发资源，则向第五个算子分配该空闲线程，并将令牌数据分配至第五个算子对应的线程，使得第二个算子对应的线程开始执行本线程对应的算子操作。
在本申请实施例的一种可选实施方式中，可以将令牌数据以全局编号的形式加以实现。示例性地，为每一个算子赋予一个有序编号，同时在电子设备中登记一个全局编号，每一个算子被执行时，将该全局编号修改为下一算子对应的编号，以此进行下一算子的确定及相应线程的查找，并在查找到下一算子对应的线程后，实现全局编号的传递，并在该下一算子被执行时，修改全局编号，以此类推，直至所有算子被执行。
s203、在各线程执行本线程对应算子的操作时，对于每两个相邻算子，通过所述两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入所述两个相邻算子对应的缓冲队列中；以及，通过所述两个相邻算子中后一算子对应的线程，并行从所述缓冲队列中读取所述两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。
本申请实施例的技术方案，通过按照各算子的执行顺序，将令牌数据在各算子对应的线程间传递，以使接收到令牌数据的线程开始执行本线程对应算子的操作，并将所述令牌数据传递至下一算子对应的线程，从而通过令牌数据在各算子对应的线程间的传递，关联触发下一算子对应的线程的启动，缩短了相邻算子对应的线程之间的等待时间，进而提高了执行效率。
实施例三
图3a是本申请实施例三中的一种图数据库遍历方法的流程图，本申请实施例在上述各实施例的技术方案的基础上进行了优化改进。
进一步的，在图数据库遍历方法中，追加以下操作“在除第一个算子以外的任一目标算子对应的线程确定满足算子执行终止条件时，执行预设操作以通知所述任一目标算子之前的各算子对应的线程终止对应算子的操作”，以消除大量的无效计算。
如图3a所示的一种图数据库遍历方法，包括：
s301、获取输入的图遍历语句，确定所述图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列。
s302、对于每两个相邻算子，通过所述两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入所述两个相邻算子对应的缓冲队列中；以及，通过所述两个相邻算子中后一算子对应的线程，并行从所述缓冲队列中读取所述两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。
s303、在除第一个算子以外的任一目标算子对应的线程确定满足算子执行终止条件时，执行预设操作以通知所述任一目标算子之前的各算子对应的线程终止对应算子的操作。
可以理解的是，在各算子对应的线程执行相应算子的操作的过程中，当除第一个算子以外的任一目标算子对应的线程满足算子终止条件时，通过执行预设操作，通知该任一目标算子之前的各算子对应的线程终止对相应算子的执行操作；该任一目标算子之后的各算子对应的线程，继续执行算子对应的操作，得到最终执行结果。示例性地，算子执行终止条件可以是以获取到所需的全部数据。上述方案通过执行预设操作，产生终止信息，并沿着缓冲队列链中数据流相反的方向进行终止信息传递，实现线程的逐层关闭。
在本申请实施例的一种可选实施方式中，执行预设操作以通知所述任一目标算子之前的各算子对应的线程终止对应算子的操作，可以是：将所述任一目标算子作为当前算子；将用于保存当前算子的前一算子的执行结果数据的缓冲队列的读端状态关闭，以使前一算子对应的线程在检测到该缓冲队列的读端状态被关闭时，停止向该缓冲队列写入数据并关闭该缓冲队列的写端状态，以终止前一算子的执行；将前一算子作为新的当前算子，并返回执行将用于保存当前算子的前一算子的执行结果数据的缓冲队列的读端状态关闭的操作，直至所述第一个算子的执行被终止。
具体的，在出第一个算子以外的任一目标算子对应的线程满足算子执行终止条件时，将该任一目标算子作为当前算子，并将保存该当前算子的前一算子的执行结果数据的缓冲队列的读端状态关闭，使得执行当前算子的线程无法从缓冲队列中继续读取前一算子的执行结果数据。相应的，前一算子对应的线程在检测到存储其执行结果数据的缓冲队列的读端状态被关闭时，获知其后一算子已无需进行本线程对应算子执行结果数据的获取，因此其主动停止向该缓冲队列写入数据，也即停止执行本线程对应的算子，阻止执行结果数据的生成；同时，关闭该缓冲队列的写端状态，被动停止向缓冲队列写入数据。将该前一算子作为新的当前算子，循环执行将用于保存当前算子的前一算子的执行结果数据的缓冲队列的读端状态关闭的操作，直至所述第一个算子的执行被终止。
参见图3b所示的每两个相邻算子进行终止信息传递的示意图。当后一算子从缓冲队列中获取到执行结果数据①后，确定满足算子执行终止条件，此时关闭缓冲队列的读端状态，禁止后一算子从缓冲队列中进行后续执行结果数据②、③和④等的读取。当前一算子检测到该缓冲队列的读端状态被关闭时，停止向缓冲队列中写入正在执行的算子的执行结果数据⑤，并关闭缓冲队列的写端状态，禁止前一算子对应线程向缓冲队列中写入数据，从而终止该前一算子的执行，实现终止信息的反向传递。将该前一算子作为新的后一算子，继续进行与其前一算子对应的缓冲队列的读端状态的关闭，以此类推，直至第一个算子的执行被终止。
在本申请实施例的另一可选实施方式中，执行预设操作以通知所述任一目标算子之前的各算子对应的线程终止对应算子的操作，还可以是：在预设全局信息表上登记终止信息，以使所述任一目标算子之前的各算子对应的线程读取到所述终止信息时，终止执行对应算子的操作。
具体的，可以预先设置一全局信息表，每个算子均可以在该全局信息表中登记或读取信息。当除第一个算子以外的任一算子对应的线程，确定满足算子执行终止条件时，在预先设置的全局信息表中，登记终止信息。由于执行图遍历语句所包含的各算子对应的线程，均能够在全局信息表中读取到终止信息，因此，当全局信息表中登记有终止信息时，任一目标算子之前的各算子对应的线程终止执行对应算子的操作，从而不再产生新的执行结果数据作为该任一目标算子的输入。
可以理解的是，由于上述方式可以实现该任一目标算子之前的算子同时读取到终止信息并终止执行结果数据的产生，各相邻算子被终止执行时不存在时间延迟，因此能够进一步减少无效计算的产生。另外，还可以在全局信息表中同时登记其他全局信息，以供图遍历语句所包含的各算子对应的线程之间实现信息共享。
本申请实施例在除第一个算子以外的任一目标算子对应的线程确定满足算子执行终止条件时，执行预设操作以通知所述任一目标算子之前的各算子对应的线程终止对应算子的操作。上述技术方案通过在后一算子在确定满足终止条件时，执行预设操作以通知前面所有算子终止执行，从而通过反馈机制消除了潜在的大量无效计算。
实施例四
图4是本申请实施例四中的一种图数据库遍历装置的结构图，本申请实施例适用于在图数据库中进行数据遍历的情况，该装置采用软件和/或硬件实现，并具体配置于具备一定数据运算能力的电子设备中。
如图4所示的一种图数据库遍历装置400，包括：遍历语句获取模块401和算子并行执行模块402。其中，
遍历语句获取模块401，用于获取输入的图遍历语句，确定所述图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列；
算子并行执行模块402，用于对于每两个相邻算子，通过所述两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入所述两个相邻算子对应的缓冲队列中；以及，通过所述两个相邻算子中后一算子对应的线程，并行从所述缓冲队列中读取所述两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。
本申请实施例通过遍历语句获取模块获取输入的图遍历语句，确定图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列；通过算子并行执行模块对于每两个相邻算子，通过两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入两个相邻算子对应的缓冲队列中；以及，通过两个相邻算子中后一算子对应的线程，并行从缓冲队列中读取两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。上述技术方案通过在每两个相邻算子之间创建缓冲队列，使得在两个相邻算子中的前一算子产生执行结果数据并被写入缓冲队列中后，即可开始读取缓冲队列中的数据以执行后一算子，从而实现了算子的并行执行，提高了遍历操作的执行效率和系统资源利用率。
进一步地，该装置还包括，令牌传递模块，用于：
按照各算子的执行顺序，将令牌数据在各算子对应的线程间传递，以使接收到令牌数据的线程开始执行本线程对应算子的操作，并将所述令牌数据传递至下一算子对应的线程。
进一步地，遍历语句获取模块401，在执行为各算子分别分配线程时，具体用于：
根据可用线程的数量，按照各算子的执行顺序，为各算子分别分配线程。
进一步地，若所述可用线程的数量小于算子的数量，则遍历语句获取模块401，在按照各算子的执行顺序，将令牌数据在各算子对应的线程间传递时，具体用于：
接收到所述令牌数据的线程判断下一算子是否具有对应的线程；
若接收到所述令牌数据的线程判断下一算子不具有对应的线程，则在出现满足预设条件的已分配线程时，将所述已分配线程重新分配给所述下一算子，并将所述令牌数据传递至所述已分配线程，以使所述已分配线程执行所述下一算子的操作；
其中，所述预设条件为所述已分配线程已执行完本线程对应的算子的操作。
进一步地，遍历语句获取模块401，在执行为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列时，具体用于：
为各算子分别分配本地计算机设备的线程，并为每两个相邻算子在所述本地计算机设备分别创建缓冲队列；或者，
针对各算子，从至少两个计算机设备中确定用于执行所述算子的计算机设备，并为所述算子分配所确定的计算机设备的线程；
针对每两个相邻算子，从至少两个计算机设备中确定用于创建缓冲队列的计算机设备，并在所确定的计算机设备中创建所述两个相邻算子对应的缓冲队列。
进一步地，该装置还包括，地址信息保存模块，具体用于：
针对第一个算子，将用于保存所述第一个算子的执行结果数据的缓冲队列的地址信息发送至用于执行所述第一个算子的计算机设备，以使执行所述第一个算子的计算机设备基于接收到的所述地址信息定位对应的缓冲队列；
针对除所述第一个算子以外的任一目标算子，将用于保存所述任一目标算子的前一算子的执行结果数据的第一缓冲队列的地址信息和用于保存所述任一目标算子的执行结果数据的第二缓冲队列的地址信息，发送至用于执行所述任一目标算子的计算机设备，以使执行所述任一目标算子的计算机设备基于接收到的地址信息定位对应的所述第一缓冲队列和所述第二缓冲队列。
进一步地，若所述缓冲队列创建于队列集群中，则所述缓冲队列的地址信息包括队列标识；
若所述缓冲队列创建于计算机设备中，则所述缓冲队列的地址信息包括队列所在计算机设备的设备标识、端口信息和队列标识中的至少一个。
进一步地，该装置还包括，线程终止模块，用于：
在除第一个算子以外的任一目标算子对应的线程确定满足算子执行终止条件时，执行预设操作以通知所述任一目标算子之前的各算子对应的线程终止对应算子的操作。
进一步地，线程终止模块，在执行如下操作时：执行预设操作以通知所述任一目标算子之前的各算子对应的线程终止对应算子的操作，具体用于：
将所述任一目标算子作为当前算子；将用于保存当前算子的前一算子的执行结果数据的缓冲队列的读端状态关闭，以使前一算子对应的线程在检测到该缓冲队列的读端状态被关闭时，停止向该缓冲队列写入数据并关闭该缓冲队列的写端状态，以终止前一算子的执行；将前一算子作为新的当前算子，并返回执行将用于保存当前算子的前一算子的执行结果数据的缓冲队列的读端状态关闭的操作，直至所述第一个算子的执行被终止；或者，
在预设全局信息表上登记终止信息，以使所述任一目标算子之前的各算子对应的线程读取到所述终止信息时，终止执行对应算子的操作。
上述图数据库遍历装置可执行本申请任意实施例所提供的图数据库遍历方法，具备执行图数据库遍历方法相应的功能模块和有益效果。
实施例五
根据本申请的实施例，本申请还提供了一种电子设备和一种可读存储介质。
如图5所示，是实现本申请实施例的图数据库遍历方法的电子设备的框图。电子设备旨在表示各种形式的数字计算机，诸如，膝上型计算机、台式计算机、工作台、个人数字助理、服务器、刀片式服务器、大型计算机、和其它适合的计算机。电子设备还可以表示各种形式的移动装置，诸如，个人数字处理、蜂窝电话、智能电话、可穿戴设备和其它类似的计算装置。本文所示的部件、它们的连接和关系、以及它们的功能仅仅作为示例，并且不意在限制本文中描述的和/或者要求的本申请的实现。
如图5所示，该电子设备包括：一个或多个处理器501、存储器502，以及用于连接各部件的接口，包括高速接口和低速接口。各个部件利用不同的总线互相连接，并且可以被安装在公共主板上或者根据需要以其它方式安装。处理器可以对在电子设备内执行的指令进行处理，包括存储在存储器中或者存储器上以在外部输入/输出装置(诸如，耦合至接口的显示设备)上显示gui的图形信息的指令。在其它实施方式中，若需要，可以将多个处理器和/或多条总线与多个存储器和多个存储器一起使用。同样，可以连接多个电子设备，各个设备提供部分必要的操作(例如，作为服务器阵列、一组刀片式服务器、或者多处理器系统)。图5中以一个处理器501为例。
存储器502即为本申请所提供的非瞬时计算机可读存储介质。其中，所述存储器存储有可由至少一个处理器执行的指令，以使所述至少一个处理器执行本申请所提供的图数据库遍历方法。本申请的非瞬时计算机可读存储介质存储计算机指令，该计算机指令用于使计算机执行本申请所提供的图数据库遍历方法。
存储器502作为一种非瞬时计算机可读存储介质，可用于存储非瞬时软件程序、非瞬时计算机可执行程序以及模块，如本申请实施例中的图数据库遍历方法对应的程序指令/模块(例如，附图4所示的包括遍历语句获取模块401和算子并行执行模块402的图数据库遍历装置400)。处理器501通过运行存储在存储器502中的非瞬时软件程序、指令以及模块，从而执行服务器的各种功能应用以及数据处理，即实现上述方法实施例中的图数据库遍历方法。
存储器502可以包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需要的应用程序；存储数据区可存储执行图数据库遍历方法的电子设备的使用所创建的数据等。此外，存储器502可以包括高速随机存取存储器，还可以包括非瞬时存储器，例如至少一个磁盘存储器件、闪存器件、或其他非瞬时固态存储器件。在一些实施例中，存储器502可选包括相对于处理器501远程设置的存储器，这些远程存储器可以通过网络连接至执行图数据库遍历方法的电子设备。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。
执行图数据库遍历方法的电子设备还可以包括：输入装置503和输出装置504。处理器501、存储器502、输入装置503和输出装置504可以通过总线或者其他方式连接，图5中以通过总线连接为例。
输入装置503可接收输入的数字或字符信息，以及产生与执行图数据库遍历方法的电子设备的用户设置以及功能控制有关的键信号输入，例如触摸屏、小键盘、鼠标、轨迹板、触摸板、指示杆、一个或者多个鼠标按钮、轨迹球、操纵杆等输入装置。输出装置504可以包括显示设备、辅助照明装置(例如，led)和触觉反馈装置(例如，振动电机)等。该显示设备可以包括但不限于，液晶显示器(lcd)、发光二极管(led)显示器和等离子体显示器。在一些实施方式中，显示设备可以是触摸屏。
此处描述的系统和技术的各种实施方式可以在数字电子电路系统、集成电路系统、专用asic(专用集成电路)、计算机硬件、固件、软件、和/或它们的组合中实现。这些各种实施方式可以包括：实施在一个或者多个计算机程序中，该一个或者多个计算机程序可在包括至少一个可编程处理器的可编程系统上执行和/或解释，该可编程处理器可以是专用或者通用可编程处理器，可以从存储系统、至少一个输入装置、和至少一个输出装置接收数据和指令，并且将数据和指令传输至该存储系统、该至少一个输入装置、和该至少一个输出装置。
这些计算程序(也称作程序、软件、软件应用、或者代码)包括可编程处理器的机器指令，并且可以利用高级过程和/或面向对象的编程语言、和/或汇编/机器语言来实施这些计算程序。如本文使用的，术语“机器可读介质”和“计算机可读介质”指的是用于将机器指令和/或数据提供给可编程处理器的任何计算机程序产品、设备、和/或装置(例如，磁盘、光盘、存储器、可编程逻辑装置(pld))，包括，接收作为机器可读信号的机器指令的机器可读介质。术语“机器可读信号”指的是用于将机器指令和/或数据提供给可编程处理器的任何信号。
为了提供与用户的交互，可以在计算机上实施此处描述的系统和技术，该计算机具有：用于向用户显示信息的显示装置(例如，crt(阴极射线管)或者lcd(液晶显示器)监视器)；以及键盘和指向装置(例如，鼠标或者轨迹球)，用户可以通过该键盘和该指向装置来将输入提供给计算机。其它种类的装置还可以用于提供与用户的交互；例如，提供给用户的反馈可以是任何形式的传感反馈(例如，视觉反馈、听觉反馈、或者触觉反馈)；并且可以用任何形式(包括声输入、语音输入或者、触觉输入)来接收来自用户的输入。
可以将此处描述的系统和技术实施在包括后台部件的计算系统(例如，作为数据服务器)、或者包括中间件部件的计算系统(例如，应用服务器)、或者包括前端部件的计算系统(例如，具有图形用户界面或者网络浏览器的用户计算机，用户可以通过该图形用户界面或者该网络浏览器来与此处描述的系统和技术的实施方式交互)、或者包括这种后台部件、中间件部件、或者前端部件的任何组合的计算系统中。可以通过任何形式或者介质的数字数据通信(例如，通信网络)来将系统的部件相互连接。通信网络的示例包括：局域网(lan)、广域网(wan)和互联网。
计算机系统可以包括客户端和服务器。客户端和服务器一般远离彼此并且通常通过通信网络进行交互。通过在相应的计算机上运行并且彼此具有客户端-服务器关系的计算机程序来产生客户端和服务器的关系。
本申请实施例通过获取输入的图遍历语句，确定图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列；对于每两个相邻算子，通过两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入两个相邻算子对应的缓冲队列中；以及，通过两个相邻算子中后一算子对应的线程，并行从缓冲队列中读取两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。上述技术方案通过在每两个相邻算子之间创建缓冲队列，使得在两个相邻算子中的前一算子产生执行结果数据并被写入缓冲队列中后，即可开始读取缓冲队列中的数据以执行后一算子，从而实现了算子的并行执行，提高了遍历操作的执行效率和系统资源利用率。
应该理解，可以使用上面所示的各种形式的流程，重新排序、增加或删除步骤。例如，本发申请中记载的各步骤可以并行地执行也可以顺序地执行也可以不同的次序执行，只要能够实现本申请公开的技术方案所期望的结果，本文在此不进行限制。
上述具体实施方式，并不构成对本申请保护范围的限制。本领域技术人员应该明白的是，根据设计要求和其他因素，可以进行各种修改、组合、子组合和替代。任何在本申请的精神和原则之内所作的修改、等同替换和改进等，均应包含在本申请保护范围之内。
1.一种图数据库遍历方法，其特征在于，包括：
获取输入的图遍历语句，确定所述图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列；
对于每两个相邻算子，通过所述两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入所述两个相邻算子对应的缓冲队列中；以及，通过所述两个相邻算子中后一算子对应的线程，并行从所述缓冲队列中读取所述两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。
2.根据权利要求1所述的方法，其特征在于，所述方法还包括：
按照各算子的执行顺序，将令牌数据在各算子对应的线程间传递，以使接收到令牌数据的线程开始执行本线程对应算子的操作，并将所述令牌数据传递至下一算子对应的线程。
3.根据权利要求2所述的方法，其特征在于，为各算子分别分配线程，包括：
根据可用线程的数量，按照各算子的执行顺序，为各算子分别分配线程。
4.根据权利要求3所述的方法，其特征在于，若所述可用线程的数量小于算子的数量，在按照各算子的执行顺序，将令牌数据在各算子对应的线程间传递时，所述方法还包括：
接收到所述令牌数据的线程判断下一算子是否具有对应的线程；
若接收到所述令牌数据的线程判断下一算子不具有对应的线程，则在出现满足预设条件的已分配线程时，将所述已分配线程重新分配给所述下一算子，并将所述令牌数据传递至所述已分配线程，以使所述已分配线程执行所述下一算子的操作；
其中，所述预设条件为所述已分配线程已执行完本线程对应的算子的操作。
5.根据权利要求1所述的方法，其特征在于，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列，包括：
为各算子分别分配本地计算机设备的线程，并为每两个相邻算子在所述本地计算机设备分别创建缓冲队列；或者，
针对各算子，从至少两个计算机设备中确定用于执行所述算子的计算机设备，并为所述算子分配所确定的计算机设备的线程；
针对每两个相邻算子，从至少两个计算机设备中确定用于创建缓冲队列的计算机设备，并在所确定的计算机设备中创建所述两个相邻算子对应的缓冲队列。
6.根据权利要求5所述的方法，其特征在于，所述方法还包括：
针对第一个算子，将用于保存所述第一个算子的执行结果数据的缓冲队列的地址信息发送至用于执行所述第一个算子的计算机设备，以使执行所述第一个算子的计算机设备基于接收到的所述地址信息定位对应的缓冲队列；
针对除所述第一个算子以外的任一目标算子，将用于保存所述任一目标算子的前一算子的执行结果数据的第一缓冲队列的地址信息和用于保存所述任一目标算子的执行结果数据的第二缓冲队列的地址信息，发送至用于执行所述任一目标算子的计算机设备，以使执行所述任一目标算子的计算机设备基于接收到的地址信息定位对应的所述第一缓冲队列和所述第二缓冲队列。
7.根据权利要求6所述的方法，其特征在于，若所述缓冲队列创建于队列集群中，则所述缓冲队列的地址信息包括队列标识；
若所述缓冲队列创建于计算机设备中，则所述缓冲队列的地址信息包括队列所在计算机设备的设备标识、端口信息和队列标识中的至少一个。
8.根据权利要求1-7任一项所述的方法，其特征在于，所述方法还包括：
在除第一个算子以外的任一目标算子对应的线程确定满足算子执行终止条件时，执行预设操作以通知所述任一目标算子之前的各算子对应的线程终止对应算子的操作。
9.根据权利要求8所述的方法，其特征在于，执行预设操作以通知所述任一目标算子之前的各算子对应的线程终止对应算子的操作，包括：
将所述任一目标算子作为当前算子；将用于保存当前算子的前一算子的执行结果数据的缓冲队列的读端状态关闭，以使前一算子对应的线程在检测到该缓冲队列的读端状态被关闭时，停止向该缓冲队列写入数据并关闭该缓冲队列的写端状态，以终止前一算子的执行；将前一算子作为新的当前算子，并返回执行将用于保存当前算子的前一算子的执行结果数据的缓冲队列的读端状态关闭的操作，直至所述第一个算子的执行被终止；或者，
在预设全局信息表上登记终止信息，以使所述任一目标算子之前的各算子对应的线程读取到所述终止信息时，终止执行对应算子的操作。
10.一种图数据库遍历装置，其特征在于，包括：
遍历语句获取模块，用于获取输入的图遍历语句，确定所述图遍历语句包含的至少两个算子和各算子的执行顺序，为各算子分别分配线程，并为每两个相邻算子分别创建缓冲队列；
算子并行执行模块，用于对于每两个相邻算子，通过所述两个相邻算子中前一算子对应的线程，执行前一算子的操作，并将前一算子的执行结果数据写入所述两个相邻算子对应的缓冲队列中；以及，通过所述两个相邻算子中后一算子对应的线程，并行从所述缓冲队列中读取所述两个相邻算子中前一算子的执行结果数据，以用于执行后一算子的操作。
11.一种电子设备，其特征在于，包括：
至少一个处理器；以及
与所述至少一个处理器通信连接的存储器；其中，
所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行权利要求1-9中任一项所述的一种图数据库遍历方法。
12.一种存储有计算机指令的非瞬时计算机可读存储介质，其特征在于，所述计算机指令用于使所述计算机执行权利要求1-9中任一项所述的一种图数据库遍历方法。
技术总结