make t-sql execute faster

I would like your suggestions on how to make a sql server 2008 r2 stored procedure
to run more efficiently. The stored procdure is used as a 'search' for users to see the hitory of information before the user decide what to do with the records they are currently working with. The following is the stored procedure as it exists currently:

alter PROCEDURE [dbo].[brw_Rec]
@rId numeric(18,0),
@rId2 numeric(18,0) = NULL
AS
BEGIN

select RID,PA_ID
from app_table
WHERE (PA_ID= @rId) or (RID between @rId and @rId2) or
(PA_ID= @rId) or (PA_ID between @rId and @rId2)
END
go

This stored procedure takes too long to execute when either of the 'between' parameters
are used. The between is picking a range of values. This stored procedure can not be split up into two stored procedures since it is called by a C#.net 2008 desktop application.

Basically the same parameters a used here. The PA_ID column is the parent record and
the RID column is the child record. The PA_ID column can never have the same value that
the RID column has. This is programmed into the C#.net 2008 desktop application.

1. I see PA_ID= @rId repeated and all conditions are connected using OR. Is there an "AND" missing or a value misspelled?
2. Since you are have @rId2 as an optional parameter, Can you use IF @rId2 IS NULL and branch out to two queries?

Essentially , let me plan the main generic briefcase of any index optimization

Reaching to much index seek besides of the least I/O + CPU cost < 1 and much preferred to be < 0.1 as possible by:

· Avoiding any table scans by assuring one clustered or non clustered index is there at least

· Also index scans as possible.

· Using compound covered indexes for the important queries.

· Using compression technology for indexes and particularly more page compression.

· Using Filtered indexing according to the most generic business parameters.
· Reaching to much index seek besides of the least I/O + CPU cost < 1 and much preferred to be < 0.1 as possible.

Specifically , you could add the following simple non clustered index :

Key columns: RID,PA_ID

Hi,
A common performance problem with stored procedures is Parameter Sniffing. That means that stored procedure performs well for some parameter combinations and for some other the execution is very slow. One of the solutions for this problem is using the hint OPTION (RECOMPILE) at the end of the stored procedure definition. This option forces the SQL Server optimizer to create a new plan (at the statement level) rather than using the existing one from cache, whenever the stored procedure is invoked. Just try to put OPTION (RECOMPILE)as the last statement in the procedure definition.

Rgds,
M.