Come trovare record quasi simili in sql?

Tale criterio di ricerca non potrà utilizzare alcun indice, ma può essere fatto...

SELECT
  *
FROM
  yourTable
WHERE
  N-M <= CASE WHEN yourTable.field1 = searchValue1 THEN 1 ELSE 0 END
       + CASE WHEN yourTable.field2 = searchValue2 THEN 1 ELSE 0 END
       + CASE WHEN yourTable.field3 = searchValue3 THEN 1 ELSE 0 END
       ...
       + CASE WHEN yourTable.fieldN = searchValueN THEN 1 ELSE 0 END

Allo stesso modo, se i tuoi criteri di ricerca sono in un'altra tabella...

SELECT
  *
FROM
  yourTable
INNER JOIN
  search
    ON N-M <= CASE WHEN yourTable.field1 = search.field1 THEN 1 ELSE 0 END
            + CASE WHEN yourTable.field2 = search.field2 THEN 1 ELSE 0 END
            + CASE WHEN yourTable.field3 = search.field3 THEN 1 ELSE 0 END
            ...
            + CASE WHEN yourTable.fieldN = search.fieldN THEN 1 ELSE 0 END

(Devi compilare il valore di N-M te stesso)

MODIFICA:

Un approccio più prolisso, che può farne alcuni uso di indici...

SELECT
    id,  -- your table would need to have a primary key / identity column
    MAX(field1)   AS field1,
    MAX(field2)   AS field2,
    MAX(field3)   AS field3,
    ...
    MAX(fieldN)   AS fieldN
FROM
(
    SELECT * FROM yourTable WHERE field1 = searchValue1
    UNION ALL
    SELECT * FROM yourTable WHERE field2 = searchValue2
    UNION ALL
    SELECT * FROM yourTable WHERE field3 = searchValue3
    ...
    SELECT * FROM yourTable WHERE fieldN = searchValueN
)
    AS unioned_seeks
GROUP BY
    id
HAVING
    COUNT(*) >= N-M

Se hai un indice su ogni campo individualmente e dove ti aspetti un numero relativamente basso di corrispondenze per ogni campo, questo potrebbe superano la prima opzione, a scapito di un codice molto ripetitivo.