How can I speed up a stored procedure? Here is an interview question I just had. I would like to know what a good answer to this would have been and what the different options would be.


  We have a stored procedure that is taking 26 seconds to return
  information that is grabbed from 5 tables. Our server times out after
  25 seconds. How can you solve this problem?


This is not verbatim but it is close to the question that was asked. I had no clue, and I don't even think we went into that kind of detail in our db class. All I could think of telling them is to make sure that the tables are indexed and I don't even know if that is right.

Here's an example of how this could look on creation:

CREATE PROCEDURE GetOrderForCustomers(@CustID varchar(20))
AS
BEGIN
SELECT * FROM orders o
    JOIN state s ON s.stateID = o.stateID
    JOIN customers c ON c.customerID = o.customerID
    JOIN items i ON i.itemID = o.itemID
    JOIN parts p ON p.partListID = o.partListID
WHERE c.customerID = @CustID
END


Once again this would be taking slightly more time than the timeout time allows.


What are my options for speeding up this stored procedure syntactically? 
What are the different types of metadata that might help solve the problem?
What practices should be avoided that are seen in the procedure above?
(As a non-required aside question) Would it be acceptable to tell an interviewer that I would ask the real-life question on Stack Overflow?
Amazingly broad question but a couple of simple answers.  


Indexing like you suggested.  Make sure the appropriate indexes exist and if the need is great enough make sure they are all covering.
Get rid of the *.  Specify the columns you need.  If you are pulling across 100 columns over a million rows that's going to be a LOT of data.  If you only need 3 columns only specify 3 columns.
Change the timeout.  This sounds hokey but honestly sometimes it really is the answer.  SQL Server (for example) doesn't actually have a timeout so the problem is on the connection side.  Have them increase the timeout to 30 seconds (assuming this is an acceptable amount of time, and it frequently won't be).
Make sure it's the DBMS's fault.  It's very possible you are having a problem on the connection side that's causing it to take 5-10 seconds just to connect.  Fix that and you are well within your time.