"Should I make a Stored procedure that receives arrays and just send all - potentially thousands - of the records in one single call to that SP? Or should I limit it to a certain amount of records at a time and call that SP (records/limit) amount of times?"
Limit to a certain amount of records. I generally start with between 100 and 1000, depending on the total size of a record.
"Or should I stay away from using arrays, and have a stored procedure that just receives the information for one record, and call it as many times as I have records?"
No. You will waste CPU and above all time: every time Java calls the database there is time spent just on sending the message and getting the reply back (related to "latency").
"If I were to do multiple calls, I was thinking of utilizing PreparedStatements and the .addBatch() and .executeBatch() methods, would this be the way to go?"
Yes, but those methods are at their best with SQL statements (such as INSERT), not calls to stored procedures.
I need to be able to insert all the records, and rollback in case of any error.
Set autocommit off (which I recommend in general) and commit when all is OK.
If your stored procedures have no added value, but simply do the inserts, then it would be simpler and very efficient to do batched inserts. There are very good arguments for using stored procedures despite the extra complication, but then you would have to populate the arrays.
In every case, it is vital to use bind variables and not concatenate the values into the SQL statements (or calls to SPs) as literals.
Best regards, Stew Ashton
P.S. for 5k+ records, multi-threading is overkill.