Peer To Patent

Home > Archived Applications > 20090119247 > Prior Art > Detail

Pre-Grant Publication Number: 20090119247

Efficient hash based full-outer join

Please help the USPTO examine the application by evaluating the relevance of the publicly submitted prior art to the patent application. Peer To Patent forwards the Top 10 most relevant prior art submissions and their annotations to the USPTO.

Review this prior art and click on the thumbs up (or down) to indicate whether this submission should be forwarded to the USPTO.
If you login then you can add an annotation by typing in the box at the bottom of the screen to comment on the relevance of the prior art to the claims of the patent application.

Prior Art Detail

Annotations(0)

#533Hash joins and hash teams in Microsoft SQL Server

Applies to Claims 1,3,5

Submitted by: Steven PearsonLast updated: over 2 years ago

1 thumb up 0 thumbs down

Summary / Description

Summary / Description	Some general coverage on hash join including hash full outer join, that mentions some specific techniques relevant to application's claims.

Basic Information

Type of Prior Art	Print Publication

Publication Title *	VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998,

Author	Goetz Graefe, Ross Bunker, Shaun Cooper

ISBN	1-55860-566-5

Page Range	86-97

Medium	Journal article

Publication Date *	August 1998

URL	http://www.vldb.org/conf/1998/p...

Notes / To Do

Notes	I have not spent much time with this so can't provide full relevance, but did find a couple specific things worth pointing out.

Excerpt

Excerpt

If some of the spilled build overflow files are smaller than the memory allocated for the hash operation, multlple spilled partitions may be processed concurrently, and it is sufficient to create a single probe overflow file for an entire group of build overflow files. [...] Given that selectivity estimation can be rather inaccurate, and that hash joins derive much of their advantage over merge joins from their asymmetry, i.e., from using the smaller of the two inputs as build input, a natural idea is to defer the assignment of build and probe roles to the two inputs ... Therefore, when starting to process a spilled partition, our implementation always considers role reversal. Note that in recursive partitioning, in particular if bit vector filtering is effective, role reversal back and forth may be useful in multiple successive recursion levels.

Relevance

Claims

A computer-implemented method used during computation of a full outer join based on a join condition, comprising:partitioning rows from a left table into left table partitions, wherein said partitioning is based on values in a left table join column of said join condition;

selecting a first subset of said left table partitions;

generating a hash table that indexes said first subset of left table partitions by the respective join column of said join condition;

for each right table row of right table rows from a right table,(a) probing said hash table to find any particular left table row to inner join with said each right table row based on said join condition,

(b) for any particular left table row found that should be inner joined with said each right table row, generating an inner join row and marking said particular left table row in said first subset of left table partitions as being inner joined,

(c) determining whether said each right table row was inner joined with any left table row in said first subset of left table partitions, and

(d) if said each right table row was not inner joined with any particular left table row in said first left table partition, generating a right outer join row for said each right table row; and

for each left table row in said first subset of left table partitions that is not marked as being inner joined, generating a left outer join row.

Relevance

The prior art covers some or all of Claim 1's familiar hash full outer join technique.

Claim Chart

All

The computer-implemented method of Claim 1, wherein said first subset of left table partitions includes multiple left table partitions.

Relevance

The prior art pecifically anticipates this claim; see section "Partition Tuning" on p.90 of prior art (a portion of which is in the first part of excerpt further above).

Claim Chart

All

The method of Claim 4, wherein a pair of corresponding partitions includes a right table partition that corresponds to a left table partition, the steps further including:determining which one of said pair of corresponding partitions is to be loaded into memory as a hashed in-memory partition, the other of said pair of corresponding partitions being a scan partition;

generating a second hash table that indexes said hashed in-memory partition by the respective join column of said join condition;

for each scan partition row from said scan partition,(1) probing said second hash table to find any row in the hashed in-memory partition to inner join with said each scan partition row,

(2) for any particular row found in the hashed in-memory partition that should be inner joined with said each scan partition row, generating an inner join row and marking said particular row in the hashed in-memory partition as being inner joined,

(3) determining whether said each scan partition row was inner joined with any row in said hashed in-memory partition, and

(4) if said each scan partition row was not inner joined with any row in said hashed in-memory partition, generating a left or right outer join row for said each scan partition row;

for each row in said hashed in-memory partition that is not marked as being inner joined, generating a left or right outer join row.

Relevance

The prior art specifically anticipates the main new element introduced in claim 5, which is the choice of whether to hash a left table partition or a right table partition. See prior art's section "Role reversal" on p. 91 (a portion of which I pasted in as 2nd part of excerpt further above). Note that the term "build" in the prior art refers to the hashed portion, while "probe" refers to the non-hashed portion ("scan partition" in the application).

Claim Chart

All

0 days left