Kolejność rekordów w GROUP BY Opcje

[kitol]

Mam tabelę a w niej kolumny: user_id, record_id (primary key,autoincrement), oraz inne pola z danymi.
Potrzebuję wyjąć dla każdego usera jeden najstarszy rekord (czyli ten który ma najmniejszy record_id dla danego usera). Zapytanie ma zwracać tyle wierszy ile jest userów w każdym wierszu dane (pozostałe kolumny) z najstarszego rekordu.
Zapytanie wygląda tak:

[SQL] pobierz, plaintext 
SELECT * FROM tabela GROUP BY user_id
[SQL] pobierz, plaintext 

Zauważyłem, (MySQL 5.0) że za każdym razem dla każdego usera zwracany jest wynik z najmiejszym record_id pomimo, że w zapytaniu nie mam zdefiniowanego sortowania po record_id. Czy baza przyjmuje takie sortowanie domyślnie (bo record_id jest kluczem głównym)? Czy takie wyniki będą zwracane zawsze? Czy muszę wprowadzić do zapytania klauzulę ORDER BY i LIMIT 1? Zależy mi na szybkości dla dużej ilości rekordów.