Consider the following aggregation on a uniform collection with a [0,999999] (with an index on {a:1}

[
	{
		"$match" : {
			"$and" : [
				{
					"a" : {
						"$gte" : 500000
					}
				},
				{
					"a" : {
						"$lte" : 700000
					}
				}
			]
		}
	},
	{
		"$sample" : {
			"size" : 25
		}
	}
]

This will examine 200001 documents, but in this case, only the record locator needs to be random sorted and 25 documents fetched after record locators are chosen.