>>Now, I have got some code working.
     >Do tell, do tell! You first...

;-). Actually, I solved my own problem. So, here I present my code. The last if (scalar(@arr) > $num); line solves my speed problem greatly. The speed is down from 20 wallclock seconds to 4 wallclock seconds when none of the date parts are provided. I still present the code here for monks to tell me better ways to do the same.

my $num  = 5;

sub get_latest {
  my ($year, $mon, $day) = @_;
  my @arr;
  
  if ($year && $mon && $day) {
    my $h = $d_dbd->{$year}->{$mon}->{$day};
    @arr = keys(%$h);
  }
  elsif ($year && $mon) {
    my $h = $d_dbd->{$year}->{$mon};
    for (sort {$a <=> $b} (values %$h)) {
      push(@arr, keys(%$_));
      last if (scalar(@arr) > $num);
    }
  }
  elsif ($year) {
    my $h = $d_dbd->{$year};
    for my $m (sort {$a <=> $b} (values %$h)) {
      for (sort {$a <=> $b} (values %$m)) {
        push(@arr, keys(%$_));
        last if (scalar(@arr) > $num);
      }
    }
  }
  else {
    for my $y (keys %$d_dbd) {
      my $h = $d_dbd->{$y};
      for my $m (sort {$a <=> $b} (values %$h)) {
        for (sort {$a <=> $b} (values %$m)) {
          push(@arr, keys(%$_));
          last if (scalar(@arr) > $num);
        }
      }
    }
  }

  return extract(\@arr);
}

sub extract {
  my ($arr) = @_;
  
  my @p;
  my @arr = @$arr;
  
  if (scalar(@arr) > $num) {
    for (1..$num) {
      my $rand = int(rand(scalar(@arr)));
      push(@p, splice(@arr, $rand, 1));
    }
  }
  else {
    @p = @arr;
  }
  return \@p;
}
[download]

sub get_latest {
  my ($year, $mon, $day, $num) = @_;
  my @arr;
  
  if ($year && $mon && $day) {
    my $h = $d_dbd->{$year}->{$mon}->{$day};
    @arr = keys(%$h);
  }
  elsif ($year && $mon) {
    my $h = $d_dbd->{$year}->{$mon};
    FOO: for my $day (sort {$b <=> $a} (keys %$h)) {
      my $h = $d_dbd->{$year}->{$mon}->{$day};
      push(@arr, keys(%$h));
      last FOO if (scalar(@arr) > $num);
    }
  }
  elsif ($year) {
    my $h = $d_dbd->{$year};
    FOO: for my $mon (sort {$b <=> $a} (keys %$h)) {
      my $h = $d_dbd->{$year}->{$mon};
      for my $day (sort {$b <=> $a} (keys %$h)) {
        my $h = $d_dbd->{$year}->{$mon}->{$day};
        push(@arr, keys(%$h));
        last FOO if (scalar(@arr) > $num);
      }
    }
  }
  else {
    FOO: for my $year (sort {$b <=> $a} (keys %$d_dbd)) {
      my $h = $d_dbd->{$year};
      for my $mon (sort {$b <=> $a} (keys %$h)) {
        my $h = $d_dbd->{$year}->{$mon};
        for my $day (sort {$b <=> $a} (keys %$h)) {
          my $h = $d_dbd->{$year}->{$mon}->{$day};
          push(@arr, keys(%$h));
          last FOO if (scalar(@arr) > $num);
        }
      }
    }
  }

  return extract(\@arr, $num);
}
[download]

I get the error

Exiting subroutine via last at script.pl line 57.
Label not found for "last FOO" at script.pl line 57.
[download]

What gives?