Firstly, I concur with ++zentara's recommendation to use Tk::Entry's -validate option set to 'key'.

In addition, I also suggest the following:

• Cache your search results so that you only need to query the database once per unique search query.
• Add a progress bar, or similar graphical feedback, to advise the user that something is happening.
• Look at your database and see if there's anything you can do to speed up the queries.

The following code implements all of that (except, of course, the database point). I've simply dummied up some data to simulate whatever's on your database; as well as a two second delay for new searches.

When you run this, you can just type, for instance, 'qwerty' in the "Search" field: see how each (i.e. 'q', 'qw', ..., 'qwerty') is queried in turn and the progress bar runs separately for each. You can then hit "Backspace" several times and see the results (i.e. for 'qwert', 'qwer', ..., 'q') appear immediately because they're cached.

#!/usr/bin/env perl

use strict;
use warnings;
use constant {
    DB_DELAY => 2000,
    RESULTS_SEPARATOR => '=' x 40 . "\n",
};

use Tk;
use Tk::ProgressBar;

{
    my $mw = MainWindow::->new();
    sub _mw () { $mw }

    my ($progress_bar, $progress, $results);
    sub _progress_bar () { \$progress_bar }
    sub _progress () { \$progress }
    sub _results () { \$results }
}

{
    my $search_F = _mw->Frame->pack;
    $search_F->Label(
        -text => 'Search:',
    )->pack(-side => 'left');
    $search_F->Entry(
        -validate => 'key',
        -validatecommand => \&run_query,
    )->pack(-side => 'left');
    $search_F->Label(
        -text => 'Progress:',
    )->pack(-side => 'left');
    ${+_progress} = 0;
    ${+_progress_bar} = $search_F->ProgressBar(
        -variable => _progress,
        -from => 0,
        -to => 100,
        -blocks => 10,
        -gap => 0,
        -colors => [ 0 => '#99ccff' ],
        -width => 20,
        -length => 200,
    )->pack(-side => 'left');
    $search_F->Button(
        -text => 'Exit',
        -command => sub { exit },
    )->pack(-side => 'left');

    my $results_F = _mw->Frame->pack;
    ${+_results} = $results_F->Scrolled('Text',
        -scrollbars => 'osoe',
    )->pack;
}

MainLoop;

sub run_query {
    my ($query) = @_;

    if (length $query) {
        ${+_results}->insert(end => "Query: $query\n");
        ${+_results}->insert(end => "Results:\n");

        for (@{get_results($query)}) {
            ${+_results}->insert(end => "$_\n");
        }

        ${+_results}->insert(end => RESULTS_SEPARATOR);
        ${+_results}->yviewMoveto(1);
    }

    return 1;
}

{
    my @data; INIT { @data = qw{q qwe qwerty a asd asdfgh} }
    my %cache;

    sub get_results {
        my ($query) = @_;

        unless (exists $cache{$query}) {
            $cache{$query} = [ grep /\Q$query/, @data ];

            my $step = int 0.5 + DB_DELAY / 10;

            for (my $i = 0; $i <= DB_DELAY; $i += $step) {
                _mw->after($step);
                ${+_progress} = $i / DB_DELAY * 100;
                ${+_progress_bar}->idletasks;
            }

            ${+_progress} = 0;
        }

        return $cache{$query};
    }
}
[download]

You may have also noticed a complete absence of any global variables. These often become a source of all sorts of issues, particularly with Tk applications of any substance, and especially when callbacks are involved. Aim to avoid them wherever possible: which is pretty much everywhere.