We present a pipelining, dynamically usercontrollable reorder operator, for use in dataintensive applications. Allowing the user to reorder the data delivery on the fly increases the interactivity in several contexts such as online aggregation and large-scale spreadsheets; it allows the user to control the processing of data by dynamically specifying preferences for different data items based on prior feedback, so that data of interest is prioritized for early processing. We describe an efficient, non-blocking mechanism for reordering, which can be used over arbitrary data streams from files, indexes, and continuous data feeds. We also investigate several policies for the reordering based on the performance goals of various typical applications. We present results from an implementation used in Online Aggregation in the Informix Dynamic Server with Universal Data Option, and in sorting and scrolling in a large-scale spreadsheet. Our experiments demonstrate that for a variety of data distributions and applications, reordering is responsive to dynamic preference changes, imposes minimal overheads in overall completion time, and provides dramatic improvements in the quality of the feedback over time. Surprisingly, preliminary experiments indicate that online reordering can also be useful in traditional batch query processing, because it can serve as a form of pipelined, approximate sorting.
展开▼
机译：我们提出了一种流水线型的，可动态用户控制的重排序运算符，用于数据密集型应用程序。允许用户即时重新排序数据交付，可以在多种情况下提高交互性，例如在线汇总和大规模电子表格；它允许用户通过基于先前的反馈动态指定不同数据项的首选项来控制数据的处理，从而优先考虑感兴趣的数据以进行早期处理。我们描述了一种有效的无阻塞重新排序机制，该机制可用于来自文件，索引和连续数据源的任意数据流。我们还根据各种典型应用程序的性能目标研究了几种用于重新排序的策略。我们展示了在带有Universal Data Option的Informix Dynamic Server中的在线聚合中以及在大型电子表格中进行排序和滚动时使用的实现结果。我们的实验表明，对于各种数据分布和应用程序，重新排序可响应动态首选项的变化，在总体完成时间上的开销最小，并且可以随着时间的推移显着改善反馈质量。令人惊讶的是，初步实验表明，在线重新排序在传统的批查询处理中也很有用，因为它可以用作流水线近似排序的一种形式。
展开▼
