var query = Query.All<MyEntity>()
  .Where(i => i.IsFtIndexUpToDate == false)
  .Select(i => i.Key)
  .Take(100);
query.ToList();

generates the SQL:

SELECT TOP 100 [a].[Id] 
FROM [dbo].[MyEntity] [a] 
WHERE ([a].[IsFtIndexUpToDate] = 0) 
ORDER BY [a].[Id] ASC;

which takes 30s on our database, due to the order by.

Why this LINQ query does not generate this SQL (without order by) ?

SELECT TOP 100 [a].[Id] 
FROM [dbo].[MyEntity] [a] 
WHERE ([a].[IsFtIndexUpToDate] = 0);

That takes less than one second to execute.

In that case we do not want the result in a particular order : we do not care if we get an unordered result set. Actually the performance hit of the order by is so important that it causes timeouts.

I understand the idea behind the automatically added OrderBy but this is into relevant to our case. How can we write this query in LINQ without an order by in SQL?

If you keep this behavior, it should be documented in manual.