I've been dealing with this problem for a while now, and after seeing this thread, I decided to dive in a little deeper.
With LZ4-compressed lists, running an apt search on my Rock64 currently takes at least 20 minutes. As other users have reported, it appears to be bottlenecked by CPU, and is not saturating the storage I/O. Needless to say, this is not a usable speed.
Based on what I've found, I believe with substantial confidence that there is no performance problem with LZ4. This should not be too much of a surprise, because speed, especially decompression speed, is LZ4's primary objective; it is in fact considerably faster than LZO in that regard, which means that it's dramatically faster than DEFLATE (gzip). I cannot imagine any conceivable case where switching from LZ4 to DEFLATE would result in decompression performance improvements, and indeed it does not seem to do so here.
In any case, you can trivially see this for yourself by using the command-line lz4 utility to decompress one of the compressed list files in /var/lib/apt/lists. On my Rock64, decompressing the largest of these (/var/lib/apt/lists/apt.armbian.com_dists_buster_main_binary-arm64_Packages.lz4, which weighs about 1.8 MB) takes around a tenth of a second. For some perspective, my test run of an apt search took just over 2700 seconds, so if it did spend all or most of this time doing LZ4 decompression, then it could easly have decompressed every list in the directory over a thousand times each. I am not an expert on the intricacies of file compressors, but I find it to be highly unlikely that LZ4 is responsible for the slowness we're seeing here.
I had a look at the strace output for the search operation. I'm new to reading straces, but I think I can confirm what a previous poster said, which is that it's accessing the same files over and over again with small reads, often many times in the same place. It is unclear to me what function this serves, but this appears to be what takes up the majority of the runtime. If you would like to see for yourself, I've made the full strace output available at https://fluora.net/strace_apt-search_armbian.7z. Be warned that it's around 260 megabytes when uncompressed, but since it's extremely repetitive, it compresses efficiently, and the 7z archive is only about 96 kB. In addition, you may compare this to the strace of a sane apt-search operation that I took on an x86 laptop running Debian Bullseye with gzip-compressed package lists, available at https://fluora.net/strace_apt-search_debian86.txt (116 kB, not compressed). This isn't much more than a guess, but I wonder if apt is decompressing the entire list with each one of these repeated read operations - this would explain not only the slowness, but also why switching to uncompressed lists seems to help (since it allows the storage cache to render the repeated accesses cheap).
From what I've found here, I strongly suspect that something is wrong with the version of apt distributed by Armbian. I don't know enough about the code to know where to start looking, but this is the point where I would hope that someone familiar with Armbian's modifications to apt could help out.