在rdbms中构建反向csr图索引的快速存储器内技术
技术领域
1.本发明涉及将异构图从关系数据库的表加载到存储器中。本文是并行技术，用于加速冗余压缩稀疏行(csr)编码的对的构建，用于在任一方向上遍历特性图的有向边。
背景技术：2.对驻留在关系数据库管理系统(rdbms)中的数据的图分析的需求正在增长。一些解决方案需要在rdbms之外构造图来存储感兴趣的数据。一种解决方案需要在专用的图分析引擎中构造图。另一种解决方案需要将数据迁移到图数据库。这些解决方案是不期望的，因为它们大大增加了企业中数据管理的复杂性并导致外部引擎的显著加载/数据传送成本。
3.在rdbms中，直接在关系表上执行图分析(诸如图模式匹配查询，或图算法执行，或两者的组合)的性能明显低于专用图引擎提供的性能，尤其是对于感兴趣的算法(诸如pagerank)。rdbms可以将图算法作为一系列缓慢的并且要求短期中间结果的繁琐物化的表连接来实现。
4.一些查询(诸如路径查找查询)比关系查询(诸如结构化查询语言(sql))更好地表达为图查询。例如，拓扑查询可以更好地表达为正则表达式或上下文无关表达式，它们不容易表达为sql。只预期sql和/或表格的查询的rdbms通常没有专门用于图分析的数据结构。以这些方式，本领域rdbms的状态对于图分析来说可能太慢了。
5.rdbms处理关系数据，即，存储为通过主键-外键关系连接在一起的表的数据。这种关系数据可以作为图被分析。例如，n:m关系可以被解释为边。然后可以在关系数据之上构建存储器内图表示，诸如邻接列表或邻接矩阵。
6.一种存储器内图索引方法是压缩稀疏行(csr)表示，它提供了仅使用两个数组(本文中称为源数组和目的地数组)的邻接列表的紧凑表示。有向图的技术问题是csr表示只能使得有可能遵循一个方向上的边：从源数组到目的地数组，这对于各种图分析可能表现不佳。
附图说明
7.在附图中：
8.图1a是描绘示例关系模式和示例图数据模型之间的示例映射的框图；
9.图1b是描绘示例正向csr和反向csr的框图；
10.图2是描绘为图的边类型填充一对csr的示例过程的流程图；
11.图3描绘了填充反向csr时可以发生的示例活动；
12.图4是描绘使用并行性来加速图的csr编码的对的填充的示例计算机的框图；
13.图5描绘了促进反向目的地数组的数据和/或元数据的并行填充的示例活动；
14.图6描绘了促进反向源数组的数据和/或元数据的并行填充的示例活动；
15.图7是图示可以在其上实现本发明的实施例的计算机系统的框图；
16.图8是图示可以用于控制计算系统的操作的基本软件系统的框图。
具体实施方式
17.在下面的描述中，出于解释的目的，阐述了许多具体细节以便提供对本发明的透彻理解。但是，将显而易见的是，可以在没有这些具体细节的情况下实践本发明。在其它情况下，以框图形式示出了众所周知的结构和设备，以避免不必要地使本发明晦涩难懂。
18.总体概述
19.本文是将异构图从关系数据库的表加载到存储器中的方法。呈现了并行化技术以加速冗余压缩稀疏行(csr)编码对的构造，用于在任一方向上遍历特性图的有向边。
20.正向和反向csr是存储器内关系数据库管理系统(rdbms)图索引，它们单独地或作为对一起使得有可能在任何方向上快速遵循来自图数据的边并加速一些图模式匹配查询和图算法(诸如pagerank)。就像正向csr，反向csr可以使用sql查询从关系数据构建，但这样做很慢。本文的技术使得有可能通过使用快速存储器内并行算法从预先存在的正向csr构建反向csr来加速反向csr的创建。
21.除了正向csr，构建第二个图索引(本文中称为反向csr)可以是有益的，除了它们的方向反转之外，它再次存储图的所有边。除了正向csr之外，构建反向csr的优势在于它可以在任一方向上遵循边，这对于图模式匹配查询和图算法都是有益的。在一个示例中，用户想要匹配一长串顶点(a1)
→
(a2)
→
...
→
(an)，并在顶点(an)的特性上使用非常有选择性的过滤器。如果正向csr是唯一可用的图索引，那么必须在丢弃之前一直探索许多链到(an)。如果反向csr可用，那么可以从(an)开始探索，并且只有在(an)没有被过滤掉的极少数情况下，才会遵循该链，这对性能有益。
22.在另一个示例中，用户想要使用多个线程来运行本文稍后解释的pagerank图算法。如果没有可用的反向csr，那么多个线程将迭代通过正向csr的源数组的不同部分，每次都增加在目的地数组中找到的邻居顶点的排名。由于由不同线程处理的多个源顶点可以连接到同一个目的地顶点，因此线程要求同步来更新目的地顶点的新排名。但是，如果反向csr可用，那么多个线程可以迭代通过不同的目的地顶点，每次都找到所有对应的源顶点并立即计算新的排名，而无需同步。去除跨线程同步的需要可以增加吞吐量并减少时延。
23.同时使用正向和反向csr有两个主要缺点：(1)存储器使用量是仅使用正向csr的两倍；以及(2)构建两个图索引比构建单个图索引慢。通过提出一种快速的存储器内和并行算法来从预先存在的正向csr构建反向csr，而不是使用对顶点和边表的sql查询从头开始构建它，本文的技术减少了(2)的影响。
24.在实施例中，计算机获得数据库的关系模式到图数据模型的映射。关系模式识别与图数据模型中的(一种或多种)相应顶点类型对应的(一个或多个)顶点表和与图数据模型中的(一种或多种)相应边类型对应的(一个或多个)边表。每种边类型是有向的，因此与相应的源顶点类型和相应的目标顶点类型相关联。基于那个映射，正向压缩稀疏行(csr)表示被填充用于相同边类型的边的正向遍历。边类型的每条边起始于边类型的源顶点类型的源顶点并终止于边类型的目标顶点类型的目标顶点。基于正向csr表示，填充边类型的反向csr表示以用于边类型的边的反向遍历。加速以两种方式发生。首先，为正向csr计算的值被重用于反向csr。其次，弹性和非弹性缩放可能以相应的方式发生。
25.1.0示例计算机和图
26.图1a-1b是在实施例中描绘示例计算机100和示例图105的框图。计算机100使用并行化来加速逻辑图105的冗余压缩稀疏行(csr)编码对的填充。计算机100可以是至少一个机架服务器，诸如刀片、个人计算机、大型机、虚拟计算机或其它计算设备。当计算机100包括多个计算机时，计算机通过通信网络互连。
27.图105是有向图，它包含顶点a-d和互连顶点a-d有向边u-z，如图所示。图105是图数据模型130的实例，它包含顶点类型141-142和边类型151-152，如图数据模型130的元素类型列中所示。图数据模型130的显示列是图实例的说明性图例，诸如105。例如并且根据显示列，边y被示为点线，其指示边y是边类型152的实例。
28.图1a描绘了在实施例中的示例关系模式160与示例图数据模型130之间的示例映射120。图数据模型130可以定义特性(未示出)以及顶点和边的类型。例如，顶点类型141可以具有年龄特性和颜色特性，其中一些、没有或全部也可以是顶点类型142的特性。
29.根据图数据模型130，每种边类型具有相应的源顶点类型和目标顶点类型，对于其它边类型，它们中的任一个、没有或两者都可以是完全相同的。例如，两种边类型151-152具有相同的源顶点类型141，但具有不同的相应目标顶点类型141-142。
30.对于边类型151，源顶点类型也是目标顶点类型，这促进自有向边，诸如x，其起源和终止于同一个顶点。在一些实施例中，第一顶点可以通过相同或不同边类型的多条边在相同方向或相反方向上冗余地连接到相同的第二顶点。例如，边u和x冗余地将顶点a连接到自身。
31.在操作中并且取决于实施例，将图105加载到易失性或非易失性存储器中以作为各种列向量进行分析。向量的内容在元素数据类型方面是同质的，但是不同的向量可以具有不同的内容数据类型。例如，向量可以存储相同类型的顶点或边的相同特性的值。向量可以存储图元素的系统特性，诸如顶点类型141的顶点的标识符。向量可以存储图元素的应用特性，诸如顶点类型141的顶点的运输状态。
32.虽然同一向量的元素在存储器中被连续存储，但同一图元素类型的不同相应特性的多个向量在存储器中不需要相邻。同一图元素类型的不同相应特性的多个向量应当具有相同数量的元素，并且那些向量的内容应当具有完全相同的次序。例如，对于顶点类型141，顶点a的颜色或年龄应当出现在相应颜色和年龄特性向量中的每一个中的相同偏移量处。
33.那个偏移量可以作为规范偏移量来操作以访问同一顶点或边的所有特性。规范偏移量在本文中还可以被称为内部标识符、易失性标识符或存储器内图拓扑标识符(imgtid)。如本文稍后解释的，规范偏移量是各种密集标识符中的一种。
34.如本文所使用的，取决于上下文，用于一种图形元素类型的存储器内数组可以是单个特性向量或多个不同特性向量的逻辑聚合，这些特性向量接受图元素类型的规范偏移量作为偏移量。每个图元素类型具有自己的从零开始增加的规范偏移量值序列。计算机100注意不要混淆不同图形元素类型的规范偏移量值，即使此类偏移量在语法上是可互换的。规范偏移量在语义上不可互换。
35.规范偏移量在其顶点类型或边类型内唯一识别顶点或边。规范偏移量不是全局唯一的。不同类型的顶点和/或边可以无意中共享相同的规范偏移量。例如，零可以是具有不同顶点类型的顶点a和d的相同规范偏移量。
36.在实施例中，规范偏移量的唯一性仅针对相同的图实例得到保证。如果图数据模型130描述并发地驻留在存储器中的多个图实例，那么每个图实例具有其自己的顶点数组和边数组的集合。例如并且不管两个图实例是否共享相同的图数据模型130，如果两个图实例共享顶点类型141，那么对于相同的顶点类型141，存在具有单独特性向量的两个单独顶点数组。因此，不应当混淆用于两个图实例的相同顶点类型141的顶点。
37.在实施例中，图实例可以部分重叠以共享(一个或多个)顶点和/或(一个或多个)边。即使对于不共享元数据120、130和/或160的图实例，当(一种或多种)顶点类型和/或(一种或多种)边类型被共享时，图实例也可以共享一些csr、向量或数组。例如，这种聚合和/或索引结构可以为一个、一些或所有图元素类型存储两个图实例的联合。在实施例中，可以仅共享元数据120、130和/或160，但不共享图实例内容。csr将在本文后面解释。
38.将任何或每种图元素类型加载到存储器中可以为每个图元素类型创建至少一个特性向量。因此，每种顶点类型和边类型都有特性向量的非空逻辑集合。对于顶点类型，向量的逻辑集合在本文中被称为顶点数组，其在逻辑上是表格的。对于边类型，向量的那个逻辑集合被称为边数组，其在逻辑上是表格的。
39.因此，顶点类型141-142和边类型151-152各自具有特性向量的相应顶点数组或边数组。在本文中，存储器中的图元素的所有内部标识符都是到相应图元素类型的顶点数组或边数组的规范偏移量值。每种图元素类型具有其自己的从零开始的、密集的、升序的和连续的非负整数值序列，在将图105加载到存储器中时以及将图105从存储器中逐出和/或重新加载到存储器中之前，该序列是有效的，如在相关美国专利申请16/747,827中解释的那样。
40.一种图元素类型的数组中的(一个或多个)一些特性向量可以存储另一种图元素类型的规范偏移量以进行交叉引用。例如，边数组可以具有存储边类型的目标顶点类型的顶点的规范偏移量的特性向量。因此，各种图元素数组可以彼此关联，这足以对图105的整个拓扑进行编码。
41.图105从具有定义顶点表171-172和边表181-182的关系模式160的关系数据库加载。关系模式160定义用于图105的数据的持久性格式，并且图数据模型130定义适用于存储器中的图分析的分析格式。例如，顶点表171的每一行可以是顶点类型141的相应顶点的持久表示。例如，顶点a可以作为行存储在顶点表171中，而顶点d可以存储在顶点表172中。
42.映射120或多或少是图数据模型130与关系模式160之间的数据绑定。映射120可以是双向的，以促进在加载或持久化期间的数据重新格式化。在实施例中，映射120的行被存储为映射表中的行，诸如在关系模式160中或在不同模式和/或数据库中。在实施例中，映射120代替地被持久化到单独的数据文件或在操作期间交互式地输入。
43.虽然未示出，映射120可以包含比表到顶点类型的一对一映射更细或更粗粒度的绑定。例如，映射120可以包含查询谓词，该查询谓词可以基于顶点表行的内容选择性地将顶点表的行绑定到不同的相应顶点类型。同样，映射120可以包含可以将顶点类型绑定到多个顶点表的查询联合或查询连接。
44.映射的语义，诸如120，提供了促进各种场景的灵活性。例如，多个数据库实例可以共享相同的关系模式160，但在关系表中每个数据库实例具有不同的内容，并且可以使用相同的图数据模型130和映射120来为每个数据库实例生成单独的图实例。不同的映射，诸如
120，可以各自将相同的关系模式160映射到不同的相应图数据模型。不同的映射，诸如120，可以各自将不同的相应关系模式映射到相同的图数据模型。
45.映射120为各种结构规一化、重新规一化或去规一化场景提供灵活性。例如，每个顶点表行可以映射到顶点，并且每个边表行可以映射到边。边表可以具有到顶点表的外键，反之亦然。这些和以下映射细节(诸如哪些表列是主键或外键以及那些键如何被使用以及如何与图元素类型相关联)在映射120中指定。
46.在一些实施例中，表关系的极性可以如下改变。例如，连接两个顶点表的边表可以具有一个顶点表的外键，而另一个顶点表可以具有边表的外键。边表可以是关联表，对于两个连接的顶点表分别具有两个外键。边表可以没有外键，诸如当两个连接的表都具有边表的外键时。边类型不需要具有任何边表，诸如当一个顶点表具有另一个顶点表的外键时。
47.可以存在表行的某种过载，使得映射120可以将同一顶点表的同一行映射到多种顶点类型。例如，同一行可以具有两列，该两列具有不同的相应外键，用于映射到具有不同相应源顶点类型和/或不同相应目标顶点类型的不同相应边类型的不同相应关系。
48.映射120的各种实施例可以包含各种绑定元组，诸如以下任何一个：
49.·
(关系表，图元素类型)
50.·
(源顶点类型、边类型、目标顶点类型)
51.·
(源顶点表、边表、目标顶点表)
52.·
(源主键、源外键、目标主键、目标外键)。
53.实施例可以部分地或完全地组合那些种类的元组来替代地实现其它种类的元组。
54.以上面呈现的许多方式，有足够的灵活性，使得映射120可以与不同的数据库实例重用，诸如一月销售数据库和二月销售数据库，并且不同的映射可以：a)使不同的相应关系模式适应同一个图数据模型，和/或b)使不同的相应图数据模型适应同一个关系模式。例如，两个不同的映射可以交替地将同一个边表映射到不同的相应边类型，这些边类型在不同的相应图数据模型中仅在方向上不同。例如，两种边类型可以连接相同的两种顶点类型，使得一种边类型使用一种顶点类型作为源顶点类型，而另一种边类型使用相同的顶点类型作为目标顶点类型。因此，外键极性和边类型方向可以相关也可以不相关。
55.这种适应性可以促进与遗留数据库的集成，而不会干扰其遗留模式，从而使遗留模式和遗留内容面向未来。因此，促进映射、关系模式、图数据模型和/或数据库内容的重用和/或再利用。
56.1.1示例正向csr
57.图1b描绘了实施例中的示例正向csr 110和反向csr 115。图1b是参考图1a呈现的。
58.图1a的映射120是元数据，不需要为了分析而提供任何特定图实例的实际内容，诸如105。图105的分析表示基于(一个或多个)csr聚合，诸如110和/或115，用于存储器(诸如易失性动态随机存取存储器(dram))中的拓扑编码。如图所示，csr 110和115仅对边类型151的边进行编码。其它边类型可以各自具有一对单独的csr。
59.正向csr 110包含正向数组190和195，虽然被示为表格，但它们是相应单列的整数向量，其实际存储的内容被示为粗体。正向csr 110中未被示为粗体的列是隐含列，它们可以是说明性的并且实际上并未存储。
60.图105的顶点和边被拓扑编码为csr的(一个或多个)对，诸如用于边类型151的110和115，如下所示。每种边类型具有其自己的正向csr，该正向csr具有其自己的正向源数组，诸如190。正向源数组190的每一行表示顶点类型141的不同顶点，它是边类型151的源顶点类型。每种边类型具有其自己的边数组，诸如用于边类型151的正向目标数组195。正向目标数组195的每一行表示边类型151的不同边。
61.每种边类型具有其自己的csr对，诸如用于边类型151的csr110和115。虽然多个边类型151-152共享相同的源顶点类型141，但边类型151-152的相应正向csr具有其自己的相应正向源数组。
62.正向源数组190包含正向边位置向量，该向量包含正向目的地数组195的行的偏移量。正向源数组190的正向边位置向量中的值单调递增以指示表示边类型151的边的正向目标数组195的行的子序列的起始位置，这些边源自正向源数组190的给定行的顶点。例如，在正向源数组190中，顶点a源自边类型151的边，这些边被表示为在正向目标数组195的第0行开始的连续相应行。正向源数组190的正向边位置向量中的每个值可以通过将源自正向源数组190的前一行的前一个顶点的边类型151的边的计数与前一个值相加来计算。
63.例如，顶点a引发边类型151的四条边u-x，它们由正向目的地数组195的第0-3行表示。因此，零+四＝四是用于顶点b的正向源数组190的正向边位置向量中的值。同样，顶点b不引发边，因此四+零＝四是用于顶点c的正向源数组190的正向边位置向量中的值。在实施例中，正向源数组190的正向边位置向量中的最后一个条目包含边类型151的边的计数，它也是正向目的地数组195中的行的计数。
64.正向目的地数组195的每个边行在顶点位置向量中指示目标顶点类型141的顶点数组中的行的偏移量，在这种情况下，正向目的地数组195可以是或包括正向源数组190，如下面所解释的。例如，正向目的地数组195的顶点位置向量指示边v终止于正向源数组190的第1行中的顶点，即，顶点b。
65.通过仅使用正向源数组190的正向边位置向量，计算机100可以通过减去相邻值来检测顶点a引发边类型151的四条边。通过在使用正向源数组190之后使用正向目的地数组195，计算机100还可以检测这四条边终止于顶点a-c。对于每种边类型都有单独的csr，图105的整个拓扑可以被密集编码和快速遍历。
66.数组190和195都被示为具有顶点位置和正向边位置列或向量。所有那些列/向量都包含图元素的规范偏移量，对于给定的列或向量，这些偏移量是针对单一图元素类型的。在正向源数组190中，顶点位置列包含顶点类型141的规范偏移量，而正向边位置向量包含边类型151的规范偏移量。
67.在正向目的地数组195中，正向边位置列包含用于边类型151的规范偏移量，并且顶点位置向量包含用于顶点类型141的规范偏移量。同一csr 110中的相应数组190和195的正向边位置向量和列应当用于相同的边类型。取决于边类型151的源顶点类型与目标顶点类型是否相同，同一csr 110中的相应数组190和195的顶点位置列和向量可以针对或不针对相同的顶点类型。
68.虽然数组190和195被示为正向csr 110的内容，但在一些实施例中，那些数组在逻辑上也可以是图元素数组的垂直切片。例如，在实施例中，正向源数组190可以是顶点类型141的顶点数组的列的子集。在任何情况下，正向源数组190和顶点类型141的顶点数组都具
有相同数量和排序的顶点。
69.即使边类型151-152都具有相同的源顶点类型141，边类型151-152也具有带有单独正向边位置向量的单独csr。在实施例中，那些单独的正向边位置向量也可以是用于顶点类型141的同一顶点数组中的单独的列。
70.在实施例中，正向目的地数组195可以是用于边类型151的边数组的列的子集，在这种情况下，正向目的地数组195与用于边类型151的边数组具有相同的边排序。在另一个实施例中，正向目的地数组195与用于边类型151的边数组可以具有不同的边排序，只要在那些排序之间存在映射即可，如本文稍后解释的。在任何情况下，正向目的地数组195与用于边类型151的边数组具有相同数量的边。
71.1.2示例反向csr
72.csr 110和115是促进单向边类型151的边的双向遍历的一对。边方向上的边遍历使用正向csr 110。反向边方向的边遍历使用反向csr 115。因此，任一方向上的边遍历可以发生在或多或少相似的时间和空间中。
73.虽然csr 110和115用于相反方向的遍历，但这与连接相同的两种顶点类型但方向相反的两种不同的边类型不同。例如，对于边类型152，可以有一对csr，它起源于顶点类型141，终止于顶点类型142。代替地，起源于顶点类型142并终止于顶点类型141的另一种边类型将具有一对单独的csr。即使两种边类型具有相同的源顶点类型和目标顶点类型，那两种边类型也会有一对单独的csr。
74.csr 110和115是冗余对，因为两个csr都以替代方式对图105的相同拓扑部分进行编码，在图105的相同遍历期间可以使用其中一种或两种方式。例如，查询单向街道的城市中的路线可能需要分别从起点和目的地进行两次并发搜索，并且当两次搜索都到达任何相同的中间顶点时成功。在实施例中，csr 110和115都用于将有向图105视为无向图。仅需要使用反向csr 115的示例是pagerank算法，该算法可以通过向后遍历超链接到引用网页以发现包围所测量网页的传递闭包来测量网页的重要性。
75.反向csr 115包含反向数组117和119，虽然被示为表格，但它们是相应单个列的整数向量，其实际存储的内容被示为粗体。反向csr 115中未示为粗体的列是隐含的列，其可以是说明性的，但实际上并未被存储。
76.图105的顶点和边被拓扑编码为反向csr，诸如用于边类型151的115，如下所示。每种边类型都有其自己的反向csr，该反向csr具有其自己的反向目的地数组，诸如117。反向目的地数组117的每一行表示顶点类型141的不同顶点，它是边类型151的目标顶点类型。反向源数组119的每一行表示边类型151的不同边。
77.每种边类型都有其自己的csr对，诸如用于边类型151的csr110和115。虽然多个边类型151-152共享相同的目标顶点类型141，但边类型151-152的相应反向csr具有其相应的反向源数组。
78.反向目的地数组117包含反向边位置向量，该反向边位置向量包含反向源数组119的行的偏移量。反向目的地数组117的反向边位置向量中的值单调增加以指示表示边类型151的边的反向源数组119的行的子序列的起始位置，这些边终止于反向目的地数组117的给定行的顶点。例如，在反向目的地数组117中，顶点a终止边类型151的边，这些边被表示为在反向源数组119的第0行开始的连续相应行。反向目的地数组117的反向边位置向量中的
每个值可以通过将终止于反向目的地数组117的前一行的前一个顶点的边类型151的边的计数与前一个值相加来计算。
79.例如，顶点a终止边类型151的两条边u和x，它们由反向源数组119的第0-1行表示。因此，零+二＝二是用于顶点b的反向目的地数组117的反向边位置向量中的值。同样，顶点b终止两条边v和z，因此二+二＝四是用于顶点c的反向目的地数组117的反向边位置向量中的值。在实施例中，反向目的地数组117的反向边位置向量中的最后一个条目包含边类型151的边的计数，它也是反向源数组119中的行的计数。
80.反向源数组119的每个边行在顶点位置向量中指示源顶点类型141的顶点数组中的行的偏移量，在这种情况下，反向源数组119可以是或包括反向目的地数组117，如下面所解释的。例如，反向源数组119的顶点位置向量指示边z起源于反向目的地数组117的第2行中的顶点，即，顶点c。
81.通过仅使用反向目的地数组117的反向边位置向量，计算机100可以通过减去相邻值来检测顶点b终止边类型151的两条边，诸如从用于顶点b的值中减去用于顶点a的值，产生2-0＝二。通过在使用反向目的地数组117之后使用反向源数组119，计算机100还可以检测这两条边起源于顶点a和c。对于每种边类型使用单独的反向csr，可以对图105的整个拓扑进行密集编码和快速向后遍历。
82.反向数组117和119都被示为具有顶点位置和反向边位置列或向量。所有那些列/向量都包含图元素的规范偏移量，对于给定的列或向量，这些偏移量是针对单个图元素类型的。在反向目的地数组117中，顶点位置列包含用于顶点类型141的规范偏移量，并且反向边位置向量包含用于边类型151的规范偏移量。
83.在反向源数组119中，反向边位置列包含用于边类型151的规范偏移量，并且顶点位置向量包含用于顶点类型141的规范偏移量。同一反向csr 115中的相应反向数组117和119的反向边位置向量和列应当用于相同的边类型。取决于边类型151的源顶点类型与目标顶点类型是否相同，同一反向csr 115中的相应反向数组117和119的顶点位置列和向量可以针对或不针对相同的顶点类型。
84.虽然反向数组117和119被示为反向csr 115的内容，但是在一些实施例中，那些反向数组在逻辑上也可以是图元素数组的垂直切片。例如，在实施例中，反向目的地数组117可以是顶点类型141的顶点数组的列的子集。在任何情况下，反向目的地数组117和用于顶点类型141的顶点数组都具有相同数量和排序的顶点。
85.两种边类型具有单独的csr，单独的csr具有单独的反向目的地数组和单独的反向边位置向量，即使两种边类型具有相同的目标顶点类型。在实施例中，那些单独的反向边位置向量也可以是用于目标顶点类型的同一顶点数组中的单独列。
86.反向源数组119的正向边位置向量为每个边存储正向目的地数组195和/或用于边类型151的边数组内的边的偏移量。在实施例中，反向源数组119与用于边类型151的边数组可以具有不同排序的边，只要那些排序之间存在映射即可。例如，反向源数组119的正向和反向边位置列可以作为双向查找表操作以翻译边位置。在任何情况下，反向源数组119与用于边类型151的边数组具有相同数量的边。
87.本文呈现了用于并行填充相同反向csr和/或相同csr对的条目以在共享存储器中加速的技术，诸如通过对称多处理(smp)，诸如用多核处理器。例如，图105可以是巨大的，诸
如具有数十亿个顶点、数万亿条边和/或数万或数十万个顶点的直径。例如，时间可行性可以取决于根据本文的同步和协调技术水平缩放的相同反向csr的填充。
88.在实施例中，诸如csr和顶点表之类的存储器结构是可选的。以下数据定义语言(ddl)语句可以将my_graph 105指定为有资格加载到存储器中，其中所有者是用户或模式。
89.alter property graph[owner.]my_graph inmemory
[0090]
类似的ddl语句可以将图105指定为不再适合存储器加载。在实施例中并且如本文稍后讨论的，计算机100以相同的方式向客户端暴露图105，而不管图105是否驻留在存储器中。例如，如果图105不驻留在存储器中，那么计算机100可以将诸如结构化查询语言(sql)之类的数据操纵语言(dml)语句应用到包含关系模式160的数据库及其表，以根据需要即时执行过滤、连接和投影，以检索表示图105或特定图数据元素或特定图数据元素类型的所有实例的结果集。
[0091]
而且如本文后面所述，将图105的一些或全部加载到存储器中可以异步发生在后台进程中，使得：a)客户端请求或多或少地被完全委托给由计算机100或不同的计算机托管的数据库管理系统(dbms)进行查询处理，b)但相同请求的重复在相同的图形分析会话期间仅应用于存储器中的图105。各种实施例可以将计算机100的图处理功能性中的一些或全部结合到dbms本身中。例如，计算机100上的dbms可以既作为关系数据库引擎又作为图数据库引擎操作。
[0092]
同样如本文稍后所述，图105可以以与客户端请求同步或异步(诸如在后台中)的分段方式加载到存储器和/或从存储器卸载。例如，csr和/或顶点表在需求的驱动下并且单独加载到存储器中，并在存储器稀缺的驱动下从存储器中逐出。在本文稍后描述的另一个示例中：a)顶点表和/或边表的水平和/或垂直切片将它们的数据存储到存储器块中；b)每个块可以单独加载，或者在实施例中，单独逐出；以及c)多个块可以从(一个或多个)相同或不同的关系表中并行加载。因此，客户端请求的履行可能需要混合访问数据库表和存储器。
[0093]
2.0csr对填充过程
[0094]
图2是描绘计算机100可以执行以填充图105的用于边类型151的一对csr 110和115的示例过程的流程图。参考图1a-1b讨论图2。反向csr 115的并行填充在本文稍后呈现。在相关的美国专利申请16/747,827中介绍了正向csr 110的并行填充。
[0095]
如本文前面所呈现的，步骤202获得将关系模式160绑定到图数据模型130的映射120。例如，映射120可以包括其键是关系表名称并且其值是顶点类型名称的查找表。映射120可以为每个边类型指定源和目标顶点类型。映射120可以手动组成或自动导出，诸如通过分析图数据模型130和关系模式160。
[0096]
可以为图数据模型130的每个边类型151-152生成单独的csr对。步骤204和206为一种边类型填充csr对并且可以针对相同图数据模型130的附加边类型重复。
[0097]
基于映射120，步骤204填充正向csr 110，如本文其它地方和/或相关美国专利申请16/747,827中所述。在步骤204之后，正向csr 110准备好使用。
[0098]
基于正向csr表示110，步骤206填充反向csr表示115，如本文别处所述。步骤206的并行化将在后面呈现。在步骤206之后，反向csr 115准备好使用。
[0099]
咨询正向csr 110通过重用在步骤204期间已经完成的工作来加速步骤206。咨询csr表示110通过避免诸如计算、分组或分类(sort)顶点和/或边之类的冗余工作和/或输
入/输出(i/o)(诸如访问持久存储装置)来加速步骤206。用于填充csr的其它技术不咨询另一个csr。
[0100]
3.0示例性能改进
[0101]
图3描绘了可能发生以填充反向csr 115的示例活动。参考图1a-1b和2讨论图3。在个实施例中，在图3的一些活动发生之前填充正向csr 110。在实施例中，正向csr 110的填充是流水线式的或在某种程度上与图3的一些活动并发发生。
[0102]
实施例可以以任何次序执行活动301-309中的一些或全部。活动301-309呈现了不相互排斥的设计选择，并且可以是或可以不是可选的。大多数活动301-309可以组合。
[0103]
活动301高效地填充反向csr 115。活动302-303禁止一些高时延活动。换句话说，活动302-303指定在填充反向csr 115时不发生的操作。
[0104]
活动302填充反向csr 115，而不执行输入/输出(i/o)。换句话说，活动302具有在诸如易失性ram之类的随机存取存储器(ram)中已经可用的所有需要的数据。例如，正向csr 110可以已经驻留在存储器中并且可以被活动302查询。
[0105]
活动303填充反向csr 115，而不访问为边类型151提供顶点和边的关系表。例如，活动303不需要访问任何关系表，也不需要访问数据库中持久化的任何内容，除非边类型用作叶边，如本文后面所解释的。特别地，活动303不访问以下任何一个：源顶点表171、目标顶点表(在这个示例中也是171)，也不访问边表181。例如，活动303可以代替地访问存储器中的正向csr 110中的所需数据。
[0106]
活动304使用并行化来加速反向csr 115的填充，诸如通过用多个计算线程、cpu和/或cpu核进行水平缩放。例如，(一个或多个)反向数组117和/或119中的一些(一个或多个)行的填充可以指派给不同的线程。本文稍后将讨论诸如数据分区、线程池、积压和线程安全之类的工作分配技术。
[0107]
活动305并发地处理至少两条边。例如，源自或终止于同一顶点的两条边可以由相应的线程处理。例如，反向源数组119中的每一行可以由相应的线程填充。
[0108]
活动306执行递增用于目标顶点的计数器的原子操作。例如并且如本文稍后讨论的，顶点类型141的每个目标顶点a-c可以具有其自己的相应计数器，计数器由指令集体系架构(isa)的原子指令访问。例如，提取并添加(fetch-and-add)可以原子地读取和递增计数器。如本文稍后讨论的，争用会造成同时的原子指令被串行执行。
[0109]
活动307对终止于目标顶点类型141的每个顶点处的边类型151的边进行计数。例如，反向csr 115中的反向边位置向量可以基于这种边计数来填充。同样，反向源数组119中用于边的行可以基于这种边计数被指派给目标顶点。
[0110]
csr 110和115的填充可以在一定程度上在时间上重叠，尤其是当正向csr 110的填充需要和/或计算填充反向csr 115也需要的值时。例如，同步逻辑或异步流水线并行化可以使得csr 110和115的填充：a)在某种程度上并发地发生，b)复制和/或重用计算出的值，和/或c)咨询先前填充的数据分区，诸如本文稍后呈现的块。
[0111]
当为边类型151的每条边填充正向目的地数组195时，活动308为终止该边的目标顶点递增相应的计数器。例如，因为目标顶点b终止了两条边v和z，所以用于目标顶点b的计数器应当递增一两次。此类边计数器和线程安全将在后面讨论。
[0112]
正向目的地数组195可以提供边类型151的任何或所有边。活动308可以具有或促
进避免诸如在正向目的地数组195内的边的线性处理(即，迭代)的并行化。活动309是单线程的实施例，它通过线性迭代正向目的地数组195或用于边类型151的其它边数组来计数每个目标顶点的边。活动308-309可以有些互斥。但是，如本文稍后呈现的，数据分块可以促进并发地对不同块中的边进行计数但顺序地处理同一块内的边的多线程。
[0113]
4.0反向目的地数组的并行填充
[0114]
图4是描绘实施例中的示例计算机400和示例图410的框图。计算机400使用并行化来加速逻辑图410的冗余压缩稀疏行(csr)编码对的填充。计算机400可以是计算机100的实施方式。
[0115]
图5描绘了促进并行填充反向目的地数组430的数据和/或元数据的示例活动。实施例可以实现可以以任何次序发生的活动501-507中的一些或全部。活动501-507中的一些可以组合成一个活动。如下，图4-5展示了计算机400的示例配置和操作。
[0116]
示例图410具有图数据模型，其仅具有分别示为实线或虚线箭头的一种顶点类型和两种边类型。实边类型可以如下编码成csr对，其不包括具有不同边类型并且属于不同csr对的边r。正向目的地数组420和正向源数组如本文前面所述被编码。
[0117]
具有共享存储器和多个异步计算线程、cpu和/或cpu核的单程序多数据(spmd)提供了水平扩展，其加速csr对的数组中的一些或全部的填充，如下所示。在实施例中，csr对的任何数组都可以在逻辑上和/或物理上划分为多个块，每个块具有数组的多个相邻行。例如，正向目的地数组420包含每个具有三个边的块a1-2。
[0118]
为了加速处理任何数组，每个线程可以同时处理数组的相应块。如果块多于线程，那么有序或无序积压可以包含未处理的块。当线程完成一个块时，该线程可以从积压中获取并处理另一个块，直到积压为空。
[0119]
两个并发线程可以分别处理块a1-a2，这可以包括填充和/或随后读取块a1-a2。为方便起见，那些线程在本文中根据它们相应的块是已知的。因此，块a1-a2分别由线程a1-a2处理，线程a1-a2如下并发地填充反向目的地数组430并被示为活动501。
[0120]
线程a1-a2可以在各个阶段操作并且与处理流水线的其它并行或串行阶段的其它线程共享数据。目标是填充反向目的地数组430的反向边位置向量。为了实现这一点，反向目的地数组430的反向边位置向量可以在不同时间临时存储各种中间值，诸如所示的旧值和新值。
[0121]
在第一阶段，线程a1-a2并发地计算和调整存储在反向目的地数组430的反向边位置向量中的旧值。虽然线程a1-a2一起是并发的，但每个线程串行处理线程自己的块的每条边。即，每个线程一次处理一条边，诸如在时间t1-t4中的每一个期间。
[0122]
因为反向目的地数组430的反向边位置向量具有用于每个顶点e-j的元素，因此每个元素都有旧值。最初在t1之前，所有旧值都为零。
[0123]
时间t1-t4是逻辑和相对时间，虽然单调增加，但不需要等间距。例如，t1-t2可以相隔几毫秒，而t2-t3可以相隔几纳秒。
[0124]
在时间t1，线程a1-a2通过以下方式处理它们相应块的第一条边：a)在填充或读取正向目的地数组420的同时，检测哪个是第一条边的目标顶点，以及b)将那个目标顶点的旧值递增一。例如，块a2的第一条边的目标顶点是顶点h，其顶点位置为三。因此，如在时间t1对于顶点h所示，1a2是指线程a2存储一，即，初始零递增一。线程a1在时间t1针对其第一条
边n并发地类似表现，示为1a1。
[0125]
旧值是反向目的地数组430的反向边位置向量的说明性别名。因此，在时间t1-t4的旧值中所示的值实际上在那些时间存储到反向目的地数组430的反向边位置向量中.
[0126]
在时间t2，线程a1-a2处理它们相应的第二条边o和s，它们都在相同的目标顶点f处终止。因此，线程a1-a2同时尝试增加顶点f的旧值，这是需要可能会破坏顶点f的旧值的竞争的操作冲突。一些实施例不支持冗余边，诸如具有相同源顶点和相同目标顶点的o和s。
[0127]
在线程安全实施例中，旧值受cpu指令集体系架构(isa)的原子指令保护。诸如提取并添加之类的原子指令可以原子地：读取数值变量的值，并递增该数值变量。线程a1-a2使用原子指令来递增旧值。在实施例中，比较并交换是代替提取并添加使用的原子指令。
[0128]
当多个线程同时发出针对相同变量(诸如数组元素或存储器地址)的原子指令时，原子指令的执行被串行化，诸如沿着时间t2-3，如图所示。例如，如图所示，线程a2在时间t2递增顶点f的旧值，并且线程a1在时间t3递增顶点f的旧值。这种串行化安全地解决了冲突。
[0129]
在其它实施例中，其它软件同步机构实现线程安全，诸如互斥(mutex)、信号量、锁或临界区。在任何情况下，冲突只能发生在数组的同一元素上。同时访问同一数组的不同元素本质上是线程安全的。例如，每个元素可以具有自己独立的锁。
[0130]
由于原子串行化或其它因素，线程a2提前并在时间t3完成其最后一条边，如图所示。而线程a1滞后并在时间t4完成，如图所示。只要所有参与的线程都完成，这个填充阶段就会持续下去，这可以用诸如信号量或屏障之类的软件同步机构来检测。
[0131]
在实施例中，反向目的地数组430包含块b1-b3，每个块包含两个目标顶点。在下一个填充阶段，线程b1-b3可以处理相应的块b1-b3。在实施例中，线程a1-a2和b1-b3是重叠的线程集合。例如，线程a1和b3可以是被重新调整用途的同一线程。例如，线程可以在完成处理后返回到空闲线程的池并等待重新调整用途。
[0132]
基于最终的旧值，线程b1-b3中的每一个在线程的相应块的目标顶点上进行迭代，以计算块中的边的运行总数，对于每个目标顶点，其被存储到新值的相应元素中。如图所示，每个块的第一个目标顶点的新值被设置为零。块中每个后续目标顶点的新值是块中前一个元素的新值加上前一个元素的最终旧值之和。
[0133]
例如对于块b1的第二个目标顶点f，前一个目标顶点e的新值为零，并且前一个目标顶点e的最终旧值为一。因此，线程b1将用于目标顶点f的新值计算为0+1＝一，如图所示，并将其存储。新值是反向目的地数组430的反向边位置向量的说明性别名。因此，新值中所示的值实际上存储到反向目标数组430的反向边位置向量中，从而覆写先前存储的旧值，示为活动503。
[0134]
每个块b1-b3可以包含或以其它方式与其自己的元数据字段相关联，诸如所示的最后一个值和块偏移量。每个块可以具有由相应线程计算和存储的元数据。如上面所解释的，旧值是针对每个目标顶点的边的计数，并且新值是块内那些计数的运行总和。
[0135]
用于目标顶点的新值不包括目标顶点的旧值边计数，而仅包括块中先前目标顶点的旧值边计数。因此，块中最后一个目标顶点的旧值边计数被排除在新值之外。虽然排除了新值，但运行总数应当包括被排除的计数以最终确定运行总数，该总数存储在块的最后一个值元数据字段中。
[0136]
如出于演示目的所示，最后一个值有效地，虽然不是可操作地，也是块中所有目标
顶点的所有最终旧值的总和。例如在时间t3，块b1的旧值最终分别为一和三。因此，最后一个值实际上是1+3＝四，如图所示。用于填充新值和最后一个值的线程安全是固有的，因为每个线程b1-b3只访问自己的块。
[0137]
因此，在多线程处理阶段计算新值和最后一个值。下一个处理阶段是单线程的，但可以与前一个阶段流水线化，如下所示。例如，流水线并行性可能需要相应流水线阶段的活动502-503的并发。
[0138]
单个线程应当按照那些块出现在反向目的地数组430中的次序来处理块b1-b3。因此，单个线程应当首先处理块b1并且最后处理b3。当开始处理块时，单个线程应当等到前一个阶段的线程完成那个块。
[0139]
例如，单个线程不应当在线程b1完成块b1之前开始块处理，即使线程b3已经完成了块b3。当单个线程处理一个块但另一个块仍在前一个阶段中被另一个线程处理时，发生流水线操作。例如，如果前一个阶段在块b3之前完成了块b1，那么单个线程可以处理块b1，而块b3仍在前一个阶段中被线程b3处理。
[0140]
单个线程按升序顺序填充所有块的块偏移量元数据字段，一次一个块。用于块偏移量的算术公式取决于哪个块。如图所示，第一个块b1的块偏移量为零。第二个块b2的块偏移量是第一个块b1的最后一个值元数据字段，如图所示为四。
[0141]
如由活动502计算的，每个后续块的块偏移量是前一个块的最后一个值加上前一个块的块偏移量的总和。例如，对于块b3，前一个块b2的最后一个值如图所示为二，并且前一个块b2的块偏移量如图所示为四。因此，如图所示，块b3的块偏移量为2+4＝六。
[0142]
当单个线程完成时，块元数据填充完成，并且用于反向目的地数组430的最终并行填充阶段如下发生。每个块都在两个并行阶段中进行处理，其中一个阶段已经发生。在实施例中，每个块在两个并行阶段中由同一个线程处理。
[0143]
例如，线程b1-b3再次各自处理其相应的块。在实施例中，将块指派给线程在第二并行阶段中改变，诸如当线程在两个并行阶段之间返回到线程池时。在实施例中，两个并行阶段具有不同数量的线程。
[0144]
活动504如下应用块偏移量。第二并行阶段最终确定反向目的地数组430的反向边位置向量中的值，如下所示并且如图所示。新值是此阶段开始时反向目的地数组430的反向边位置向量的说明性别名。在这个阶段结束时，反向目的地数组430的反向边位置向量具有最终值，如图所示，对于每个块，该值是在活动505期间增加了块的块偏移量的新值。
[0145]
例如，块b2具有四的块偏移量。因此，将四添加到块b2的每个新值。例如，目标顶点h的新值为零。因此，在反向目的地数组430中，用于目标顶点h的反向边位置是0+4＝四，如图所示。
[0146]
用于这个算术阶段的线程安全是固有的，因为每个线程b1-b3只访问其自己的块。如上面所解释的，spmd并行处理多个块，但对于较早的处理阶段，在块内可以是顺序的。在实施例中，这个算术阶段将spmd与单指令多数据(simd)组合用于数据并行化，以便在活动507期间通过非弹性缩放进一步加速。在这种情况下和在活动506期间，块中的最终值中的一些或全部可以被并发地计算，因为相同的块偏移量被添加到块中的所有新值，这适用于向量硬件。
[0147]
在所有线程完成这个阶段之后，反向目的地数组430的填充完成。包含反向目的地
数组430的反向csr直到反向源数组440被填充采完成，如下所示。
[0148]
5.0反向源数组的并行填充
[0149]
图6描绘了促进并行填充反向源数组440的数据和/或元数据的示例活动。实施例可以实现可以以任何次序发生的活动601-604中的一些或全部。活动601-604中的一些可以组合成一个活动。如下，图4和6展示了计算机400的示例配置和操作。
[0150]
在实施例中，反向源数组440的填充基于如下的目的地数组420和430。如上面所解释的，旧值作为终止于反向目的地数组430中的相应目标顶点的边的共享计数器操作。反向源数组440的并行填充还使用如下共享计数器的向量。
[0151]
如上面所讨论的，正向目的地数组420的块a1-a2在初始并行阶段由线程a1-a2并行处理。在接下来的最终并行阶段，线程a1-a2或相同或不同数量的其它并发线程再次并行处理块a1-2，如下所示。
[0152]
每个线程通过以下方式顺序地处理其块中的边：a)检测正向目的地数组420中边的目标顶点的顶点位置，b)使用那个顶点位置作为反向目的地数组430内那个目标顶点的偏移量，c)在反向目的地数组430的反向边位置向量中检测终止于那个目标顶点的边的子集在反向源数组440中的第一偏移量，以及d)线程安全突变，如下所示。
[0153]
终止于目标顶点的每条边都应当填充到反向源数组440中的单独相邻行中。线程a1-2的并行化可以使得终止于目标顶点的边以任意次序进行处理，这是被容忍的。因为线程a1-a2在活动604期间处理单独的边，所以线程a1-a2不应当共享反向源数组440中的同一行。
[0154]
同样，线程a1-a2不应当在反向源数组440中留下任何空行。因此，需要一些协调来指派反向源数组440的行以供相应线程a1-a2填充。
[0155]
在实施例中，反向目的地数组430的每一行与相应的计数器相关联，该计数器表明有多少在相应目标顶点处终止的边已经填充到反向源数组440的相邻行中。每个计数器最初为零并且当终止于相应目标顶点的边被填充到反向源数组440中时递增一。
[0156]
在实施例中在活动605期间，那些计数器是线程安全的，通过使用原子指令(诸如获取并添加)或以其它方式同步每个计数器，诸如上面所解释的。例如，当线程a1-a2分别处理相应块a1-a2中的边o和s时，对于选择反向源数组440的相应行以供线程a1-a2分别填充，相同的目标顶点f可以是有争议的。通过线程a1-2对目标顶点f使用相同的原子计数器来防止这种争用。
[0157]
基于反向目的地数组430的反向边位置列，线程a1-a2检测到终止于目标顶点f的边在反向源数组440中的反向边位置1处开始。在这个示例中，线程a1已在反向源数组440中的那个位置填充边n并且将目标顶点f的计数器从零递增到一。在这个示例中，线程a1领先于线程a2，在处理边o时将一读取为计数器的值。
[0158]
为了计算边o在反向源数组440内的位置，线程a1将计数器的值加上反向源数组440中的目标顶点f的起始偏移量，并在活动601期间将计数器递增一。因此，线程a1在反向源数组440内的反向边位置1+1＝二处填充边o，如图所示。因此，边o和最终的边s被安全且原子地添加到反向源数组440的单独行。在活动602和/或603期间填充反向源数组440中的边o可能需要从数组420到数组440复制边o的正向边位置，如图所示。
[0159]
6.0示例性实施例
[0160]
这里是基于诸如oracle之类的现代关系dbms(rdbms)的示例性实施例。这个实施例改进了可以进一步解释这个实施例的先前示例。因此，这个实施例的以下解释被省略以强调改进。被解释为要求的这个实施例的限制不需要是先前示例的要求。
[0161]
顶点和边可以作为表行在rdbms的数据库中持久化。每行可以包含自然标识符，诸如主键。每行可以包含或与密集标识符(诸如单调增加的序列号)相关联。在实施例中，一些标识符是rdbms原生的。稍后将在本文中呈现可以依赖或可以不依赖于原生标识符的一些实施方式变体。以下是rdbms可以提供原生标识符的两种示例方式。
[0162]
一种方式是用于主存储器列式数据库，诸如saphannah、actianvector和vertica。这些主存储器数据库系统通常已经有可以被用于访问数据列中的特定值的一等标识符。此类标识符是顺序的并且从零开始，因此是密集标识符。
[0163]
oracle数据库有使用混合存储的不同方式，如下所示。数据主要存储为盘上的行(即，行为主)，但可以可选地高速缓存在主存储器列式存储库(即，列为主)中。在这种情况下，从零开始的一等顺序标识符不与每一行永久关联。代替地，每一行都与相应的盘地址永久关联，其值可以是不连续的，因此是稀疏标识符。例如，oracle有rowid。
[0164]
正向csr结构可用于为创建反向csr提供数据。在实施例中，正向csr由两个数组组成。在实施例中，csr结构在rdbms的上下文中需要更多数据，如下所示。
[0165]
假设正向csr的源和目的地数组是分段的，这在存储器管理方面可以更好地控制rdbms。分段数组被拆分成可以用作并行化的单位的块。
[0166]
当边类型对于源和目标顶点类型具有相同的顶点类型时，正向源数组包含到正向目的地数组中的偏移量(dstoff)，并且正向目的地数组包含到正向源数组中的偏移量(srcoff)。由于正向源数组中的位置，即，srcoff，从0开始并且是顺序的，因此它们等于顶点表中对应的denseid。下面的变体1可以适用于其中denseid不可用的rdbms。
[0167]
正向源数组中的元素i指向正向目的地数组中用于源顶点i的外邻列表开始处的索引，并且正向源数组中的元素i+1指向正向目的地数组中的索引，在该索引之后，用于正向源顶点i的外邻列表结束。
[0168]
除了来自正向源数组的索引外，正向目的地数组还存储边表的行的denseid，称为edgeid值。
[0169]
这个示例性实施例中的数组中的一些(诸如正向csr中的目的地数组)包含共享相同索引的元素对。这可以通过使用复合数据类型来实现。
[0170]
在这个示例性实施例中，反向csr数据结构如下填充。反向csr数据结构或多或少与正向csr数据结构完全相同，只是源数组与目的地数组的作用相反，因为反向csr使得有可能快速找到内邻而不是外邻：
[0171]
反向目的地数组中的元素i指向反向源数组中目标顶点i的内邻列表开始处的索引，并且反向目的地数组中的元素i+1指向反向源数组中的索引，在该索引之后，用于目的地顶点i的内邻列表结束。
[0172]
除了来自反向目的地数组的索引外，反向源数组还存储边表的行的denseid，称为edgeid值。
[0173]
在这个示例性实施例中，如果已经可用，那么反向csr直接从正向csr构建。构建反向csr在以下步骤1-3中完成。
[0174]
步骤1分配已满和/或具有最终尺寸但未填充的反向目的地和反向源数组。当边在两端具有相同的顶点类型时，反向目的地数组的元素与来自正向csr的源数组一样多(顶点表中的行数)。这意味着反向目的地数组的尺寸是已知的并且可以被直接分配。类似地，反向源数组与正向csr中的目的地数组具有一样多的元素(边表中的行数)，这意味着它也可以被立即分配。对于两个反向数组，如果存储器分配器支持，那么单个块的分配可以并行化。
[0175]
步骤2通过将偏移量计算到数组中来填充反向csr，如下所示。步骤2计算存储在反向目的地块中的srcoff值，这些值是反向源数组中的偏移量，在该偏移量处，用于每个目的地顶点的内邻开始。srcoff的值可以从每个顶点的内邻的数量推导出来，因为srcoff i+1与srcoff i之间的差异是顶点i具有的内邻数。可以通过sql操作从持久性关系表中查找内邻的数量，但是，因为填充的存储器内正向csr可用，所以提高了步骤2的效率。之后，需要计算内邻的数量的运行总和以获得srcoff值。在可能的情况下，使用多线程来提高性能是期望的。
[0176]
步骤2通过以下四个子步骤a-d完成。子步骤a是多线程的，用于使用正向csr计算每个顶点的传入的边的数量。反向csr的目的地数组中的所有值都初始化为0。然后促生线程，每个线程同时从正向csr的源数组的单个相应块工作。每个线程跟随来自线程的块的每个源顶点的每个传出的边，并递增反向csr的目的地数组中与每个传出的边的目的地对应的元素。由于多个线程可以同时递增相同的值，因此使用由硬件提供的原子指令来执行递增。例如，目的地块2中的第一个元素有3个来自源顶点的内邻，这些源顶点分散开来，可能来自不同的块。这意味着这三个增量可以来自多个线程并且原子操作对于避免丢失更新是必要的。
[0177]
子步骤b是多线程的，用于根据传入的边的数量计算每块运行总和。在这个子步骤中，每个线程一次在反向csr的目的地数组中的单个块上工作。计算本地的、从零开始的每块运行总和。例如，目的地块1的前三个元素分别具有3、2和1个内邻。在子步骤b之后，目的地块1的前四个元素将是0、3(＝0+3)、5(＝3+2)和6(＝5+1)。最后一个计算出的值(即，本文前面呈现的最后一个值)2398不是块的一部分：它是块中的内邻的总数并且需要是步骤2结束时的下一个块的第一个值(即，本文前面呈现的第一个新值)。此时，该值被存储在块的元数据的字段中，该字段在下面称为lastval并且本文前面称为最后一个值。
[0178]
子步骤c是单线程的，用于计算块偏移量，如下所示。chunkoff值也存储在块的元数据中并且表示块开始的偏移量，其可以被计算为lastval值的从零开始的、块级运行总和，具有以下条件。目的地块1的chunkoff值等于目的地块0的lastval，并且i》1的目的地块i的chunkoff值等于目的地块i-1的chunkoff和lastval之和。在计算出chunkoff值之后，可以丢弃lastval值。目的地块2的chunkoff值被设置为目的地块1的lastval：2398，并且目的地块3的chunkoff value被设置为目的地块2的chunkoff和lastval之和：3682(2398+1284)。注意的是，子步骤c不需要在子步骤b完全结束之后开始：有可能针对前一个目的地块(0到i-1)的子步骤b一完成就开始计算用于目的地块i的块级运行总和。
[0179]
子步骤d是多线程的，用于计算最终的srcoff值。最终的srcoff值可以用多个线程在每块基础上计算：每个线程只需将chunkoff值添加到块中的每个元素。这个操作可以是硬件向量化的，诸如用simd。在该子步骤结束时，可以丢弃chunkoff值。来自目的地块1的元
素不变，因为第一个块没有偏移量，但是2398被添加到来自目的地块2的所有元素，因为它是用于那个块的chunkoff值。
[0180]
在步骤2的这四个子步骤a-d之后，反向目的地块包含它们的最终值。步骤3具有子步骤a-b。为了确保良好的性能，反向源块由多个线程填充，其中一些线程可能为同一源顶点添加不同的edgerid(例如，到反向源数组中的边偏移量)和dstoff值。为了处置冲突，应当跟踪在这个步骤期间已经为每个元素插入了多少edgerid/dstoff值。为此，分配了名为cur_pos的新分段数组并在构建反向csr的步骤3a期间初始填充为零。来自cur_pos的值通过使用来自硬件的原子指令自动递增。
[0181]
步骤3b完成反向csr填充，包括用传入的边和内邻的edgerid和dstoff值填充反向源块。这个子步骤再次充分利用正向csr。线程被促生(spawn)或重新调整用途，每个线程都在来自正向csr的源数组的块上工作。每个线程从它当前正在处理的块的每个源顶点跟随每个传出的边，并且每次，线程都将新的(edgeid，dstoff)对添加到传出的边引导它到的目的地顶点的内邻。(edgeid，dstoff)对应当被插入到反向csr的源数组中的位置被计算为传出的边遍历导致的目的地顶点的srcoff和考虑先前插入到内邻列表的cur_pos的值的总和。edgerid值从正向csr的目的地数组中复制，并且dstoff值与源顶点在正向csr的源数组中的位置对应。当为操作读取cur_pos时，它也被递增。使用原子增量是必要的，以避免来自其它线程的冲突，这些线程可能尝试为反向csr中的相同目的地顶点写入edgerid/dstoff值。在填充完所有edgerid/dstoff值之后，cur_pos数组不再有用并且因此可以被释放。
[0182]
在完成上述三个步骤1-3后，反向csr已完全填充。由于这完全用多个线程在存储器中完成，因此构建反向csr的开销比通过sql查询构建正向csr的开销低得多，如本文稍后讨论的那样。
[0183]
上述算法可以用任何数量的促生线程，包括仅单个线程，在这种情况下它是顺序的。但是，注意的是，由于每个线程一次总是在一个块上工作，因此使用的线程多于目的地数组中的块将导致一些线程处于空闲状态。因此，应当使用介于1和目的地数组中的块数之间的线程数。选择要使用的确切线程数是个逻辑问题，它取决于硬件、机器使用以及有关各种权衡的决策。
[0184]
以下是填充正向相对于反向csr数据结构的比较。从源和目的地关系表高效地构建正向csr的步骤如下i-iii，特别是在相关的美国专利申请16/747,827中所呈现的。
[0185]
与反向csr填充一样，在步骤1中，需要分配源和目的地数组。为这些数组分配的存储器的量在依赖于先前存在的正向csr的反向csr填充中是已知的，但这种方法不能用于填充正向csr。正向源和目的地数组中的元素数分别等于源顶点和边关系表中的行数。只要rdbms不高速缓存表尺寸并且源和目标顶点具有相同的顶点类型，就需要运行以下两个sql查询来检索这些行数：
[0186]
select count(*)from vertex；select count(*)from edge；
[0187]
之后，可以进行存储器分配。块分配可以并行完成，类似于正向csr。
[0188]
在步骤ii中，必须计算源数组中的dstoff值。提醒一下，在上述反向csr填充的步骤2中，在目的地数组中填充srcoff值涉及使用正向csr查找每个目的地顶点的内邻的数量。此处不能使用这种方法来查找每个源顶点的外邻的数量。代替地，可以使用以下查询找到每个源顶点的外邻的数量：
[0189]
select src，count(*)from edge where edge.rowid group by src order by src；
[0190]
可以将对来自边表的行的范围的过滤器添加到查询中，以在多个过程之间拆分工作。在这个操作之后，可以并行计算出度的运行总和，类似于在反向csr填充中对入度所做的操作。
[0191]
在步骤iii中，需要找到每个源顶点的外邻来填充目的地数组。在反向csr填充的步骤2中，通过充分利用正向csr找到每个目的地顶点的内邻，但同样不能在此处使用这种方法。代替地，需要运行双join查询来找出外邻：
[0192]
select src.rowid，dst.rowid，edge.rowid from vertex src，vertex dst，edge etab where src.key＝etab.src and dst.key＝etab.dst where etab.rowid；
[0193]
再次，可以将对行的范围的过滤器添加到查询中，以便多个过程可以运行其一部分。在填充目的地数组时的并发处置可以与填充源数组时对反向csr所做的类似，即，使用cur_pos分段数组和原子指令。
[0194]
填充正向csr的步骤ii-iii使用orderby和双join，这是昂贵的操作。以下是重要的变体1-2，它们适用于不同的rdbms行标识方案和/或关于图拓扑的不同约束。
[0195]
变体1用于rdbms未提供denseid标识符时。上面描述的反向csr填充算法预期rdbms为每个表提供从0开始的顺序标识符，即，denseid。变体1处置数据库仅提供非连续并且可以从任何值开始的标识符的情况。那个标识符是sparseid。
[0196]
虽然即使denseid标识符不可用也可以如上所述构建正向和反向csr，但它们的用处将受到限制，因为不可能识别顶点表中与正向csr的源数组或反向csr的目的地数组中的位置对应的行。这意味着不可能访问顶点特性。为了解决这个问题，在变体1中，正向csr的源数组存储srcid，即，每个源顶点的sparseid，并且反向csr的目的地数组存储dstid，即，每个目的地顶点的sparseid。denseid没有这样做的原因是它们等于数组中的索引并且因此可以被推断出来。虽然这个变体中的edgeid存储sparseid而不是denseid，但它们可以以与上面相同的方式用于访问边特性。
[0197]
上述反向csr填充需要调整以与变体1一起使用。在上述步骤i中，反向csr的目的地数组的尺寸将更大，因为该数组还需要容纳dstid。在步骤ii中，反向csr的目的数组中的dstid可以直接从正向csr的源数组中的srcid中复制，次序相同，只要图是同构的即可，这意味着图只有一种顶点类型和一种边类型。换句话说，在同构图中，一种边类型对于源顶点和目标顶点具有相同的顶点类型。
[0198]
变体2用于当边类型可以具有不同的源和目标顶点类型时。上面描述的反向csr填充假设图是同质的，即，它包含单个顶点表和单个边表。rdbms还可以支持异构图，即，具有多个顶点表和/或多个边表的图。在异构图中，边表中的源和目的地列可以指向两个不同的顶点表。异构图有多个好处，特别是在性能方面。异构图支持对正向csr的影响，如下所示。
[0199]
用于不同边类型的csr可以菊花链式连接，如下所示。正向csr的目的地数组中的srcoff可能无法识别正向csr的源数组中的元素，代替地，它们可以识别另一个正向csr的源数组中的元素。类似地，反向csr的源数组中的dstoff可以识别来自反向csr的目的地数组的元素，代替地，它们可以识别来自另一个反向csr的目的地数组的元素。以这种方式，csr对可以用作遍历多种边类型的路径的操作链。
[0200]
图查询可以遍历各种类型的边和顶点以找到解。一些类型的边和顶点可以仅与中间值相关，而与查询的最终目的地顶点无关。图遍历中的最后一条边可以具有某种特殊的csr编码，并且那些边在本文中称为叶子。因此，可以存在用于(一个或多个)特定查询或(一个或多个)模式的菊花链式csr。例如，遍历相同边类型的不同查询可以共享也可以不共享那种边类型的相同csr对。因此，边类型可以有用于不同上下文用途的多个csr对。
[0201]
对中的一个csr是否为叶子取决于：a)csr对的边类型是遍历中的最后一个边类型，以及b)遍历的方向。在此，最后一个边类型基于遍历的方向，该方向可以与边类型的边的方向相同或者可以不同。对于正向遍历，最后一个边类型的正向csr的目的地数组对最后一条边进行编码。
[0202]
对于反向遍历，遍历中的最后一个边类型有点违反直觉，是遍历找到的路径中的第一个边类型。对于反向遍历，找到的路径中第一个边类型的反向csr的源数组对最后遍历的边进行编码以找到那些路径，因为路径是向后遍历的。
[0203]
如下对于正向遍历，叶子边的正向csr的目的地数组具有特殊的编码。同样对于反向遍历，叶子边的反向csr的源数组具有如下特殊编码。
[0204]
如果正向csr用于叶子边，那么其srcoff将替换为目的地表内行的标识符(对于标准算法是denseid，对于变体1是sparseid)。类似地，如果反向csr是叶子，那么它的dstoff将被源表内的行的标识符代替(对于标准算法是denseid，对于变体1是sparseid)。
[0205]
变体2处置反向csr填充的异构情况。以下是对上述算法的修改。步骤1需要被修改，因为反向csr的目的地数组的尺寸可以不等于对应的正向csr的源数组的尺寸。代替地，以下修改可以是必要的。
[0206]
如果正向csr不是叶子，那么反向csr的目的地数组具有与源数组一样多的元素，使得正向csr的目的地数组中的srcoff从中识别元素。如果反向csr是变体1中的叶子，那么元素的尺寸可以有所不同，因为dstoff被替换为sparseid，sparseid可以大于偏移量而不是denseid。
[0207]
如果正向csr是叶子，那么它的目的地数组将不会从另一个csr的源数组中识别元素，而是直接从目的地表中识别行：反向csr的目的地数组中srcoff(以及变体1中的dstid)的数量等于那个表中的行数。如果目的地表中的行数没有被高速缓存，那么可以通过sql查询来检索它。
[0208]
关于步骤2，有以下两种情况。用标准实施方式，步骤2不要求任何修改。注意的是，通过正向csr导致目的地偏移量在步骤1中创建的反向csr的源数组的范围内。
[0209]
如果变体2与变体1组合，那么在步骤2中，反向csr的目的地数组中的dstid是源数组中对应正向csr的目的地数组中的srcoff从中识别元素的srcid的副本。
[0210]
变体2中的步骤3保持不变。变体2适合oracle数据库。在实施例中，denseid在主存储器列式存储库中实现(例如，作为易失性标识符)并且不支持为未加载到存储器中的表创建正向和反向csr。
[0211]
7.0数据库概述
[0212]
本发明的实施例在数据库管理系统(dbms)的上下文中使用。因此，提供了示例dbms的描述。
[0213]
一般而言，诸如数据库服务器之类的服务器是集成的软件组件和诸如存储器、节
点以及节点上用于执行集成的软件组件的进程之类的计算资源的分配的组合，其中软件和计算资源的组合专用于代表服务器的客户端提供特定类型的功能。数据库服务器控制并促进对特定数据库的访问，处理客户端访问数据库的请求。
[0214]
用户通过向数据库服务器提交使数据库服务器对存储在数据库中的数据执行操作的命令来与dbms的数据库服务器进行交互。用户可以是在与数据库服务器交互的客户端计算机上运行的一个或多个应用。多个用户在本文中也可以被统称为用户。
[0215]
数据库包括数据和数据库字典，其存储在诸如硬盘集之类的持久性存储器机构上。数据库由其自己的分开数据库字典定义。数据库字典包括定义数据库中包含的数据库对象的元数据。实际上，数据库字典定义了数据库的许多。数据库对象包括表、表列和表空间。表空间是用于存储各种类型的数据库对象(诸如表)的数据的一个或多个文件的集合。如果将用于数据库对象的数据存储在表空间中，那么数据库字典将数据库对象映射到保存用于数据库对象的数据的一个或多个表空间。
[0216]
dbms参考数据库字典来确定如何执行提交给dbms的数据库命令。数据库命令可以访问由字典定义的数据库对象。
[0217]
数据库命令可以是数据库语句的形式。为了使数据库服务器处理数据库语句，数据库语句必须符合数据库服务器支持的数据库语言。许多数据库服务器支持的数据库语言的一个非限制性示例是sql，包括由诸如oracle之类的数据库服务器支持的sql专有形式(诸如oracle database 11g)。将sql数据定义语言(“ddl”)指令发布到数据库服务器以创建或配置数据库对象，诸如表、视图或复杂类型。数据操纵语言(“dml”)指令被发布给dbms，以管理存储在数据库结构内的数据。例如，select、insert、update和delete是一些sql实施方式中常见的dml指令示例。sql/xml是在对象-关系数据库中操纵xml数据时使用的sql的常见扩展。
[0218]
多节点数据库管理系统由相互连接的节点组成，这些节点共享对同一数据库的访问。通常，节点经由网络互连并且在不同程度上共享对共享存储装置的访问，诸如共享对盘驱动器的集合和存储在其上的数据块的访问。多节点数据库系统中的节点可以是经由网络互连的一组计算机(诸如工作站和/或个人计算机)的形式。可替代地，节点可以是网格的节点，该网格由与机架上的其它服务器刀片互连的服务器刀片形式的节点组成。
[0219]
多节点数据库系统中的每个节点都托管数据库服务器。服务器(诸如数据库服务器)是集成软件组件和计算资源(诸如存储器、节点以及节点上的用于在处理器上执行集成软件组件的进程)的分配的组合、专用于代表一个或多个客户端执行特定功能的软件和计算资源的组合。
[0220]
可以分配来自多节点数据库系统中多个节点的资源，以运行特定的数据库服务器的软件。软件和节点中的资源的分配的每种组合都是在本文中被称为“服务器实例”或“实例”的服务器。数据库服务器可以包括多个数据库实例，其中一些或全部在单独的计算机(包括单独的服务器刀片)上运行。
[0221]
7.1查询处理
[0222]
查询是表达式、命令或命令集，在执行时，使服务器对数据集执行一个或多个操作。查询可以指定要从中确定(一个或多个)结果集的(一个或多个)源数据对象，诸如(一个或多个)表、(一个或多个)列、(一个或多个)视图或(一个或多个)快照。例如，(一个或多个)
源数据对象可以出现在结构化查询语言(“sql”)查询的from子句中。sql是用于查询数据库对象的众所周知的示例语言。如本文所使用的，术语“查询”被用于指表示查询的任何形式，包括数据库语句形式的查询和用于内部查询表示的任何数据结构。术语“表”是指被查询引用或定义并且表示行的集合(诸如数据库表、视图或内联查询块(诸如内联视图或子查询))的任何源对象。
[0223]
查询可以在(一个或多个)对象被加载时逐行地对来自源数据对象的数据执行操作，或者在(一个或多个)对象已被加载之后对(一个或多个)整个源数据对象执行操作。由一些操作生成的结果集可以让(一个或多个)其它操作可用，并且以这种方式，可以基于某些标准将结果集过滤掉或缩小范围，和/或与(一个或多个)其它结果集和/或(一个或多个)其它源数据对象联接或组合。
[0224]
子查询是查询的一部分或组件，它不同于查询的(一个或多个)其它部分或(一个或多个)组件，并且可以与查询的(一个或多个)其它部分或(一个或多个)组件分开评估(即，作为单独的查询)。查询的(一个或多个)其它部分或(一个或多个)组件可以形成外查询，其可以包括或者可以不包括其它子查询。嵌套在外查询中的子查询可以被单独评估一次或多次，同时为外查询计算结果。
[0225]
一般而言，查询解析器接收查询语句并生成查询语句的内部查询表示。通常，内部查询表示是互连的数据结构的集合，其表示查询语句的各种组件和结构。
[0226]
内部查询表示可以是节点图的形式，每个互连的数据结构与节点和所表示的查询语句的组件对应。内部表示通常在存储器中生成，以用于评估、操作和变换。
[0227]
硬件概述
[0228]
根据一个实施例，本文描述的技术由一个或多个专用计算设备实现。专用计算设备可以是硬连线的以执行这些技术，或者可以包括数字电子设备(诸如被持久地编程为执行这些技术的一个或多个专用集成电路(asic)或现场可编程门阵列(fpga))，或者可以包括被编程为根据固件、存储器、其它存储装置或组合中的程序指令执行这些技术的一个或多个通用硬件处理器。这种专用计算设备还可以将定制的硬连线逻辑、asic或fpga与定制编程相结合，以实现这些技术。专用计算设备可以是台式计算机系统、便携式计算机系统、手持设备、联网设备或者结合硬连线和/或程序逻辑以实现这些技术的任何其它设备。
[0229]
例如，图7是图示可以在其上实现本发明实施例的计算机系统700的框图。计算机系统700包括总线702或用于传送信息的其它通信机制，以及与总线702耦合以处理信息的硬件处理器704。硬件处理器704可以是例如通用微处理器。
[0230]
计算机系统700还包括耦合到总线702的主存储器706，诸如随机存取存储器(ram)或其它动态存储设备，用于存储将由处理器704执行的信息和指令。主存储器706还可以用于存储在执行由处理器704执行的指令期间的临时变量或其它中间信息。当存储在处理器704可访问的非瞬态存储介质中时，这些指令使计算机系统700成为被定制以执行指令中指定的操作的专用机器。
[0231]
计算机系统700还包括耦合到总线702的只读存储器(rom)708或其它静态存储设备，用于存储用于处理器704的静态信息和指令。提供存储设备710(诸如磁盘、光盘或固态驱动器)并耦合到总线702，用于存储信息和指令。
[0232]
计算机系统700可以经由总线702耦合到显示器712(诸如阴极射线管(crt))，用于
向计算机用户显示信息。包括字母数字键和其它键的输入设备714耦合到总线702，用于将信息和命令选择传送到处理器704。另一种类型的用户输入设备是光标控件716(诸如鼠标、轨迹球或光标方向键)，用于将方向信息和命令选择传送到处理器704并用于控制显示器712上的光标移动。这种输入设备通常在两个轴上具有两个自由度，第一轴(例如，x)和第二轴(例如，y)，这允许设备指定平面中的位置。
[0233]
计算机系统700可以使用定制的硬连线逻辑、一个或多个asic或fpga、固件和/或程序逻辑(它们与计算机系统相结合，使计算机系统700成为或将计算机系统700编程为专用机器)来实现本文所述的技术。根据一个实施例，响应于处理器704执行包含在主存储器706中的一个或多个指令的一个或多个序列，计算机系统700执行所述的技术。这些指令可以从另一个存储介质(诸如存储设备710)读入到主存储器706中。包含在主存储器706中的指令序列的执行使得处理器704执行本文所述的处理步骤。在替代实施例中，可以使用硬连线的电路系统代替软件指令或与软件指令组合。
[0234]
如本文使用的术语“存储介质”是指存储使机器以特定方式操作的数据和/或指令的任何非瞬态介质。这种存储介质可以包括非易失性介质和/或易失性介质。非易失性介质包括例如光盘、磁盘或固态驱动器，诸如存储设备710。易失性介质包括动态存储器，诸如主存储器706。存储介质的常见形式包括例如软盘、柔性盘、硬盘、固态驱动器、磁带或任何其它磁数据存储介质、cd-rom、任何其它光学数据存储介质、任何具有孔图案的物理介质、ram、prom和eprom、flash-eprom、nvram、任何其它存储器芯片或盒式磁带。
[0235]
存储介质不同于传输介质但可以与传输介质结合使用。传输介质参与在存储介质之间传送信息。例如，传输介质包括同轴电缆、铜线和光纤，包括包含总线702的导线。传输介质也可以采用声波或光波的形式，诸如在无线电波和红外数据通信期间生成的那些。
[0236]
各种形式的介质可以参与将一个或多个指令的一个或多个序列传送到处理器704以供执行。例如，指令最初可以在远程计算机的磁盘或固态驱动器上携带。远程计算机可以将指令加载到其动态存储器中，并使用调制解调器通过电话线发送指令。计算机系统700本地的调制解调器可以在电话线上接收数据并使用红外发送器将数据转换成红外信号。红外检测器可以接收红外信号中携带的数据，并且适当的电路系统可以将数据放在总线702上。总线702将数据传送到主存储器706，处理器704从主存储器706检索并执行指令。由主存储器706接收的指令可以可选地在由处理器704执行之前或之后存储在存储设备710上。
[0237]
计算机系统700还包括耦合到总线702的通信接口718。通信接口718提供耦合到网络链路720的双向数据通信，其中网络链路720连接到本地网络722。例如，通信接口718可以是集成服务数字网(isdn)卡、电缆调制解调器、卫星调制解调器或者提供与对应类型的电话线的数据通信连接的调制解调器。作为另一个示例，通信接口718可以是局域网(lan)卡，以提供与兼容lan的数据通信连接。还可以实现无线链路。在任何此类实现中，通信接口718都发送和接收携带表示各种类型信息的数字数据流的电信号、电磁信号或光信号。
[0238]
网络链路720通常通过一个或多个网络向其它数据设备提供数据通信。例如，网络链路720可以提供通过本地网络722到主计算机724或到由互联网服务提供商(isp)726操作的数据设备的连接。isp 726进而通过全球分组数据通信网络(现在通常称为“互联网”728)提供数据通信服务。本地网络722和互联网728都使用携带数字数据流的电信号、电磁信号或光信号。通过各种网络的信号以及网络链路720上并通过通信接口718的信号(其将数字
数据携带到计算机系统700和从计算机系统700携带数字数据)是传输介质的示例形式。
[0239]
计算机系统700可以通过(一个或多个)网络、网络链路720和通信接口718发送消息和接收数据，包括程序代码。在互联网示例中，服务器730可以通过互联网728、isp 726、本地网络722和通信接口718发送对应用程序的所请求代码。
[0240]
接收到的代码可以在被接收到时由处理器704执行，和/或存储在存储设备710或其它非易失性存储器中以供稍后执行。
[0241]
软件概述
[0242]
图8是可以用于控制计算系统700的操作的基本软件系统800的框图。软件系统800及其组件，包括它们的连接、关系和功能，仅仅是示例性的，并且不意味着限制(一个或多个)示例实施例的实现。适于实现(一个或多个)示例实施例的其它软件系统可以具有不同的组件，包括具有不同的连接、关系和功能的组件。
[0243]
提供软件系统800用于指导计算系统700的操作。可以存储在系统存储器(ram)706和固定存储装置(例如，硬盘或闪存)710上的软件系统800包括内核或操作系统(os)810。
[0244]
os 810管理计算机操作的低级方面，包括管理进程的执行、存储器分配、文件输入和输出(i/o)以及设备i/o。表示为802a、802b、802c...802n的一个或多个应用可以被“加载”(例如，从固定存储装置710传送到存储器706中)以供系统800执行。意图在计算机系统700上使用的应用或其它软件也可以被存储为可下载的计算机可执行指令集，例如，用于从互联网位置(例如，web服务器、app商店或其它在线服务)下载和安装。
[0245]
软件系统800包括图形用户界面(gui)815，用于以图形(例如，“点击”或“触摸手势”)方式接收用户命令和数据。进而，这些输入可以由系统800根据来自操作系统810和/或(一个或多个)应用802的指令来操作。gui 815还用于显示来自os 810和(一个或多个)应用802的操作结果，用户可以提供附加的输入或终止会话(例如，注销)。
[0246]
os 810可以直接在计算机系统700的裸硬件820(例如，(一个或多个)处理器704)上执行。可替代地，管理程序或虚拟机监视器(vmm)830可以插入在裸硬件820和os 810之间。在这个配置中，vmm 830充当os 810与计算机系统700的裸硬件820之间的软件“缓冲”或虚拟化层。
[0247]
vmm 830实例化并运行一个或多个虚拟机实例(“客人机”)。每个客人机包括“客人”操作系统(诸如os 810)，以及被设计为在客户操作系统上执行的一个或多个应用(诸如(一个或多个)应用802)。vmm 830向客人操作系统呈现虚拟操作平台并管理客人操作系统的执行。
[0248]
在一些情况下，vmm 830可以允许客人操作系统如同其直接在计算机系统800的裸硬件820上运行一样运行。在这些实例中，被配置为直接在裸硬件820上执行的客人操作系统的相同版本也可以在vmm 830上执行而无需修改或重新配置。换句话说，vmm 830可以在一些情况下向客人操作系统提供完全硬件和cpu虚拟化。
[0249]
在其它情况下，客人操作系统可以被专门设计或配置为在vmm 830上执行以提高效率。在这些实例中，客人操作系统“意识到”它在虚拟机监视器上执行。换句话说，vmm 830可以在某些情况下向客户操作系统提供半虚拟化。
[0250]
计算机系统进程包括硬件处理器时间的分配，以及存储器的分配(物理和/或虚拟)，存储器的分配用于存储由硬件处理器执行的指令，用于存储由硬件处理器执行指令所
生成的数据，和/或用于当计算机系统进程未运行时在硬件处理器时间的分配之间存储硬件处理器状态(例如，寄存器的内容)。计算机系统进程在操作系统的控制下运行，并且可以在计算机系统上执行的其它程序的控制下运行。
[0251]
云计算
[0252]
本文一般地使用术语“云计算”来描述计算模型，该计算模型使得能够按需访问计算资源的共享池，诸如计算机网络、服务器、软件应用和服务，并且允许以最少的管理工作或服务提供商交互来快速提供和释放资源。
[0253]
云计算环境(有时称为云环境或云)可以以各种不同方式实现，以最好地适应不同要求。例如，在公共云环境中，底层计算基础设施由组织拥有，该组织使其云服务可供其它组织或公众使用。相反，私有云环境一般仅供单个组织使用或在单个组织内使用。社区云旨在由社区内的若干组织共享；而混合云包括通过数据和应用可移植性绑定在一起的两种或更多种类型的云(例如，私有、社区或公共)。
[0254]
一般而言，云计算模型使得先前可能由组织自己的信息技术部门提供的那些职责中的一些代替地作为云环境内的服务层来输送，以供消费者使用(根据云的公共/私人性质，在组织内部或外部)。取决于特定实现，由每个云服务层提供或在每个云服务层内提供的组件或特征的精确定义可以有所不同，但常见示例包括：软件即服务(saas)，其中消费者使用在云基础设施上运行的软件应用，同时saas提供者管理或控制底层云基础设施和应用。平台即服务(paas)，其中消费者可以使用由paas的供应者支持的软件编程语言和开发工具，以开发、部署和以其它方式控制它们自己的应用，同时paas提供者管理或控制云环境的其它方面(即，运行时执行环境下的一切)。基础设施即服务(iaas)，其中消费者可以部署和运行任意软件应用，和/或提供进程、存储装置、网络和其它基础计算资源，同时iaas提供者管理或控制底层物理云基础设施(即，操作系统层下面的一切)。数据库即服务(dbaas)，其中消费者使用在云基础设施上运行的数据库服务器或数据库管理系统，同时dbaas提供者管理或控制底层云基础设施和应用。
[0255]
为了说明可以用于实现(一个或多个)示例实施例的基本底层计算机组件而呈现的上述基本计算机硬件和软件以及云计算环境。但是，(一个或多个)示例实施例不必限于任何特定的计算环境或计算设备配置。代替地，根据本公开，(一个或多个)示例实施例可以在本领域技术人员将理解为能够支持本文呈现的(一个或多个)示例实施例的特征和功能的任何类型的系统体系架构或处理环境中实现。
[0256]
在前面的说明书中，已经参考众多具体细节描述了本发明的实施例，这些细节可以从实现到实现有所变化。因而，说明书和附图应被视为说明性而非限制性的。本发明范围的唯一和排他性指示，以及申请人意图作为本发明范围的内容，是以发布这种权利要求书的具体形式从本技术发布的权利要求书集合的字面和等同范围，包括任何后续更正。
技术特征：1.一种方法，包括：获得数据库的关系模式到图数据模型的映射，其中：关系模式识别与图数据模型中的一种或多种相应顶点类型对应的一个或多个顶点表以及与图数据模型中的一种或多种相应边类型对应的一个或多个边表，以及所述一种或多种边类型中的每一种边类型与所述一种或多种顶点类型中的相应源顶点类型和所述一种或多种顶点类型中的相应目标顶点类型相关联；基于所述映射，填充正向压缩稀疏行(csr)表示，用于所述一种或多种边类型中的边类型的边的正向遍历，其中边类型的每条边：起源于该边类型的源顶点类型的源顶点，以及终止于该边类型的目标顶点类型的目标顶点；基于正向csr表示，填充边类型的反向csr表示，用于该边类型的边的反向遍历。2.如权利要求1所述的方法，其中：所述填充正向csr表示还基于：与边类型的源顶点类型对应的顶点表，与边类型的目标顶点类型对应的顶点表，以及与边类型对应的边表；所述填充反向csr表示不包括：输入/输出(i/o)，也不访问：与边类型的源顶点类型对应的顶点表，与边类型的目标顶点类型对应的顶点表，也不访问与边类型对应的边表。3.如权利要求1所述的方法，其中：正向csr表示包括：正向目的地数组，其指示边类型的目标顶点类型的哪些顶点终止该边类型的哪些相应边，以及正向源数组，其指示对于边类型的源顶点类型的每个顶点，到正向目的地数组的偏移量的相应正向范围；反向csr表示包括：反向源数组，其指示边类型的源顶点类型的哪些顶点引发该边类型的哪些相应边，以及反向目的地数组，其指示对于边类型的目标顶点类型的每个顶点，到反向源数组的偏移量的相应反向范围。4.如权利要求3所述的方法，其中：所述填充反向csr表示包括对终止于边类型的目标顶点类型的每个顶点的该边类型的相应边进行计数；对终止于边类型的目标顶点类型的每个顶点的该边类型的边的所述计数包括以下之一：扫描正向目的地数组，或者
在为该边类型的每条边填充正向目的地数组时，递增用于终止该边的目标顶点的相应计数器。5.如权利要求4所述的方法，其中：反向目的地数组最初用零填充；用于终止边的顶点的所述计数器包括用于该顶点的反向目的地数组的相应元素。6.如权利要求5所述的方法，其中对终止于每个顶点的边的所述计数包括并发地处理至少两条边。7.如权利要求6所述的方法，其中：所述至少两条边终止于同一个目标顶点；所述并发地处理所述至少两条边包括递增用于所述同一个目标顶点的所述计数器的原子操作。8.如权利要求5所述的方法，其中：一个或多个数组作为多个块被处理；所述多个块中的每个块包含多个元素；所述一个或多个数组包括：正向目的地数组、正向源数组、反向目的地数组，和/或反向源数组。9.如权利要求8所述的方法，其中：该方法还包括用相应的新值替换反向目的地数组的每个块的每个元素的相应旧值；当所述元素是块中的第一个元素时，新值为零；否则，新值是块的前一个元素的旧值加上所述前一个元素的新值的总和。10.如权利要求9所述的方法，其中所述替换每个块的每个元素的旧值包括并发地处理至少两个块。11.如权利要求9所述的方法，其中反向目的地数组的每个块与以下内容相关联：最后一个值，它是块的所述多个元素的所述旧值的总和，以及块偏移量，其：当块是反向目的地数组的第一个块时，是零，当块是反向目的地数组的第二个块时，是所述第一个块的所述最后一个值，否则，是前一个块的所述最后一个值加上前一个块的所述块偏移量的总和。12.如权利要求11所述的方法，还包括并发地：计算前一个块的所述最后一个值加上前一个块的所述块偏移量的所述总和，以及所述替换所述块的每个元素的旧值。13.如权利要求11所述的方法，还包括将所述块的每个元素递增所述块的块偏移量。14.如权利要求13所述的方法，其中所述递增所述块的每个元素包括并发地递增所述块的多个元素。15.如权利要求14所述的方法，其中所述并发地递增所述块的多个元素包括单指令多数据(simd)。16.如权利要求3所述的方法，其中所述填充反向csr表示包括对于边类型的每条边：通过将与该边的目标顶点对应的反向目的地数组的元素的值加上用于目标顶点的相应计数器的值来计算到反向源数组中的偏移量；
基于所述偏移量，向反向源数组的元素中存储：该边的标识符，和/或该边的源顶点到正向源数组中的偏移量。17.如权利要求16所述的方法，其中边的标识符是从正向目的地数组复制的。18.如权利要求16所述的方法，其中所述对于边类型的每条边包括并发地对于该边类型的至少两条边。19.如权利要求18所述的方法，其中：所述至少两条边终止于同一顶点；所述并发地处理所述至少两条边包括递增用于所述同一顶点的所述计数器的原子操作。20.如权利要求1所述的方法，还包括基于所述一个或多个边类型中的第二边类型的第二正向csr表示来填充第二边类型的第二反向csr表示以用于第二边类型的边的反向遍历。21.如权利要求20所述的方法，其中：所述正向csr表示是第一正向csr表示；所述反向csr表示是第一反向csr表示；第二正向csr表示包括正向目的地数组，该数组包含用于与所述一个或多个顶点表中的顶点表对应的第二边类型的第二源顶点类型的每个顶点的稀疏标识符或持久密集标识符，和/或第一反向csr表示包括反向源数组，该数组包含用于第二边类型的第二目的地顶点类型的每个顶点的稀疏标识符或持久密集标识符。22.如权利要求1所述的方法，其中：正向csr表示包括正向目的地数组，该数组包含用于边类型的目的地顶点类型的每个顶点的稀疏标识符或持久密集标识符，和/或反向csr表示包括反向源数组，该数组包含用于边类型的源顶点类型的每个顶点的稀疏标识符或持久密集标识符。23.一种或多种非暂态计算机可读介质，存储一个或多个指令序列，指令序列在由一个或多个处理器执行时使得执行如权利要求1-22中的任一项所述的步骤。24.一种设备，包括：一个或多个处理器；以及存储器，其耦合到所述一个或多个处理器并且包括存储在其上的指令，指令在由所述一个或多个处理器执行时使得执行如权利要求1-22中的任一项所述的步骤。
技术总结在实施例中，计算机获得数据库的关系模式到图数据模型的映射。关系模式识别与图数据模型中的(一种或多种)顶点类型对应的(一个或多个)顶点表和与图数据模型中的(一种或多种)边类型对应的(一个或多个)边表。每种边类型都与源顶点类型和目标顶点类型相关联。基于该映射，正向压缩稀疏行(CSR)表示被填充，用于相同边类型的边的正向遍历。每条边起源于源顶点并终止于目标顶点。基于正向CSR表示，填充边类型的反向CSR表示，用于边类型的边的反向遍历。加速以两种方式发生。为正向CSR计算的值被重用于反向CSR。弹性和非弹性缩放可以发生。弹性和非弹性缩放可以发生。弹性和非弹性缩放可以发生。
技术研发人员：J-P
受保护的技术使用者：甲骨文国际公司
技术研发日：2021.03.10
技术公布日：2022/11/1
