Magento 2 – How to Generate a Random String

I recently implemented something very similar and will share the relevant code below. But first some comments about performance, since that was the question:

General thoughts on performance for your requirements:

• "they shouldn't be in cart" means, you have only limited means to cache the upsell block. I strongly recommend to do it anyway, but set cache key and cache lifetime only if the cart is empty.
• Don't ORDER BY RAND() because it results in a resource intensive temp table copy. It has to load all results into a temporary table, assign a random number to each row and then sort without any index. Instead we retrieve all candidate ids (this is faster and the amount of data is managable even for large catalogs), pick some randomly and retrieve these rows directly. You can read about it in detail in my blog: http://www.schmengler-se.de/en/2015/09/show-random-products-in-magento-you-are-doing-it-wrong/

Specific performance problems with your solution

• Don't use addAttributeToSelect('*') with EAV collections, only select what you need
• Not entirely sure, but I doubt that new Zend_Db_Expr('FIELD(category_id, ' . implode(',', $_cat_order).')')) can efficiently use the MySQL indexes

Complete Solution

This is an observer for the catalog_product_upsell event. It uses the product collection provided by the product's category because I didn't need to fall back to the parent, but I'm sure you can adjust it.

use Mage_Catalog_Model_Product as Product;
use Mage_Catalog_Model_Product_Link as RelatedProduct;
use Mage_Catalog_Model_Resource_Product_Link_Product_Collection as RelatedProductCollection;

class IntegerNet_AutoUpsell_Model_Observer
{
    /**
     * @see event catalog_product_upsell
     * @param Varien_Event_Observer $observer
     * @throws Mage_Core_Exception
     */
    public function fillUpsellCollection(Varien_Event_Observer $observer)
    {
        $collection = $observer->getCollection();
        if ($collection instanceof RelatedProductCollection
            && $collection->getLinkModel()->getLinkTypeId() === RelatedProduct::LINK_TYPE_UPSELL
            && $collection->count() < $observer->getLimit('upsell')
        ) {
            $this->addItemsFromCategory($collection, $observer->getLimit('upsell') - $collection->count(), $observer->getProduct());
        }
    }
    protected function addItemsFromCategory(RelatedProductCollection $collection, $numberOfItems, Product $product)
    {
        /** @var Mage_Catalog_Model_Resource_Product_Collection $productsToAdd */
        $productsToAdd = $this->_getProductCategory($product)->getProductCollection();
        $productsToAdd
            ->addStoreFilter()
            ->addIdFilter(array_merge([$product->getId()], $collection->getAllIds()), true)
            ->setVisibility(Mage::getSingleton('catalog/product_visibility')->getVisibleInCatalogIds());

        $candidateIds = $productsToAdd->getAllIds();
        $choosenIds = [];
        $maxKey = count($candidateIds)-1;
        while (count($choosenIds) < $numberOfItems)) {
            $randomKey = mt_rand(0, $maxKey);
            $choosenIds[$randomKey] = $candidateIds[$randomKey];
        }    
        $productsToAdd
            ->addIdFilter($choosenIds)
            ->addMinimalPrice()
            ->addFinalPrice()
            ->addTaxPercents()
            ->addAttributeToSelect(Mage::getSingleton('catalog/config')->getProductAttributes())
            ->addUrlRewrite();
        foreach ($productsToAdd as $product) {
            $collection->addItem($product);
        }
    }

    /**
     * @param Mage_Catalog_Model_Product $product
     * @return Mage_Catalog_Model_Category
     */
    protected function _getProductCategory(Product $product)
    {
        $category = $product->getCategoryCollection()
            ->setPageSize(1)
            ->getFirstItem();
        return $category;
    }
}

Some parts that I'd like to highlight:

->addIdFilter(array_merge($product->getId(), $collection->getAllIds()), true)

This excludes the product itself and the products that are already manually defined as upsell products (I leave them and only fill the blanks with random products)

->addMinimalPrice()
->addFinalPrice()
->addTaxPercents()
->addAttributeToSelect(Mage::getSingleton('catalog/config')->getProductAttributes())
->addUrlRewrite();

This prepares the product collection to load the necessary data to display prices, the product link and any attributes configured as "used in product listing", but not more.