SQLite Forum

Nearest-match join
Thanks everyone for your solutions and sorry for not following-up sooner.

I spend more time writing C++ than SQL and in my mind I have an "obvious" algorithm for this problem - I would concurrently scan both tables sequentially using by-timestamp indexes. If the first table has N rows and the second table has M rows, then that is O(N+M).

If I do an exact join in SQL, it seems to do:

    |--SCAN TABLE table1
    `--SEARCH TABLE table2 USING INDEX table2_by_datetime (<expr>=?)

That is O(N log M), which is worse than O(N+M) unless M is much larger than N. In this test, table1 has 8000 rows and table 2 has 62000 rows.

There is also an index table1_by_datetime, but it's not using that. Perhaps the query planner has looked at the sizes of the tables and decided that this is better. Does sqlite have a join implementation that scans two indexes?

It may also be significant that my indexes and join use the datetime() function:

    create index table1_by_datetime on table1( datetime(timestamp) );
    create index table2_by_datetime on table2( datetime(timestamp) );
    select * from table1 join table2 on( datetime(table1.timestamp) == datetime(table2.timestamp) );

Anyway... if that query plan for the exact join is the best, then I can believe that some of the solutions you've posted above may be have the same cost. I will investigate.

I envisage eventually having hundreds of thousands of rows in the first table and tens of millions of rows in the second table.