An apparatus, system, and method are disclosed for scanning a partitioned data set (“PDS”). A receive module is included to receive a search criteria comprising one or more expressions. A member module is included to determine a set of PDS members to search based on the search criteria. A scan module is included to scan a record contained within each member of the set of PDS members. A determination module is included to determine whether a record satisfies the search criteria, where the search criteria comprises at least one expression that identifies a record that lacks a specified character string of the at least one expression. A return module is included to return the determined record. Each record in the scanned PDS has any length within a range supported by an operating system maintaining the scanned PDS.