The transaction originating from Oraclize to your __callback function costs gas, just like any other transaction. You need to pay Oraclize the gas cost. The ether oraclize_query charges to make a query are also used to provide gas while calling the __callback function. By default, Oraclize provides 200,000 gas while calling the __callback function.

This return gas cost is actually in your control since you write the code in the __callback method and as such, can estimate it. So, when placing a query with Oraclize, you can also specify how much the gasLimit should be on the __callback transaction. Note, however, that since Oraclize sends the transaction, any unspent gas is returned to Oraclize, not you.

If the default, and minimum, value of 200,000 gas is not enough, you can increase it by specifying a different gasLimit in this way:

oraclize_query("WolframAlpha", "random number between 0 and 100", 500000);

Here, you can see that if the last argument is a number, then it's assumed to be the custom gas. In the preceding code, Oraclize will use a 500k gasLimit for the callback transaction instead of 200k. Because we are asking Oraclize to provide more gas, Oraclize will deduct more ether (depending on how much gas is required) while calling oraclize_query.