On Tue, Jun 4, 2019 at 12:08 PM Robert Haas <robertmh...@gmail.com> wrote:
> On Tue, Jun 4, 2019 at 2:47 PM Melanie Plageman > <melanieplage...@gmail.com> wrote: > > Oops! You are totally right. > > I will amend the idea: > > For each chunk on the inner side, loop through both the original batch > > file and the unmatched outer tuples file created for the last chunk. > > Emit any matches and write out any unmatched tuples to a new unmatched > > outer tuples file. > > > > I think, in the worst case, if no tuples from the outer have a match, > > you end up writing out all of the outer tuples for each chunk on the > > inner side. However, using the match bit in the tuple header solution > > would require this much writing. > > Probably the bigger problem is that in this worst case you would also > > need to read double the number of outer tuples for each inner chunk. > > > > However, in the best case it seems like it would be better than the > > match bit/write everything from the outer side out solution. > > I guess so, but the downside of needing to read twice as many outer > tuples for each inner chunk seems pretty large. It would be a lot > nicer if we could find a way to store the matched-bits someplace other > than where we are storing the tuples, what Thomas called a > bits-in-order scheme, because then the amount of additional read and > write I/O would be tiny -- one bit per tuple doesn't add up very fast. > > In the scheme you propose here, I think that after you read the > original outer tuples for each chunk and the unmatched outer tuples > for each chunk, you'll have to match up the unmatched tuples to the > original tuples, probably by using memcmp() or something. Otherwise, > when a new match occurs, you won't know which tuple should now not be > emitted into the new unmatched outer tuples file that you're going to > produce. So I think what's going to happen is that you'll read the > original batch file, then read the unmatched tuples file and use that > to set or not set a bit on each tuple in memory, then do the real work > setting more bits, then write out a new unmatched-tuples file with the > tuples that still don't have the bit set. So your unmatched tuple > file is basically a list of tuple identifiers in the least compact > form imaginable: the tuple is identified by the entire tuple contents. > That doesn't seem very appealing, although I expect that it would > still win for some queries. > > I'm not sure I understand why you would need to compare the original tuples to the unmatched tuples file. This is the example I used to try and reason through it. let's say you have a batch (you are joining two single column tables) and your outer side is: 5,7,9,11,10,11 and your inner is: 7,10,7,12,5,9 and for the inner, let's say that only two values can fit in memory, so it is split into 3 chunks: 7,10 | 7,12 | 5,9 The first time you iterate through the outer side (joining it to the first chunk), you emit as matched 7,7 10,10 and write to unmatched tuples file 5 9 11 11 The second time you iterate through the outer side (joining it to the second chunk) you emit as matched 7,7 Then, you iterate again through the outer side a third time to join it to the unmatched tuples in the unmatched tuples file (from the first chunk) and write the following to a new unmatched tuples file: 5 9 11 11 The fourth time you iterate through the outer side (joining it to the third chunk), you emit as matched 5,5 9,9 Then you iterate a fifth time through the outer side to join it to the unmatched tuples in the unmatched tuples file (from the second chunk) and write the following to a new unmatched tuples file: 11 11 Now that all chunks from the inner side have been processed, you can loop through the final unmatched tuples file, NULL-extend, and emit them Wouldn't that work? -- Melanie Plageman
