Background check is done by the RCMP in connection with CSIS. It all depends on a lot of things. Your country of origin, your current location, how long you've been at the location, what countries you've travelled to. It should be relatively easy for anyone who hasn't gone home in over a year. The only issue that can happen is if many people bear your name also. For example in India, every girl born in Sikh is given the last name 'Kaur' and every man born is given 'Singh' (please correct me if i'm wrong). Let's assume your first name is amit...I tell u dat a lot of people wl have the same name as you. If any of them should have a criminal record, then it will slow down yours a little bit. That's the essence of submitting a finger print with your police certificate. It helps to distinguish you.
In all, background check can be very fast & can also be very slow. If you've visited some countries in the middle east, expect that they will do further verifications on you. This doesn't mean you are a bad person.
