Why is it faster to create index and run query than run query without it?
The reason is the you repeatedly scan the Logs table. And you even have two cross apply in that query. The repeated scanning of this table is evidently more expensive than building the index and then using that index.
Nothing strange or unexpected here.
SQL Server could possibly do an index spool so it can used that for each visit to the Logs table. Perhaps the optimizer evaluated that strategy and discarded it since its estimates showed that it wouldn't be beneficial (incorrectly, perhaps). One very first step would be to study the execution plan, the estimates compared to actual values and take it from there.