In many data processing systems it is common to want to combine historical data at some point in time together with the decision made for that data at that time. In the case of feature stores, it is used to generate training data sets based on historical user behavior and the previous decisions made by the machine learning engine. In many other cases it is also common to want to make a time series data combination between two sets. There are two important aspects to this join, we cannot combine a label with future data, i.e.: temporal correctness must be respected, and this join is usually done on big data sets where performance and memory efficiency have high value. Many feature store solutions exist, and many types of data processing engines exist, but there is no industry standard agreement on how to perform this specific type of time series join. This thesis explores a version of the point-in-time correct join algorithm that is based on the Sort-Merge Join algorithm used by many data processing engines when performing some SQL specified join. The point-in- time correct join can be done in SQL via union or via a left join, but it leads to intermediate data or many passes over the entire dataset. A modification of Sort-Merge Join which is dubbed Early Stop Sort-Merge can perform a type of left join which avoids generating extra rows by stopping early. We base our research on previous work which explores the same conceptual algorithm for Apache Spark, but Apache Flink has a different runtime engine with a different way to utilize memory, and it is stateful. The results indicates that the Early Stop Sort-Merge performs better overall except for a few specific cases, and it also avoids unnecessary intermediate data which reduces memory footprint.

I många databehandlingssystem är det vanligt att man någon gång vill kombinera historisk data tillsammans med det beslut som fattats för den datan vid den tidpunkten. När det gäller funktionsbutiker används den för att generera träningsdatauppsättningar baserat på historiskt användarbeteende och de tidigare beslut som tagits av maskininlärningsmotorn. I många andra fall är det också vanligt att man vill göra en tidsseriedatakombination mellan två uppsättningar. Det finns två viktiga aspekter på denna join, vi kan inte kombinera en etikett från en maskininlärning med framtida data, dvs: temporal korrekthet måste respekteras, och denna join görs vanligtvis på stora datamängder där prestanda och minneseffektivitet har högt värde. Det finns många funktionsbutikslösningar och många typer av databehandlingsmotorer finns, men det finns ingen branschstandardöverenskommelse om hur man utför denna specifika typ av tidsseriekoppling. Det här examensarbetet utforskar en version av algoritmen för den korrekta tidpunkten som är baserad på Sort- Merge Join-algoritmen som används av många databehandlingsmotorer när de utför någon SQL-specificerad join. Tidpunktens korrekta join kan göras i SQL via union eller via en left join, men det leder till mellanliggande data eller många pass över hela datasetet. En modifiering av Sort-Merge Join som kallas Early Stop Sort-Merge kan utföra en typ av vänster-join som undviker att generera extra rader genom att stoppa tidigt. Vi baserar vår forskning på tidigare arbete som utforskar samma konceptuella algoritm för Apache Spark, men Apache Flink har en annan runtime-motor med olika sätt att utnyttja minnet, och den är tillståndsfull. Resultaten indikerar att Early Stop Sort-Merge presterar bättre överlag med undantag för några få specifika fall, och den undviker också onödiga mellanliggande data vilket minskar minnesfotavtrycket.