The problem isn't unique to the BBB/Debian, I've found quite a few
other people with similar issues where parts of apt take a very long
time.
The time taken seems to relate to how many hits there are in the
search! If you search for something that doesn't exist it takes (on
my BBB) about 30 seconds:-
chris@beaglebone$ time apt search xyzabc
Sorting... Done
Full Text Search... Done
real 0m27.532s
user 0m26.315s
sys 0m1.035s
Searching for something that has three hits takes longer:-
chris@beaglebone$ time apt search xvile
Sorting... Done
Full Text Search... Done
vile-common/stable,now 9.8t-1 all [installed,automatic]
VI Like Emacs - support files for vile/xvile
vile-filters/stable,now 9.8t-1 armhf [installed]
VI Like Emacs - highlighting filters for vile/xvile
xvile/stable 9.8t-1 armhf
VI Like Emacs - vi work-alike (X11)
real 1m2.063s
user 0m59.874s
sys 0m1.862s
Searching for just 'vile' produces quite a lot of hits because there's quite a few packages
with the word 'privilege' in them, so it takes around four minutes.
A workaround is to use 'apt-cache search' instead:-
chris@beaglebone$ time apt-cache search vile
bubblewrap - setuid wrapper for unprivileged chroot and namespace manipulation
calife - Provides super user privileges to specific users
chiark-really - really - a tool for gaining privilege (simple, realistic sudo)
cups-pk-helper - PolicyKit helper to configure cups with fine-grained privileges
fakeroot - tool for simulating superuser privileges
libfakeroot - tool for simulating superuser privileges - shared libraries
gssproxy - Privilege separation daemon for GSSAPI
libkf5su5 - Integration with su for elevated privileges.
lacme - ACME client written with process isolation and minimal privileges in mind
libprivileges-drop-perl - module to make it simple to drop all privileges
libutempter-dev - privileged helper for utmp/wtmp updates (development)
libutempter0 - privileged helper for utmp/wtmp updates (runtime)
policykit-1 - framework for managing administrative policies and privileges
privbind - Allow unprivileged apps to bind to a privileged port
libpseudo - advanced tool for simulating superuser privileges
pseudo - advanced tool for simulating superuser privileges
python-oslo.privsep - OpenStack library for privilege separation - Python 2.7
python-oslo.privsep-doc - OpenStack library for privilege separation - doc
python3-oslo.privsep - OpenStack library for privilege separation - Python 3.x
slirp4netns - User-mode networking for unprivileged network namespaces
sudo - Provide limited super user privileges to specific users
sudo-ldap - Provide limited super user privileges to specific users
vile - VI Like Emacs - vi work-alike
vile-common - VI Like Emacs - support files for vile/xvile
vile-filters - VI Like Emacs - highlighting filters for vile/xvile
xvile - VI Like Emacs - vi work-alike (X11)
weborf - Fast and small webserver meant to be run without root privileges
libyubikey-udev - udev rules for unprivileged access to YubiKeys
zulupolkit - handler the polkit privileges
real 0m21.826s
user 0m20.697s
sys 0m0.944s
chris@beaglebone$
That's not affected by the number of hits:-
chris@beaglebone$ time apt-cache search xvile
vile-common - VI Like Emacs - support files for vile/xvile
vile-filters - VI Like Emacs - highlighting filters for vile/xvile
xvile - VI Like Emacs - vi work-alike (X11)
real 0m21.663s
user 0m20.614s
sys 0m0.924s