Every time a request is properly handled by the server, one API call is consumed. Specifically, in regards to queries, there's two functions, named
queryMore. Every call to
queryMore counts as one API call. So, the more records you return, the more times you'll have to call queryMore, and the more API calls you'll consume. As you may know, query and queryMore are limited by a Batch Size, which means that the API consumption of a query is a function of how many results are returned and the Batch Size of that result set.
The cost complexity of the query (including sub-queries and other relationship queries) are not cost factors, although in exchange for this freedom, we do have limitations on what we can query so that the query cost has an upper limit on how many resources are used by the salesforce.com servers. For example, there's limits on query complexity, and some special per-object limits. You can read more about those limits in SOQL and SOSL Limits. Fortunately, we have several tools available to us.
First, and perhaps most importantly, is that we can optimize our queries to return as few rows as possible. If we query the entire Lead database to find just the converted leads for this week (and filtering the rest out by code), then we're causing a tremendous amount of wasted API calls. This would also be true if you were polling the server every 2 seconds for new records (for which we might be better off using the replication API or streaming API).
Second, we can increase the Batch Size of query/queryMore, which is available as SOAP QueryOptions and REST QueryOptions. If we're confident that the client app can handle the memory requirements of a really large request, we can try bumping up the batch size (we can go up to 2,000 rows of data in a request). This would have the effect of reducing the total number of API calls used for large query results. The Apex Data Loader includes an option to change the Batch Size, which can reduce the number of API calls.
Third, we can decide to use the Bulk API, which processes a query asynchronously, and then allows us to download the results in a very efficient manner. The Apex Data Loader has an option to enable the Bulk API in the menu settings. This may actually take slightly longer to get all the results, but it allows us to retrieve many more rows of data using very few API calls (in fact, the Bulk API generates results that are up to 1GB in size, which is far more efficient in terms of API calls).
Finally, we can always ask for temporary increases so we're not completely crippled. This is not a long term, permanent solution, but it can be highly effective for those one-off situations where perhaps someone accidentally set the batch size to the minimum and then queried 50,000,000 rows of data, or maybe an app was misconfigured and causing tons of wasted API calls. Support can also help us identify which apps are causing problems so we can disable/fix/block those apps as necessary.