Here's another method using map & grep functions. I believe this should capture all the data you need.

It only performs a single pass through the hash keys. There are no nested loops.

# hash_key_cmp

use strict;
use warnings;

# Test data

our %CVS = (
    b   => 1,
    c   => 0,
    d   => 1,
    e   => 1,
    f   => 1,
    g   => 0,
    h   => 1,
    i   => 1,
    j   => 1,
    k   => 1,
    l   => 1,
);

our %SQL = (
    x_a   => 1,
    x_b   => 1,
    x_d   => 1,
    x_e   => 1,
    x_f   => 0,
    x_g   => 1,
    x_h   => 0,
    x_i   => 1,
    x_j   => 1,
    x_l   => 1,
    x__k  => 1,
    x_m   => 0,
);


# Compare hashes

(my $prefix = (each %SQL)[0]) =~ s/^(.+_)?.*/$1/;
my $prefix_len = length $prefix;

my (@valid_in_both, @bad_in_both, @not_in_sql, @not_in_cvs);

map { exists $SQL{join '', $prefix, $_}
        ? $CVS{$_} eq $SQL{join '', $prefix, $_}
                ? push(@valid_in_both, $_)
                : push(@bad_in_both, $_)
        : push(@not_in_sql, $_)
    } keys %CVS;

@not_in_cvs = grep { ! exists($CVS{substr $_, $prefix_len}) } keys %SQ
+L;


# Output results

print 'Not in SQL:    ', "@not_in_sql", "\n";
print 'Not in CVS:    ', "@not_in_cvs", "\n";
print 'Valid in both: ', "@valid_in_both", "\n";
print 'Bad in both:   ', "@bad_in_both", "\n";
[download]

Here's the output:

[ ~/tmp ] $ perl hash_key_cmp
Not in SQL:    c k
Not in CVS:    x_a x__k x_m
Valid in both: b d e i j l
Bad in both:   f g h
[ ~/tmp ] $
[download]

Update: Changed second map to a grep. Line used to read:

map { exists($CVS{substr $_, $prefix_len}) || push(@not_in_cvs, $_) } 
+keys %SQL;
[download]

Brain stuck in push() mode, I think :-)