Running a simple LINQ query in parallel

There is no need to abandon normal LINQ syntax to achieve parallelism. You can rewrite your original query:

var matchedStaff = from s in allStaff
    where s.Matches(searchString)
    select s;

The parallel LINQ (“PLINQ”) version would be:

var matchedStaff = from s in allStaff.AsParallel()
    where s.Matches(searchString)
    select s;

To understand where the bools are coming from, when you write the following:

var matchedStaff = allStaff.AsParallel().Select(s => s.Matches(searchString));

That is equivalent to the following query syntax:

var matchedStaff = from s in allStaff.AsParallel() select s.Matches(searchString);

As stated by darkey, if you want to use the C# syntax instead of the query syntax, you should use Where():

var matchedStaff = allStaff.AsParallel().Where(s => s.Matches(searchString));

For your first question, you should just replace Select with Where :

var matchedStaff = allStaff.AsParallel().Where(s => s.Matches(searchString));

Select is a projection operator, not a filtering one, that's why you are getting an IEnumerable<bool> corresponding to the projection of all your Staff objects from the input sequence to bools returned by your Matches method call.

I understand it can be counter intuitive for you not to use select at all as it seems you are more familiar with the "query syntax" where select keyword is mandatory which is not the case using the "lambda syntax" (or "fluent syntax" ... whatever the naming), but that's how it is ;)

Projections operators, such a Select, are taking as input an element from the sequence and transform/projects this element somehow to another type of element (here projecting to bool type). Whereas filtering operators, such as Where, are taking as input an element from the sequence and either output the element as such in the output sequence or are not outputing the element at all, based on a predicate.

As for your second question, AsEnumerable returns an IEnumerable as it's name indicates ;) If you want to get a List<Staff> you should rather call ToList() (as it's name indicates ;)) :

return allStaff.AsParallel().Select(/* something */).ToList();

Hope this helps.