关系语言中的隐式排序

天真地做到这一点并不是特别困难。这里的挑战是像编写批处理查询一样实现它，但要以这样的方式实现，例如 materialize 或 dida 之类的增量系统可以在新编辑到达时有效地更新结果。不是因为这段代码本身特别有用，而是因为它有助于发现可以通过这种方式解决哪些类型的问题的界限。该练习有点像 GPU 编程，因为避免顺序算法和共享可变数据结构需要非常小心地将问题的实际基本数据依赖项与典型编程技术意外引入的数据依赖项分开。我们有一个编辑树，每个编辑都代表一个字符的插入。每个编辑都有一个唯一的 id，为了这个简单的例子，我们将说它只是一个整数。每个其他编辑都有一个父编辑。编辑的 id 总是大于其父级的 id。为了构建实际的文本，我们采用这棵编辑树，按 id 对每个编辑的子项进行排序，然后对树进行预序遍历。创建表编辑（id 整数，parent_id 整数，字符文本）；插入编辑值（ 0 ， null ， 'a' ）；插入编辑值 ( 1 , 0 , 'b' );插入编辑值 ( 2 , 0 , 'e' );插入编辑值 ( 3 , 1 , 'c' );插入编辑值 ( 4 , 1 , 'd' );插入编辑值 ( 5 , 2 , 'f' );插入编辑值 ( 6 , 5 , 'g' );插入编辑值 ( 7 , 5 , 'h' );插入编辑值 ( 8 , 5 , 'i' );

鉴于我们正在尝试对这组编辑进行排序，自然的反应是从以下内容开始：但我们立即陷入困境，因为没有明显的排序键。让我们决定一个编辑应该在另一个编辑之前还是之后的信息隐含在树的形状中。为了得到一个实际值进行排序，我们需要包含所有这些信息。递归路径 (id, path , character) as ( select edits . id , edits . id , edits . character from edits where edits . parent_id is null union all select child . id , parent . path || ',' || child . id , child . character from edits as child, path as parent where child . parent_id = parent . id ) select * from path order by path 。小路 ;这就是问题的本质 - 按照从根目录开始的路径中的 id 对编辑进行排序。这是一个很好的解决方案，对于平衡良好的树木，这将是故事的结尾。但是用于文本编辑 crdt 的树往往非常深和狭窄，因此实现这些路径将使存储成本看起来像 O(N²)。 （在典型情况下，我们可以通过只查看具有多个孩子的路径的一部分来减少这一点。但最坏的情况仍然是 O(N²)）在大多数语言中，如果显式存储密钥太昂贵，我们只是使用自定义比较函数进行排序。创建函数 compare_edits (id1 integer , id2 integer ) 将比较返回为 ???;通过比较 compare_edits( edit . id ) 从编辑顺序中选择 *；

增量维护这样的排序运算符会很棘手。可能必须显式存储一组比较。对于我来说，如何以一种使所需的比较集相对于输入的微小变化保持稳定的方式选择支点并不明显。但它可能是可能的。如果使用内置的排序运算符不可行，也许我们可以自己显式遍历树。 with recursiverightmost_child(id, parent_id) as ( select max (id), edit . parent_id from edit where edit . parent_id is not null group by parent_id),rightmost_descendant(id, child_id) as ( select id, id from edit union select parent . parent_id , child . child_id 从 rightmost_child 为父级， rightmost_descendant 为 child where parent . id = child . id ),rightmost_leaf(id, Leaf_id) as ( select id, max (child_id) as leaf_id from rightmost_descendant group by id),prev_sibling(id) , prev_id) as ( select edit . id , ( select max (sibling . id ) from edit as mirror where edit . parent_id = mirror . parent_id and edit . id > mirror . id ) as prev_id from edit where prev_id is not null ), prev_edit(id, prev_id) as ( -- 没有上一个兄弟姐妹的编辑在他们的父级之后选择 edit . id , edit . parent_id from edit where prev_sibling where prev_sibling . id = edit . id ) union all - - 其他编辑出现在他们上一个兄弟选择编辑的最右边的叶子之后. id ， rightmost_leaf 。 Leaf_id 来自 edit、prev_sibling、rightmost_leaf，其中 edit 。 id = prev_sibling 。 id 和 prev_sibling 。 prev_id = rightmost_leaf 。 id ),position(id, position, character) as ( -- root is at position 0 select edit . id , 0 , edit . character from edit where edit . parent_id is null union all -- 所有其他编辑都在他们上一次编辑之后select edit . id , position . position + 1 , edit . character from edit, prev_edit, position where edit . id = prev_edit . id and prev_edit . prev_id = position . id ) select * from position order by position .位置 ;让兄弟=编辑（？编辑。编辑。（编辑父~父））入口rightmost_child =编辑（？编辑。编辑。（最大[编辑~父]））入口rightmost_leaf=修复（编辑（？编辑。编辑。编辑） ) (?[rightmost_leaf] . (rightmost_leaf (?edit . ?leaf .edit . (max [leaf | (leaf rightmost_child)]))))) 入口prev = edits (?edit .edit .let prev_siblings = (edit兄弟) ( ?sibling . (when (edit >sibling)sibling)) in if !!prev_siblings (max [prev_siblings] rightmost_leaf) (edit parent)) 入口位置 = fix (root . 0) (?[position] . (position | (position) (?edit . ?pos . (edit ~prev) . (pos + 1))))) inedits (?edit . (edit position) .edit . (edit character)) 在任何一种情况下，我们都可能不得不至少维护一个关于 parent、~parent 和 character 的索引，可能还有许多中间结果的索引。有点令人担忧的是，从代码中根本无法预测这些将是什么以及它们将花费多少。在理想情况下，prev 的输出非常稳定，因此应该允许合理有效的增量维护。但是位置输出的很大一部分会在每次新编辑时发生变化，因此维护起来效率低下。这是因为 prev 隐式表示排序，就相邻编辑之间的相对排序而言，而 position 通过对序列中的每个位置进行编号来显式表示排序。在这个问题中，每个新的编辑只改变它右边的第一个编辑的 prev 值，但增加它右边的每个编辑的位置编号。

我们从一个空序列开始，我们将在其中以正确的顺序存储编辑。对于每次编辑，我们通过首先扫描序列找到它的父级，然后向右扫描找到正确的点插入子级来将其插入到序列中。如果序列被实现为一个 b 树，那么这些扫描和插入是相当便宜的。我们还可以跟踪 b 树每个分支中的字符数，以便通过沿着 b 树的主干走下去，可以有效地回答诸如“第 142 个字符的编辑 ID 是什么”之类的查询。命令式解决方案根据某些有序数据结构中的位置隐式表示排序。在数据结构的开头附近插入新编辑不需要显式更新每个后面元素的位置 - 该位置隐含在整个结构中。使用递归序列(last_id, characters, ids) as ( select edit . id , edit . character , array[ edit . id ] from edit where edit . parent_id is null union all select edit . id , -- insert edit.character and edit .id at insert_point substring ( sequence . characters , 1 , insert_point . insert_point - 1 ) || edit . character || substring ( sequence . characters , insert_point . insert_point ), sequence . ids [ 1 : insert_point . insert_point - 1 ] ||编辑 . id || 序列 . ids [ 插入点 . 插入点 :] 来自序列，编辑连接横向（选择合并（分钟（i），数组长度（序列。ids，1）+ 1）作为插入点来自生成下标（序列。ids，1 ) as i -- 侧向编辑连接的父级的数组扫描（从 generate_subscripts( sequence . ids , 1 ) 中选择 j 作为 j where sequence . ids [j] = edit . parent_id ) as parent_ix on true -- 对父级的数组扫描ids[i] 加入横向（从 generate_subscripts( sequence . ids , 1 ) 中选择 k作为 k，编辑为 o_edit 其中序列。 ids [k] = o_edit 。 parent_id 和序列。 ids [i] = o_edit 。 id ) as o_parent_ix on true - 找到 i > parent_ix 的插入点。 j 和 o_parent_ix 。 k < parent_ix 。 j) 作为对 true where 序列的插入点。 last_id + 1 = 编辑。 id ) select * from sequence order by last_id desclimit 1 ; Imp 没有任何序列数据结构，但我们可以伪造一个有关系的数据结构，至少看看代码会是什么样子。 // 处理“数组”的函数let insert = ?[sequence] . ？位置 。 ？物品 。让 old = 序列 (?old_position . ?old_item . (if (old_position >= position) (old_position + 1) old_position) . old_item ) in old | (position . item)inlet find_min_pos = ?[sequence] 。 ？[条件] 。 ( let found = sequence (?pos . ?edit . (when (cond pos edit) pos)) in min [found] ) in// 实际 crdt codelet sequence = fix (0 . root) (?[sequence] . let next_edit = 1 + (max [sequence (?pos . ?edit .edit)]) in if !(edits next_edit) 序列 let parent_pos = find_min_pos [sequence] [?pos . ?edit . ((next_edit parent) = edit)] 在let insert_point = find_min_pos [sequence] [?o_pos . ?o_edit . ( let o_parent_pos = find_min_pos [sequence] [?pos . ?edit . ((o_edit parent) = edit)] in (o_pos > parent_pos) & (parent_pos > o_parent_pos) )] in insert [sequence] (if !!insertion_point inserting_point (max [sequence (?pos . ?edit . pos)])) next_edit ) insequence (?pos . ?edit . pos .edit . (edit character))

这使当前蹩脚的解释器屈服，但我认为可以有效地执行它。对于 sql 和 imp 版本，似乎可以逐步维护这一点。如果我们使用持久数据结构来实现数组，那么插入不会太昂贵。如果我们提示运行时不会删除任何编辑并且新编辑的 id 编号会增加，那么它可以推断它不需要存储数组的旧值（参见例如 edelweiss）。另一方面，我们引入了一个完全偶然的顺序依赖，失去了利用并行性或矢量化的能力，也失去了处理乱序编辑的能力。任何下游代码的增量维护可能需要能够区分序列的连续版本。该序列按一个键进行排序，该键实现甚至比较的成本都很高。快速命令式解决方案依赖于不适合增量维护的巧妙隐式比较。虽然编辑的相对顺序是稳定的（例如，如果 id=4 出现在 id=12 之前，那么它总是在它之前），但绝对位置非常不稳定（如果插入新的编辑，则必须增加其后所有内容的位置）。因此，绝对位置的任何明确表示都将导致下游大量流失。后一个问题并不是关系语言独有的——稳定的 id 是任何增量维护问题的核心（例如，文本编辑器中的增量算法通常依赖于指向树节点的指针而不是字符位置）。关系语言的难点在于我们不能使用指针标识作为 id，因为这需要严格约束的执行顺序。也许一种选择是拥有一个下降到插入和删除级别的逃生舱口。在那个级别，我们可以基于操作历史构建稳定的 id，类似于使用树节点作为序列中的 id。我们只需要保证在声明层中无法观察到 id 的详细信息，以便插入/删除的顺序不会影响最终结果。

我的工作目前是通过与在 github 上赞助我的人分享想法和正在进行的工作来资助的。