When you are using native queries you should ensure that the query is optimized. First check that the required jars are referenced.
For native queries you need to add these jars: db4o-X.XX-nqopt-javax.jar, db4o-X.XX-instrumentation-javax.jar, bloat-1.0.jar. See "Dependency Overview"
Native queries try to translate the original query to a SODA query. If this optimization fails the query runs an order of magnitude slower, because it cannot use indexes and instantiates all objects.
For the native queries see: See "Native Query Optimization"
The optimizer only can optimize simple access patterns. When you call a complex method within a query the optimization almost certainly fails and the query runs slowly. For example when you call your equals method on your objects. Only calling the equals method of built in types will be recognized by the optimizer. However the optimizer almost certainly cannot find out what your equals method does.
Also take a look at this overview to see which kind of queries run fast and which ones slowly See "Native Queries Performance Characteristics".
Ensure that fields which you are using in queries are indexed. Without an index db4o has to scan through all objects in order to find the right object.
Note also that currently you cannot index arrays and collections. That means that queries which do checks on array or collection members will be slow.
Also db4o currently cannot use the index for advanced operations on strings, like end-with, contains or start-with comparisons.
Take a look at this overview to see which kind of queries run fast and which ones slowly. See "SODA Performance Characteristics"