The native language in Bali is bahasa Bali (Balinese). The official language in Indonesia is bahasa Indonesia (not Malay as you said, due to political reasons the two languages have separated). Anyway, Bahasa Indonesia is used by all people for education, government and almost everything else in Indonesia. You definitely should choose Bahasa Indonesia since it is spoken by all people in Bali and all other islands of Indonesia. Also, people in the touristic places will be able to understand basic English words and you can manage by English only, but it will be nicer if you use some Bahasa Indonesia words and people there will respect that.
Here are some few words that can help you get by:
- Yes: Ya
- No: Tidak or Nggak
- Hello: Halo or Salam
- How are you: Apa kabar
- Fine: Baik
- Please: Tolong
- Excuse me: Permisi
- Sorry: Maaf
- Thank you: Terima kasih
- You are welcome: Sama sama
- How much: Berapa
- Where: Dimana
- What: Apa
- When: Kapan
- Restaurant: Restoran
- Toilet: Kamar mandi or just use toilet
- Room: Kamar
- Food: Makanan
- Hospital: Rumah sakit
- Airport: Bandara
- Beach: Pantai
- Expensive: Mahal
- Me, I: Saya or Aku
- I want: Saya mau
Remember, the letter C in Indonesian is pronounced as CH.
P.S. I speak Bahasa Indonesia and I always managed by just Bahasa Indonesia anywhere in Indonesia.