公开(公告)号：US07490113B2

公开(公告)日：2009-02-10

申请号：US10650353

申请日：2003-08-27

申请人： Serge Bourbonnais ,  Siquan Li ,  Bruce Gilbert Lindsay

发明人： Serge Bourbonnais ,  Siquan Li ,  Bruce Gilbert Lindsay

IPC分类号： G06F17/30

CPC分类号： G06F17/30575 ,  G06F11/2056 ,  G06F2201/80 ,  G06Q40/12 ,  Y10S707/99938 ,  Y10S707/99953

摘要： A first log reader publishes first messages to a plurality of queues. The first messages comprise changes for transactions extracted from a log by the first log reader. In response to one of the queues becoming unavailable, launching a second log reader to read and extract from the log, and to publish second messages comprising changes for transactions extracted from the log by the second log reader to the unavailable queue as a catch-up queue. In response to the catch-up queue becoming available and the second log reader reaches the end of the log, the publishing of the second messages for the catch-up queue is transferred from the second log reader to the first log reader.

摘要翻译： 第一个日志读取器将第一消息发布到多个队列。 第一个消息包括由第一个日志读取器从日志中提取的事务的更改。 响应于其中一个队列变得不可用，启动第二个日志读取器以从日志读取和解压缩，并且发布包括由第二个日志读取器从日志提取的事务的更改的第二个消息作为追赶 队列。 响应追赶队列变为可用，第二个日志读取器到达日志的末尾，追赶队列的第二个消息的发布从第二个日志读取器传输到第一个日志读取器。

公开(公告)号：US06546402B1

公开(公告)日：2003-04-08

申请号：US09586809

申请日：2000-06-05

申请人： Kevin Scott Beyer ,  Roberta Jo Cochrane ,  Bruce Gilbert Lindsay ,  Kenneth Mark Salem

发明人： Kevin Scott Beyer ,  Roberta Jo Cochrane ,  Bruce Gilbert Lindsay ,  Kenneth Mark Salem

IPC分类号： G06F1730

CPC分类号： G06F17/30457 ,  G06F17/30383 ,  G06F17/30451 ,  Y10S707/954 ,  Y10S707/99952

摘要： A method and system for refreshing materialized join views includes asynchronously evaluating changes to the base tables, i.e., evaluating changes for an intended time tintended at an evaluation time teval that is later than the intended time. Changes made to the base table between the intended time tintended and evaluation time teval are recursively compensated for. The results of the evaluating and compensating are then applied to the materialized view to refresh the view.

摘要翻译： 用于刷新物化连接视图的方法和系统包括异步地评估对基表的更改，即评估在比预期时间晚的评估时间teval所期望的期望时间的改变。 递归地补偿预期时间和计时时间之间对基准表的变化。 然后将评估和补偿的结果应用于物化视图以刷新视图。

公开(公告)号：US06304866B1

公开(公告)日：2001-10-16

申请号：US08884602

申请日：1997-06-27

申请人： Jyh-Herng Chow ,  John Frederick Hornibrook ,  Bruce Gilbert Lindsay ,  Geoffrey Peddle ,  Eugene Jon Shekita ,  Amit Somani ,  Surendra Kumar Verma ,  Honesty Cheng Young

发明人： Jyh-Herng Chow ,  John Frederick Hornibrook ,  Bruce Gilbert Lindsay ,  Geoffrey Peddle ,  Eugene Jon Shekita ,  Amit Somani ,  Surendra Kumar Verma ,  Honesty Cheng Young

IPC分类号： G06F1730

CPC分类号： G06F9/505 ,  G06F2209/5017 ,  Y10S707/99932 ,  Y10S707/99933

摘要： In a multiprocessing system, multiple concurrently operating task execution units are operated to perform an aggregate task by using incremental and on-demand sub-task allocation. A command is received to perform a machine-executed task divisible into multiple sub-tasks, i.e., an “aggregate task”. A granularity is then established, for dividing the aggregate task into sub-tasks. Preferably, the granularity is not too large to permit potentially uneven sub-task allocation, and not too small to incur excessive overhead in allocating sub-tasks. Having established the granularity, multiple task execution units are independently operated on-demand to sequentially self-allocate and execute sub-tasks of the aggregate tasks. Each sub-task is sized according to the established granularity. Operating “on-demand”, each task execution unit sequentially allocates and executes one sub-task at a time, then proceeding to the next unexecuted sub-task. Thus, the multiprocessing system operates like multiple people drinking water from a common glass through individual straws—although each drinker works independently, all finish simultaneously, thus completing the aggregate task as expeditiously as possible.

摘要翻译： 在多处理系统中，通过使用增量和按需子任务分配来操作多个并发操作任务执行单元来执行聚合任务。 接收到用于执行可分为多个子任务（即，“聚合任务”）的机器执行任务的命令。 然后建立粒度，将聚合任务划分为子任务。 优选地，粒度不是太大，不能允许潜在的不均匀的子任务分配，并且不太小，在分配子任务时不会产生过多的开销。 建立粒度后，多个任务执行单元按需独立运行，顺序自动分配和执行总任务的子任务。 每个子任务的大小根据建立的粒度。 每个任务执行单元按“按需”运行，一次顺序分配并执行一个子任务，然后进行到下一个未执行的子任务。 因此，多处理系统通过个人吸管，像普通玻璃饮水一样运作，虽然每个饮酒者独立工作，但是同时完成，从而尽可能快地完成总体任务。

公开(公告)号：US06226639B1

公开(公告)日：2001-05-01

申请号：US09158741

申请日：1998-09-22

申请人： Bruce Gilbert Lindsay ,  Sridhar Rajagopalan ,  Eugene Jon Shekita

发明人： Bruce Gilbert Lindsay ,  Sridhar Rajagopalan ,  Eugene Jon Shekita

IPC分类号： G06F1730

CPC分类号： G06F17/30501 ,  G06F17/30498 ,  Y10S707/99931 ,  Y10S707/99935

摘要： A system and method for joining a build table to a probe table in response to a query for data includes over partitioning the build table into “N” build partitions using a uniform hash function and writing the build partitions into main memory of a database computer. When the main memory becomes full, one or more partitions is selected as a victim partition to be written to disk storage, and the process continues until all build table rows or tuples have either been written into main memory or spilled to disk. Then, a packing algorithm is used to initially designate never-spilled partitions as “winners” and spilled partitions as “losers”, and then to randomly select one or more winners for prospective swapping with one or more losers. The I/O savings associated with each prospective swap is determined and if any savings would be realized, the winners are designated as losers the losers are designated as winners. The swap determination can be made multiple times, e.g., 256, after which losers are moved entirely to disk and winners are moved entirely to memory. At the end of the swapping, probe table rows associated with winner partitions are joined to rows in the winner build partitions while probe table rows associated with loser partitions are spilled to disk. Then, the loser build partitions are written to main memory for joining with corresponding probe table partitions, to undertake the requested join of the build table and probe table in an I/O- and memory-efficient manner.

摘要翻译： 响应于数据查询将构建表连接到探测表的系统和方法包括使用统一散列函数将构建表过度分割为“N”构建分区，并将构建分区写入数据库计算机的主存储器。 当主内存变满时，将选择一个或多个分区作为要写入磁盘存储器的受害分区，并且该过程继续进行，直到所有构建表行或元组都已写入主内存或溢出到磁盘。 然后，打包算法用于初始地将未分配的分区指定为“获胜者”，将分区分散为“输家”，然后随机选择一个或多个获胜者进行与一个或多个输家的潜在交换。 确定与每个预期掉期相关的I / O节省，如果实现了任何节省，则获胜者被指定为失败者被指定为赢家的输家。 交换确定可以进行多次，例如256次，之后输家完全移动到磁盘，获胜者完全移动到内存。 在交换结束时，与优胜者分区关联的探测表行将连接到优胜者构建分区中的行，而与失败分区关联的探测表行会溢出到磁盘。 然后，失败者构建分区被写入主存储器以与相应的探测表分区相连接，以I / O和存储器高效的方式承载构建表和探测表的所请求的连接。

公开(公告)号：US6108658A

公开(公告)日：2000-08-22

申请号：US50434

申请日：1998-03-30

申请人： Bruce Gilbert Lindsay ,  Gurmeet Singh Manku ,  Sirdhar Rajogopalan

发明人： Bruce Gilbert Lindsay ,  Gurmeet Singh Manku ,  Sirdhar Rajogopalan

IPC分类号： G06F7/22 ,  G06F17/30

CPC分类号： G06F7/22 ,  Y10S707/99932 ,  Y10S707/99936 ,  Y10S707/99937 ,  Y10S707/99942

摘要： A system and method for finding an .epsilon.-approximate .phi.-quantile data element of a data set with N data elements in a single pass over the data set. The .epsilon.-approximate .phi.-quantile data element is guaranteed to lie within a user-specified approximation error .epsilon. of a true .phi.-quantile data element being sought. B buffers, each having a capacity of k elements, initially are filled with sorted data elements from the data set, with the values of b and k depending on .epsilon. and N. The buffers are then collapsed into an output buffer, with the remaining buffers then being refilled with data elements, collapsed (along with the previous output buffer), and so on until the entire data set has been processed and a single output buffer remains. A data element of the output buffer corresponding to the .epsilon.-approximate .phi.-quantile is then output as the approximate .phi.-quantile data element. If desired, the system and method can be practiced with sampling to even further reduce the amount of space required to find a desired .epsilon.-approximate .phi.-quantile data element.

摘要翻译： 一种用于在数据集中的单次传递中找到具有N个数据元素的数据集的ε-近似phi-量子数据元素的系统和方法。 ε-近似phi - 数量数据元素被保证位于正在寻找的真实phi - 数量数据元素的用户指定的近似误差ε。 每个具有k个元素的容量的B缓冲器最初由来自数据集的排序数据元素填充，其中b和k的值取决于epsilon和N.然后，缓冲器被折叠成输出缓冲器，其余的缓冲器 然后使用数据元素重新填充数据元素，并与之前的输出缓冲区一起折叠，等等，直到整个数据集被处理完毕，并保留单个输出缓冲区。 然后，输出对应于ε-近似phi - 数量的输出缓冲器的数据元素作为近似phi - 数量数据元素。 如果需要，可以采用系统和方法来实施，以进一步减少找到所需的ε-近似phi - 数量数据元素所需的空间量。