ASOF Join — From Scratch

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.11%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22marimo%22%2C%0A%23%20%20%20%20%20%22altair%3D%3D5.5.0%22%2C%0A%23%20%20%20%20%20%22pandas%3D%3D2.3.0%22%2C%0A%23%20%5D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.22.5%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22%2C%20app_title%3D%22ASOF%20Join%20%E2%80%94%20From%20Scratch%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20ASOF%20Join%20%E2%80%94%20From%20Scratch%0A%0A%20%20%20%20This%20notebook%20builds%20an%20ASOF%20join%20algorithm%20step%20by%20step%20in%20pure%20Python%2C%0A%20%20%20%20using%20the%20trades%2Fquotes%20domain%20that%20motivated%20the%20concept%20in%20the%20first%20place.%0A%0A%20%20%20%20**Sections%3A**%0A%20%20%20%201.%20The%20data%20%E2%80%94%20synthetic%20trades%20and%20quotes%20for%20three%20tickers%0A%20%20%20%202.%20The%20problem%20%E2%80%94%20what%20we%20want%2C%20visually%0A%20%20%20%203.%20The%20naive%20way%20%E2%80%94%20inequality%20join%20%2B%20dedup%2C%20and%20why%20it%20explodes%0A%20%20%20%204.%20The%20sort-merge%20algorithm%20%E2%80%94%20two-pointer%20merge%2C%20step%20by%20step%0A%20%20%20%205.%20Hash%20%2B%20binary%20search%20%E2%80%94%20ClickHouse's%20approach%0A%20%20%20%206.%20How%20they%20differ%20%E2%80%94%20visual%20comparison%0A%20%20%20%207.%20Three-way%20comparison%20%E2%80%94%20same%20results%2C%20different%20costs%0A%20%20%20%208.%20Tolerance%20%E2%80%94%20bounding%20the%20lookback%20window%0A%0A%20%20%20%20See%20the%20companion%20notes%3A%0A%20%20%20%20%5BASOF%20Join%5D(..%2F..%2F2%2520-%2520Areas%2FTech%2FData%2FDatabases%2FASOF%2520Join.md)%20%C2%B7%0A%20%20%20%20%5BImplementation%20Strategies%5D(..%2F..%2F2%2520-%2520Areas%2FTech%2FData%2FDatabases%2FASOF%2520Join%2520%25E2%2580%2594%2520Implementation%2520Strategies.md)%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%201.%20The%20Data%0A%0A%20%20%20%20We%20generate%20synthetic%20**trades**%20and%20**quotes**%20for%20three%20tickers%20over%20a%0A%20%20%20%20short%20time%20window.%20Quotes%20arrive%20more%20frequently%20than%20trades%20%E2%80%94%20this%20is%0A%20%20%20%20realistic%3A%20exchanges%20publish%20quotes%20continuously%2C%20but%20trades%20only%20happen%0A%20%20%20%20when%20a%20buyer%20and%20seller%20agree.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20pandas%20as%20pd%0A%20%20%20%20from%20datetime%20import%20datetime%2C%20timedelta%0A%20%20%20%20import%20random%0A%0A%20%20%20%20random.seed(42)%0A%0A%20%20%20%20_tickers%20%3D%20%5B%22AAPL%22%2C%20%22GOOG%22%2C%20%22MSFT%22%5D%0A%20%20%20%20_base%20%3D%20datetime(2026%2C%204%2C%2028%2C%2010%2C%200%2C%200)%0A%0A%20%20%20%20%23%20Generate%20quotes%3A%20~5%20per%20ticker%20per%20second%20(frequent)%0A%20%20%20%20_quotes_rows%20%3D%20%5B%5D%0A%20%20%20%20for%20_t%20in%20_tickers%3A%0A%20%20%20%20%20%20%20%20_price%20%3D%20%7B%22AAPL%22%3A%20182.50%2C%20%22GOOG%22%3A%20141.00%2C%20%22MSFT%22%3A%20420.00%7D%5B_t%5D%0A%20%20%20%20%20%20%20%20_ts%20%3D%20_base%0A%20%20%20%20%20%20%20%20for%20_i%20in%20range(30)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ts%20%3D%20_ts%20%2B%20timedelta(milliseconds%3Drandom.randint(50%2C%20400))%0A%20%20%20%20%20%20%20%20%20%20%20%20_price%20%2B%3D%20random.uniform(-0.10%2C%200.10)%0A%20%20%20%20%20%20%20%20%20%20%20%20_quotes_rows.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22time%22%3A%20_ts%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22ticker%22%3A%20_t%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22bid%22%3A%20round(_price%2C%202)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22ask%22%3A%20round(_price%20%2B%200.05%2C%202)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D)%0A%0A%20%20%20%20quotes%20%3D%20pd.DataFrame(_quotes_rows).sort_values(%22time%22).reset_index(drop%3DTrue)%0A%0A%20%20%20%20%23%20Generate%20trades%3A%20~1%20per%20ticker%20per%20second%20(sparse)%0A%20%20%20%20_trades_rows%20%3D%20%5B%5D%0A%20%20%20%20for%20_t%20in%20_tickers%3A%0A%20%20%20%20%20%20%20%20_ts%20%3D%20_base%20%2B%20timedelta(milliseconds%3Drandom.randint(100%2C%20500))%0A%20%20%20%20%20%20%20%20for%20_i%20in%20range(8)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ts%20%3D%20_ts%20%2B%20timedelta(milliseconds%3Drandom.randint(200%2C%201500))%0A%20%20%20%20%20%20%20%20%20%20%20%20_trades_rows.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22time%22%3A%20_ts%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22ticker%22%3A%20_t%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22volume%22%3A%20random.choice(%5B100%2C%20200%2C%20500%2C%201000%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D)%0A%0A%20%20%20%20trades%20%3D%20pd.DataFrame(_trades_rows).sort_values(%22time%22).reset_index(drop%3DTrue)%0A%20%20%20%20return%20pd%2C%20quotes%2C%20trades%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20quotes%2C%20trades)%3A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20**%7Blen(trades)%7D%20trades**%20and%20**%7Blen(quotes)%7D%20quotes**%20across%203%20tickers.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20quotes%2C%20trades)%3A%0A%20%20%20%20mo.hstack(%5B%0A%20%20%20%20%20%20%20%20mo.vstack(%5Bmo.md(%22%23%23%23%20Trades%20(sparse)%22)%2C%20trades%5D)%2C%0A%20%20%20%20%20%20%20%20mo.vstack(%5Bmo.md(%22%23%23%23%20Quotes%20(frequent)%22)%2C%20quotes.head(15)%5D)%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%202.%20The%20Problem%0A%0A%20%20%20%20For%20each%20trade%2C%20we%20want%20to%20find%20**the%20most%20recent%20quote%20for%20the%20same%0A%20%20%20%20ticker%20at%20or%20before%20the%20trade%20time**.%20This%20is%20the%20classic%20trade-time%0A%20%20%20%20quote%20lookup%20%E2%80%94%20the%20operation%20that%20kdb%2B%20was%20built%20to%20do.%0A%0A%20%20%20%20Visually%3A%20each%20trade%20(vertical%20line)%20should%20snap%20to%20the%20most%20recent%0A%20%20%20%20quote%20(dot)%20to%20its%20left%20for%20the%20same%20ticker.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(alt%2C%20mo%2C%20quotes%2C%20trades)%3A%0A%20%20%20%20_ticker_sel%20%3D%20%22AAPL%22%0A%20%20%20%20_q%20%3D%20quotes%5Bquotes%5B%22ticker%22%5D%20%3D%3D%20_ticker_sel%5D.copy()%0A%20%20%20%20_t%20%3D%20trades%5Btrades%5B%22ticker%22%5D%20%3D%3D%20_ticker_sel%5D.copy()%0A%0A%20%20%20%20_quote_chart%20%3D%20alt.Chart(_q).mark_circle(size%3D60%2C%20color%3D%22%2366BB6A%22).encode(%0A%20%20%20%20%20%20%20%20x%3Dalt.X(%22time%3AT%22%2C%20title%3D%22Time%22)%2C%0A%20%20%20%20%20%20%20%20y%3Dalt.Y(%22bid%3AQ%22%2C%20title%3D%22Price%22%2C%20scale%3Dalt.Scale(zero%3DFalse))%2C%0A%20%20%20%20%20%20%20%20tooltip%3D%5B%22time%3AT%22%2C%20%22bid%3AQ%22%5D%2C%0A%20%20%20%20)%0A%0A%20%20%20%20_trade_rules%20%3D%20alt.Chart(_t).mark_rule(color%3D%22%23E57373%22%2C%20strokeWidth%3D2).encode(%0A%20%20%20%20%20%20%20%20x%3D%22time%3AT%22%2C%0A%20%20%20%20%20%20%20%20tooltip%3D%5B%22time%3AT%22%2C%20%22volume%3AQ%22%5D%2C%0A%20%20%20%20)%0A%0A%20%20%20%20_chart%20%3D%20(_quote_chart%20%2B%20_trade_rules).properties(%0A%20%20%20%20%20%20%20%20width%3D600%2C%20height%3D250%2C%0A%20%20%20%20%20%20%20%20title%3Df%22%7B_ticker_sel%7D%3A%20Quotes%20(green%20dots)%20and%20Trades%20(red%20lines)%22%0A%20%20%20%20)%0A%20%20%20%20mo.ui.altair_chart(_chart)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%203.%20The%20Naive%20Way%20%E2%80%94%20Inequality%20Join%20%2B%20Dedup%0A%0A%20%20%20%20Without%20a%20native%20ASOF%20join%2C%20you'd%20write%3A%0A%0A%20%20%20%20%60%60%60sql%0A%20%20%20%20SELECT%20*%20FROM%20(%0A%20%20%20%20%20%20SELECT%20t.*%2C%20q.bid%2C%0A%20%20%20%20%20%20%20%20ROW_NUMBER()%20OVER%20(%0A%20%20%20%20%20%20%20%20%20%20PARTITION%20BY%20t.ticker%2C%20t.time%0A%20%20%20%20%20%20%20%20%20%20ORDER%20BY%20q.time%20DESC%0A%20%20%20%20%20%20%20%20)%20AS%20rn%0A%20%20%20%20%20%20FROM%20trades%20t%0A%20%20%20%20%20%20JOIN%20quotes%20q%0A%20%20%20%20%20%20%20%20ON%20t.ticker%20%3D%20q.ticker%20AND%20t.time%20%3E%3D%20q.time%0A%20%20%20%20)%20sub%20WHERE%20rn%20%3D%201%3B%0A%20%20%20%20%60%60%60%0A%0A%20%20%20%20Let's%20implement%20this%20in%20Python%20and%20count%20the%20intermediate%20rows.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20quotes%2C%20trades)%3A%0A%20%20%20%20%23%20Step%201%3A%20inequality%20join%20%E2%80%94%20every%20trade%20matched%20against%20every%20older%20quote%0A%20%20%20%20%23%20%20%20%20%20%20%20%20%20for%20the%20same%20ticker%0A%20%20%20%20_intermediate%20%3D%20trades.merge(quotes%2C%20on%3D%22ticker%22%2C%20suffixes%3D(%22_trade%22%2C%20%22_quote%22))%0A%20%20%20%20_intermediate%20%3D%20_intermediate%5B%0A%20%20%20%20%20%20%20%20_intermediate%5B%22time_trade%22%5D%20%3E%3D%20_intermediate%5B%22time_quote%22%5D%0A%20%20%20%20%5D%0A%0A%20%20%20%20%23%20Step%202%3A%20dedup%20%E2%80%94%20keep%20only%20the%20most%20recent%20quote%20per%20trade%0A%20%20%20%20_intermediate%20%3D%20_intermediate.sort_values(%22time_quote%22%2C%20ascending%3DFalse)%0A%20%20%20%20naive_result%20%3D%20_intermediate.groupby(%0A%20%20%20%20%20%20%20%20%5B%22ticker%22%2C%20%22time_trade%22%5D%2C%20sort%3DFalse%0A%20%20%20%20).first().reset_index()%0A%20%20%20%20naive_result%20%3D%20naive_result%5B%0A%20%20%20%20%20%20%20%20%5B%22time_trade%22%2C%20%22ticker%22%2C%20%22volume%22%2C%20%22time_quote%22%2C%20%22bid%22%5D%0A%20%20%20%20%5D.sort_values(%22time_trade%22).reset_index(drop%3DTrue)%0A%20%20%20%20naive_result.columns%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%22trade_time%22%2C%20%22ticker%22%2C%20%22volume%22%2C%20%22quote_time%22%2C%20%22bid%22%2C%0A%20%20%20%20%5D%0A%0A%20%20%20%20intermediate_count%20%3D%20len(_intermediate)%0A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20**Intermediate%20rows%20after%20inequality%20join%3A**%20%7Bintermediate_count%3A%2C%7D%0A%20%20%20%20(from%20%7Blen(trades)%7D%20trades%20%C3%97%20%7Blen(quotes)%7D%20quotes%20per%20ticker)%0A%0A%20%20%20%20**Final%20rows%20after%20dedup%3A**%20%7Blen(naive_result)%7D%0A%0A%20%20%20%20The%20intermediate%20result%20is%20**%7Bintermediate_count%20%2F%20len(naive_result)%3A.0f%7D%C3%97%0A%20%20%20%20larger**%20than%20the%20final%20output.%20With%20real%20data%20(millions%20of%20quotes)%2C%0A%20%20%20%20this%20ratio%20can%20be%2010%2C000%C3%97%20or%20more%20%E2%80%94%20enough%20to%20spill%20to%20disk%20or%20OOM.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%20intermediate_count%2C%20naive_result%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20naive_result)%3A%0A%20%20%20%20mo.vstack(%5Bmo.md(%22%23%23%23%20Naive%20result%22)%2C%20naive_result%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%204.%20The%20Sort-Merge%20ASOF%20Join%0A%0A%20%20%20%20The%20core%20algorithm%20used%20by%20DuckDB%2C%20Polars%2C%20and%20pandas.%20Two%20phases%3A%0A%0A%20%20%20%20**Phase%201%20%E2%80%94%20Group%20and%20sort.**%20Group%20both%20tables%20by%20the%20equality%20key%0A%20%20%20%20(ticker).%20Within%20each%20group%2C%20sort%20both%20sides%20by%20timestamp.%20No%20hash%0A%20%20%20%20table%20%E2%80%94%20this%20is%20purely%20sort-based.%0A%0A%20%20%20%20**Phase%202%20%E2%80%94%20Two-pointer%20merge%20(per%20group).**%20For%20each%20ticker%2C%20walk%0A%20%20%20%20through%20the%20sorted%20trades%20and%20sorted%20quotes%20simultaneously%20with%20two%0A%20%20%20%20pointers.%20For%20each%20trade%2C%20advance%20the%20quote%20pointer%20forward%20until%20it%0A%20%20%20%20passes%20the%20trade%20time.%20The%20match%20is%20the%20quote%20just%20before%20that%20point.%0A%0A%20%20%20%20The%20quote%20pointer%20**never%20moves%20backward**.%20Each%20trade%20picks%20up%20where%0A%20%20%20%20the%20last%20one%20left%20off.%20So%20the%20merge%20phase%20is%20a%20single%20linear%20pass%3A%0A%20%20%20%20%24O(n%20%2B%20m)%24.%20The%20sort%20is%20%24O(n%20%5Clog%20n)%24.%0A%0A%20%20%20%20Below%2C%20%60asof_join_sort_merge%60%20implements%20this%20exactly.%20Read%20the%20code%20%E2%80%94%0A%20%20%20%20the%20inner%20loop%20is%20just%20a%20%60while%60%20that%20advances%20%60j%60%20forward.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(pd)%3A%0A%20%20%20%20def%20asof_join_sort_merge(%0A%20%20%20%20%20%20%20%20left%3A%20pd.DataFrame%2C%0A%20%20%20%20%20%20%20%20right%3A%20pd.DataFrame%2C%0A%20%20%20%20%20%20%20%20*%2C%0A%20%20%20%20%20%20%20%20on_eq%3A%20str%2C%0A%20%20%20%20%20%20%20%20on_ts%3A%20str%2C%0A%20%20%20%20%20%20%20%20tolerance%3A%20pd.Timedelta%20%7C%20None%20%3D%20None%2C%0A%20%20%20%20)%20-%3E%20tuple%5Bpd.DataFrame%2C%20list%5Bdict%5D%5D%3A%0A%20%20%20%20%20%20%20%20%22%22%22Sort-merge%20ASOF%20join%20(backward)%20with%20step-by-step%20trace.%0A%0A%20%20%20%20%20%20%20%20Returns%20(result_df%2C%20trace_steps)%20where%20trace_steps%20records%20pointer%0A%20%20%20%20%20%20%20%20positions%20at%20each%20iteration%20for%20visualization.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20results%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20trace%20%3D%20%5B%5D%0A%0A%20%20%20%20%20%20%20%20%23%20Phase%201%3A%20Group%20by%20equality%20key%2C%20sort%20each%20group%20by%20timestamp%0A%20%20%20%20%20%20%20%20left_groups%20%3D%20left.groupby(on_eq)%0A%20%20%20%20%20%20%20%20right_sorted_by_key%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20key%3A%20grp.sort_values(on_ts).reset_index(drop%3DTrue)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20key%2C%20grp%20in%20right.groupby(on_eq)%0A%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20%20%20%20%20for%20key%2C%20left_grp%20in%20left_groups%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20left_sorted%20%3D%20left_grp.sort_values(on_ts).reset_index(drop%3DTrue)%0A%20%20%20%20%20%20%20%20%20%20%20%20right_sorted%20%3D%20right_sorted_by_key.get(key)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20right_sorted%20is%20None%20or%20len(right_sorted)%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20_%2C%20row%20in%20left_sorted.iterrows()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20results.append(%7B**row.to_dict()%2C%20%22quote_time%22%3A%20None%2C%20%22bid%22%3A%20None%7D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Phase%202%3A%20Two-pointer%20merge%20within%20this%20group%0A%20%20%20%20%20%20%20%20%20%20%20%20j%20%3D%200%20%20%23%20quote%20pointer%20%E2%80%94%20only%20moves%20forward%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20i%2C%20left_row%20in%20left_sorted.iterrows()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20left_ts%20%3D%20left_row%5Bon_ts%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Advance%20j%20while%20right%5Bj%5D.ts%20%3C%3D%20left_ts%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20j%20%3C%20len(right_sorted)%20and%20right_sorted.loc%5Bj%2C%20on_ts%5D%20%3C%3D%20left_ts%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20j%20%2B%3D%201%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Match%20is%20at%20j-1%20(last%20quote%20not%20exceeding%20trade%20time)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20match_idx%20%3D%20j%20-%201%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20match_idx%20%3E%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20match_row%20%3D%20right_sorted.loc%5Bmatch_idx%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20gap%20%3D%20left_ts%20-%20match_row%5Bon_ts%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20tolerance%20is%20not%20None%20and%20gap%20%3E%20tolerance%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20results.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20**left_row.to_dict()%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22quote_time%22%3A%20None%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22bid%22%3A%20None%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20results.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20**left_row.to_dict()%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22quote_time%22%3A%20match_row%5Bon_ts%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22bid%22%3A%20match_row%5B%22bid%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20results.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20**left_row.to_dict()%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22quote_time%22%3A%20None%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22bid%22%3A%20None%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20trace.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22ticker%22%3A%20key%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22left_idx%22%3A%20int(i)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22left_ts%22%3A%20left_ts%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22right_ptr%22%3A%20j%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22match_idx%22%3A%20match_idx%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22match_ts%22%3A%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20right_sorted.loc%5Bmatch_idx%2C%20on_ts%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20match_idx%20%3E%3D%200%20else%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D)%0A%0A%20%20%20%20%20%20%20%20result_df%20%3D%20pd.DataFrame(results)%0A%20%20%20%20%20%20%20%20result_df%20%3D%20result_df.rename(columns%3D%7B%22time%22%3A%20%22trade_time%22%7D)%0A%20%20%20%20%20%20%20%20result_df%20%3D%20result_df%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B%22trade_time%22%2C%20%22ticker%22%2C%20%22volume%22%2C%20%22quote_time%22%2C%20%22bid%22%5D%0A%20%20%20%20%20%20%20%20%5D.sort_values(%22trade_time%22).reset_index(drop%3DTrue)%0A%0A%20%20%20%20%20%20%20%20return%20result_df%2C%20trace%0A%0A%20%20%20%20return%20(asof_join_sort_merge%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(asof_join_sort_merge%2C%20quotes%2C%20trades)%3A%0A%20%20%20%20merge_result%2C%20merge_trace%20%3D%20asof_join_sort_merge(%0A%20%20%20%20%20%20%20%20trades%2C%20quotes%2C%20on_eq%3D%22ticker%22%2C%20on_ts%3D%22time%22%2C%0A%20%20%20%20)%0A%20%20%20%20return%20merge_result%2C%20merge_trace%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(merge_result%2C%20mo)%3A%0A%20%20%20%20mo.vstack(%5Bmo.md(%22%23%23%23%20Sort-merge%20result%22)%2C%20merge_result%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(merge_trace%2C%20mo%2C%20pd)%3A%0A%20%20%20%20_trace_df%20%3D%20pd.DataFrame(merge_trace)%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20mo.md(%22%22%22%23%23%23%20Pointer%20trace%0A%0A%20%20%20%20Each%20row%20shows%20one%20iteration%3A%20which%20trade%20we're%20processing%20(%60left_ts%60)%2C%0A%20%20%20%20where%20the%20right%20pointer%20advanced%20to%20(%60right_ptr%60)%2C%20and%20which%20quote%0A%20%20%20%20matched%20(%60match_ts%60).%20Notice%3A%20%60right_ptr%60%20never%20goes%20backward.%22%22%22)%2C%0A%20%20%20%20%20%20%20%20_trace_df%5B%5B%22ticker%22%2C%20%22left_ts%22%2C%20%22right_ptr%22%2C%20%22match_ts%22%5D%5D%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%205.%20Hash%20%2B%20Binary%20Search%20(ClickHouse's%20Approach)%0A%0A%20%20%20%20Sort-merge%20requires%20**both%20sides%20sorted**%20before%20the%20merge%20can%20start.%0A%20%20%20%20What%20if%20the%20left%20side%20arrives%20in%20unpredictable%20order%20%E2%80%94%20say%2C%20trades%0A%20%20%20%20streaming%20in%20from%20multiple%20exchanges%20with%20no%20global%20timestamp%20ordering%3F%0A%0A%20%20%20%20Hash%20%2B%20binary%20search%20avoids%20sorting%20the%20left%20side%20entirely%3A%0A%0A%20%20%20%20**Build%20phase%20(right%20side%20only)%3A**%20Group%20quotes%20by%20ticker%20into%20a%20hash%0A%20%20%20%20table.%20Within%20each%20bucket%2C%20store%20a%20sorted%20list%20of%20%60(timestamp%2C%20bid)%60%0A%20%20%20%20pairs.%20This%20is%20done%20once.%0A%0A%20%20%20%20**Probe%20phase%20(left%20side%2C%20any%20order)%3A**%20For%20each%20trade%20%E2%80%94%20regardless%20of%0A%20%20%20%20arrival%20order%20%E2%80%94%20do%20an%20O(1)%20hash%20lookup%20to%20find%20the%20ticker's%20bucket%2C%0A%20%20%20%20then%20**binary%20search**%20for%20the%20largest%20timestamp%20%E2%89%A4%20the%20trade%20time.%0A%20%20%20%20Cost%3A%20O(log%20k)%20per%20probe%2C%20where%20k%20is%20the%20bucket%20size.%0A%0A%20%20%20%20Each%20probe%20is%20independent%20%E2%80%94%20no%20pointer%20state%20carries%20between%20trades.%0A%20%20%20%20The%20left%20side%20does%20**not**%20need%20to%20be%20sorted.%20This%20is%20the%20key%0A%20%20%20%20difference%20from%20sort-merge%2C%20where%20both%20sides%20must%20be%20sorted%20and%20the%0A%20%20%20%20two-pointer%20state%20carries%20between%20rows.%0A%0A%20%20%20%20Below%2C%20we%20deliberately%20shuffle%20the%20trades%20into%20random%20order%20before%0A%20%20%20%20probing%2C%20to%20show%20that%20the%20algorithm%20works%20regardless%20of%20input%20order.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(pd)%3A%0A%20%20%20%20from%20bisect%20import%20bisect_right%0A%0A%20%20%20%20def%20asof_join_hash_bisect(%0A%20%20%20%20%20%20%20%20left%3A%20pd.DataFrame%2C%0A%20%20%20%20%20%20%20%20right%3A%20pd.DataFrame%2C%0A%20%20%20%20%20%20%20%20*%2C%0A%20%20%20%20%20%20%20%20on_eq%3A%20str%2C%0A%20%20%20%20%20%20%20%20on_ts%3A%20str%2C%0A%20%20%20%20%20%20%20%20tolerance%3A%20pd.Timedelta%20%7C%20None%20%3D%20None%2C%0A%20%20%20%20)%20-%3E%20tuple%5Bpd.DataFrame%2C%20list%5Bdict%5D%5D%3A%0A%20%20%20%20%20%20%20%20%22%22%22Hash%20%2B%20binary%20search%20ASOF%20join%20(backward)%20with%20probe%20trace.%22%22%22%0A%20%20%20%20%20%20%20%20results%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20trace%20%3D%20%5B%5D%0A%0A%20%20%20%20%20%20%20%20%23%20Build%20phase%3A%20dict%20of%20sorted%20(timestamp%2C%20bid)%20lists%20per%20ticker%0A%20%20%20%20%20%20%20%20hash_table%3A%20dict%5Bstr%2C%20list%5Btuple%5D%5D%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20for%20key%2C%20grp%20in%20right.groupby(on_eq)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20sorted_grp%20%3D%20grp.sort_values(on_ts)%0A%20%20%20%20%20%20%20%20%20%20%20%20hash_table%5Bkey%5D%20%3D%20list(zip(sorted_grp%5Bon_ts%5D%2C%20sorted_grp%5B%22bid%22%5D))%0A%0A%20%20%20%20%20%20%20%20%23%20Probe%20phase%3A%20for%20each%20trade%2C%20hash%20lookup%20%2B%20binary%20search%0A%20%20%20%20%20%20%20%20for%20_%2C%20left_row%20in%20left.iterrows()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20key%20%3D%20left_row%5Bon_eq%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20left_ts%20%3D%20left_row%5Bon_ts%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20bucket%20%3D%20hash_table.get(key)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20match_ts%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20match_bid%20%3D%20None%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20bucket%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20bisect_right%20finds%20insertion%20point%3B%20idx-1%20is%20the%20last%20ts%20%3C%3D%20left_ts%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20timestamps%20%3D%20%5Bt%20for%20t%2C%20_%20in%20bucket%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20idx%20%3D%20bisect_right(timestamps%2C%20left_ts)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20idx%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20match_ts%2C%20match_bid%20%3D%20bucket%5Bidx%20-%201%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20tolerance%20is%20not%20None%20and%20(left_ts%20-%20match_ts)%20%3E%20tolerance%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20match_ts%2C%20match_bid%20%3D%20None%2C%20None%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20results.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20**left_row.to_dict()%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22quote_time%22%3A%20match_ts%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22bid%22%3A%20match_bid%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D)%0A%20%20%20%20%20%20%20%20%20%20%20%20trace.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22ticker%22%3A%20key%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22left_ts%22%3A%20left_ts%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22bucket_size%22%3A%20len(bucket)%20if%20bucket%20else%200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22bisect_idx%22%3A%20idx%20if%20bucket%20else%200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22match_ts%22%3A%20match_ts%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D)%0A%0A%20%20%20%20%20%20%20%20result_df%20%3D%20pd.DataFrame(results)%0A%20%20%20%20%20%20%20%20result_df%20%3D%20result_df.rename(columns%3D%7B%22time%22%3A%20%22trade_time%22%7D)%0A%20%20%20%20%20%20%20%20result_df%20%3D%20result_df%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B%22trade_time%22%2C%20%22ticker%22%2C%20%22volume%22%2C%20%22quote_time%22%2C%20%22bid%22%5D%0A%20%20%20%20%20%20%20%20%5D.sort_values(%22trade_time%22).reset_index(drop%3DTrue)%0A%0A%20%20%20%20%20%20%20%20return%20result_df%2C%20trace%0A%0A%20%20%20%20return%20(asof_join_hash_bisect%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(asof_join_hash_bisect%2C%20quotes%2C%20trades)%3A%0A%20%20%20%20%23%20Deliberately%20shuffle%20trades%20into%20random%20order%20%E2%80%94%20hash%2Bbisect%20doesn't%0A%20%20%20%20%23%20care%20about%20input%20order%2C%20unlike%20sort-merge%20which%20needs%20sorted%20input.%0A%20%20%20%20_shuffled_trades%20%3D%20trades.sample(frac%3D1%2C%20random_state%3D99).reset_index(drop%3DTrue)%0A%20%20%20%20bisect_result%2C%20bisect_trace%20%3D%20asof_join_hash_bisect(%0A%20%20%20%20%20%20%20%20_shuffled_trades%2C%20quotes%2C%20on_eq%3D%22ticker%22%2C%20on_ts%3D%22time%22%2C%0A%20%20%20%20)%0A%20%20%20%20return%20bisect_result%2C%20bisect_trace%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(bisect_trace%2C%20mo%2C%20pd)%3A%0A%20%20%20%20_trace_df%20%3D%20pd.DataFrame(bisect_trace)%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20mo.md(%22%22%22%23%23%23%20Probe%20trace%0A%0A%20%20%20%20Each%20row%20shows%20one%20probe%3A%20the%20trade's%20timestamp%2C%20how%20large%20the%20bucket%0A%20%20%20%20was%20(all%20quotes%20for%20that%20ticker)%2C%20and%20where%20binary%20search%20landed.%0A%20%20%20%20Each%20probe%20is%20independent%20%E2%80%94%20no%20state%20carries%20between%20rows.%22%22%22)%2C%0A%20%20%20%20%20%20%20%20_trace_df%5B%5B%22ticker%22%2C%20%22left_ts%22%2C%20%22bucket_size%22%2C%20%22bisect_idx%22%2C%20%22match_ts%22%5D%5D%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%206.%20How%20They%20Differ%20%E2%80%94%20Visually%0A%0A%20%20%20%20Both%20algorithms%20produce%20the%20same%20matches.%20The%20difference%20is%20in%0A%20%20%20%20**what%20they%20require%20from%20the%20left%20side**%20and%20**how%20the%20probe%20works**%3A%0A%0A%20%20%20%20%7C%20%7C%20Sort-merge%20%7C%20Hash%20%2B%20binary%20search%20%7C%0A%20%20%20%20%7C---%7C---%7C---%7C%0A%20%20%20%20%7C%20**Left%20side**%20%7C%20Must%20be%20sorted%20by%20timestamp%20%7C%20Any%20order%20(we%20shuffled%20it%20above)%20%7C%0A%20%20%20%20%7C%20**Right%20side**%20%7C%20Must%20be%20sorted%20by%20timestamp%20%7C%20Sorted%20once%20per%20bucket%20during%20build%20%7C%0A%20%20%20%20%7C%20**Probe**%20%7C%20Advance%20pointer%20forward%20(amortized%20O(1))%20%7C%20Binary%20search%20per%20trade%20(O(log%20k))%20%7C%0A%20%20%20%20%7C%20**State%20between%20probes**%20%7C%20Yes%20%E2%80%94%20pointer%20%60j%60%20carries%20forward%20%7C%20No%20%E2%80%94%20each%20probe%20is%20independent%20%7C%0A%20%20%20%20%7C%20**Merge%20cost**%20%7C%20O(n%20%2B%20m)%20total%20%7C%20O(n%20%C2%B7%20log%20k)%20total%20%7C%0A%0A%20%20%20%20The%20pointer%20chart%20below%20shows%20the%20sort-merge%20algorithm%20processing%0A%20%20%20%20AAPL%20trades.%20Notice%20%60j%60%20only%20increases%20%E2%80%94%20that%20monotonic%20advance%20is%0A%20%20%20%20why%20the%20merge%20is%20linear.%20Hash%2Bbisect%20has%20no%20equivalent%20chart%20because%0A%20%20%20%20there's%20no%20persistent%20pointer%20to%20track.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(alt%2C%20merge_trace%2C%20mo%2C%20pd%2C%20quotes%2C%20trades)%3A%0A%20%20%20%20_ticker%20%3D%20%22AAPL%22%0A%20%20%20%20_q%20%3D%20quotes%5Bquotes%5B%22ticker%22%5D%20%3D%3D%20_ticker%5D.sort_values(%22time%22).reset_index(drop%3DTrue)%0A%20%20%20%20_t%20%3D%20trades%5Btrades%5B%22ticker%22%5D%20%3D%3D%20_ticker%5D.sort_values(%22time%22).reset_index(drop%3DTrue)%0A%0A%20%20%20%20%23%20Build%20sort-merge%20visualization%20data%3A%20show%20the%20quote%20pointer%20position%0A%20%20%20%20%23%20after%20processing%20each%20trade%0A%20%20%20%20_sm_trace%20%3D%20%5Bt%20for%20t%20in%20merge_trace%20if%20t%5B%22ticker%22%5D%20%3D%3D%20_ticker%5D%0A%20%20%20%20_sm_rows%20%3D%20%5B%5D%0A%20%20%20%20for%20step%20in%20_sm_trace%3A%0A%20%20%20%20%20%20%20%20%23%20The%20quote%20pointer%20scanned%20from%20previous%20position%20to%20right_ptr%0A%20%20%20%20%20%20%20%20_sm_rows.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22trade_time%22%3A%20step%5B%22left_ts%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22quote_ptr_at%22%3A%20step%5B%22right_ptr%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22match_time%22%3A%20step%5B%22match_ts%22%5D%2C%0A%20%20%20%20%20%20%20%20%7D)%0A%20%20%20%20_sm_df%20%3D%20pd.DataFrame(_sm_rows)%0A%0A%20%20%20%20%23%20Quote%20timeline%3A%20show%20all%20quotes%20as%20dots%20on%20a%20horizontal%20line%0A%20%20%20%20_q_points%20%3D%20alt.Chart(_q).mark_circle(size%3D50%2C%20color%3D%22%2366BB6A%22).encode(%0A%20%20%20%20%20%20%20%20x%3Dalt.X(%22time%3AT%22%2C%20title%3D%22Time%22)%2C%0A%20%20%20%20%20%20%20%20y%3Dalt.value(20)%2C%0A%20%20%20%20%20%20%20%20tooltip%3D%5B%22time%3AT%22%2C%20%22bid%3AQ%22%5D%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Trade%20positions%3A%20red%20triangles%0A%20%20%20%20_t_points%20%3D%20alt.Chart(_t).mark_point(%0A%20%20%20%20%20%20%20%20shape%3D%22triangle-down%22%2C%20size%3D100%2C%20color%3D%22%23E57373%22%2C%20filled%3DTrue%0A%20%20%20%20).encode(%0A%20%20%20%20%20%20%20%20x%3Dalt.X(%22time%3AT%22)%2C%0A%20%20%20%20%20%20%20%20y%3Dalt.value(0)%2C%0A%20%20%20%20%20%20%20%20tooltip%3D%5B%22time%3AT%22%2C%20%22volume%3AQ%22%5D%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Sort-merge%20arrows%3A%20connect%20each%20trade%20to%20its%20matched%20quote%0A%20%20%20%20if%20len(_sm_df)%20%3E%200%20and%20_sm_df%5B%22match_time%22%5D.notna().any()%3A%0A%20%20%20%20%20%20%20%20_arrow_data%20%3D%20_sm_df%5B_sm_df%5B%22match_time%22%5D.notna()%5D.copy()%0A%20%20%20%20%20%20%20%20_arrows%20%3D%20alt.Chart(_arrow_data).mark_rule(%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22%235C6BC0%22%2C%20strokeWidth%3D1.5%2C%20opacity%3D0.7%0A%20%20%20%20%20%20%20%20).encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3D%22trade_time%3AT%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20x2%3D%22match_time%3AT%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.value(10)%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_sm_chart%20%3D%20(_q_points%20%2B%20_t_points%20%2B%20_arrows)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_sm_chart%20%3D%20(_q_points%20%2B%20_t_points)%0A%0A%20%20%20%20%23%20Pointer%20position%20line%3A%20show%20how%20j%20advances%20across%20trades%0A%20%20%20%20_ptr_chart%20%3D%20alt.Chart(_sm_df).mark_line(%0A%20%20%20%20%20%20%20%20color%3D%22%235C6BC0%22%2C%20strokeWidth%3D2%2C%20point%3DTrue%0A%20%20%20%20).encode(%0A%20%20%20%20%20%20%20%20x%3Dalt.X(%22trade_time%3AT%22%2C%20title%3D%22Trade%20time%22)%2C%0A%20%20%20%20%20%20%20%20y%3Dalt.Y(%22quote_ptr_at%3AQ%22%2C%20title%3D%22Quote%20pointer%20(j)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20scale%3Dalt.Scale(domain%3D%5B0%2C%20len(_q)%5D))%2C%0A%20%20%20%20%20%20%20%20tooltip%3D%5B%22trade_time%3AT%22%2C%20%22quote_ptr_at%3AQ%22%5D%2C%0A%20%20%20%20).properties(width%3D600%2C%20height%3D120%2C%20title%3D%22Sort-merge%3A%20quote%20pointer%20advances%20monotonically%22)%0A%0A%20%20%20%20_timeline%20%3D%20(_sm_chart).properties(%0A%20%20%20%20%20%20%20%20width%3D600%2C%20height%3D80%2C%0A%20%20%20%20%20%20%20%20title%3Df%22AAPL%3A%20trades%20(red%20%E2%96%BC)%20matched%20to%20quotes%20(green%20%E2%97%8F)%20%E2%80%94%20lines%20show%20the%20match%22%0A%20%20%20%20)%0A%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20mo.as_html(_timeline)%2C%0A%20%20%20%20%20%20%20%20mo.as_html(_ptr_chart)%2C%0A%20%20%20%20%20%20%20%20mo.md(%22%22%22%0A%20%20%20%20The%20pointer%20chart%20shows%20%60j%60%20(the%20quote%20pointer%20position)%20after%20each%0A%20%20%20%20trade%20is%20processed.%20It%20only%20goes%20up%20%E2%80%94%20never%20back%20down.%20This%20is%20why%0A%20%20%20%20the%20merge%20phase%20is%20O(n%20%2B%20m)%3A%20each%20quote%20is%20visited%20at%20most%20once.%0A%0A%20%20%20%20**Hash%20%2B%20binary%20search**%20has%20no%20pointer%20to%20track%20%E2%80%94%20each%20trade%20does%20an%0A%20%20%20%20independent%20O(log%20k)%20binary%20search.%20That%20independence%20is%20both%20the%0A%20%20%20%20strength%20(left%20side%20can%20arrive%20in%20any%20order)%20and%20the%20weakness%20(total%0A%20%20%20%20work%20is%20O(n%20%C2%B7%20log%20k)%20instead%20of%20O(n%20%2B%20m)%20for%20the%20merge%20phase).%0A%20%20%20%20%20%20%20%20%22%22%22)%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%207.%20Three-Way%20Comparison%0A%0A%20%20%20%20All%20three%20approaches%20produce%20identical%20results.%20The%20cost%20structure%0A%20%20%20%20is%20radically%20different.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20bisect_result%2C%0A%20%20%20%20bisect_trace%2C%0A%20%20%20%20intermediate_count%2C%0A%20%20%20%20merge_result%2C%0A%20%20%20%20merge_trace%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20naive_result%2C%0A%20%20%20%20pd%2C%0A%20%20%20%20quotes%2C%0A)%3A%0A%20%20%20%20_all_match%20%3D%20(%0A%20%20%20%20%20%20%20%20naive_result%5B%22bid%22%5D.equals(merge_result%5B%22bid%22%5D)%0A%20%20%20%20%20%20%20%20and%20naive_result%5B%22bid%22%5D.equals(bisect_result%5B%22bid%22%5D)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Count%20bisect%20operations%0A%20%20%20%20_total_bisect_ops%20%3D%20sum(%0A%20%20%20%20%20%20%20%20%23%20Each%20probe%20does%20O(log2(bucket_size))%20comparisons%0A%20%20%20%20%20%20%20%20int(t%5B%22bucket_size%22%5D).bit_length()%0A%20%20%20%20%20%20%20%20for%20t%20in%20bisect_trace%0A%20%20%20%20%20%20%20%20if%20t%5B%22bucket_size%22%5D%20%3E%200%0A%20%20%20%20)%0A%0A%20%20%20%20_comparison%20%3D%20pd.DataFrame(%5B%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Algorithm%22%3A%20%22Naive%20(inequality%20%2B%20dedup)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Build%20cost%22%3A%20%22%E2%80%94%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Per-trade%20cost%22%3A%20f%22scan%20all%20older%20quotes%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Intermediate%20rows%22%3A%20f%22%7Bintermediate_count%3A%2C%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Total%20comparisons%22%3A%20f%22~%7Bintermediate_count%3A%2C%7D%22%2C%0A%20%20%20%20%20%20%20%20%7D%2C%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Algorithm%22%3A%20%22Sort-merge%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Build%20cost%22%3A%20%22sort%20both%20sides%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Per-trade%20cost%22%3A%20%22advance%20pointer%20(amortized%20O(1))%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Intermediate%20rows%22%3A%20%220%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Total%20comparisons%22%3A%20f%22%7Blen(merge_trace)%7D%20pointer%20moves%22%2C%0A%20%20%20%20%20%20%20%20%7D%2C%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Algorithm%22%3A%20%22Hash%20%2B%20binary%20search%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Build%20cost%22%3A%20f%22build%20hash%20table%20(%7Blen(quotes)%7D%20inserts)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Per-trade%20cost%22%3A%20f%22O(log%20k)%20bisect%20per%20probe%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Intermediate%20rows%22%3A%20%220%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Total%20comparisons%22%3A%20f%22~%7B_total_bisect_ops%7D%20bisect%20steps%22%2C%0A%20%20%20%20%20%20%20%20%7D%2C%0A%20%20%20%20%5D)%0A%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20mo.md(f%22**All%20three%20produce%20identical%20results%3A**%20%7B'Yes'%20if%20_all_match%20else%20'NO%20%E2%80%94%20BUG!'%7D%22)%2C%0A%20%20%20%20%20%20%20%20_comparison%2C%0A%20%20%20%20%20%20%20%20mo.md(%22%22%22%0A%20%20%20%20**When%20to%20use%20which%3A**%0A%0A%20%20%20%20%7C%20Situation%20%7C%20Best%20algorithm%20%7C%20Why%20%7C%0A%20%20%20%20%7C---%7C---%7C---%7C%0A%20%20%20%20%7C%20Both%20tables%20large%2C%20similar%20size%20%7C%20**Sort-merge**%20%7C%20Single%20linear%20pass%20after%20sorting%20%7C%0A%20%20%20%20%7C%20Right%20table%20fits%20in%20memory%2C%20random%20probe%20order%20%7C%20**Hash%20%2B%20bisect**%20%7C%20O(log%20k)%20per%20probe%2C%20no%20sort%20needed%20on%20left%20%7C%0A%20%20%20%20%7C%20Left%20table%20tiny%2C%20right%20table%20huge%20%7C%20**Loop%20join**%20(not%20shown)%20%7C%20Memory%20proportional%20to%20small%20table%20only%20%7C%0A%20%20%20%20%7C%20Both%20tables%20pre-sorted%20(time-series%20DB)%20%7C%20**Streaming%20merge**%20%7C%20Skip%20the%20sort%20entirely%20%E2%80%94%20O(n%2Bm)%20%7C%0A%20%20%20%20%20%20%20%20%22%22%22)%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%208.%20Tolerance%20%E2%80%94%20Bounding%20the%20Lookback%0A%0A%20%20%20%20Sometimes%20a%20quote%20from%2010%20minutes%20ago%20is%20too%20stale%20to%20be%20useful.%0A%20%20%20%20The%20**tolerance**%20parameter%20sets%20a%20maximum%20gap%3A%20if%20the%20best%20matching%0A%20%20%20%20quote%20is%20older%20than%20the%20tolerance%2C%20return%20NULL%20instead.%0A%0A%20%20%20%20This%20is%20supported%20by%20Polars%20(%60tolerance%3D%225m%22%60)%2C%20pandas%0A%20%20%20%20(%60tolerance%3Dpd.Timedelta(%225min%22)%60)%2C%20and%20QuestDB%20(%60TOLERANCE%60%20clause).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20tolerance_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D100%2C%20stop%3D5000%2C%20step%3D100%2C%20value%3D500%2C%0A%20%20%20%20%20%20%20%20label%3D%22Tolerance%20(milliseconds)%22%2C%0A%20%20%20%20)%0A%20%20%20%20tolerance_slider%0A%20%20%20%20return%20(tolerance_slider%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(asof_join_sort_merge%2C%20mo%2C%20pd%2C%20quotes%2C%20tolerance_slider%2C%20trades)%3A%0A%20%20%20%20_tol%20%3D%20pd.Timedelta(milliseconds%3Dtolerance_slider.value)%0A%20%20%20%20_result%2C%20_%20%3D%20asof_join_sort_merge(%0A%20%20%20%20%20%20%20%20trades%2C%20quotes%2C%20on_eq%3D%22ticker%22%2C%20on_ts%3D%22time%22%2C%20tolerance%3D_tol%2C%0A%20%20%20%20)%0A%20%20%20%20_null_count%20%3D%20_result%5B%22bid%22%5D.isna().sum()%0A%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20**Tolerance%3A**%20%7Btolerance_slider.value%7Dms%20%E2%86%92%0A%20%20%20%20**%7B_null_count%7D%20trades**%20have%20no%20quote%20within%20the%20window%20(NULL%20bid).%0A%0A%20%20%20%20Drag%20the%20slider%20left%20to%20tighten%20the%20window%20%E2%80%94%20more%20trades%20lose%20their%0A%20%20%20%20match.%20Drag%20right%20to%20loosen%20it%20%E2%80%94%20all%20trades%20find%20a%20quote.%0A%20%20%20%20%20%20%20%20%22%22%22)%2C%0A%20%20%20%20%20%20%20%20_result%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20altair%20as%20alt%0A%0A%20%20%20%20return%20alt%2C%20mo%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A