I have a new stellar core instance with CATCHUP COMPLETE true and one stellar horizon instance with INGEST true. I'm totally new with stellar. I've started the core node and it's catching up the data. I'm not sure if I have to start the horizon after core or I should wait until it's syncing if finished?
You could start Horizon anytime (before or after Core), even though Core is still catching up.
Horizon is depending on Core, and will "ingest" data after Core has processed it, little-by-little. Without Horizon, Core can still work perfectly, but not the other way around.
p.s. If you are catching up with the public main-net / test-net (where both contains tonnes of data), it could take you tens of hours... so be sure if your Core is running good, or you would have hours wasted before getting the right configurations.