Why do these queries deadlock and how to work this around in MariaDB?

Question

The following 2 queries enounter DB deadlock in my program:

DELETE FROM proxies
WHERE NOT EXISTS (
  SELECT 1 FROM proxy_xref_proxy_list AS pxpl
  WHERE pxpl.ProxyID=proxies.ID
    AND (pxpl.DeactivationTS IS NULL OR pxpl.DeactivationTS >= (NOW() - INTERVAL 24 HOUR))
  ORDER BY pxpl.ProxyListID
  LIMIT 1
)
ORDER BY proxies.ID

INSERT IGNORE INTO proxy_xref_proxy_list (ProxyID, ProxyListID)
(SELECT ID, 13 FROM proxies
JOIN new_proxies ON proxies.Url=new_proxies.Url
ORDER BY proxies.ID)
ON DUPLICATE KEY UPDATE DeactivationTS=NULL

However, they are both ordered by proxies.ID. Why do they deadlock and how to solve this?

Tables:

CREATE TABLE `proxies` (
    `ID` BIGINT(20) NOT NULL AUTO_INCREMENT,
    `Url` VARCHAR(767) NOT NULL DEFAULT '' COLLATE 'utf8mb4_unicode_ci',
    `Schema` TINYTEXT NULL DEFAULT NULL COLLATE 'utf8mb4_unicode_ci',
    `Host` TINYTEXT NULL DEFAULT NULL COLLATE 'utf8mb4_unicode_ci',
    `Port` TINYTEXT NULL DEFAULT NULL COLLATE 'utf8mb4_unicode_ci',
    `SuccessCount` BIGINT(20) UNSIGNED NOT NULL DEFAULT '0',
    `UnknownCount` BIGINT(20) UNSIGNED NOT NULL DEFAULT '0',
    `FailureCount` BIGINT(20) UNSIGNED NOT NULL DEFAULT '0',
    PRIMARY KEY (`ID`) USING BTREE,
    UNIQUE INDEX `UrlUnique` (`Url`) USING BTREE
)
COLLATE='utf8mb4_unicode_ci'
ENGINE=InnoDB
;

CREATE TABLE `proxy_xref_proxy_list` (
    `ProxyID` BIGINT(20) NOT NULL,
    `ProxyListID` BIGINT(20) NOT NULL,
    `DeactivationTS` DATETIME NULL DEFAULT NULL,
    PRIMARY KEY (`ProxyID`, `ProxyListID`) USING BTREE,
    UNIQUE INDEX `DisactivationTS_ProxyID_ProxyListID` (`DeactivationTS`, `ProxyID`, `ProxyListID`) USING BTREE,
    INDEX `ProxyXRefProxyList_ProxyListID_FK2` (`ProxyListID`, `DeactivationTS`) USING BTREE,
    CONSTRAINT `ProxyXRefProxyList_ProxyID_FK1` FOREIGN KEY (`ProxyID`) REFERENCES `mydb`.`proxies` (`ID`) ON UPDATE CASCADE ON DELETE CASCADE,
    CONSTRAINT `ProxyXRefProxyList_ProxyListID_FK2` FOREIGN KEY (`ProxyListID`) REFERENCES `mydb`.`proxy_lists` (`ID`) ON UPDATE CASCADE ON DELETE CASCADE
)
COLLATE='utf8mb4_unicode_ci'
ENGINE=InnoDB
;

CREATE TEMPORARY TABLE `new_proxies` (
    `Url` VARCHAR(767) NOT NULL DEFAULT '' COLLATE 'utf8mb4_unicode_ci',
    `Schema` TINYTEXT NULL DEFAULT NULL COLLATE 'utf8mb4_unicode_ci',
    `Host` TINYTEXT NULL DEFAULT NULL COLLATE 'utf8mb4_unicode_ci',
    `Port` TINYTEXT NULL DEFAULT NULL COLLATE 'utf8mb4_unicode_ci',
    UNIQUE INDEX `UrlUnique` (`Url`) USING BTREE
)
COLLATE='utf8mb4_unicode_ci'
ENGINE=InnoDB
;

Table proxy_lists referenced by the foreign key is linked to proxies via a many-to-many relation.

UPDATE1: Upon the request of @Rick James, here is a query that selects the proxy IDs that need deletion:

SELECT p.ID FROM proxies AS p
LEFT JOIN proxy_xref_proxy_list AS pxpl
  ON p.ID=pxpl.ProxyID
    AND (pxpl.DeactivationTS IS NULL OR pxpl.DeactivationTS >= (NOW() - INTERVAL 24 HOUR))
WHERE pxpl.ProxyID IS NULL

Answer 1

OR is terrible on performance, and probably equally bad on transaction locks.

pxpl.DeactivationTS IS NULL OR pxpl.DeactivationTS >= ...

Instead of depending on NULL in that, consider storing a date in the future. That way this would suffice:

pxpl.DeactivationTS >= ...

EXISTS -- Since EXISTS stops at the first occurrence, LIMIT 1 is redundant. Similarly, the inner ORDER BY seems fishy.

TINYTEXT -- This datatype has some minor disadvantages compared to VARCHAR(255) Better yet, is to use VARCHAR with a realistic limit.

If those don't help enough, please provide a SELECT (possibly with a LEFT JOIN) that would list the rows that should be deleted. With that, we might be able to devise a variation on the DELETE that will be more deadlock-proof.

If that, too, fails, then simply plan on handling deadlocks: Detect them, then replay the transaction containing the DELETE.

This might be a better DELETE:

DELETE proxies FROM proxies
    LEFT JOIN proxy_xref_proxy_list AS pxpl
      ON proxies.ID = proxy_xref_proxy_list.ProxyID
    AND (proxy_xref_proxy_list.DeactivationTS IS NULL
      OR proxy_xref_proxy_list.DeactivationTS >= (NOW() - INTERVAL 24 HOUR))
   WHERE proxy_xref_proxy_list.ProxyID IS NULL