Database system with improved methods for filtering duplicates from a tuple stream

Claim 1

In a database system storing a plurality of database tables, each database table comprising a plurality of tuples storing columns of information, each column representing a particular category of information for which each tuple stores a data value, a method for eliminating duplicate tuples from a tuple stream, the method comprising: receiving a query specifying selection criteria for selecting information of interest from the database system, said query specifying that said information of interest is to be selected by a database join operation which joins selected ones of said database tables by one or more columns shared between tables (key columns), said query further specifying that the particular information is to be returned as distinct tuples; determining a join order specifying a sequence indicating how said selected ones of said database tables are to be preferentially scanned by the system for determining which tuples of each said selected ones of said database tables qualify, said join order indicating innermost and outermost tables of the join and being selected so as to guarantee that tuples will stream in order during execution of the query; initializing a filter at the outermost table for said one or more key columns, for forcing the method to pass a first tuple encountered and to construct an initial key from it; attaching the filter to the innermost table, so that the filter is executed for each tuple which qualifies on the innermost table; executing the query for generating a tuple stream satisfying said selection criteria, said executing step including scanning, according to said determined join order, said selected ones of said database tables; and as the innermost table is scanned, executing the filter for filtering duplicate tuples from the tuple stream by discarding those tuples having keys already encountered in the tuple stream.