Use sort based merge for CompactedRecordScanner & MergeHandle #314

https://github.com/uber/hudi/issues/314

## JIRA info

- Link: https://issues.apache.org/jira/browse/HUDI-50
- Type: New Feature

---

## Comments

02/Apr/19 19:52;jingc;hi [~vc], was CompactedRecordScanner removed/moved? I don't see that file, could you provide any update on this ticker?

 ;;;

---

03/Apr/19 17:18;vinoth;I guess I was writing offhand.. Actual class name is `_RealtimeCompactedRecordReader_`. You can look at the class hierarchy of AbstractRealtimeRecordReader for more understanding.. 

 

Happy to provide more context into this ticket, if needed. Its pretty involved.. ;;;

---

03/Apr/19 22:35;jingc;thanks [~vc], please share some insights;;;

---

08/Apr/19 01:49;vinoth;So... Here's a fully brain dump as promised.. 

 

Basic idea here is to ensure all files written by Hudi (HoodieCreateHandle, HoodieMergeHandle) and data in log files (HoodieAppendHandle) are sorted by _`_hoodie_record_key`_ . This will unlock few benefits 

 
* During ingestion/compaction we move away from memory-intensive hash-join between incoming records and file on disk. Instead, we would do a merge-sort like running streaming merge. 
* Similarly, on RealtimeInputFormat (code paths will ultimately invoke RealtimeCompactedRecordReader), since the base file and the log data blocks are all individually sorted, we can just do a N-way sort merge to serve queries. Once again reducing the amount of memory needed to merge. 

 

The implementation could be pretty challenging, in the sense, we need to support older data written un-sorted on disk already. Otherwise, we have to force a heavy upgrade cost for users to rewrite their existing data in such a manner.. May be there are more scenarios like this too.. 

 

Again, this is pretty involved. but could be super useful. So happy to jam on this if you are interested. :) 

[~jingc]

 

 

 ;;;

---

08/Apr/19 03:10;jingc;thanks [~vc], I would love to work on the ticket.;;;

---

09/Apr/19 17:18;vinoth;Awesome.. [~vbalaji] +  [~nishith29] as FYI.. This would also be fun.. Since its a technically deep one :) ;;;

---

09/Apr/19 17:32;nishith29;That's awesome [~jingc]! Great to see this initiative, this is critical component of providing sorted data on disk, always and has deep implications on writer and reader both.

Vinoth already pointed out the classes that you should look at, that's a good starting point. I would suggest taking the following approach :
# Go through the class hierarchy first to understand the code structure. 
# Summarize your understanding of the problem in detail
# Detail out your approach to make sort-merge happen (for readers and writers)

We can have an initial (and short) back-and-forth on this Jira. Once you are more clear on the problem and solution, you can propose a HIP where we can provide detailed comments and feedback on the problem and the use-cases it can un-lock. 

[~vc] [~varadarb] Let me know if this sounds good to you too.;;;

---

09/Apr/19 20:08;jingc;[~vc] [~nishith29] thanks for your sharing.

Hopefully I could come up with an design doc for the feature shortly :) ;;;

---

24/May/23 07:59;kongwei;[~vinoth] [~nishith29] [~rmahindra] [~jingc] hi, is this ticket still active, or already achieved? sound useful for both reader and writer;;;

Start with the class hierarchy around AbstractRealtimeRecordReader and RealtimeCompactedRecordReader, then inspect HoodieCreateHandle, HoodieMergeHandle, and HoodieAppendHandle. Clarify the design for sort-merge readers and writers, including compatibility with older unsorted data; done means Hudi-written files and log data are sorted by _hoodie_record_key without requiring an immediate rewrite of existing data.

Written by the indexing model from the issue text.