title: What is the running time (big "O" order) of pandas DataFrame.join?
body: <p>This problem is more conceptual/theoretical (has to do with run times for very large datasets), so I apologize for not having a minimial example to show. </p>
  
  <p>I have a bunch of DataFrames from two different sensors that I need to eventually concatenate into two <em>very</em> large DataFrames from two different sensors (<code>df_snsr1</code> and <code>df_snsr2</code>), and then left join into a single DataFrame. My data is such that I can also join first, then concat, or some combination. I am trying to figure out the most efficient way to do this.</p>
  
  <p>From reading <a href="https://stackoverflow.com/a/36489724/2464597">this SO answer</a> I know that <a href="https://pandas.pydata.org/pandas-docs/stable/generated/pandas.concat.html" rel="noreferrer"><code>pandas.concat</code></a> allocates space for the concatenation of all of its dataframes, and if you do this in a loop it can lead to <code>O(N**2)</code> copying and some major slowdowns. Thus I am currently first building a big list of dataframes (loaded from files), concatenating them all at once, and then joining the two big dataframes:</p>
  
  <pre><code>df_list = []
  for file in my_pickle_files_snsr1:  # O(M) loop over M files
      df_list.append(pd.read_pickle(file))  # O(1) append, M times
  df_snsr1 = pd.concat(df_list)  # O(N) copies of N records
  # repeat for sensor 2 (df_snsr2)
  df_snsr1.join(df_snsr2, on=['some', 'columns'])  # O(dunno, maybe bears?)
  </code></pre>
  
  <p>I am unable to find anything about execution speed in the documentation on <a href="https://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.join.html" rel="noreferrer"><code>pandas.DataFrame.join</code></a>. Is it <code>O(N)</code>? <code>O(N**2)</code>? My thought is that if it is similar order to <code>pandas.concat</code>, then it really doesn't matter what order I do the two operations in. If it is <code>O(N**2)</code>, however, then it will likely be more efficient for me to join many small dataframes and then concatenate them rather than concat and then join. The overall operation takes long enough that it is worth-while for me to ask the question on here, so "run it and see" isn't going to work.</p>
  
  <p>Does anybody know what algorithm <code>join</code> is using and what its execution big-O order is? Or does anybody have any other suggestions on getting the most-efficient combination of <code>join</code> and <code>concat</code>?</p>